《數(shù)據(jù)結(jié)構(gòu)[C語言版]第2版習(xí)題答案_嚴(yán)蔚敏[簡(jiǎn)化版]》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)[C語言版]第2版習(xí)題答案_嚴(yán)蔚敏[簡(jiǎn)化版]（27頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 第2章 線性表 1．選擇題 （1）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（ ）。 A．110 B．108 C．100 D．120 答案：B 解釋：順序表中的數(shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。 （3）向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變，平均要移動(dòng)的元素個(gè)數(shù)為（ ）。 A．8 B．63.5 C．63 D．7 答案：B 解釋：平均要移動(dòng)的元素個(gè)數(shù)為：n/2。 （4）存儲(chǔ)的存儲(chǔ)結(jié)

2、構(gòu)所占存儲(chǔ)空間（ ）。 A．分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B．只有一部分，存放結(jié)點(diǎn)值 C．只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針 D．分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù) 答案：A （5）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ ）。 A．必須是連續(xù)的 B．部分地址必須是連續(xù)的 C．一定是不連續(xù)的 D．連續(xù)或不連續(xù)都可以 答案：D （6）線性表Ｌ在（ ）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。 A．需經(jīng)常修改Ｌ中的結(jié)點(diǎn)值 Ｂ．需不斷對(duì)Ｌ進(jìn)行刪除插入 C．Ｌ中含有大量的

3、結(jié)點(diǎn) Ｄ．Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜 答案：B 解釋：鏈表最大的優(yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。 （7）單鏈表的存儲(chǔ)密度（ ）。 A．大于1 B．等于1 C．小于1 D．不能確定 答案：C 解釋：存儲(chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D，指針域所占的空間為N，則存儲(chǔ)密度為：D/(D+N)，一定小于1。 （8）將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（ ）。 A．n B．2n-1 C．2n

4、 D．n-1 答案：A 解釋：當(dāng)?shù)谝粋€(gè)有序表中所有的元素都小于（或大于）第二個(gè)表中的元素，只需要用第二個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n次。 （9）在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1≤i≤n+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（ ）個(gè)元素。 A．n-i B．n-i+1 C．n-i-1 D．I 答案：B (10) 線性表L=(a1，a2,……an)，下列說法正確的是（ ）。 A．每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B．線性表中至少有一個(gè)元素 C．表中諸元素的排列必須是由小到大或由大到小 D．除第一個(gè)和最后一個(gè)元素外，其余每

5、個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。 答案：D (12) 以下說法錯(cuò)誤的是（ ）。 A．求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低 B．順序存儲(chǔ)的線性表可以隨機(jī)存取 C．由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活 D．線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu) 答案：D 解釋：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，有不同的適用場(chǎng)合。 (13) 在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語句應(yīng)為（ ）。 A．s->next=p+1;p->next=s; B．(*p).next=s;(*s).next

6、=(*p).next; C．s->next=p->next;p->next=s->next; D．s->next=p->next;p->next=s; 答案：D (14) 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。 A．p->next->prior=p->prior;p->prior->next=p->next; B．p->next=p->next->next;p->next->prior=p; C．p->prior->next=p;p->prior=p->prior->prior; D．p->prior=p->next->next;p->next=p

7、->prior->prior; 答案：A (15) 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（ ）。 A．p->next=q; q->prior=p;p->next->prior=q;q->next=q; B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next; C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q;

8、 答案：C 2．算法設(shè)計(jì)題 （1）將兩個(gè)遞增的有序鏈表合并為一個(gè)遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個(gè)鏈表的存儲(chǔ)空間, 不另外占用其它的存儲(chǔ)空間。表中不允許有重復(fù)的數(shù)據(jù)。 [算法描述] void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向 pa=La->next; pb=Lb->next; //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個(gè)結(jié)點(diǎn) Lc=pc=La; //用La的頭結(jié)點(diǎn)作為L(zhǎng)c的頭結(jié)點(diǎn) while(pa

9、 && pb) {if(pa->datadata){pc->next=pa;pc=pa;pa=pa->next;} //取較小者La中的元素，將pa在pc的后面，pa指針后移 else if(pa->data>pb->data) {pc->next=pb; pc=pb; pb=pb->next;} //取較小者Lb中的元素，將pb在pc的后面，pb指針后移 else //相等時(shí)取La中的元素，刪除Lb中的元素 {pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;

10、pb =q; } } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //釋放Lb的頭結(jié)點(diǎn) } （6）設(shè)計(jì)一個(gè)算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點(diǎn)。 [算法描述] ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一個(gè)結(jié)點(diǎn)中數(shù)據(jù)具有最大值 p=L->next->next; while(p != NULL ){//如果下一個(gè)結(jié)點(diǎn)存在 if(p->data > pmax->da

