《數(shù)據(jù)結構[C語言版]第2版習題答案_嚴蔚敏[簡化版]》由會員分享，可在線閱讀，更多相關《數(shù)據(jù)結構[C語言版]第2版習題答案_嚴蔚敏[簡化版]（27頁珍藏版）》請在裝配圖網上搜索。

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）存儲的存儲結

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

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

4、 D．n-1 答案：A 解釋：當?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．每個元素都有一個直接前驅和一個直接后繼 B．線性表中至少有一個元素 C．表中諸元素的排列必須是由小到大或由大到小 D．除第一個和最后一個元素外，其余每

5、個元素都有一個且僅有一個直接前驅和直接后繼。 答案：D (12) 以下說法錯誤的是（ ）。 A．求表長、定位這兩種運算在采用順序存儲結構時實現(xiàn)的效率不比采用鏈式存儲結構時實現(xiàn)的效率低 B．順序存儲的線性表可以隨機存取 C．由于順序存儲要求連續(xù)的存儲區(qū)域，所以在存儲管理上不夠靈活 D．線性表的鏈式存儲結構優(yōu)于順序存儲結構 答案：D 解釋：鏈式存儲結構和順序存儲結構各有優(yōu)缺點，有不同的適用場合。 (13) 在單鏈表中，要將s所指結點插入到p所指結點之后，其語句應為（ ）。 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) 在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針（ ）。 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指針所指的結點后插入q所指向的新結點，其修改指針的操作是（ ）。 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．算法設計題 （1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復的數(shù)據(jù)。 [算法描述] void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向 pa=La->next; pb=Lb->next; //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點 Lc=pc=La; //用La的頭結點作為Lc的頭結點 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的頭結點 } （6）設計一個算法，通過一趟遍歷在單鏈表中確定值最大的結點。 [算法描述] ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一個結點中數(shù)據(jù)具有最大值 p=L->next->next; while(p != NULL ){//如果下一個結點存在 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)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數(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）鏈式棧結點為：(data,link)，top指向棧頂.若想摘除棧頂結點，并將刪除結點的值保存到x中,則應執(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將結點的值保存到x中，top=top->link棧頂指針指向棧頂下一結點，即摘除棧頂結點。 （5）設有一個遞歸算法如下 ?????? int fact(int n) {? //n大于等于0 ??????????? if(n<=0) return 1; ??????????? else return n*fact(n-1);?????? } 則計算fact(n)需要調用該函數(shù)的次數(shù)為（）。? A．?n+1?????B．?n-1?????C． n?????D． n+2 答案：A 解釋：特殊值法。設n=0，易知僅調用一次fact(n)函數(shù)，故選A。 （6）棧在

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

16、依次進入棧S，一個元素出棧后即進入Q，若6個元素出隊的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應該是（?。?。 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設為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）設計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（?。?shù)據(jù)結構最佳。 A．線性表的順序存儲結構B．隊列 C. 線性表的鏈式存儲結構D. 棧 答案：D 解釋：利用棧的后進先出原則。 （11）用方式存儲的隊列

18、，在進行刪除運算時（　）。 A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改 答案：D 解釋：一般情況下只修改頭指針，但是，當刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。 （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個元素，故在求模運算時應除以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．算法設計題 （1）將編號為0和1的兩個棧存放于一個數(shù)組空間V[m]中，棧底分別處于數(shù)組的兩端。當?shù)?號棧的棧頂指針top[0]等于-1時該棧為空，當?shù)?號棧的棧頂指針top[1]等于m時該棧為空。兩個棧均從兩端向中間增長。試編寫雙棧初始化，判斷?？?、棧滿、進棧和出棧等算法

