数据结构部分.pdf

数据结构部分
注意事项：
1、算法应说明基本思路，应对主要数据类型、变量给出说明，所写算法应结构清
晰、简明易懂，应加上必要的注释。
2、算法可用（类）PASCAL语言、（类）C语言等你所熟悉的高级语言编写，但要注明
语种。
一、填空题[每空2分，共20分。注：题目中预留填空位置大小与答案填写内容多少无关。
]：
1、数据逻辑结构主要包括①、②、③、④，四种结构，树形结构和
图形结构合称为⑤。
2、线性表与栈和队列的主要区别是?。
3、在单链表中设置头结点的作用是?。
4、从概念上讲，森林、树与二叉树是不同的数据结构，将森林与树转化为二叉树的基本
目的是?。
5、在各种查找方法中，平均查找长度与结点个数n无关的查找方法是?。
6、折半查找的存储结构仅限于?，且要求元素按其关键字有序。
二、综合应用题[每小题7分，共35分]：
1、采用子表分析法或表头表尾分析法画出广义表（（（（a）,b））,(((),d),(e,f)
))的存储结构图，并求它的深度及长度。
2、某二叉树的前序遍历结点访问顺序是abdgcefh，中序遍历的结点访问顺序是
dgbaechf。画出该二叉树，并将其后序线索化。
3、已知一个图的顶点集V为：V={1,2,3,4,5,6,7};共有10条边。该图用如下边集数组存
储：
起点1225522613终点6454767775权1122233457试用克鲁斯卡尔算法依次求出该图的最小生
成树中所得到的各条边及权值。
4、试证明当深度优先遍历算法应用于一个连通图时，所经历的边形成一棵树。
5、有n个不同的英文单词，它们的长度相等，均为m，若n>>50，m<5，试问采用什么排序
方法时间复杂度最佳？为什么？
三、[15分]选择适合的结构存储稀疏多项式，编写求其导函数的算法，要求利用原多项式
中的结点存放其导函数（多项式），同时释放所有无用（被删）结点。
四、[15分]对给定关键字的序号j（0≤j<n）,要求在无序记录A[0...n-1]中找按关键字从
小到大排在第j位上的记录，利用快速排序的划分思想设计上述算法。
五、[15分]试编写一个算法，判断给定的二叉树是否二叉排序树。

操作系统部分
一、名词解释（每题4分，总计12分）
1、目录
2、线程
3、操作系统
二、简单题（每题5分，总计20分）
1、死锁的四个必要条件是什么？如果四个条件全部具备，是否一定发生死锁？
2、请描述虚拟内存管理技术中缺页（PageFault）的处理流程。
3、请问，在I/O控制中为什么引入DMA控制方式？并请简要描述DMA控制方式的工作流程。
4、请问进程和程序有何差异？
三、综合题（总计18分）
1、(本题7分)请用信号量机制（wait、signal）解决下述的进程间同步问题:

同步要求：先关门，后开车；先停车，后开门
2、（本题总计6分）当在一个采用页式虚拟存储管理的系统中，有一用户进程，它依次
要访问的字地址序列是：115，228，120，88，446，102，321，432，260，167，现分配
给该作业的主存共300字，页的大小为100字，请解答下列问题、
（1）给出该进程的页访问串（referencestring）（即其访问的页号序列）；
（2）如果按FIFO替换算法，缺页率是多少？依次淘汰的页的页号是哪些？
（3）如果按LRU替换算法，缺页率是多少？依次淘汰的页的页号是哪些？
3、（本题总计5分）提高IO性能是操作系统的重要目标之一。请列举操作系统中至少三种
提高IO性能的措施（或方法）？