數據結構[C語言版]第2版習題答案_嚴蔚敏

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

1、 數據結構（C語言版）（第2版） 課后習題答案 李冬梅 2015.3 目 錄 第1章緒論1 第2章線性表5 第3章棧和隊列13 第4章串、數組和廣義表26 第5章樹和二叉樹33 第6章圖43 第7章查找54 第8章排序65 74 / 76 第1章 緒論 1．簡述下列概念：數據、數據元素、數據項、數據對象、數據結構、邏輯結構、存儲結構、抽象數據類型。 答案： 數據：是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數學計算中用到的整數和實數，文本編輯所用到的字符串，多媒體程序處理

2、的圖形、圖像、聲音、動畫等通過特殊編碼定義后的數據。 數據元素：是數據的基本單位，在計算機中通常作為一個整體進行考慮和處理。在有些情況下，數據元素也稱為元素、結點、記錄等。數據元素用于完整地描述一個對象，如一個學生記錄，樹中棋盤的一個格局（狀態(tài)）、圖中的一個頂點等。 數據項：是組成數據元素的、有獨立含義的、不可分割的最小單位。例如，學生基本信息表中的學號、XX、性別等都是數據項。 數據對象：是性質相同的數據元素的集合，是數據的一個子集。例如：整數數據對象是集合N={0，±1，±2，…}，字母字符數據對象是集合C={‘A’，‘B’，…，‘Z’， ‘a’，‘b’，…，‘z’}，學生基本信息表

3、也可是一個數據對象。 數據結構：是相互之間存在一種或多種特定關系的數據元素的集合。換句話說，數據結構是帶“結構”的數據元素的集合，“結構”就是指數據元素之間存在的關系。 邏輯結構：從邏輯關系上描述數據，它與數據的存儲無關，是獨立于計算機的。因此，數據的邏輯結構可以看作是從具體問題抽象出來的數學模型。 存儲結構：數據對象在計算機中的存儲表示，也稱為物理結構。 抽象數據類型：由用戶定義的，表示應用問題的數學模型，以及定義在這個模型上的一組操作的總稱。具體包括三部分：數據對象、數據對象上關系的集合和對數據對象的基本操作的集合。 2．試舉一個數據結構的例子，敘述其邏輯結構和存儲結構兩方面的含

4、義和相互關系。 答案： 例如有一X學生基本信息表，包括學生的學號、XX、性別、籍貫、專業(yè)等。每個學生基本信息記錄對應一個數據元素，學生記錄按順序號排列，形成了學生基本信息記錄的線性序列。對于整個表來說，只有一個開始結點(它的前面無記錄)和一個終端結點(它的后面無記錄)，其他的結點則各有一個也只有一個直接前趨和直接后繼。學生記錄之間的這種關系就確定了學生表的邏輯結構，即線性結構。 這些學生記錄在計算機中的存儲表示就是存儲結構。如果用連續(xù)的存儲單元(如用數組表示)來存放這些記錄，則稱為順序存儲結構；如果存儲單元不連續(xù)，而是隨機存放各個記錄，然后用指針進行，則稱為鏈式存儲結構。 即相同的邏輯

5、結構，可以對應不同的存儲結構。 3．簡述邏輯結構的四種基本關系并畫出它們的關系圖。 答案： （1）集合結構 數據元素之間除了“屬于同一集合”的關系外，別無其他關系。例如，確定一名學生是否為班級成員，只需將班級看做一個集合結構。 （2）線性結構 數據元素之間存在一對一的關系。例如，將學生信息數據按照其入學報到的時間先后順序進行排列，將組成一個線性結構。 （3）樹結構 數據元素之間存在一對多的關系。例如，在班級的管理體系中，班長管理多個組長，每位組長管理多名組員，從而構成樹形結構。 （4）圖結構或網狀結構 數據元素之間存在多對多的關系。例如，多位同學之間的朋友關系，任何兩位同學

