數(shù)據(jù)結(jié)構(gòu)[C語言版]第2版習(xí)題答案_嚴(yán)蔚敏[簡化版]

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

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

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

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

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

5、個元素都有一個且僅有一個直接前驅(qū)和直接后繼。 答案：D (12) 以下說法錯誤的是（ ）。 A．求表長、定位這兩種運算在采用順序存儲結(jié)構(gòu)時實現(xiàn)的效率不比采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時實現(xiàn)的效率低 B．順序存儲的線性表可以隨機存取 C．由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活 D．線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲結(jié)構(gòu) 答案：D 解釋：鏈?zhǔn)酱鎯Y(jié)構(gòu)和順序存儲結(jié)構(gòu)各有優(yōu)缺點，有不同的適用場合。 (13) 在單鏈表中，要將s所指結(jié)點插入到p所指結(jié)點之后，其語句應(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) 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（ ）。 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é)點后插入q所指向的新結(jié)點，其修改指針的操作是（ ）。 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è)計題 （1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復(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)鏈表的第一個結(jié)點 Lc=pc=La; //用La的頭結(jié)點作為Lc的頭結(jié)點 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 //相等時取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é)點 } （6）設(shè)計一個算法，通過一趟遍歷在單鏈表中確定值最大的結(jié)點。 [算法描述] ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一個結(jié)點中數(shù)據(jù)具有最大值 p=L->next->next; while(p != NULL ){//如果下一個結(jié)點存在 if(p->data > pmax->da

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

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

13、D．（n+r-f)%n 答案：D 解釋：對于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環(huán)隊列，差值可能為負數(shù)，所以需要將差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+r-f)%n。 （4）鏈?zhǔn)綏＝Y(jié)點為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到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é)點的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點，即摘除棧頂結(jié)點。 （5）設(shè)有一個遞歸算法如下 ?????? int fact(int n) {? //n大于等于0 ??????????? if(n<=0) return 1; ??????????? else return n*fact(n-1);?????? } 則計算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 解釋：遞歸調(diào)用、函數(shù)調(diào)用、表達式求值均用到了棧的后進先出性質(zhì)。 （7）為解決計算機主機與打印機間速度不匹配問題，通常設(shè)一個打印數(shù)據(jù)緩沖區(qū)。主機將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（）。 A．隊列 B．棧 C． 線性表 D．有序表 答案：A 解釋：解決緩沖區(qū)問題應(yīng)利用一種先進先出的線性表，而隊列正是一種先進先出的線性表。 （8）設(shè)棧S和隊列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6

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

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ù)組向量的高端地址進棧，又因為元素存儲在向量空間V[1..n]中，所以進棧時top指針先下移變?yōu)閚，之后將元素x存儲在V[n]。 （10）設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（?。?shù)據(jù)結(jié)構(gòu)最佳。 A．線性表的順序存儲結(jié)構(gòu)B．隊列 C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)D. 棧 答案：D 解釋：利用棧的后進先出原則。 （11）用方式存儲的隊列

18、，在進行刪除運算時（　）。 A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改 答案：D 解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。 （12）循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（?。?。 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個元素，故在求模運算時應(yīng)除以m+1。 （13）最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊空的條件是（?。?。 A. (rear+1)%n==front B. rear==front C．rear+1==front D. (rear-l)%n==front 答案：B 解釋：最大容量為n的循環(huán)隊列，隊滿條件是(rear+1)%n==front，隊空條件是rear==front。 （14）棧和隊列的共同點是（?。?。 A. 都是先進先出 B. 都是先

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

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

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

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

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

25、后，棧中元素和字符串后一半進行比較。即將第一個出棧元素和后一半串中第一個字符比較，若相等，則再出棧一個元素與后一個字符比較，……，直至?？眨Y(jié)論為字符序列是回文。在出棧元素與串中字符比較不等時，結(jié)論字符序列不是回文。 [算法描述] #define StackSize 100 //假定預(yù)分配的?？臻g最多為100個元素 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); //求向量長度 for ( i=0; i

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

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

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

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

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

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