11、ta) pmax=p;//如果p的值大于pmax的值，則重新賦值 p=p->next;//遍歷鏈表 } return pmax->data; 第3章 棧和隊(duì)列 1．選擇題 （1）若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（ ）種情況。 A．5，4，3，2，1 B．2，1，5，4，3 C．4，3，1，2，5 D．2，3，5，4，1 答案：C 解釋：棧是后進(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素1比元素2先出棧，違背了棧的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)所示的情況。 （2）若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3

12、，…，pn，若p1=n，則pi為（ ）。 A．i B．n-i C．n-i+1 D．不確定 答案：C 解釋：棧是后進(jìn)先出的線性表，一個(gè)棧的入棧序列是1，2，3，…，n，而輸出序列的第一個(gè)元素為n，說明1，2，3，…，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n，p2=n-1，…，pi=n-i+1。 （3）數(shù)組Ｑ［ｎ］用來表示一個(gè)循環(huán)隊(duì)列，ｆ為當(dāng)前隊(duì)列頭元素的前一位置，ｒ?yàn)殛?duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于ｎ，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（ ）。 A．r-f B．(n+f-r)%n C．n+r-f

13、D．（n+r-f)%n 答案：D 解釋：對(duì)于非循環(huán)隊(duì)列，尾指針和頭指針的差值便是隊(duì)列的長(zhǎng)度，而對(duì)于循環(huán)隊(duì)列，差值可能為負(fù)數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+r-f)%n。 （4）鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作（）。 A．x=top->data;top=top->link；B．top=top->link;x=top->link； C．x=top;top=top->link； D．x=top->link； 答案：A 解釋：

14、x=top->data將結(jié)點(diǎn)的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點(diǎn)，即摘除棧頂結(jié)點(diǎn)。 （5）設(shè)有一個(gè)遞歸算法如下 ?????? int fact(int n) {? //n大于等于0 ??????????? if(n<=0) return 1; ??????????? else return n*fact(n-1);?????? } 則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（）。? A．?n+1?????B．?n-1?????C． n?????D． n+2 答案：A 解釋：特殊值法。設(shè)n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選A。 （6）棧在

15、?（）中有所應(yīng)用。 A．遞歸調(diào)用B．函數(shù)調(diào)用C．表達(dá)式求值D．前三個(gè)選項(xiàng)都有 答案：D 解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。 （7）為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。 A．隊(duì)列 B．棧 C． 線性表 D．有序表 答案：A 解釋：解決緩沖區(qū)問題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線性表。 （8）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6

16、依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（?。?。 A．2 B．3 C．4 D． 6 答案：B 解釋：元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，可知元素入隊(duì)的序列是e2、e4、e3、e6、e5和e1，即元素出棧的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧，易知棧S中最多同時(shí)存在3個(gè)元素，故棧S的容量至少為3。 （9）若一個(gè)棧以向量V[1..n]存儲(chǔ)，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確操作是(

17、 )。 A．top++; V[top]=x; B．V[top]=x; top++; C．top--; V[top]=x; D．V[top]=x; top--; 答案：C 解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進(jìn)棧，又因?yàn)樵卮鎯?chǔ)在向量空間V[1..n]中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚，之后將元素x存儲(chǔ)在V[n]。 （10）設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（?。?shù)據(jù)結(jié)構(gòu)最佳。 A．線性表的順序存儲(chǔ)結(jié)構(gòu)B．隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)D. 棧 答案：D 解釋：利用棧的后進(jìn)先出原則。 （11）用方式存儲(chǔ)的隊(duì)列

18、，在進(jìn)行刪除運(yùn)算時(shí)（?。?。 A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改 答案：D 解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個(gè)元素時(shí)，隊(duì)尾指針也丟失了，因此需對(duì)隊(duì)尾指針重新賦值。 （12）循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A[0..m]中，則入隊(duì)時(shí)的操作為（　）。 A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%mD. rear=(rear+1)%(m+1) 答案：D 解釋：數(shù)組A[0..m

19、]中共含有m+1個(gè)元素，故在求模運(yùn)算時(shí)應(yīng)除以m+1。 （13）最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（?。? A. (rear+1)%n==front B. rear==front C．rear+1==front D. (rear-l)%n==front 答案：B 解釋：最大容量為n的循環(huán)隊(duì)列，隊(duì)滿條件是(rear+1)%n==front，隊(duì)空條件是rear==front。 （14）棧和隊(duì)列的共同點(diǎn)是（?。?。 A. 都是先進(jìn)先出 B. 都是先

