1、由n个数据元素组成的两个表:一个递增有序,一个无序。采用顺序查找算法,对有序表从头开始查找,发现当前元素已不小于待查元素时,停止查找,确定查找不成功,已知查找任一元素的概率是相同的,则在两种表中成功查找()。
- A:平均时间后者小
- B:平均时间两者相同
- C:平均时间前者小
- D:无法确定
解析
对于顺序查找,不管线性表是有序的还是无序的,成功查找一个元素的比较次数为1,成功查找第二个元素的比较次数为2,以此类推,即每个元素查找成功的比较次数只与其位置有关(与是否有序无关),因此查找成功的平均时间两者相同。
答案:B
2、在有11个元素的有序表A[1,2,...,11]中进行折半查找(),查找元素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)。
网友评论