数据结构
一． 选选择题（每题只有一个答案正确，每题2分，共26分）
1. 以下图的叙述中，正确的是_______。
A．图与树的区别在于图的边数大于或等于顶点数
B．假设有图G=(V, {E}), 顶点集V’íV，E’ íE，则V’和{E’}构成G的子图
C．无向图的连通分量指无向图中的极大连通子图
D. 图的遍历就是从图中某一顶点出发访遍图中其余顶点
2. 下列判断中，______是正确的。
A. 深度为k的二叉树最多有2k-1个结点(k≥1)，最少有k个结点
B. 二叉树中不存在度大于2的结点
C. 对二叉树遍历是指先序、中序或后序遍历中的一种
D. 构造线索二叉树是为能方便找到每个结点的双亲
3. 对各种内部排序方法来说，__________。
A. 快速排序时间性能最佳 B. 基数排序和归并排序是稳定的排序方法
C. 快速排序是一种选择排序 D. 堆排序所用的辅助空间比较大
4. 稀疏矩阵的三元组存储方法_______。
A．实现转置运算很简单，只需将每个三元组中的行标和列标交换
B．是一种链式存储方法
C．矩阵的非零元个数和位置在操作过程中变化不大时较有效
D．比十字链表法更高效
5. 对于二叉排序树，下面的说法_______是正确的。
A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合
B．对二叉排序树进行层序遍历可得到有序序列
C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大
D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2
6. 在构造哈希表方面，下面的说法_________是正确的。
A．再哈希法在处理冲突时不会产生聚集
B．哈希表的装填因子越大说明空间利用率越好，因此应使装填因子尽量大
C．哈希函数选的好可减少冲突现象
D．对任何具体关键字集都不可能找到不产生冲突的哈希函数
7. 已知广义表(( ),(a), (b, c, (d), ((d, f))))，则以下说法正确的是__________。
A．表长为3，表头为空表，表尾为((a), (b, c, (d), ((d, f))))
B．表长为3，表头为空表，表尾为(b, c, (d), ((d, f)))
C．表长为4，表头为空表，表尾为((d, f))
D．表长为3，表头为(())，表尾为((a), (b, c, (d), ((d, f))))
8. 已知一棵5阶B树有53个关键字，并且每个结点的关键字都达到最少状态，则它的深度是________。
A. 3 B. 4 C. 5 D. 6
9. 一个有向图，共有n条弧，则所有顶点的度的总和为_______。
A．2n B. n C. n-1 D. n/2
10. 对邻接表的叙述中，_____是正确的。
A．无向图的邻接表中，第i个顶点的度为第i个链表中结点数的二倍
B．邻接表比邻接矩阵的操作更简便
C．邻接矩阵比邻接表的操作更简便
D．求有向图结点的度，必须遍历整个邻接表
11. 一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为_____。
A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB
12. 以下说法中，________是正确的。
A. 完全二叉树中，叶结点的双亲的左兄弟（如果存在）一定不是叶结点
B. 任何一棵二叉树，终端结点数为度为2的结点数减1
C. 二叉树不适合用顺序结构存储
D. 结点按层序编号的二叉树，第i个结点的左孩子（如果存在）的编号为2i
13. 给定一组关键字{4，26，46，12，9，33}，哈希函数为H(key)=key MOD 6，则用线性探测再散列方法来处理冲突，则构造此哈希表共需要比较关键字____次。
A. 4 B. 5 C. 6 D. 7
二． 解答题（每题4分，共36分）
1. 线性表的双向链表的存储结构为：
typedef struct DNode {
TElem info;
struct DNode *left;
struct DNode *right;
};
并假设已建立头指针为head的双向链表，p指向其中某个结点，写一个程序段，从该循环链表中删除p所指向结点的前一个结点(假设该结点存在)。
2. 简述在AOV网中求拓扑排序的过程，
- 并写出下面AOV网中的两个拓扑有序序列。
3. 给出下面有向图的邻接矩阵、邻接表及逆邻接表。
4. 假定字符集{a, b, c, d, e, f}中的字符在通信网络中出现的频率见下表，请设计赫夫曼编码。
|
字符 |
a |
b |
c |
d |
e |
f |
|
频率 |
0.10 |
0.23 |
0.36 |
0.11 |
0.15 |
0.05 |
5．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列问题；
(1)图中有多少条边？
(2)任意两个结点i和j是否有边相连？
(3)任意一个顶点的度是多少？
6．对下图所示的AOE网，回答：工程完成的最短时间是多少？写出关键路径（不需过程），是否有某些活动提高速度后能导致整个工程缩短工期？
7. 已知Q是一个非空队列
，S是一个空栈。仅用队列和栈的ADT函数，用C语言伪码编写一个算法，将队列Q中的所有元素逆置。
栈的ADT函数有：
makeEmpty(stack s); 置空栈
push(stack s，datatype value); 新元素value进栈
datatype pop(stack s) 出栈，返回栈顶值
boolean isEmpty(stack s) 判栈空否
队列的ADT函数有
enQueue(queue q, datatype value) 元素value进队
datatype deQueue(queue q) 出队列，返回队头值
boolean isEmpty(queue q) 判队列空否
8．你所知道的排序方法有几类？简述各类方法的原理。
9．在为一个实际应用设计数据结构时，主要应考虑哪些方面的内容？
三． 算法设计。做出简要分析并写函数。（共13分）
1. 以二叉链表作存储结构，试编写非递规的前序遍历算法。(5分)
2. 无向图用邻接表存储，写出邻接表定义，给出求图中顶点Vi到 Vj的最短路径的函数。（8分）
操作系统
一、名词解释：（18分）
1． 进程
2． Spooling技术
3． 系统调用
4． 死锁
5． 并发
6． 缺页中断
二、有3个并发进程R、M、P，它们共享同一个缓冲区，假定缓冲区只能存放一条记录。进程R负责从输入设备读信息，每读入一个记录后，就把它放进缓冲区；进程M在缓冲区中加工读入的记录；进程P把加工后的记录打印输出。读入的记录经加工输出后，缓冲区又可以存放下一个记录。试写出他们能够正确执行的并发程序。（10分）
三、在某页式管理系统中，假定主存为64K,分成16块，块号为0，1，2，…，15。设某进程有４页，其页号为0，1，2，3，被分别装入主存的第9、0、1、14块。试问：（10分）
１） 该进程的总长度是多大？
２） 写出该进程每一页在主存中的起始地址。
３）若给出逻辑地址［0，0］、［1，72］、［2，1023］、［3，99］，请计算出相应的内存地址。（方括号内的第一个数为页号，第二个数为页内地址，题目中的数字均为10进制）。
四、I/O控制可用哪几种方式，各有什么优缺点？（8分）
五、某软盘有40个磁道，磁头从一个磁道移到另一个磁道需要6ms。文件在磁盘上非连续存放，逻辑上相邻的数据块的平均距离为13个磁道，每块的旋转延迟时间及传输时间分别为100ms和25ms。问：（8分）
1） 读取一个100块的文件需要多少时间？
2） 如果对磁盘进行整理使得同一文件的磁盘块尽可能靠拢，从而使逻辑上相邻的数据块的平均距离降为2个磁道，这时读取100块的文件有需要多少时间？
六、两个进程A和B，每一个进程都需要读取数据库中的记录1、2、3假如这两个进程都以1、2、3的次序请求读取记录，系统将不会发生死锁。但如果A以3、2、1的次序读取记录，B以1、2、3的次序读取记录，则死锁可能会发生。试计算两个进程读取记录的次序如果不确定，那么系统保证不发生死锁的概率是多少？（6分）
七、为什么需要一个打开文件的系统调用？一般来讲打开文件的系统调用主要做了些什么？（7分）
八、试说明UNIX操作系统中文件系统的权限是如何控制的（8分）
