数据结构与算法复习题+答案（附解析）.docx

数据结构与算法复习题+答案（附解析）

一、单选题（共60题，每题1分，共60分）

1.度量结果集相关性时，如果准确率很高而召回率很低，则说明：

A、大部分相关文件被检索到，但很多不相关的文件也在检索结果里

B、大部分相关文件被检索到，但基准数据集不够大

C、大部分检索出的文件都是相关的，但基准数据集不够大

D、大部分检索出的文件都是相关的，但还有很多相关文件没有被检索出来

正确答案：D

答案解析：准确率很高说明大部分检索出的文件都是相关的，召回率很低说明还有很多相关文件没有被检索出来。

2.在单链表中，若p所指的结点不是最后结点，在p之后插入s所指结点，则执行

A、s-next=p-next;p=s;

B、s-next=p;p-next=s;

C、s-next=p-next;p-next=s;

D、p-next=s;s-next=p;

正确答案：C

3.给定散列表大小为11，散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的5个元素。问：此时该散列表的平均不成功查找次数是多少？

A、不确定

B、26/11

C、5/11

D、1

正确答案：B

4.已知初始为空的队列Q的一端仅能进行入队操作，另外一端既能进行入队操作又能进行出队操作。若Q的入队序列是1、2、3、4、5，则不能得到的出队序列是：

A、5、4、3、1、2

B、5、3、1、2、4

C、4、2、1、3、5

D、4、1、3、2、5

正确答案：D

答案解析：对于这种一端只能入队，另一端既能入队又能出队的队列，我们来分析每个选项。选项A：先让1、2、3、4、5依次入队，然后从另一端依次出队5、4、3、1、2，是可以实现的。选项B：同样先让1、2、3、4、5入队，再从另一端出队5、3、1、2、4，也可实现。选项C：先入队1、2、3、4，出队4、2、1，再入队5，出队3、5，能实现。选项D：若要先出队4，那么前面需要入队1、2、3、4，此时出队4后，下一个出队的应该是3而不是1，所以无法得到4、1、3、2、5这个出队序列。

5.设最小堆（小根堆）的层序遍历结果为{1,3,2,5,4,7,6}。用线性时间复杂度的算法将该堆调整为最大堆（大根堆），则该树的中序遍历结果为：

A、3,5,4,2,6,1,7

B、1,4,3,7,2,6,5

C、3,5,4,7,2,6,1

D、4,1,3,7,6,2,5

正确答案：C

答案解析：首先，已知最小堆的层序遍历结果为{1,3,2,5,4,7,6}，对应的最小堆结构为：1/\32/\/\5476要将其调整为最大堆，从最后一个非叶子节点开始调整。最后一个非叶子节点是2，它有两个子节点5和4，由于5大于4，所以不需要调整。接着看节点3，它有两个子节点5和2，由于5大于2，需要交换3和5，得到：5/\32/\/\1476再看节点1，它有两个子节点3和2，由于3大于2，需要交换1和3，得到：5/\32/\/\1476继续调整，节点3有子节点1和4，不需要调整。此时最大堆结构为：5/\32/\/\1476最大堆的中序遍历结果为：3,5,4,7,2,6,1。所以答案选C。

6.在下列查找的方法中，平均查找长度与结点个数无关的查找方法是：

A、顺序查找

B、二分法

C、利用哈希（散列）表

D、利用二叉搜索树

正确答案：C

答案解析：哈希查找的平均查找长度主要取决于哈希表的装填因子，而不是结点个数。装填因子等于表中记录数与哈希表长度之比。在理想情况下，哈希表的平均查找长度接近1，与结点个数没有直接关系。顺序查找的平均查找长度与结点个数n有关，为(n+1)/2。二分法查找要求数据有序，其平均查找长度与log?n有关，与结点个数n相关。二叉搜索树的平均查找长度也与树的高度有关，而树的高度与结点个数有关。

7.设一棵非空完全二叉树T的所有叶节点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是：

A、k2

B、2k

C、2k?1

D、2k?1

正确答案：C

答案解析：1.首先设完全二叉树的高度为\(h\)。-因为所有叶节点均位于同一层，所以叶节点所在层为