6、都可以是朋友，從而構成圖形結構或網狀結構。 其中樹結構和圖結構都屬于非線性結構。 四類基本邏輯結構關系圖 4．存儲結構由哪兩種基本的存儲方法實現？ 答案： （1）順序存儲結構 順序存儲結構是借助元素在存儲器中的相對位置來表示數據元素之間的邏輯關系，通常借助程序設計語言的數組類型來描述。 （2）鏈式存儲結構 順序存儲結構要求所有的元素依次存放在一片連續(xù)的存儲空間中，而鏈式存儲結構，無需占用一整塊存儲空間。但為了表示結點之間的關系，需要給每個結點附加指針字段，用于存放后繼元素的存儲地址。所以鏈式存儲結構通常借助于程序設計語言的指針類型來描述。 5．選擇題 （1）

7、在數據結構中，從邏輯上可以把數據結構分成（ ）。 A．動態(tài)結構和靜態(tài)結構 B．緊湊結構和非緊湊結構 C．線性結構和非線性結構 D．內部結構和外部結構 答案：C （2）與數據元素本身的形式、內容、相對位置、個數無關的是數據的（ ）。 A．存儲結構 B．存儲實現 C．邏輯結構 D．運算實現 答案：C （3）通常要求同一邏輯結構中的所有數據元素具有相同的特性，這意味著（ ）。 A．數據具有同一特點 B．不僅數據元素所包含的數據項的個數要相同，而且對應數據項的類型要一致 C．每個數據元素都一樣

8、 D．數據元素所包含的數據項的個數要相等 答案：B （4）以下說法正確的是（ ）。 A．數據元素是數據的最小單位 B．數據項是數據的基本單位 C．數據結構是帶有結構的各數據項的集合 D．一些表面上很不相同的數據可以有相同的邏輯結構 答案：D 解釋：數據元素是數據的基本單位，數據項是數據的最小單位，數據結構是帶有結構的各數據元素的集合。 （5）算法的時間復雜度取決于（ ）。 A．問題的規(guī)模 B．待處理數據的初態(tài) C．計算機的配置 D．A和B 答案：D 解釋：算法的時間復雜度不僅與問題的規(guī)模有關，還與問題的其他因素有關。如某些排序的算法，其執(zhí)行時間與待排