20、進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒有共同點(diǎn) 答案：C 解釋：棧只允許在棧頂處進(jìn)行插入和刪除元素，隊(duì)列只允許在隊(duì)尾插入元素和在隊(duì)頭刪除元素。 （15）一個(gè)遞歸算法必須包括（?。?。 A. 遞歸部分B. 終止條件和遞歸部分 C. 迭代部分 D. 終止條件和迭代部分 答案：B 2．算法設(shè)計(jì)題 （1）將編號(hào)為0和1的兩個(gè)棧存放于一個(gè)數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號(hào)棧的棧頂指針top[0]等于-1時(shí)該棧為空，當(dāng)?shù)?號(hào)棧的棧頂指針top[1]等于m時(shí)該棧為空。兩個(gè)棧均從兩端向中間增長(zhǎng)。試編寫雙棧初始化，判斷?？铡M、進(jìn)棧和出棧等算法

21、的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下： Typedef struct {int top[2],bot[2]; //棧頂和棧底指針 SElemType *V; //棧數(shù)組 int m; //棧最大可容納元素個(gè)數(shù) }DblStack [題目分析] 兩棧共享向量空間，將兩棧棧底設(shè)在向量?jī)啥?，初始時(shí)，左棧頂指針為-1，右棧頂為m。兩棧頂指針相鄰時(shí)為棧滿。兩棧頂相向、迎面增長(zhǎng)，棧頂指針指向棧頂元素。 [算法描述] (1)?棧初始化 int?Init() ?{S.top[0]=-1; ??S.top[1]=m; ??return?1;?//初始化成功 } (2)

22、?入棧操作： int?push(stk S?,int?i,int?x) ∥i為棧號(hào)，i=0表示左棧，i=1為右棧，x是入棧元素。入棧成功返回1，失敗返回0 {if(i<0||i>1){ cout<<“棧號(hào)輸入不對(duì)”<

23、操作 ElemType pop(stk S,int?i) ∥退棧。i代表?xiàng)Ｌ?hào)，i=0時(shí)為左棧，i=1時(shí)為右棧。退棧成功時(shí)返回退棧元素 ∥否則返回-1 {if(i<0 || i>1){cout<<“棧號(hào)輸入錯(cuò)誤”<

24、[S.top[1]++]); ???}∥switch????? }∥算法結(jié)束 (4)?判斷?？? int?Empty(); {return?(S.top[0]==-1 && S.top[1]==m); } [算法討論]? 請(qǐng)注意算法中兩棧入棧和退棧時(shí)的棧頂指針的計(jì)算。左棧是通常意義下的棧，而右棧入棧操作時(shí)，其棧頂指針左移（減1），退棧時(shí)，棧頂指針右移（加1）。 （2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個(gè)算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)? [題目分析] 將字符串前一半入棧，然

25、后，棧中元素和字符串后一半進(jìn)行比較。即將第一個(gè)出棧元素和后一半串中第一個(gè)字符比較，若相等，則再出棧一個(gè)元素與后一個(gè)字符比較，……，直至?？眨Y(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時(shí)，結(jié)論字符序列不是回文。 [算法描述] #define StackSize 100 //假定預(yù)分配的?？臻g最多為100個(gè)元素 typedef char DataType;//假定棧元素的數(shù)據(jù)類型為字符 typedef struct {DataType data[StackSize]; int top; }SeqStack; int IsHuiwen( char *t) {//判斷t字

26、符向量是否為回文，若是，返回1，否則返回0 SeqStack s; int i , len; char temp; InitStack( &s); len=strlen(t); //求向量長(zhǎng)度 for ( i=0; i

27、 （3）設(shè)從鍵盤輸入一整數(shù)的序列：a1, a2, a3，…，an，試編寫算法實(shí)現(xiàn)：用棧結(jié)構(gòu)存儲(chǔ)輸入的整數(shù)，當(dāng)ai≠-1時(shí)，將ai進(jìn)棧；當(dāng)ai=-1時(shí)，輸出棧頂整數(shù)并出棧。算法應(yīng)對(duì)異常情況（入棧滿等）給出相應(yīng)的信息。 [算法描述] #define maxsize 棧空間容量 void InOutS(int s[maxsize]) //s是元素為整數(shù)的棧，本算法進(jìn)行入棧和退棧操作。 {int top=0; //top為棧頂指針，定義top=0時(shí)為?？铡? for(i=1; i<=n; i++) //n個(gè)整數(shù)序列作處理。 {cin>>x); //從

28、鍵盤讀入整數(shù)序列。 if(x!=-1) // 讀入的整數(shù)不等于-1時(shí)入棧。 ｛if(top==maxsize-1){cout<<“棧滿”<

29、指針) ，試編寫相應(yīng)的置空隊(duì)、判隊(duì)空 、入隊(duì)和出隊(duì)等算法。 [算法描述] //先定義鏈隊(duì)結(jié)構(gòu): typedef struct queuenode {Datatype data; struct queuenode *next; }QueueNode; //以上是結(jié)點(diǎn)類型的定義 typedef struct {queuenode *rear; }LinkQueue; //只設(shè)一個(gè)指向隊(duì)尾元素的指針 (1) 置空隊(duì) void InitQueue( LinkQueue *Q) { //置空隊(duì)：就是使頭結(jié)點(diǎn)成為隊(duì)尾元素 　QueueNode *s; Q->rear = Q