33、可以順序存儲 B．?dāng)?shù)據(jù)元素是一個字符 C．可以鏈?zhǔn)酱鎯? D．?dāng)?shù)據(jù)元素可以是多個字符若 答案：B （2）串下面關(guān)于串的的敘述中，（ ）是不正確的？ A．串是字符的有限序列 B．空串是由空格構(gòu)成的串 C．模式匹配是串的一種重要運算 D．串既可以采用順序存儲，也可以采用鏈?zhǔn)酱鎯? 答案：B 解釋：空格常常是串的字符集合中的一個元素，有一個或多個空格組成的串成為空格串，零個字符的串成為空串，其長度為零。 （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）串的長度是指（ ）。 A．串中所含不同字母的個數(shù)B．串中所含字符的個數(shù) C．串中所含不同字符的個數(shù) D．串中所含非空格字符的個數(shù) 答案：B 解釋：串中字符的數(shù)目稱為串的長度。 （6）假設(shè)以行序為主序存儲二維數(shù)組A=array[1..100,1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基

35、地址為10，則LOC[5,5]=（ ）。 A．808 B．818 C．1010 D．1020 答案：B 解釋：以行序為主，則LOC[5,5]=[（5-1）*100+（5-1）]*2+10=818。 （7）設(shè)有數(shù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A[5,8]的存儲首地址為（ ）。 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è)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ ）。 A．13 B．32 C．33 D．40 答案：C （9）若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(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的每個元素是由10個字符組成的串，其行下標(biāo)i=0,1,…,8,列下標(biāo)j=1,2,…,10。若A按行先存儲，元素A[8,5]的起始地址與當(dāng)A按列先存儲時的元素（）的起始地址相同。設(shè)每個字符占一個字節(jié)。 A．A[8,5] B．A[3,10] C. A[5,8] D．A[0,9] 答案：B 解釋：設(shè)數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲，元素A[8,5]的起始地址為：M+[（8-0）*10+（5-1）]*1=M+84；若數(shù)組按列先存儲，易計

38、算出元素A[3,10]的起始地址為：M+[（10-1）*9+（3-0）]*1=M+84。故選B。 （11）設(shè)二維數(shù)組A[1.. m，1.. n]（即m行n列）按行存儲在數(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，四個選項中僅有A選項能確定的值為1，故選A。 （12）數(shù)組A[0..4,-1..-3,5..7]中含有元素的個數(shù)（ ）。 A．55 B．45

39、 C．36 D．16 答案：B 解釋：共有5*3*3=45個元素。 （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 解釋：表頭為非空廣義表的第一個元素，可以是一個單原子，也可以是一個子表，((a,b,c,d))的表頭為一個子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個廣義表，((a,b,c,d))的表尾為空表( )。 （15）設(shè)廣義表L=((a,b,c))，則L的長度和深度分別為（ ）。 A．1和1 B．1和3

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

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

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

45、A[i++] = ch;//字符串逆序存儲 } A[i] = '\0'; //字符串結(jié)尾標(biāo)記 } （3）編寫算法，實現(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個字符到字符串s尾的子串向后移動字符串t的長度，然后將字符串t復(fù)制到字符串s的第pos位置后。 對插入位置pos要驗證其合法性，小于1

46、或大于串s的長度均為非法，因題目假設(shè)給字符串s的空間足夠大，故對插入不必判溢出。 [算法描述] void insert(char *s,char *t,int pos) //將字符串t插入字符串s的第pos個位置。 {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的最后一個字符 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é)點都沒有左孩子 Ｄ．有多種，但根結(jié)點都沒有右孩子 答案：A 解釋：因為二叉樹有左孩子、右孩子之分，故一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。 （2）由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（） A．

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

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

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

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

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

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

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

56、序列相同②中序序列與后序序列相同 ③ 先序序列與中序序列相同④中序序列與層次遍歷序列相同 答案：先序遍歷二叉樹的順序是“根—左子樹—右子樹”，中序遍歷“左子樹—根—右子樹”，后序遍歷順序是：“左子樹—右子樹―根＂，根據(jù)以上原則有 ①或為空樹，或為只有根結(jié)點的二叉樹 ②?或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹． ③?或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹． ④或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹 （2）設(shè)一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C ①畫出這棵二叉樹。 ②畫出這棵二叉樹的后序線索樹。

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

58、如果是空樹，則葉子結(jié)點個數(shù)為0 else if(T->lchild==NULL&&T->rchild==NULL) return 1; //判斷結(jié)點是否是葉子結(jié)點（左孩子右孩子都為空），若是則返回1 else return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); } （2）判別兩棵樹是否相等。 [題目分析]先判斷當(dāng)前節(jié)點是否相等(需要處理為空、是否都為空、是否相等)，如果當(dāng)前節(jié)點不相等，直接返回兩棵樹不相等;如果當(dāng)前節(jié)點相等，那么就遞歸的判斷他們的左右孩子是否相等。 [算法描述] 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) {//如果兩個都是NULL，則相等 return 0; }//如果根節(jié)點不相等，直接返回不相等，否則的話，看看他們孩子相等不相等 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）交換二叉樹每個結(jié)點的左孩子和右孩子。 [題目分析]如果某結(jié)點左右子樹為空，返回，否則交換該結(jié)點左右孩子，然后遞歸交換左右子樹。 [算法描述] 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）計算二叉樹最大的寬度（二叉樹的最大寬度是指二叉樹所有層中結(jié)點個數(shù)的最大值）。 [題目分析] 求二叉樹高度的算法見上題。求最大寬度可采

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

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

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

65、，元素?zé)o序B．方式存儲，元素有序 C．順序方式存儲，元素?zé)o序D．順序方式存儲，元素有序 答案：D 解釋：折半查找要求線性表必須采用順序存儲結(jié)構(gòu)，而且表中元素按關(guān)鍵字有序排列。 （3）如果要求一個線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，最好采用( )查找法。 A．順序查找 B．折半查找 C．分塊查找 D．哈希查找 答案：C 解釋：分塊查找的優(yōu)點是：在表中插入和刪除數(shù)據(jù)元素時，只要找到該元素對應(yīng)的塊，就可以在該塊內(nèi)進行插入和刪除運算。由于塊內(nèi)是無序的，故插入和刪除比較容易，無需進行大量移動。如果線性表既要快速查找又經(jī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個元素，第一次取?(1+10)/2?=5，與第五個元素20比較，58大于20，再取?(6+10)/2?=8，與第八個元素70比較，依次類推再與30、50比較，最終查找失敗。 （5）對22個記錄的有序表作折半查找，當(dāng)查找失敗時，至少需要比較（ ）次關(guān)鍵字。 A．3 B．4 C．5 D．6 答案：B 解釋：22個記錄的有序表，其折半查找的判定樹深度為??log222??+?1=5，且該判定樹不是滿二叉樹，即查找失敗時至多比較5次，至少比較4次。 （6）折半搜索與二叉排序樹的時間性能（ ）。 A．相同 B．完全不同