9、序記錄的初始狀態(tài)有關。為此，有時會對算法有最好、最壞以及平均時間復雜度的評價。 （6）以下數據結構中，（）是非線性數據結構 A．樹 B．字符串 C．隊列 D．棧 答案：A 6．試分析下面各程序段的時間復雜度。 （1）x=90; y=100;? while(y>0) if(x>100) {x=x-10;y--;} else x++; 答案：O(1) 解釋：程序的執(zhí)行次數為常數階。 （2）for (i=0; i

10、[i][j]=0;的執(zhí)行次數為m*n。 （3）s=0; for i=0; i

11、……＋1= n(n-1)/2。 （6）x=n; //n>1 y=0; while(x≥(y+1)* (y+1)) y++; 答案：O() 解釋：語句y++;的執(zhí)行次數為???。 第2章 線性表 1．選擇題 （1）順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。 A．110 B．108 C．100 D．120 答案：B 解釋：順序表中的數據連續(xù)存儲，所以第5個元素的地址為：100+2*4=108。 （2）在n個結點的順序表中，算法的時間復雜度是O(1)的操作是（

12、）。 A．訪問第i個結點（1≤i≤n）和求第i個結點的直接前驅（2≤i≤n） B．在第i個結點后插入一個新結點（1≤i≤n） C．刪除第i個結點（1≤i≤n） D．將n個結點從小到大排序 答案：A 解釋：在順序表中插入一個結點的時間復雜度都是O(n2)，排序的時間復雜度為O(n2)或O(nlog2n)。順序表是一種隨機存取結構，訪問第i個結點和求第i個結點的直接前驅都可以直接通過數組的下標直接定位，時間復雜度是O(1)。 （3）向一個有127個元素的順序表中插入一個新元素并保持原來順序不變，平均要移動的元素個數為（ ）。 A．8 B．63.5 C．

13、63 D．7 答案：B 解釋：平均要移動的元素個數為：n/2。 （4）存儲的存儲結構所占存儲空間（ ）。 A．分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針 B．只有一部分，存放結點值 C．只有一部分，存儲表示結點間關系的指針 D．分兩部分，一部分存放結點值，另一部分存放結點所占單元數 答案：A （5）線性表若采用鏈式存儲結構時，要求內存中可用存儲單元的地址（ ）。 A．必須是連續(xù)的 B．部分地址必須是連續(xù)的 C．一定是不連續(xù)的 D．連續(xù)或不連續(xù)都可以 答案：D （6）線性表Ｌ在（ ）情況下適用于使用鏈式結構

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

15、最少的比較次數是（ ）。 A．n B．2n-1 C．2n D．n-1 答案：A 解釋：當第一個有序表中所有的元素都小于（或大于）第二個表中的元素，只需要用第二個表中的第一個元素依次與第一個表的元素比較，總計比較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．線性表中至少

16、有一個元素 C．表中諸元素的排列必須是由小到大或由大到小 D．除第一個和最后一個元素外，其余每個元素都有一個且僅有一個直接前驅和直接后繼。 答案：D (11) 創(chuàng)建一個包括n個結點的有序單鏈表的時間復雜度是（ ）。 A．O(1) B．O(n) C．O(n2) D．O(nlog2n) 答案：C 解釋：單鏈表創(chuàng)建的時間復雜度是O(n)，而要建立一個有序的單鏈表，則每生成一個新結點時需要和已有的結點進行比較，確定合適的插入位置，所以時間復雜度是O(n2)。 (12) 以下說法錯誤的是（ ）。 A．求表長、定位這兩種運算在采用順序存儲結構時實現的效率不

17、比采用鏈式存儲結構時實現的效率低 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=(*p).next; C．s->next=p->next;p->next=s->next; D．s->next=p->next;p->next=s;

18、 答案：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->prior->prior; 答案：A (15) 在雙向循環(huán)鏈表中，在p指針所指的結點后插入q所指向的新結點，其修改指針的操作是（ ）。 A．p->

19、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; 答案：C 2．算法設計題 （1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中

20、不允許有重復的數據。 [題目分析] 合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點，從第一個結點開始進行比較，當兩個鏈表La和Lb均為到達表尾結點時，依次摘取其中較小者重新在Lc表的最后。如果兩個表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復的元素。當一個表到達表尾結點，為空時，將非空表的剩余元素直接在Lc表的最后。 [算法描述] void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc) {//合并鏈表La和Lb，合并后的新表使用頭指針Lc指

21、向 pa=La->next; pb=Lb->next; //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點 Lc=pc=La; //用La的頭結點作為Lc的頭結點 while(pa && 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

22、中的元素，將pb在pc的后面，pb指針后移 else //相等時取La中的元素，刪除Lb中的元素 {pc->next=pa;pc=pa;pa=pa->next; q=pb->next;delete pb ;pb =q; } } pc->next=pa?pa:pb; //插入剩余段 delete Lb; //釋放Lb的頭結點 } （2）將兩個非遞減的有序鏈表合并為一個非遞增的有序鏈表。要求結果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中允許有重復的數據。 [題目分析] 合并后的新表使用頭

23、指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點，從第一個結點開始進行比較，當兩個鏈表La和Lb均為到達表尾結點時，依次摘取其中較小者重新在Lc表的表頭結點之后，如果兩個表中的元素相等，只摘取La表中的元素，保留Lb表中的元素。當一個表到達表尾結點，為空時，將非空表的剩余元素依次摘取，在Lc表的表頭結點之后。 [算法描述] void MergeList(LinkList& La, LinkList& Lb, LinkList& Lc, ) {//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向 pa=La->next; pb=Lb->nex

24、t; //pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點 Lc=pc=La; //用La的頭結點作為Lc的頭結點 Lc->next=NULL; while(pa||pb ) {//只要存在一個非空表，用q指向待摘取的元素 if(!pa) {q=pb; pb=pb->next;} //La表為空，用q指向pb，pb指針后移 else if(!pb) {q=pa; pa=pa->next;} //Lb表為空，用q指向pa，pa指針后移 else if(pa->data<=pb->data) {q=pa;

25、 pa=pa->next;} //取較小者（包括相等）La中的元素，用q指向pa，pa指針后移 else {q=pb; pb=pb->next;} //取較小者Lb中的元素，用q指向pb，pb指針后移 q->next = Lc->next; Lc->next = q; //將q指向的結點插在Lc 表的表頭結點之后 } delete Lb; //釋放Lb的頭結點 } （3）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設計算法求出A與B的交集，并存放于A鏈表中。 [題目分析] 只有同時出現在兩集

26、合中的元素才出現在結果表中,合并后的新表使用頭指針Lc指向。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點，從第一個結點開始進行比較，當兩個鏈表La和Lb均為到達表尾結點時，如果兩個表中相等的元素時，摘取La表中的元素，刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當鏈表La和Lb有一個到達表尾結點，為空時，依次刪除另一個非空表中的所有元素。 [算法描述] void Mix(LinkList& La, LinkList& Lb, LinkList& Lc) {pa=La->next;pb=Lb->next; pa和

27、pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點 Lc=pc=La; //用La的頭結點作為Lc的頭結點 while(pa&&pb) { if(pa->data==pb->data)∥交集并入結果表中。 { pc->next=pa; pc=pa;pa=pa->next; u=pb;pb=pb->next; Delete u; } else if(pa->datadata) { u=pa;pa=pa->next; delete u; } else { u=pb; pb=pb->next; delete u; } }

28、while(pa){u=pa; pa=pa->next; delete u;}∥ 釋放結點空間 while(pb) {u=pb; pb=pb->next; delete u;}∥釋放結點空間 pc->next=null;∥置鏈表尾標記。 delete Lb; //釋放Lb的頭結點 } （4）已知兩個鏈表A和B分別表示兩個集合，其元素遞增排列。請設計算法求出兩個集合A和B 的差集（即僅由在A中出現而不在B中出現的元素所構成的集合），并以同樣的形式存儲，同時返回該集合的元素個數。 [題目分析] 求兩個集合A和B的差集是指在A中刪除A和B中共有的元素，即刪除鏈表中的相應結點,

29、所以要保存待刪除結點的前驅，使用指針pre指向前驅結點。pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點，從第一個結點開始進行比較，當兩個鏈表La和Lb均為到達表尾結點時，如果La表中的元素小于Lb表中的元素，pre置為La表的工作指針pa刪除Lb表中的元素；如果其中一個表中的元素較小時，刪除此表中較小的元素，此表的工作指針后移。當鏈表La和Lb有一個為空時，依次刪除另一個非空表中的所有元素。 [算法描述] void Difference（LinkList& La, LinkList& Lb,int *n） {∥差集的結果存儲于單鏈表La中，*n是結果集合中元素個數

30、，調用時為0 pa=La->next; pb=Lb->next; ∥pa和pb分別是鏈表La和Lb的工作指針,初始化為相應鏈表的第一個結點 pre=La;∥pre為La中pa所指結點的前驅結點的指針 while（pa&&pb） {if（pa->datadata）{pre=pa;pa=pa->next;*n++;} ∥ A鏈表中當前結點指針后移 else if（pa->data>q->data）q=q->next;∥B鏈表中當前結點指針后移 else {pre->next=pa->next;∥處理A，B中元素值相同的結點，應刪除 u=pa; pa=pa->n

31、ext;delete u;} ∥刪除結點 } } （5）設計算法將一個帶頭結點的單鏈表A分解為兩個具有相同結構的鏈表B、C，其中B表的結點為A表中值小于零的結點，而C表的結點為A表中值大于零的結點（鏈表A中的元素為非零整數，要求B、C表利用A表的結點）。 [題目分析] B表的頭結點使用原來A表的頭結點，為C表新申請一個頭結點。從A表的第一個結點開始，依次取其每個結點p，判斷結點p的值是否小于0，利用前插法，將小于0的結點插入B表,大于等于0的結點插入C表。 [算法描述] void Dispose(LinkedList A) { B=A; B->next= NULL;∥

32、B表初始化 C=new LNode;∥為C申請結點空間 C->next=NULL;∥C初始化為空表 p=A->next; ∥p為工作指針 while(p!= NULL) {r=p->next; ∥暫存p的后繼 if(p->data<0) {p->next=B->next; B->next=p; }∥將小于0的結點鏈入B表,前插法 else {p->next=C->next; C->next=p; }∥將大于等于0的結點鏈入C表,前插法 p=r;∥p指向新的待處理結點。 }

33、 } （6）設計一個算法，通過一趟遍歷在單鏈表中確定值最大的結點。 [題目分析] 假定第一個結點中數據具有最大值，依次與下一個元素比較，若其小于下一個元素，則設其下一個元素為最大值，反復進行比較，直到遍歷完該鏈表。 [算法描述] ElemType Max (LinkList L ){ if(L->next==NULL) return NULL; pmax=L->next; //假定第一個結點中數據具有最大值 p=L->next->next; while(p != NULL ){//如果下一個結點存在 if(p->data > pmax->data) pmax

34、=p;//如果p的值大于pmax的值，則重新賦值 p=p->next;//遍歷鏈表 } return pmax->data; （7）設計一個算法，通過遍歷一趟，將鏈表中所有結點的方向逆轉，仍利用原表的存儲空間。 [題目分析] 從首元結點開始，逐個地把鏈表L的當前結點p插入新的鏈表頭部。 [算法描述] void inverse(LinkList &L) {// 逆置帶頭結點的單鏈表 L p=L->next; L->next=NULL; while ( p) { q=p->next; // q指向*p的后繼

35、 p->next=L->next; L->next=p; // *p插入在頭結點之后 p = q; } } （8）設計一個算法，刪除遞增有序鏈表中值大于mink且小于maxk的所有元素（mink和maxk是給定的兩個參數，其值可以和表中的元素相同，也可以不同 ）。 [題目分析] 分別查找第一個值>mink的結點和第一個值 ≥maxk的結點，再修改指針，刪除值大于mink且小于maxk的所有元素。 [算法描述] void delete(LinkList &L, int mink, int maxk) { p=L->n

36、ext; //首元結點 while (p && p->data<=mink) { pre=p; p=p->next; } //查找第一個值>mink的結點 if (p) {while (p && p->datanext; // 查找第一個值 ≥maxk的結點 q=pre->next; pre->next=p; // 修改指針 while (q!=p) { s=q->next; delete q; q=s; } // 釋放結點空間

37、 }//if } （9）已知p指向雙向循環(huán)鏈表中的一個結點，其結點結構為data、prior、next三個域，寫出算法change(p),交換p所指向的結點和它的前綴結點的順序。 [題目分析] 知道雙向循環(huán)鏈表中的一個結點，與前驅交換涉及到四個結點（p結點，前驅結點，前驅的前驅結點，后繼結點）六條鏈。 [算法描述] void Exchange（LinkedList p） ∥p是雙向循環(huán)鏈表中的一個結點，本算法將p所指結點與其前驅結點交換。 {q=p->llink； q->llink->rlink=p；∥p的前驅的前驅之后繼為p p->llink=q->llink

38、；∥p的前驅指向其前驅的前驅。 q->rlink=p->rlink；∥p的前驅的后繼為p的后繼。 q->llink=p；∥p與其前驅交換 p->rlink->llink=q；∥p的后繼的前驅指向原p的前驅 p->rlink=q；∥p的后繼指向其原來的前驅 }∥算法exchange結束。 （10）已知長度為n的線性表A采用順序存儲結構，請寫一時間復雜度為O(n)、空間復雜度為O(1)的算法，該算法刪除線性表中所有值為item的數據元素。 [題目分析] 在順序存儲的線性表上刪除元素，通常要涉及到一系列元素的移動（刪第i個元素，第i+1至第n個元素要依次前移）。本題要求刪除

39、線性表中所有值為item的數據元素，并未要求元素間的相對位置不變。因此可以考慮設頭尾兩個指針（i=1，j=n），從兩端向中間移動，凡遇到值item的數據元素時，直接將右端元素左移至值為item的數據元素位置。 [算法描述] void Delete（ElemType A[ ]，int n） ∥A是有n個元素的一維數組，本算法刪除A中所有值為item的元素。 {i=1；j=n；∥設置數組低、高端指針（下標）。 while（i

40、j]==item）j--；∥若右端元素為item，指針左移 if（i

41、。 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）數組Ｑ［ｎ］用來表示一個循環(huán)隊列，ｆ為當前隊列頭元素的前一位置，ｒ為隊尾元素的位置，假定隊列中元素的個數小于ｎ，計算隊列中元素個數的公式為（ ）。 A．r-f B．(n+f-r)%n C．n+r-fD．（n+r-f)%n 答案：D 解