30、->rear->next;//將隊(duì)尾指針指向頭結(jié)點(diǎn) while (Q->rear!=Q->rear->next)//當(dāng)隊(duì)列非空，將隊(duì)中元素逐個(gè)出隊(duì) {s=Q->rear->next; Q->rear->next=s->next; delete s; 　}//回收結(jié)點(diǎn)空間 } (2) 判隊(duì)空? int EmptyQueue( LinkQueue *Q) { //判隊(duì)空。當(dāng)頭結(jié)點(diǎn)的next指針指向自己時(shí)為空隊(duì) 　return Q->rear->next->next==Q->rear->next; } (3) 入隊(duì) void EnQueue( LinkQueue *

31、Q, Datatype x) { //入隊(duì)。也就是在尾結(jié)點(diǎn)處插入元素 QueueNode *p=new QueueNode;//申請(qǐng)新結(jié)點(diǎn) p->data=x; p->next=Q->rear->next;//初始化新結(jié)點(diǎn)并鏈入 Q-rear->next=p;? Q->rear=p;//將尾指針移至新結(jié)點(diǎn) } (4) 出隊(duì) Datatype DeQueue( LinkQueue *Q) {//出隊(duì),把頭結(jié)點(diǎn)之后的元素摘下 Datatype t; QueueNode *p; if(EmptyQueue( Q )) Error("Queue underflow");

32、 p=Q->rear->next->next; //p指向?qū)⒁碌慕Y(jié)點(diǎn) x=p->data; //保存結(jié)點(diǎn)中數(shù)據(jù) if (p==Q->rear) {//當(dāng)隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí)，p結(jié)點(diǎn)出隊(duì)后，要將隊(duì)尾指針指向頭結(jié)點(diǎn) 　Q->rear = Q->rear->next; Q->rear->next=p->next; } else? Q->rear->next->next=p->next;//摘下結(jié)點(diǎn)p delete p;//釋放被刪結(jié)點(diǎn) return x; } 第4章 串、數(shù)組和廣義表 1．選擇題 （1）串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 A．

33、可以順序存儲(chǔ) B．?dāng)?shù)據(jù)元素是一個(gè)字符 C．可以鏈?zhǔn)酱鎯?chǔ) D．?dāng)?shù)據(jù)元素可以是多個(gè)字符若 答案：B （2）串下面關(guān)于串的的敘述中，（ ）是不正確的？ A．串是字符的有限序列 B．空串是由空格構(gòu)成的串 C．模式匹配是串的一種重要運(yùn)算 D．串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ) 答案：B 解釋：空格常常是串的字符集合中的一個(gè)元素，有一個(gè)或多個(gè)空格組成的串成為空格串，零個(gè)字符的串成為空串，其長(zhǎng)度為零。 （3）串“ababaaababaa”的next數(shù)組為（ ）。 A．012345678999 B．01

34、2121111212 C．011234223456 D．0123012322345 答案：C （4）串“ababaabab”的nextval為（ ）。 A．010104101 B．010102101C．010100011 D．010101011 答案：A （5）串的長(zhǎng)度是指（ ）。 A．串中所含不同字母的個(gè)數(shù)B．串中所含字符的個(gè)數(shù) C．串中所含不同字符的個(gè)數(shù) D．串中所含非空格字符的個(gè)數(shù) 答案：B 解釋：串中字符的數(shù)目稱為串的長(zhǎng)度。 （6）假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[1..100,1..100]，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基

35、地址為10，則LOC[5,5]=（ ）。 A．808 B．818 C．1010 D．1020 答案：B 解釋：以行序?yàn)橹?，則LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。 （7）設(shè)有數(shù)組A[i,j]，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時(shí)，元素A[5,8]的存儲(chǔ)首地址為（ ）。 A．BA+141 B．BA+180 C．BA+222 D．BA+225 答案：B 解釋：以列序

36、為主，則LOC[5,8]=[（8-1）*8+（5-1）]*3+BA=BA+180。 （8）設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。 A．13 B．32 C．33 D．40 答案：C （9）若對(duì)n階對(duì)稱矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B[1..(n(n+1))/2]中，則在B中確定aij（i

