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

一、填空题

1．

给定一组数据

的值为_____。 【答案】5；96

【解析】每次找两个最小的权值构建哈夫曼树：

以它构造一棵哈夫曼树，则树高为_____，

带权路径长度

2． 设广义表

则

是_____tail（L ）是_____；L 的长度是_____；深度是_____。

；；2；2 【答案】（ ）（（ ））

【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。

3． 已知二维数组中每个元素占4个单元，在按行优先方式将其存储到起始地址为1000的连续存储区域时，

【答案】1196

【解析】设元素的行标为i ，列标为j 。则它的存储位置为：

4． 高度为h 的堆中，最多有_____元素，最少有_____个元素。

【答案】

当最后一层只有

【解析】当这个堆构成的是满二叉树时，元素的个数最多，元素个数为 一个元素时，此时堆的元素个数最少，元素个数为

5． 高度为4的3阶B-树中，最多有_____个关键字。

【答案】26

【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。

的地址是：_____。

6． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录 7．

【答案】5

8． 空格串是指_____，其长度等于_____。

【答案】由空格字符（

值32）所组成的字符串；空格个数

9． 从平均时间性能而言，_____排序最佳。

【答案】快速

【解析】快速算法的平均时间复杂度为nlogn 。

10．属于不稳定排序的有_____。

【答案】希尔排序、简单选择排序、快速排序、堆排序等

=_____

二、选择题

11．某系统有n 台互斥使用的同类设备，3个并发进程需要3, 4, 5台设备，可确保系统不发生死锁的设备数n 最小为（ ）

A.9 B.10 C.11 D.12

【答案】B

【解析】2+3+4+1 = 10

12．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。

A.257 B.258 C.384 D.385 【答案】C

【解析】由

：_

则

和

_

_可知

，

即

显然

384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个

性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。

13．下列选项中，降低进程优先级的合理时机是（ ）。

A. 进程的时间片用完

B. 进程刚完成1/0, 进入就绪队列 C. 进程长期处于就绪队列 D. 进程从就绪状态转为运行态 【答案】A

【解析】进程时间片用完可以降低其优先级，完成

的进程应该提升其优先级，处于就绪队

列等待调度的进程一般不会改变其优先级。进行这样的操作主要是为了改善交互式系统的响应时间，并均衡各个作业的公平性。采用时间片轮转技术主要为改善交互式用户的感受，使其觉得是，时间片用完后降低其优独享计算机（时间片轮转可以有效地防止计算繁忙型的进程独占计算机）先级是为了改善新进程的响应时间（新进程优先级较高，老进程降低优先级可以保证新进程具有，对于刚进入就绪队列的新进程，往往在创建时已经根据其特点和要求确定好优先级，不优先权）

会随意改变。而对于从阻塞状态唤醒的进程，由于阻塞带来了较长时间的等待，一般会根据阻塞队列的不同适当地提高优先级，以改善用户响应时间。

14．给定二叉树如下图所示。设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树，若遍历后的节点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）

A.LRN B.NRL C.RLN

D.RNL

图

【答案】D

【解析】对“二叉树”而言，一般有三条搜索路径； ①先上后下的按层次遍历；

②先左（子树）后右（子树）的遍历； ③先右（子树）后左（子树）的遍历；

其中第1种路径的搜索方式就是常见的层次遍历，第2种搜索路径方式包括常见的NLR 、中序遍历LNR 、后序遍历LRN , 第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN 。本题考查的是第3种搜索路径方式的一种情况。根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D 。