42、釋：對于非循環(huán)隊列，尾指針和頭指針的差值便是隊列的長度，而對于循環(huán)隊列，差值可能為負數，所以需要將差值加上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 解釋：x=top->data將結點的值保存到x

43、中，top=top->link棧頂指針指向棧頂下一結點，即摘除棧頂結點。 （5）設有一個遞歸算法如下 ?????? int fact(int n) {? //n大于等于0 ??????????? if(n<=0) return 1; ??????????? else return n*fact(n-1);?????? } 則計算fact(n)需要調用該函數的次數為（）。? A．?n+1?????B．?n-1?????C． n?????D． n+2 答案：A 解釋：特殊值法。設n=0，易知僅調用一次fact(n)函數，故選A。 （6）棧在?（）中有所應用。 A．遞歸調用B．函

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

45、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進棧的正確操作是( )。 A．top++

46、; V[top]=x; B．V[top]=x; top++; C．top--; V[top]=x; D．V[top]=x; top--; 答案：C 解釋：初始棧頂指針top為n+1，說明元素從數組向量的高端地址進棧，又因為元素存儲在向量空間V[1..n]中，所以進棧時top指針先下移變?yōu)閚，之后將元素x存儲在V[n]。 （10）設計一個判別表達式中左，右括號是否配對出現的算法，采用（　）數據結構最佳。 A．線性表的順序存儲結構B．隊列 C. 線性表的鏈式存儲結構D. 棧 答案：D 解釋：利用棧的后進先出原則。 （11）用方式存儲的隊列，在進行刪除運算時（　）。