37、 C．i*(i+1)/2+j D．j*(j+1)/2+i 答案：B （10）二維數(shù)組A的每個(gè)元素是由10個(gè)字符組成的串，其行下標(biāo)i=0,1,…,8,列下標(biāo)j=1,2,…,10。若A按行先存儲(chǔ)，元素A[8,5]的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素（）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。 A．A[8,5] B．A[3,10] C. A[5,8] D．A[0,9] 答案：B 解釋：設(shè)數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲(chǔ)，元素A[8,5]的起始地址為：M+[（8-0）*10+（5-1）]*1=M+84；若數(shù)組按列先存儲(chǔ)，易計(jì)

38、算出元素A[3,10]的起始地址為：M+[（10-1）*9+（3-0）]*1=M+84。故選B。 （11）設(shè)二維數(shù)組A[1.. m，1.. n]（即m行n列）按行存儲(chǔ)在數(shù)組B[1.. m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為（ ）。 A．(i-1)*n+j B．(i-1)*n+j-1 C．i*(j-1) D．j*m+i-1 答案：A 解釋：特殊值法。取i=j=1，易知A[1,1]的的下標(biāo)為1，四個(gè)選項(xiàng)中僅有A選項(xiàng)能確定的值為1，故選A。 （12）數(shù)組A[0..4,-1..-3,5..7]中含有元素的個(gè)數(shù)（ ）。 A．55 B．45

39、 C．36 D．16 答案：B 解釋：共有5*3*3=45個(gè)元素。 （13）廣義表A=(a,b,(c,d),(e,(f,g)))，則Head(Tail(Head(Tail(Tail(A)))))的值為（ ）。 A．(g) B．(d) C．c D．d 答案：D 解釋：Tail(A)=(b,(c,d),(e,(f,g)))；Tail(Tail(A))=( (c,d),(e,(f,g)))； Head(Tail(Tail(A)))= (c,d)；Tail(Head(Tail(Tail(A))))=(d)；Hea

40、d(Tail(Head(Tail(Tail(A)))))=d。 （14）廣義表((a,b,c,d))的表頭是（），表尾是（ ）。 A．a(chǎn) B．( )C．(a,b,c,d) D．(b,c,d) 答案：C、B 解釋：表頭為非空廣義表的第一個(gè)元素，可以是一個(gè)單原子，也可以是一個(gè)子表，((a,b,c,d))的表頭為一個(gè)子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個(gè)廣義表，((a,b,c,d))的表尾為空表( )。 （15）設(shè)廣義表L=((a,b,c))，則L的長(zhǎng)度和深度分別為（ ）。 A．1和1 B．1和3

41、 C．1和2 D．2和3 答案：C 解釋：廣義表的深度是指廣義表中展開后所含括號(hào)的層數(shù)，廣義表的長(zhǎng)度是指廣義表中所含元素的個(gè)數(shù)。根據(jù)定義易知L的長(zhǎng)度為1，深度為2。 2．應(yīng)用題 (4)請(qǐng)將香蕉banana用工具 H( )—Head( )，T( )—Tail( )從L中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear) 答案：H（H（T（H（T（H（T（L））））））） 3．算法設(shè)計(jì)題 （1）寫一個(gè)算法統(tǒng)計(jì)在輸入字符串中各個(gè)不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A-Z這26個(gè)字母

42、和0-9這10個(gè)數(shù)字）。 [題目分析] 由于字母共26個(gè)，加上數(shù)字符號(hào)10個(gè)共36個(gè)，所以設(shè)一長(zhǎng)36的整型數(shù)組，前10個(gè)分量存放數(shù)字字符出現(xiàn)的次數(shù)，余下存放字母出現(xiàn)的次數(shù)。從字符串中讀出數(shù)字字符時(shí)，字符的ASCII代碼值減去數(shù)字字符‘0’的ASCII代碼值，得出其數(shù)值(0..9)，字母的ASCII代碼值減去字符‘A’的ASCII代碼值加上10，存入其數(shù)組的對(duì)應(yīng)下標(biāo)分量中。遇其它符號(hào)不作處理，直至輸入字符串結(jié)束。 [算法描述] void Count（） //統(tǒng)計(jì)輸入字符串中數(shù)字字符和字母字符的個(gè)數(shù)。 ｛int i，num[36]； char ch； for（i＝0；i<36；i++

43、）num[i]＝０；// 初始化 while（（ch＝getchar（））!=‘#’） //‘#’表示輸入字符串結(jié)束。 if（‘0’<=ch<=‘9’）｛i=ch－48;num[i]++；｝ // 數(shù)字字符 elseif（‘A’<=ch<=‘Z’）｛i=ch-65+10;num[i]++；｝// 字母字符 for（i=0；i<10；i++） // 輸出數(shù)字字符的個(gè)數(shù) cout<<“數(shù)字”<

