1、由n個數(shù)據(jù)元素組成的兩個表：一個遞增有序，一個無序。采用順序查找算法，對有序表從頭開始查找，發(fā)現(xiàn)當(dāng)前元素已不小于待查元素時，停止查找，確定查找不成功，已知查找任一元素的概率是相同的，則在兩種表中成功查找（）。

• A：平均時間后者小
• B：平均時間兩者相同
• C：平均時間前者小
• D：無法確定

解析

對于順序查找，不管線性表是有序的還是無序的，成功查找一個元素的比較次數(shù)為1，成功查找第二個元素的比較次數(shù)為2，以此類推，即每個元素查找成功的比較次數(shù)只與其位置有關(guān)（與是否有序無關(guān)），因此查找成功的平均時間兩者相同。

答案：B

2、在有11個元素的有序表A[1,2,...,11]中進(jìn)行折半查找（），查找元素A[11]時，被比較的元素依次是（）。

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

解析

依據(jù)折半查找的思想，第一次mid==6，第二次mid==9，第三次mid==10，第四次mid=11。

答案：B

3、已知一個長度為16的順序表，其元素按關(guān)鍵字有序排列，若采用折半查找算法查找一個不存在的元素，則比較的次數(shù)至少是（），至多是（）。

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

解析

畫出查找過程中構(gòu)成的判定樹，讓最小的分支高度對應(yīng)于最少的比較次數(shù)，讓最大的分支高度對應(yīng)于最多的比較次數(shù)，出現(xiàn)類似于長度為15的順序表時，判定樹剛好是一棵滿樹，此時最多比較次數(shù)與最少比較次數(shù)相等。

答案：A，B

4、具有12個關(guān)鍵字的有序表中，對每個關(guān)鍵字的查找概率相同，折半查找算法查找成功的平均查找長度為（），折半查找查找失敗的平均查找長度為（）。

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

解析

假設(shè)有序表中元素為A[0...11]，不難畫出對它進(jìn)行折半查找的判定樹如下圖所示，圓圈是查找成功結(jié)點(diǎn)，方形是虛構(gòu)的查找失敗結(jié)點(diǎn)。從而可以求出查找成功的ASL=（1+22+34+45）/12=37/12，查找失敗的ASL=（33+4*10）/13=49/13。

在這里插入圖片描述

答案：A，D

5、對有2500個記錄的索引順序表(分塊表)進(jìn)行查找，最理想的塊長為（）。

• A：50
• B：125
• C：500
• D：

解析

設(shè)塊長為b，索引表包含n/b項(xiàng)，索引表的ASL=(n/b+1)/2，塊內(nèi)的ASL=(b+1)/2，縱ASL=索引表的ASL+塊內(nèi)的ASL=（b
n/b+2）/2，其中對于b+n/b，由均值不等式知b=n/b時有最小值，此時b=。則最理想塊長為=50。

答案：A

6、設(shè)順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊，若對索引表采用順序查找法來確定子塊，且在確定的子塊中也采用順序查找法，則在等概率情況下，分塊查找成功的平均查找長度為（）。

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

解析

根據(jù)公式ASL=+=+=，其中b=n/s，s=123/3，n=123，代入不難得出ASL為23.故選B。

答案：B

7、為提高查找效率，對有65025個元素的有序順序表建立索引順序結(jié)構(gòu)，在最好情況下查找到表中已有元素最多需要執(zhí)行（）次關(guān)鍵字比較。

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

解析

為使查找效率最高，每個索引塊的大小應(yīng)是=255，為每個塊建立索引，則索引表中索引項(xiàng)的個數(shù)為255。若對索引項(xiàng)和索引塊內(nèi)部都采用折半查找，則查找效率最高，為+=16。

答案：C

8、在有n(n>1000)個元素的升序數(shù)組A中查找關(guān)鍵字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 查找失敗;

本算法與折半算法相比，有可能具有更少比較次數(shù)的情形是（）。

• A：當(dāng)x不在數(shù)組中
• B：當(dāng)x接近數(shù)組開頭處
• C：當(dāng)x接近數(shù)組結(jié)尾處
• D：當(dāng)x位于數(shù)組中間位置

解析

答案：B

9、設(shè)某鏈表中最常用操作是再鏈表尾部插入或刪除元素，則選用下列____存儲方式最節(jié)省運(yùn)算時間。

• A：單項(xiàng)鏈表
• B：單向循環(huán)鏈表
• C：雙向鏈表
• D：雙向循環(huán)鏈表

解析

在鏈尾的末尾插入和刪除一個結(jié)點(diǎn)時，需要修改其相鄰結(jié)點(diǎn)的指針域。而從頭尋找尾結(jié)點(diǎn)及尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)時，雙向循環(huán)鏈表用時最少。

答案：D

10、在單鏈表中，若p節(jié)點(diǎn)不是尾節(jié)點(diǎn)，在其后插入S節(jié)點(diǎn)的操作是____。

• 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節(jié)點(diǎn)的next指向p之后的節(jié)點(diǎn)（s->next = p->next），然后將p節(jié)點(diǎn)的next指向s（p->next=s)。

答案：B

學(xué)海無涯苦作舟