第一部分 数据结构（75分）
一、单项选择题(每题2分，共20分)
1. 含有m个结点的二叉树链式存储结构中空指针的个数为 ( )。
A．2m B．m-1 C．m+1 D．m
2. 下列排序算法中元素的移动次数和关键字的初始排列次序无关的是（ ）。
A. 快速排序 B. 插入排序 C. 选择排序 D. 希尔排序
3. 一个栈的进栈序列是a b c d e，则栈的输出序列不可能的是（ ）。
A．a b c d e B．e d c b a C．d e c b a D．d c e a b
4. 需要的辅助空间最多的排序算法为（ ）。
A. 归并排序 B. 快速排序
C. 基数排序 D. 堆排序
5. 哈希表的平均查找长度说法错误的是 ( )。
A. 与处理冲突方法有关而与表的长度无关
B. 与选用的哈希函数有关
C. 与哈希表的饱和程度有关
D. 与表中填入的记录数有关
6. 有n个顶点 、e条边且使用了邻接表存储的有向图进行深度优先遍历，其算法的时间复杂度是（ ）。
A. O（n+e） B. O（n2） C. O（n+2e） D. O（n*e）
7. 已知一个长度为11的顺序表，其元素按关键字有序排列，若采用折半查找查找一个其中不存存在的元素，则关键字的比较次数最多是（ ）。
A．3 B．4 C．5 D．6
8. 一棵完全二叉树上有3001个结点，其中叶子结点的个数是（ ）。
A. 1500 B.1501 C. 1000 D.1001
9. 若一棵二叉树度为2的结点有18个，度为1的结点有10个，则度为0的结点个数是（ ）。
A. 46 B. 28 C. 19 D. 17
10. m阶B-树是一棵（ ）。
A .m叉排序树 B. m-1叉平衡排序树 C. m叉平衡排序树 D. m+1叉平衡排序树
二、填空题(每空2分，共14分)
1. 已知一棵二叉树的中序遍历序列为GDHBAECIF，后序遍历序列为GHDBEIFCA，那么先序遍历序序列为 。
2. 若某记录的关键字序列是（491，77，572，16，996，101，863，258，689，325），以第一个关键字为枢轴，写出采用快速排序算法第一趟排序的结果
。
3. 将对称矩阵A[8][8]的下三角部分逐行存储到起始地址为2000的内存单元中，已知每个元素占4个单元，假设第一个元素是A[0][0]，则A[4][6]的地址是
。
4. 在顺序表中插入一个元素，需要平均移动表中一半元素，具体移动元素的个数与
有关。
5.在哈希查找方法中，要解决两方面的问题，它们是
和
。
6. 循环队列中，Q.rear == Q.front表示循环队列空，表示循环队列满的条件是
。
三、简答题（共3小题，每题7分，共21分）
1. 将下面的森林转换为二叉树（3分），并给出该二叉树的中序线索链表（4分）。
2. 设Huffman编码的长度不超过4，若已对两个字符编码为01和11，则最多还可以对多少个字符编码，为什么？(7分）
3. 假设图的顶点是A、B、C、D、E，请根据下面的邻接矩阵画出相应的有向图（3分），然后画出图的邻接表和逆邻接表（4分）。
四、编写算法（共2小题，每题10分，共20分）
1. 试编写一个算法完成下面的功能：对于输入的任意一个非负十进制整数，输出与其等值的八进制数。（10分）
2. 试编写一个算法，在有向图G中，判定从顶点Vi到顶点Vj是否有通路。（10分）
第二部分 操作系统（75分）
五、判断题(每小题1分，共10分，正确的打√，错误的打×)
1. 系统调用中的被调用程序运行在系统态。
2. 银行家算法采用了死锁预防的方法。
3. 文件系统采用树形目录结构可以节省内存空间。
4. 虚存管理允许用户程序大于主存容量，而且还可以提高系统的吞吐量。
5. SPOOLing系统实现了设备的独立性。
6. 分时系统的时间片越小，用户的满意度就越高。
7. 管程每次只允许一个进程进入。
8. 操作系统既可看作虚拟机，也可看作资源管理器。
9. 在作业调度时，采用最高响应比优先的作业调度算法可以得到最短的作业平均周转时间。
10. 并行程序设计中，使用信号量比使用管程更能保证程序的正确性。
六、填空题 (每小题1分，共10分)
1. 对于速率为9.6KB/s的数据通信而言，如果设置一个具有8位的缓冲寄存器，则CPU中断时间和响应时间分别大约为
（1） 、 （2） 。
2. 如果计算机连接了三个同类型的激光打印机及五个同类型的喷墨打印机，需要安装的驱动程序数目是
（3） 。
3. 在具有n个进程的系统中，允许m个进程(n≥m≥1)同时进入它们的临界区，其信号量S的值的变化范围是
（4） ，处于等待状态的进程数最多有
（5） 个。
4. 动态分区的
（6） 算法可以使内存中的空闲分区分布得更均匀。
5. UNIX的目录项由文件名和
（7） 构成。
6. 若干事件在同一时间间隔内发生称为
（8） 。
7. 虚拟存储器具有
（9） 、
（10） 和虚拟性三大特征。
七、单选题(每小题1分，共10分)
1. 请求调页系统中，如下算法中，( ) 淘汰自上次访问以来经历时间最长的页面。
A. FIFO B. OPT C. NRU D. LRU
2. 下列进程调度算法中，( ) 可能会出现进程长期得不到调度的情况。
A. 静态优先权法 B. 抢占式调度中采用动态优先权法
C. 分时处理中的时间片轮转调度算法 D. 非抢占式调度中采用FIFO算法
3. 分时系统中，CPU进程切换需要3ms，为使得100个用户均能在1秒内得到响应，可以选择的时间片是（ ）。
A. 2ms B. 50 ms C. 10ms D. 7 ms
4. 磁盘的I/O控制主要采取( ) 方式。
A. 程序I/O B. 中断 C. DMA D. SPOOLing
5. 系统产生死锁是指( ) 。
A. 系统发生重大故障
B. 若干进程同时处于阻塞状态
C. 请求的资源数大于系统提供的资源数
D. 若干进程等待被其他进程所占用而又不可能被释放的资源
6. 通道又称I/O处理机，它用于实现( ) 之间的信息传输。
A. CPU与外存 B. CPU与外设 C. 内存与外存 D. 内存与外设
7. 下面叙述正确的是( ) 。
A. 程序段是进程存在的唯一标志
B. 系统通过PCB来控制和管理进程，用户可以从PCB中读出与本身运行状态相关的信息
C. 当进程有执行状态变为就绪状态时，CPU现场信息必须被保存在PCB中
D. 当进程申请CPU得不到满足时，它将处于阻塞状态
8. 在没有快表的情况下，分页系统要访问( )次内存。
A. 1 B. 2 C .3 D. 4
9. 计算机操作系统中，若WAIT、SIGNAL操作的信号量S初值为3，当前值为-4，则表示当前有( ) 个等待信号量S的进程。
A. 1 B. 2 C. 3 D. 4
10. 有10个进程共享5个打印机，若信号量S的当前值是-2，则当前有( )个进程提出了打印请求？
A. 10 B. 7 C. 5 D. 2
八、简答题(每小题5分，共25分)
1. 什么是文件目录、目录文件，各起什么作用？
2. 多级树形目录的文件系统，怎样才能提高查找文件的速度?
3. 多线程系统与传统多进程系统相比有哪些优点？
4. 分页存储管理和分段存储管理的主要区别有哪些？
5. 用伪代码或文字描述fork()系统调用是如何创建进程的。
九、应用题(每小题10分，共20分)
1. 某类Unix系统采用成组链接法来管理磁盘的空闲空间，目前磁盘的状态图如下（10分）：
（1）该磁盘中目前还有多少个空闲盘块？(4分)
（2）给出该系统的磁盘块分配及回收算法（流程图或描述）。（6分）
2. 分析下面给出的表达式的并行性，并用信号量机制实现该表达式的并行计算。（10分）
（3 * a * b + 4）/ ( c + d )( e – f )
