数据结构错题收录（十七）

1、由n个数据元素组成的两个表：一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，已知查找任一元素的概率是相同的，则在两种表中成功查找（）。

A：平均时间后者小
B：平均时间两者相同
C：平均时间前者小
D：无法确定

解析

对于顺序查找，不管线性表是有序的还是无序的，成功查找一个元素的比较次数为1，成功查找第二个元素的比较次数为2，以此类推，即每个元素查找成功的比较次数只与其位置有关（与是否有序无关），因此查找成功的平均时间两者相同。

答案：B

2、在有11个元素的有序表A[1,2,...,11]中进行折半查找（ $\lfloor {(low+high)/2} \rfloor$ ），查找元素A[11]时，被比较的元素依次是（）。

A：6，8，10，11
B：6，9，10，11
C：6，7，9，11
D：6，8，9，11

解析

依据折半查找的思想，第一次mid= $\lfloor (1+11)/2 \rfloor$ =6，第二次mid= $\lfloor [(1+6)+11]/2 \rfloor$ =9，第三次mid= $\lfloor [(1+9)+11]/2 \rfloor$ =10，第四次mid=11。

答案：B

3、已知一个长度为16的顺序表，其元素按关键字有序排列，若采用折半查找算法查找一个不存在的元素，则比较的次数至少是（），至多是（）。

A：4
B：5
C：6
D：7

解析

画出查找过程中构成的判定树，让最小的分支高度对应于最少的比较次数，让最大的分支高度对应于最多的比较次数，出现类似于长度为15的顺序表时，判定树刚好是一棵满树，此时最多比较次数与最少比较次数相等。

答案：A，B

4、具有12个关键字的有序表中，对每个关键字的查找概率相同，折半查找算法查找成功的平均查找长度为（），折半查找查找失败的平均查找长度为（）。

A：37/12
B：35/12
C：39/13
D：49/13

解析

假设有序表中元素为A[0...11]，不难画出对它进行折半查找的判定树如下图所示，圆圈是查找成功结点，方形是虚构的查找失败结点。从而可以求出查找成功的ASL=（1+22+34+45）/12=37/12，查找失败的ASL=（33+4*10）/13=49/13。

在这里插入图片描述

答案：A，D

5、对有2500个记录的索引顺序表(分块表)进行查找，最理想的块长为（）。

A：50
B：125
C：500
D： $\lceil log_2{2500}\rceil$

解析

设块长为b，索引表包含n/b项，索引表的ASL=(n/b+1)/2，块内的ASL=(b+1)/2，纵ASL=索引表的ASL+块内的ASL=（b
n/b+2）/2，其中对于b+n/b，由均值不等式知b=n/b时有最小值，此时b= $\sqrt{n}$ 。则最理想块长为 $\sqrt{2500}$ =50。

答案：A

6、设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块，若对索引表采用顺序查找法来确定子块，且在确定的子块中也采用顺序查找法，则在等概率情况下，分块查找成功的平均查找长度为（）。

A：21
B：23
C：41
D：62

解析

根据公式ASL= $L_i$ + $L_s$ = $\frac{b+1}{2}$ + $\frac{s+1}{2}$ = $\frac{s^2+2s+n}{2s}$ ，其中b=n/s，s=123/3，n=123，代入不难得出ASL为23.故选B。

答案：B

7、为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行（）次关键字比较。

A：10
B：14
C：16
D：21

解析

为使查找效率最高，每个索引块的大小应是 $\sqrt{65025}$ =255，为每个块建立索引，则索引表中索引项的个数为255。若对索引项和索引块内部都采用折半查找，则查找效率最高，为 $\lceil log_2{(255+1)} \rceil$ + $\lceil log_2{(255+1)} \rceil$ =16。

答案：C

8、在有n(n>1000)个元素的升序数组A中查找关键字x，查找算法的伪代码如下所示。

k=0;
while(k<n 且 A[k]<x)  k=k+3;
if(k<n 且A[k]==x) 查找成功;
else if(k-1<n 且 A[k-1]==x) 查找成功;
    else if(k-2<n 且 A[k-2]==x) 查找成功;
        else 查找失败;

本算法与折半算法相比，有可能具有更少比较次数的情形是（）。

A：当x不在数组中
B：当x接近数组开头处
C：当x接近数组结尾处
D：当x位于数组中间位置

解析

答案：B

9、设某链表中最常用操作是再链表尾部插入或删除元素，则选用下列____存储方式最节省运算时间。

A：单项链表
B：单向循环链表
C：双向链表
D：双向循环链表

解析

在链尾的末尾插入和删除一个结点时，需要修改其相邻结点的指针域。而从头寻找尾结点及尾结点的前驱结点时，双向循环链表用时最少。

答案：D

10、在单链表中，若p节点不是尾节点，在其后插入S节点的操作是____。

A：s->next = p; p->next = s;
B：s->next = p->next; p->next = s;
C：s->next = p->next; p=s;
D：p->next = s; s->next = p;

解析

先要将s节点的next指向p之后的节点（s->next = p->next），然后将p节点的next指向s（p->next=s)。

数据结构错题收录（十七）