21、的函數(shù)。雙棧數(shù)據(jù)結構的定義如下： Typedef struct {int top[2],bot[2]; //棧頂和棧底指針 SElemType *V; //棧數(shù)組 int m; //棧最大可容納元素個數(shù) }DblStack [題目分析] 兩棧共享向量空間，將兩棧棧底設在向量兩端，初始時，左棧頂指針為-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????? }∥算法結束 (4)?判斷?？? int?Empty(); {return?(S.top[0]==-1 && S.top[1]==m); } [算法討論]? 請注意算法中兩棧入棧和退棧時的棧頂指針的計算。左棧是通常意義下的棧，而右棧入棧操作時，其棧頂指針左移（減1），退棧時，棧頂指針右移（加1）。 （2）回文是指正讀反讀均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。試寫一個算法判定給定的字符向量是否為回文。(提示：將一半字符入棧)? [題目分析] 將字符串前一半入棧，然

25、后，棧中元素和字符串后一半進行比較。即將第一個出棧元素和后一半串中第一個字符比較，若相等，則再出棧一個元素與后一個字符比較，……，直至?？眨Y論為字符序列是回文。在出棧元素與串中字符比較不等時，結論字符序列不是回文。 [算法描述] #define StackSize 100 //假定預分配的棧空間最多為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ù)的序列：a1, a2, a3，…，an，試編寫算法實現(xiàn)：用棧結構存儲輸入的整數(shù)，當ai≠-1時，將ai進棧；當ai=-1時，輸出棧頂整數(shù)并出棧。算法應對異常情況（入棧滿等）給出相應的信息。 [算法描述] #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、指針) ，試編寫相應的置空隊、判隊空 、入隊和出隊等算法。 [算法描述] //先定義鏈隊結構: typedef struct queuenode {Datatype data; struct queuenode *next; }QueueNode; //以上是結點類型的定義 typedef struct {queuenode *rear; }LinkQueue; //只設一個指向隊尾元素的指針 (1) 置空隊 void InitQueue( LinkQueue *Q) { //置空隊：就是使頭結點成為隊尾元素 　QueueNode *s; Q->rear = Q

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

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

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

33、可以順序存儲 B．數(shù)據(jù)元素是一個字符 C．可以鏈式存儲 D．數(shù)據(jù)元素可以是多個字符若 答案：B （2）串下面關于串的的敘述中，（ ）是不正確的？ A．串是字符的有限序列 B．空串是由空格構成的串 C．模式匹配是串的一種重要運算 D．串既可以采用順序存儲，也可以采用鏈式存儲 答案：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ù)組A=array[1..100,1..100]，設每個數(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ù)組A[i,j]，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內存首地址BA開始順序存放，當用以列為主存放時，元素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）設有一個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個字符組成的串，其行下標i=0,1,…,8,列下標j=1,2,…,10。若A按行先存儲，元素A[8,5]的起始地址與當A按列先存儲時的元素（）的起始地址相同。設每個字符占一個字節(jié)。 A．A[8,5] B．A[3,10] C. A[5,8] D．A[0,9] 答案：B 解釋：設數(shù)組從內存首地址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ù)組A[1.. m，1.. n]（即m行n列）按行存儲在數(shù)組B[1.. m*n]中，則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標為（ ）。 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]的的下標為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 B．( )C．(a,b,c,d) D．(b,c,d) 答案：C、B 解釋：表頭為非空廣義表的第一個元素，可以是一個單原子，也可以是一個子表，((a,b,c,d))的表頭為一個子表(a,b,c,d)；表尾為除去表頭之外，由其余元素構成的表，表為一定是個廣義表，((a,b,c,d))的表尾為空表( )。 （15）設廣義表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．應用題 (4)請將香蕉banana用工具 H( )—Head( )，T( )—Tail( )從L中取出。 L=(apple,(orange,(strawberry,(banana)),peach),pear) 答案：H（H（T（H（T（H（T（L））））））） 3．算法設計題 （1）寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結果存入文件（字符串中的合法字符為A-Z這26個字母

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

43、）num[i]＝０；// 初始化 while（（ch＝getchar（））!=‘#’） //‘#’表示輸入字符串結束。 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ī)定'.'是字符串輸入結束標志 {InvertStore(A);

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

46、或大于串s的長度均為非法，因題目假設給字符串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的結束標記('\0')也后移了，而串t的結尾標記不應插入到s中。 （ 第5章 樹和二叉樹 1．選擇題 （1）把一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 A．唯一的 Ｂ．有多種 C．有多種，但根結點都沒有左孩子 Ｄ．有多種，但根結點都沒有右孩子 答案：A 解釋：因為二叉樹有左孩子、右孩子之分，故一棵樹轉換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。 （2）由3個結點可以構造出多少種不同的二叉樹？（） A．

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

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

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

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

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

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

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

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

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

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

59、e(TreeNode* tree1, TreeNode* tree2) //用分治的方法做，比較當前根，然后比較左子樹和右子樹 {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)); }//算法結束 （3）交換二叉樹每個結點的左孩子和右孩子。 [題目分析]如果某結點左右子樹為空，返回，否則交換該結點左右孩子，然后遞歸交換左右子樹。 [算法描述] 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）計算二叉樹最大的寬度（二叉樹的最大寬度是指二叉樹所有層中結點個數(shù)的最大值）。 [題目分析] 求二叉樹高度的算法見上題。求最大寬度可采

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

63、 //根結點入隊列 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) //一層結束， {last=rear; if(temp>maxw) maxw=temp; //last指向下層最右元素, 更新當前最大寬度 temp=0; }//if

64、 }//while return (maxw); }//結束width 若某個結點左子樹空右子樹非空或者右子樹空左子樹非空，則該結點為度為1的結點 第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、，元素無序B．方式存儲，元素有序 C．順序方式存儲，元素無序D．順序方式存儲，元素有序 答案：D 解釋：折半查找要求線性表必須采用順序存儲結構，而且表中元素按關鍵字有序排列。 （3）如果要求一個線性表既能較快的查找，又能適應動態(tài)變化的要求，最好采用( )查找法。 A．順序查找 B．折半查找 C．分塊查找 D．哈希查找 答案：C 解釋：分塊查找的優(yōu)點是：在表中插入和刪除數(shù)據(jù)元素時，只要找到該元素對應的塊，就可以在該塊內進行插入和刪除運算。由于塊內是無序的，故插入和刪除比較容易，無需進行大量移動。如果線性表既要快速查找又經常動態(tài)變化，則可采用分塊查

66、找。 （4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，則它將依次與表中（ ）比較大小，查找結果是失敗。 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個記錄的有序表作折半查找，當查找失敗時，至少需要比較（ ）次關鍵字。 A．3 B．4 C．5 D．6 答案：B 解釋：22個記錄的有序表，其折半查找的判定樹深度為??log222??+?1=5，且該判定樹不是滿二叉樹，即查找失敗時至多比較5次，至少比較4次。 （6）折半搜索與二叉排序樹的時間性能（ ）。 A．相同 B．完全不同