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

一、填空题

1． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

2． 假定查找有序表

【答案】

表

平均查找次数为。

3． 设为哈夫曼树的叶结点数目，则该哈夫曼树共有_____个结点。 【答案】

【解析】哈夫曼树只有度为0和2的节点。

4． 外排序的基本操作过程是_____和_____。

【答案】生成有序归并段(顺串) ；归并

5． 堆是一种有用的数据结构。堆排序是一种_____排序，堆实质上是一棵_____结点的层次序列。对含有N 个元素的序列进行排序时，堆排序的时间复杂度是_____，所需的附加存储结点是_____。关键码序列05, 23, 16, 68, 94, 72, 71, 73是否满足堆的险质_____ 。

【答案】选择；完全二叉树；；O(1)；满足堆的性质

6． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。

【答案】69

【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。

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

【答案】提高查找速度

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。【解析】折半查找时每个的次数如表所示:

8． 已知有序表为(12，18，24，35，47，50，62，83，90，115，134) 当用二分法查找90时，需次查找成功，查找47时_____成功，查找100时，需_____次才能确定不成功。

【答案】2; 4; 3

【解析】二分法查找元素次数列表

查找100是找到115就停止了。

9． 有五个数据依次入找:1，2，3，4，5。在各种出栈的序列中，以3，4先出栈的序列有_____。(3在4之前出栈)

【答案】3个

【解析】以3，4先出栈的序列有34521、34215、34251共3个。

10．在一棵m 阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____; 若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。 【答案】

【解析】m 阶B-树除根结点和叶子结点外，结点中关键字个数最多是m －1，最少

11．遍历图的过程实质上是_____，广度优先遍历图的时间复杂度____；深度优先遍历图的时间复杂度_____，两者不同之处在于_____，反映在数据结构上的差别是_____。

【答案】查找顶点的邻接点的过程；0(n+e)；0(n+e)；访问顶点的顺序不同；队列和栈

【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。

12．求最短路径的Dijkstra 算法的时间复杂度为_____。 【答案】

二、单项选择题

13．对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次釆用的增量是（ ）。

A.1

B.4

C.3

D.2

【答案】B

【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的增量是4。

14．采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中, 正确的是（ ）。

A. 递归次数与初始数据的排列次序无关

B. 每次划分后, 先处理较长的分区可以减少递归次数

C. 每次划分后, 先处理较短的分区可以减少递归次数

D. 递归次数与每次划分后得到的分区的处理顺序无关

【答案】D

【解析】快速排序是递归的, 递归过程可用一棵二叉树给出, 递归调用层次数与二叉树的深度一致。例如:待排序列{48, 62, 35, 77, 55, 14, 35, 98) , 采用快速排序方法, 其对应递归调用过程的二叉树如下图所示。

图

在最坏情况下, 若初始序列按关键码有序或基本有序时, 快速排序反而蜕化为冒泡排序。即其对应递归调用过程的二叉树是一棵单支树。因此快速排序的递归次数与初始数据的排列次序有关。但快速排序的递归次数与每次划分后得到的分区处理顺序无关, 即先处理较长的分区或先处理较短的分区都不影响递归次数。

15．下列选项中, 对正确接收到的数据帧进行确认的MAC 协议是（ ）。

A.CSMA

B.CDMA C. D.

【答案】D

【解析】可采用排除法。CDMA 是码分多址复用, 是物理层的内容; CSMA/CD即带冲突检测的载波监听多路访问, 接收方并不需要确认; CSMA/CD是CSMA 的加强版, 故CSMA 也无确定; CSMA/CD是中的协议, 其利用ACK 信号来避免冲突的发生, 也就是说, 只有当客户端收到网络上返回的ACK 信号后才确认送出的数据已经正确到达目的地址, 因此答案是D 。

16．4个圆盘的Hanoi 塔，总的移动次数为（ ）。

A.7 B.

C.15

D.16

【答案】C

【解析】Hanoi 问题总移动次数为:2M 次。