44、數(shù)=”<>ch; if (ch!= '.') //規(guī)定'.'是字符串輸入結(jié)束標(biāo)志 {InvertStore(A);

45、A[i++] = ch;//字符串逆序存儲(chǔ) } A[i] = '\0'; //字符串結(jié)尾標(biāo)記 } （3）編寫算法，實(shí)現(xiàn)下面函數(shù)的功能。函數(shù)void insert(char*s,char*t,int pos)將字符串t插入到字符串s中，插入位置為pos。假設(shè)分配給字符串s的空間足夠讓字符串t插入。（說明：不得使用任何庫函數(shù)） [題目分析]本題是字符串的插入問題，要求在字符串s的pos位置，插入字符串t。首先應(yīng)查找字符串s的pos位置，將第pos個(gè)字符到字符串s尾的子串向后移動(dòng)字符串t的長(zhǎng)度，然后將字符串t復(fù)制到字符串s的第pos位置后。 對(duì)插入位置pos要驗(yàn)證其合法性，小于1

46、或大于串s的長(zhǎng)度均為非法，因題目假設(shè)給字符串s的空間足夠大，故對(duì)插入不必判溢出。 [算法描述] void insert(char *s,char *t,int pos) //將字符串t插入字符串s的第pos個(gè)位置。 {int i=1,x=0; char *p=s,*q=t; //p，q分別為字符串s和t的工作指針 if(pos<1) {cout<<“pos參數(shù)位置非法”<

47、/0') { cout<=pos ;j--){*(p+x)=*p; p--;}//串s的pos后的子串右移，空出串t的位置。 q--; //指針q回退到串t的最后一個(gè)字符 for(j=1;j<=x;j++) *p-

48、-=*q--; //將t串插入到s的pos位置上 [算法討論] 串s的結(jié)束標(biāo)記('\0')也后移了，而串t的結(jié)尾標(biāo)記不應(yīng)插入到s中。 （ 第5章 樹和二叉樹 1．選擇題 （1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 A．唯一的 Ｂ．有多種 C．有多種，但根結(jié)點(diǎn)都沒有左孩子 Ｄ．有多種，但根結(jié)點(diǎn)都沒有右孩子 答案：A 解釋：因?yàn)槎鏄溆凶蠛⒆?、右孩子之分，故一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。 （2）由3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹？（） A．

49、2 B．3 C．4 D．5 答案：D 解釋：五種情況如下： （3）一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（）。 A．250 B． 500 C．254 D．501 答案：D 解釋：設(shè)度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）個(gè)數(shù)為A，度為1的結(jié)點(diǎn)個(gè)數(shù)為B，度為2的結(jié)點(diǎn)個(gè)數(shù)為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹的性質(zhì)可得B=0或1，又因?yàn)镃為整數(shù)，所以B=0，C=500，A=501，即有501個(gè)葉子結(jié)點(diǎn)。 （4）一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）。 A．11

