当前位置：问答库＞考研试题

一、填空题

1． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。

【答案】f ﹣＞next ＝p ﹣＞next ；f ﹣＞prior ＝p ；p ﹣＞next ﹣＞prior ＝f ；p ﹣＞next ＝f ；

2． 求图的最小生成树有两种算法，_____算法适合于求稀疏图的最小生成树e

【答案】克鲁斯卡尔

【解析】克鲁斯卡尔算法是一种按权值的递增次序选择合适的边来构造最小生成树的方法，这种算法中，采用堆来存放边的集合，适合于边稀疏而顶点较多的图。

3． 建立索引文件的目的是_____。

【答案】提高查找速度

4． 二叉树的前序序列和中序序列相同的条件是_____。

【答案】空树或任何结点至多只有右子树的二叉树

【解析】前序遍历的顺序为根左右，中序遍历的顺序为左根右，因此若中序遍历和前序遍历序列相同，则任何结点都没有左子树。

5． 在基于关键字比较且时间为

【答案】归并；堆

6． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关，即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。

【答案】逻辑特性；在计算机内部如何表示和实现；数学特性

_ 的排序中，若要求排序是稳定的，则可选用_____排序；若要求就地排序(及辅助空间为O(1))，则可选用_____排序。

二、单项选择题

7．

参考模型的网络层提供的是（ ）。

A. 无连接不可靠的数据报服务

B. 无连接可靠的数据报服务

C. 有连接不可靠的虚电路服务

D. 有连接可靠的虚电路服务

【答案】A

【解析】TCP/IP的网络层向上只提供简单灵活的、无链接的、尽最大努力交付的数据服务, 因此答案是A 。

8． 一棵二叉树高度为h ，所有结点的度或为0或为2，则这棵二叉树最少有（ ）个结点。

A.2h

B.2h ﹣1

C.2h ＋l

D.h ＋1

【答案】B

【解析】此树满足哈夫曼树，除根节点外每层有两个节点。

9． 最大容量为n 的循环队列，队尾指针是rear ，队头:front ，则队空的条件是（ ）。

A.(rear+1)MODn＝front

B.rear ＝front

C.rear+1＝front

D.(rear-1)MODn＝front

【答案】B

【解析】循环队列队空的条件是:rear ＝front 。循环队列队满的条件，

通常采用(rear+1)%MAXQSIZE＝front 来判定队满，其中MAXQSIZE 表示队列的长度。

10．某时刻进程的资源使用情况如下表所示

此时的安全序列是（ ）。

A.P1, P2, P3, P4

B.P1, P3, P2, P4

C.P1, P4, P3, P2

D. 不存在

【答案】D

【解析】典型的死锁避免算法, 银行家算法的应用。银行家算法是操作系统中的一个重点知识单元, 考生对此应该非常熟悉, 本题并无难点。分析一下下表, 可以看到, 经过P1, P4的运行以后, 可用资源是2, 2, 1, 而P2, P3所需资源分别是1, 3, 2和1, 3, 1。所以剩余资源已经不够P2或P3的

分配, 亦即找不到能够安全运行的序列, 因此此时是处于不安全状态, 所以不存在这样的安全序列。

11．操作系统的

A. 用户级

B. 用户级

C. 用户级

D. 用户级

【答案】A 。 子系统通常由四个层次组成, 每一层明确定义了与邻近层次的接口。其合理的软件、设备无关软件、设备驱动程序、中断处理程序 软件、设备无关软件、中断处理程序、设备驱动程序 软件、设备驱动程序、设备无关软件、中断处理程序 软件、中断处理程序、设备无关软件、设备驱动程序 层次组织排列顺序是（ ）。

【解析】对于一次设备的调用, 操作系统为用户准备了系统调用的接口, 当用户使用设备时, 首先在用户程序中发起一次系统调用, 操作系统的设备无关层软件接到该调用请求后调用处理程序进行处理, 根据调用格式和形参, 再转到相应的设备驱动程序去处理; 大部分设备在运行时是需要时间的, 所以设备驱动程序会以中断方式驱动设备, 即设置好控制寄存器参数和中断向量等参数后阻塞自己; 当设备准备好或所需数据到达后设备硬件发出中断, 设备驱动程序唤醒, 将数据按上述调用顺序逆向回传到用户程序中, 或继续驱动设备执行下一条指令。因此,

为四个层次:用户层、与设备无关的软件层、设备驱动程序以及中断处理程序。

12．下列选项中, 不能改善磁盘设备性能的是（ ）。

A. 重排请求次序

B. 在一个磁盘上设置多个分区

C. 预读和滞后写

D. 优化文件物理块的分布

【答案】B 。

【解析】

磁盘

的一个瓶颈。“重排性能主要是指其读写速度。相对而言,

磁盘的性能是计算机性能提高请求次序”可以优化磁臂调度的算法, 减少读写时间, 故正确; “预读和滞

性能, 软件从上到下分后写”是利用内存作为磁盘的缓存, 使得对磁盘的访问变为对内存的访问, 也可以在总体上提高其性能; “优化文件物理块的分布”减少磁臂调度和旋转调度的等待时间, 也可以提高磁盘

而磁盘分区仅在磁盘空间的组织上进行划分, 对磁盘

盘设备

性能的, 故答案为B 。 性能的提升没有什么帮助, 是不能改善磁