47、 A. 僅修改頭指針 B. 僅修改尾指針 C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改 答案：D 解釋：一般情況下只修改頭指針，但是，當刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。 （12）循環(huán)隊列存儲在數組A[0..m]中，則入隊時的操作為（?。? A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%mD. rear=(rear+1)%(m+1) 答案：D 解釋：數組A[0..m]中共含有m+1個元素，故在

48、求模運算時應除以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. 都是先進后出 C. 只允許在端點

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

50、下： Typedef struct {int top[2],bot[2]; //棧頂和棧底指針 SElemType *V; //棧數組 int m; //棧最大可容納元素個數 }DblStack [題目分析] 兩棧共享向量空間，將兩棧棧底設在向量兩端，初始時，左棧頂指針為-1，右棧頂為m。兩棧頂指針相鄰時為棧滿。兩棧頂相向、迎面增長，棧頂指針指向棧頂元素。 [算法描述] (1)?棧初始化 int?Init() ?{S.top[0]=-1; ??S.top[1]=m; ??return?1;?//初始化成功 } (2)?入棧操作： int?pu

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

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

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

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

55、1，否則返回0 SeqStack s; int i , len; char temp; InitStack( &s); len=strlen(t); //求向量長度 for ( i=0; i

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

57、 if(x!=-1) // 讀入的整數不等于-1時入棧。 ｛if(top==maxsize-1){cout<<“棧滿”<

58、輸入結束，操作數之間用空格分隔,操作符只可能有+、-、*、/四種運算。例如：234 34+2*$。 [題目分析] 逆波蘭表達式(即后綴表達式)求值規(guī)則如下：設立運算數棧OPND,對表達式從左到右掃描(讀入)，當表達式中掃描到數時，壓入OPND棧。當掃描到運算符時，從OPND退出兩個數，進行相應運算，結果再壓入OPND棧。這個過程一直進行到讀出表達式結束符$，這時OPND棧中只有一個數，就是結果。 [算法描述] float expr( ) //從鍵盤輸入逆波蘭表達式，以‘$’表示輸入結束，本算法求逆波蘭式表達式的值。 ｛float OPND[30]; // OPND是操作數棧。

59、 init(OPND); //兩棧初始化。 float num=0.0; //數字初始化。 cin>>x;//x是字符型變量。 while(x!=’$’) {switch {case‘0’<=x<=’9’: while((x>=’0’&&x<=’9’)||x==’.’) //拼數 if(x!=’.’) //處理整數 {num=num*10+（ord(x)-ord(‘0’)）; cin>>x;} else //處理小數部分。 {scale=10.0; cin>>x; while(x>=’0’&&x<=’9’) {nu

60、m=num+(ord(x)-ord(‘0’)/scale; scale=scale*10; cin>>x; } }//else push(OPND,num); num=0.0;//數壓入棧，下個數初始化 case x=‘ ’:break; //遇空格，繼續(xù)讀下一個字符。 case x=‘+’:push(OPND,pop(OPND)+pop(OPND));break; case x=‘-’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2-x1);break; case x=‘*’:push(OPND