50、B．10 C．11至1025之間D．10至1024之間 答案：C 解釋：若每層僅有一個(gè)結(jié)點(diǎn)，則樹高h(yuǎn)為1025；且其最小樹高為??log21025??+?1=11，即h在11至1025之間。 （5）深度為h的滿m叉樹的第k層有（）個(gè)結(jié)點(diǎn)。(1=

51、用二叉鏈表存儲(chǔ)樹時(shí)，右指針指向兄弟結(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)沒有兄弟結(jié)點(diǎn)，故根節(jié)點(diǎn)的右指針指向空。 （7）對(duì)二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用（）遍歷實(shí)現(xiàn)編號(hào)。 A．先序 B. 中序 C. 后序 D. 從根開始按層次遍歷 答案：C 解釋：根據(jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點(diǎn)的順序遍歷二叉樹，即后序遍歷二叉樹。 （8）若二叉樹采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹的位置，利用（）遍歷方法最合適。 A．前序B．中序C．后序 D．按層

52、次 答案：C 解釋：后續(xù)遍歷和層次遍歷均可實(shí)現(xiàn)左右子樹的交換，不過層次遍歷的實(shí)現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。 （9）在下列存儲(chǔ)形式中，（）不是樹的存儲(chǔ)形式？ A．雙親表示法 B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲(chǔ)表示法 答案：D 解釋：樹的存儲(chǔ)結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進(jìn)行存儲(chǔ)。 （10）一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（）。 A．所有的結(jié)點(diǎn)均無左孩子 B．所有的結(jié)點(diǎn)均無右孩子 C．只有一個(gè)葉子結(jié)點(diǎn) D

53、．是任意一棵二叉樹 答案：C 解釋：因?yàn)橄刃虮闅v結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當(dāng)沒有左子樹時(shí)，就是“中右”和“右中”；當(dāng)沒有右子樹時(shí)，就是“中左”和“左中”。則所有的結(jié)點(diǎn)均無左孩子或所有的結(jié)點(diǎn)均無右孩子均可，所以A、B不能選，又所有的結(jié)點(diǎn)均無左孩子與所有的結(jié)點(diǎn)均無右孩子時(shí)，均只有一個(gè)葉子結(jié)點(diǎn)，故選C。 （11）設(shè)哈夫曼樹中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹中有（ ）個(gè)葉子結(jié)點(diǎn)。 A．99B．100 C．101D．102 答案：B 解釋：在哈夫曼樹中沒有度為1的結(jié)點(diǎn)，只有度為0（葉子結(jié)點(diǎn)）和度為2的結(jié)點(diǎn)。設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，由二叉樹的性質(zhì)

54、n0=n2+1，則總結(jié)點(diǎn)數(shù)n= n0+n2=2*n0-1，得到n0=100。 （12）若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（）。 A．X的雙親B．X的右子樹中最左的結(jié)點(diǎn) C．X的左子樹中最右結(jié)點(diǎn) D．X的左子樹中最右葉結(jié)點(diǎn) 答案：C （13）引入二叉線索樹的目的是（）。 A．加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B．為了能在二叉樹中方便的進(jìn)行插入與刪除 C．為了能方便的找到雙親 D．使二叉樹的遍歷結(jié)果唯一 答案：A （14）設(shè)F是一個(gè)森林，B是由F變換得的二叉樹。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ ）個(gè)。 A．n?1 B．n

55、 C．n + 1 D．n + 2 答案：C （15）n（n≥2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹，關(guān)于該樹的敘述中，錯(cuò)誤的是（?）。 A．該樹一定是一棵完全二叉樹 B．樹中一定沒有度為1的結(jié)點(diǎn) C．樹中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn) D．樹中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值 答案：A 解釋：哈夫曼樹的構(gòu)造過程是每次都選取權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，所以樹中一定沒有度為1的結(jié)點(diǎn)、兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)、任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。 2．應(yīng)用題 （1）試找出滿足下列條件的二叉樹 ① 先序序列與后序

56、序列相同②中序序列與后序序列相同 ③ 先序序列與中序序列相同④中序序列與層次遍歷序列相同 答案：先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根＂，根據(jù)以上原則有 ①或?yàn)榭諛?，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹 ②?或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹的二叉樹． ③?或?yàn)榭諛洌驗(yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹． ④或?yàn)榭諛?，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹的二叉樹 （2）設(shè)一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①畫出這棵二叉樹。 ②畫出這棵二叉樹的后序線索樹。

57、 ③將這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹（或森林）。 A B F D ③ C E H G ? ? ? ? ? ? ? ? ①② 3．算法設(shè)計(jì)題 以二叉鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，編寫以下算法： （1）統(tǒng)計(jì)二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)。 [題目分析]如果二叉樹為空，返回0，如果二叉樹不為空且左右子樹為空，返回1，如果二叉樹不為空，且左右子樹不同時(shí)為空，返回左子樹中葉子節(jié)點(diǎn)個(gè)數(shù)加上右子樹中葉子節(jié)點(diǎn)個(gè)數(shù)。 [算法描述] int LeafNodeCount(BiTree T) { if(T==NULL) return 0; //

58、如果是空樹，則葉子結(jié)點(diǎn)個(gè)數(shù)為0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; //判斷結(jié)點(diǎn)是否是葉子結(jié)點(diǎn)（左孩子右孩子都為空），若是則返回1 else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); } （2）判別兩棵樹是否相等。 [題目分析]先判斷當(dāng)前節(jié)點(diǎn)是否相等(需要處理為空、是否都為空、是否相等)，如果當(dāng)前節(jié)點(diǎn)不相等，直接返回兩棵樹不相等;如果當(dāng)前節(jié)點(diǎn)相等，那么就遞歸的判斷他們的左右孩子是否相等。 [算法描述] int pareTre

59、e(TreeNode* tree1, TreeNode* tree2) //用分治的方法做，比較當(dāng)前根，然后比較左子樹和右子樹 {bool tree1IsNull = (tree1==NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) { return 1; } if(tree1IsNull && tree2IsNull) {//如果兩個(gè)都是NULL，則相等 return 0; }//如果根節(jié)點(diǎn)不相等，直接返回不相等，否則的話，看看他們孩子相等不相等 if(tree1->c !=

60、 tree2->c) { 　return 1; } return (pareTree(tree1->left,tree2->left)&pareTree(tree1->right,tree2->right)) (pareTree(tree1->left,tree2->right)&pareTree(tree1->right,tree2->left)); }//算法結(jié)束 （3）交換二叉樹每個(gè)結(jié)點(diǎn)的左孩子和右孩子。 [題目分析]如果某結(jié)點(diǎn)左右子樹為空，返回，否則交換該結(jié)點(diǎn)左右孩子，然后遞歸交換左右子樹。 [算法描述] void ChangeLR(BiTree &T) {

