1、由n个数据元素组成的两个表：一个递增有序，一个无序。采用顺序查找算法，对有序表从头开始查找，发现当前元素已不小于待查元素时，停止查找，确定查找不成功，已知查找任一元素的概率是相同的，则在两种表中成功查找（）。
- A：平均时间后者小
- B：平均时间两者相同
- C：平均时间前者小
- D：无法确定
解析
对于顺序查找，不管线性表是有序的还是无序的，成功查找一个元素的比较次数为1，成功查找第二个元素的比较次数为2，以此类推，即每个元素查找成功的比较次数只与其位置有关（与是否有序无关），因此查找成功的平均时间两者相同。
答案：B
2、在有11个元素的有序表A[1,2,...,11]中进行折半查找（%2F2%7D%20%5Crfloor)
），查找元素A[11]时，被比较的元素依次是（）。
- A：6，8，10，11
- B：6，9，10，11
- C：6，7，9，11
- D：6，8，9，11
解析
依据折半查找的思想，第一次mid==6，第二次mid=
=9，第三次mid=
=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：
解析
设块长为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=。则最理想块长为
=50。
答案：A
6、设顺序存储的某线性表共有123个元素，按分块查找的要求等分为3块，若对索引表采用顺序查找法来确定子块，且在确定的子块中也采用顺序查找法，则在等概率情况下，分块查找成功的平均查找长度为（）。
- A：21
- B：23
- C：41
- D：62
解析
根据公式ASL=+
=
+
=
，其中b=n/s，s=123/3，n=123，代入不难得出ASL为23.故选B。
答案：B
7、为提高查找效率，对有65025个元素的有序顺序表建立索引顺序结构，在最好情况下查找到表中已有元素最多需要执行（）次关键字比较。
- A：10
- B：14
- C：16
- D：21
解析
为使查找效率最高，每个索引块的大小应是=255，为每个块建立索引，则索引表中索引项的个数为255。若对索引项和索引块内部都采用折半查找，则查找效率最高，为
+
=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)。