61、,pop(OPND)*pop(OPND));break; case x=‘/’:x1=pop(OPND);x2=pop(OPND);push(OPND,x2/x1);break; default: //其它符號不作處理。 }//結束switch cin>>x;//讀入表達式中下一個字符。 }//結束while（x！=‘$’） cout<<“后綴表達式的值為”<

62、為是數。這種字符的序號減去字符‘0’的序號得出數。對于整數，每讀入一個數字字符，前面得到的部分數要乘上10再加新讀入的數得到新的部分數。當讀到小數點，認為數的整數部分已完，要接著處理小數部分。小數部分的數要除以10（或10的冪數）變成十分位，百分位，千分位數等等，與前面部分數相加。在拼數過程中，若遇非數字字符，表示數已拼完，將數壓入棧中，并且將變量num恢復為0，準備下一個數。這時對新讀入的字符進入‘+’、‘-’、‘*’、‘/’及空格的判斷，因此在結束處理數字字符的case后，不能加入break語句。 （5）假設以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可

63、表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。 ①下面所示的序列中哪些是合法的？ A. IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO ②通過對①的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入一維數組中）。 答案： ①A和D是合法序列，B和C 是非法序列。 ②設被判定的操作序列已存入一維數組A中。 int Judge(char A[]) //判斷字符數組A中的輸入輸出序列是否是合法序列。如是