61、 BiTree temp; if(T->lchild==NULL&&T->rchild==NULL) return; else { temp = T->lchild; T->lchild = T->rchild; T->rchild = temp; }//交換左右孩子 ChangeLR(T->lchild); //遞歸交換左子樹 ChangeLR(T->rchild); //遞歸交換右子樹 } （5）計(jì)算二叉樹最大的寬度（二叉樹的最大寬度是指二叉樹所有層中結(jié)點(diǎn)個(gè)數(shù)的最大值）。 [題目分析] 求二叉樹高度的算法見上題。求最大寬度可采

62、用層次遍歷的方法，記下各層結(jié)點(diǎn)數(shù)，每層遍歷完畢，若結(jié)點(diǎn)數(shù)大于原先最大寬度，則修改最大寬度。 [算法描述] int Width(BiTree bt)//求二叉樹bt的最大寬度 {if (bt==null) return (0); //空二叉樹寬度為0 else {BiTree Q[];//Q是隊(duì)列，元素為二叉樹結(jié)點(diǎn)指針，容量足夠大 front=1;rear=1;last=1; //front隊(duì)頭指針,rear隊(duì)尾指針,last同層最右結(jié)點(diǎn)在隊(duì)列中的位置 temp=0; maxw=0; //temp記局部寬度, maxw記最大寬度 Q[rear]=bt;

63、 //根結(jié)點(diǎn)入隊(duì)列 while(front<=last) {p=Q[front++]; temp++; //同層元素?cái)?shù)加1 if (p->lchild!=null) Q[++rear]=p->lchild; //左子女入隊(duì) if (p->rchild!=null) Q[++rear]=p->rchild; //右子女入隊(duì) if (front>last) //一層結(jié)束， {last=rear; if(temp>maxw) maxw=temp; //last指向下層最右元素, 更新當(dāng)前最大寬度 temp=0; }//if

64、 }//while return (maxw); }//結(jié)束width 若某個(gè)結(jié)點(diǎn)左子樹空右子樹非空或者右子樹空左子樹非空，則該結(jié)點(diǎn)為度為1的結(jié)點(diǎn) 第7章 查找 1．選擇題 （1）對(duì)n個(gè)元素的表做順序查找時(shí)，若查找每個(gè)元素的概率相同，則平均查找長(zhǎng)度為（ ）。 A．(n-1)/2 B． n/2 C．(n+1)/2 D．n 答案：C 解釋：總查找次數(shù)N=1+2+3+…+n=n(n+1)/2，則平均查找長(zhǎng)度為N/n=(n+1)/2。 （2）適用于折半查找的表的存儲(chǔ)方式及元素排列要求為（ ）。 A．方式存儲(chǔ)

65、，元素?zé)o序B．方式存儲(chǔ)，元素有序 C．順序方式存儲(chǔ)，元素?zé)o序D．順序方式存儲(chǔ)，元素有序 答案：D 解釋：折半查找要求線性表必須采用順序存儲(chǔ)結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。 （3）如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，最好采用( )查找法。 A．順序查找 B．折半查找 C．分塊查找 D．哈希查找 答案：C 解釋：分塊查找的優(yōu)點(diǎn)是：在表中插入和刪除數(shù)據(jù)元素時(shí)，只要找到該元素對(duì)應(yīng)的塊，就可以在該塊內(nèi)進(jìn)行插入和刪除運(yùn)算。由于塊內(nèi)是無序的，故插入和刪除比較容易，無需進(jìn)行大量移動(dòng)。如果線性表既要快速查找又經(jīng)常動(dòng)態(tài)變化，則可采用分塊查

66、找。 （4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（ ）比較大小，查找結(jié)果是失敗。 A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 答案：A 解釋：表中共10個(gè)元素，第一次取?(1+10)/2?=5，與第五個(gè)元素20比較，58大于20，再取?(6+10)/2?=8，與第八個(gè)元素70比較，依次類推再與30、50比較，最終查找失敗。 （5）對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要比較（ ）次關(guān)鍵字。 A．3 B．4 C．5 D．6 答案：B 解釋：22個(gè)記錄的有序表，其折半查找的判定樹深度為??log222??+?1=5，且該判定樹不是滿二叉樹，即查找失敗時(shí)至多比較5次，至少比較4次。 （6）折半搜索與二叉排序樹的時(shí)間性能（ ）。 A．相同 B．完全不同