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

一、单项选择题

1． 下列二叉排序树中查找效率最高的是（ ）。

A. 平衡二叉树

B. 二叉查找树

C. 没有左子树的二叉排序树

D. 没有右子树的二叉排序树

【答案】A

【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树:①若左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1, 甚至很大，因此查找效率低。

2． 有n(n＞0) 个分支结点的满二叉树的深度是（ ）。

A.n 2﹣l

B.log 2(n＋1) ＋1

C.log 2(n＋1)

D.log 2(n—1)

【答案】C

【解析】满二叉树的结点总数＝分支的结点总数＋非分支的结点总数。由于此树为满二叉树，

所以非分支的结点总数为1，所以满二叉树共有n ＋1个结点，所以满二叉树的深度为log 2 (n＋1) 。

3． 直接插入排序在最好情况下的时间复杂度为（ ）。 A.

B.O(n) C. 2D.O(n)

【答案】B

【解析】当序列是按照直接插入排序的顺序有序时，此时进行插入时，每次都只需要和末尾的一个元素进行比较，此时的时间复杂度最好，为O(n)。

4． 下述文件中适合于磁带存储的是（ ）。

A. 顺序文件

B. 索引文件

C. 哈希文件

D. 多关键字文件

【答案】A

【解析】磁带存储是一种顺序存储，顺序文件(sequential file)是记录按其在文件中的逻辑顺序依次进入存储介质而建立的，即顺序文件中物理记录的顺序和逻辑记录的顺序是一致的。因此顺序文件适合磁带存储。

5． 线性表的顺序存储结构是一种（ ）。

A. 随机存取的存储结构

B. 顺序存取的存储结构

C. 索引存取的存储结构

D.Hash 存取的存储结构

【答案】A

【解析】线性表包括顺序存储结构和链式存储结构，顺序存储结构能够随机存取表中的元素，但插入和删除操作较麻烦，链式存储结构不能随机访问表中的元素，但是能够表示元素之间的先后次序，而且插入和删除操作较容易。

6． 假设磁头当前位于第105道，正在向磁道序号增加的方向移动. 现有一个磁道访问请求，序列为35，45，12，68，110，180，170，195，采用SCAN 调度(电梯调度) 算法得到的磁道访问序列是（ ）.

A.110， 170， 180， 195， 68， 45， 35， 12

B.110， 68， 45， 35， 12， 170， 180， 195

C.110， 170， 180， 195， 12， 35， 45， 68

D.12， 31， 45， 68， 110， 170， 180， 195

【答案】A

【解析】SCAN 算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返. 因此，当磁头从105道向序号增加的方向移动时，便会服务所有大于105的磁道号(从小到大的顺序) ；往回返时又会按照从大到小的顺序进行服务. 注意与循环扫描算法的区别，所以SCAN 算法的访问序列是：110， 170， 180， 195， 68， 45， 35， 12

7． 对给定的关键字序列110, 119, 007, 911, 114, 120, 122进行基数排序, 则第2趟分配收集后得到的关键字序列是（ ）

A.007.110.119.114.911.120.122

B.007, 110, 119, 114, 911, 122, 120

C.007, 110, 911, 114, 119, 120, 122

D.110, 120, 911, 122, 114, 007, 119

【答案】C

【解析】基数排序的第1趟排序是按照个位数字来排序的, 第2趟排序是按然十位数字的大小进行排序的, 故答案是C 选项。

8． 在一棵三元树中度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（ ）个。

A.4

B.5

C.6

D.7

【答案】C

【解析】设度为0的结点数为x ，则度为3的树总结点数n ＝度为0的结点数＋度为1的结点数＋度为2的结点数＋度为3的结点数＝x ＋2＋l ＋2＝x ＋5；从每个结点所指向的结点数的和的角度来计算度为3的树总结点数n ＝2×3＋1×2＋2×1＋1＝11。两种方法所计算出来的n 相等，所以x ＝6。

9． 主机甲通过1个路由器个路由器(存储转发方式) 与主机乙互联, 两段链路的数据传输速率均为10Mbps , 主机甲分别采用报文交换和组大小为10kb 的分组交换向主机乙发送1个大小为8Mb(1M=106)的报文。若忽略链路传播延迟、分组头开销和拆装时间, 则两种交换方式完成该报文传输所需的总时间分别为（ ）

A.800ms>1600ms

B.801ms 、1600ms

C.1600ms 、800ms

D.1600ms 、801ms

【答案】D

【解析】不进行分组时, 发送一个报文的时延是

的时延也是800ms 共计1600ms 。进行分组后发送一个报文的时延是

总时间为801ms 。

10．下列线索二叉树中(用虚线表示线索) , 符合后序线索树定义的是（ ）。

, 在接收端接收此报文件, 接收一个报文的时延也是1ms , 但是在发送第二个报文时, 第一个报文已经开始接收。共计有800个分组,