64、，返回true，否則返回false。 {i=0; //i為下標。 j=k=0; //j和k分別為I和字母O的的個數。 while(A[i]!=‘\0’) //當未到字符數組尾就作。 {switch(A[i]) {case‘I’: j++; break; //入棧次數增1。 case‘O’: k++; if(k>j){cout<<“序列非法”<

65、 } i++; //不論A[i]是‘I’或‘O’，指針i均后移。} if(j!=k) {cout<<“序列非法”<

66、態(tài)和終態(tài)都為空），否則視為非法序列。 (6）假設以帶頭結點的循環(huán)鏈表表示隊列，并且只設一個指針指向隊尾元素站點(注意不設頭指針) ，試編寫相應的置空隊、判隊空 、入隊和出隊等算法。 [題目分析] 置空隊就是建立一個頭節(jié)點，并把頭尾指針都指向頭節(jié)點，頭節(jié)點是不存放數據的；判隊空就是當頭指針等于尾指針時，隊空；入隊時，將新的節(jié)點插入到鏈隊列的尾部，同時將尾指針指向這個節(jié)點；出隊時，刪除的是隊頭節(jié)點，要注意隊列的長度大于1還是等于1的情況，這個時候要注意尾指針的修改，如果等于1，則要刪除尾指針指向的節(jié)點。 [算法描述] //先定義鏈隊結構: typedef struct queuenode {Datatype data; struct queuenode *next; }QueueNode; //以上是結點類型的定義 typedef struct {queuenode *rear; }LinkQueue; //只設一個指向隊尾元素的指針 (1) 置空隊 void InitQueue( LinkQueue *Q) { //置空隊：就是使頭結點成為隊尾元素