數(shù)據(jù)結(jié)構(gòu)C語言版第版課后習(xí)題答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)（C語言版）（第2版）課后習(xí)題答案李冬梅 目 錄專心-專注-專業(yè)第1章 緒論1簡述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、抽象數(shù)據(jù)類型。答案：數(shù)據(jù)：是客觀事物的符號表示，指所有能輸入到計算機中并被計算機程序處理的符號的總稱。如數(shù)學(xué)計算中用到的整數(shù)和實數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動畫等通過特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計算機中通常作為一個整體進行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱為元素、結(jié)點、記錄等。數(shù)據(jù)元素用于完整地描述一個對象，如一個學(xué)生記錄，樹中棋盤的一個格局（狀

2、態(tài)）、圖中的一個頂點等。數(shù)據(jù)項：是組成數(shù)據(jù)元素的、有獨立含義的、不可分割的最小單位。例如，學(xué)生基本信息表中的學(xué)號、姓名、性別等都是數(shù)據(jù)項。數(shù)據(jù)對象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集。例如：整數(shù)數(shù)據(jù)對象是集合N=0，±1，±2，字母字符數(shù)據(jù)對象是集合C=A，B，Z， a，b，z，學(xué)生基本信息表也可是一個數(shù)據(jù)對象。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。邏輯結(jié)構(gòu)：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲無關(guān)，是獨立于計算機的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問題

3、抽象出來的數(shù)學(xué)模型。存儲結(jié)構(gòu)：數(shù)據(jù)對象在計算機中的存儲表示，也稱為物理結(jié)構(gòu)。抽象數(shù)據(jù)類型：由用戶定義的，表示應(yīng)用問題的數(shù)學(xué)模型，以及定義在這個模型上的一組操作的總稱。具體包括三部分：數(shù)據(jù)對象、數(shù)據(jù)對象上關(guān)系的集合和對數(shù)據(jù)對象的基本操作的集合。2試舉一個數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩方面的含義和相互關(guān)系。答案：例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號、姓名、性別、籍貫、專業(yè)等。每個學(xué)生基本信息記錄對應(yīng)一個數(shù)據(jù)元素，學(xué)生記錄按順序號排列，形成了學(xué)生基本信息記錄的線性序列。對于整個表來說，只有一個開始結(jié)點(它的前面無記錄)和一個終端結(jié)點(它的后面無記錄)，其他的結(jié)點則各有一個也只有一個直

4、接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu)，即線性結(jié)構(gòu)。這些學(xué)生記錄在計算機中的存儲表示就是存儲結(jié)構(gòu)。如果用連續(xù)的存儲單元(如用數(shù)組表示)來存放這些記錄，則稱為順序存儲結(jié)構(gòu)；如果存儲單元不連續(xù)，而是隨機存放各個記錄，然后用指針進行鏈接，則稱為鏈?zhǔn)酱鎯Y(jié)構(gòu)。即相同的邏輯結(jié)構(gòu)，可以對應(yīng)不同的存儲結(jié)構(gòu)。3簡述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫出它們的關(guān)系圖。答案：（1）集合結(jié)構(gòu)數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無其他關(guān)系。例如，確定一名學(xué)生是否為班級成員，只需將班級看做一個集合結(jié)構(gòu)。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報到的時間先后順序進

5、行排列，將組成一個線性結(jié)構(gòu)。（3）樹結(jié)構(gòu)數(shù)據(jù)元素之間存在一對多的關(guān)系。例如，在班級的管理體系中，班長管理多個組長，每位組長管理多名組員，從而構(gòu)成樹形結(jié)構(gòu)。（4）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。其中樹結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。 四類基本邏輯結(jié)構(gòu)關(guān)系圖4存儲結(jié)構(gòu)由哪兩種基本的存儲方法實現(xiàn)？答案：（1）順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)是借助元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計語言的數(shù)組類型來描述。（2）鏈?zhǔn)酱鎯Y(jié)構(gòu)順序存儲結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲空間中，而

6、鏈?zhǔn)酱鎯Y(jié)構(gòu)，無需占用一整塊存儲空間。但為了表示結(jié)點之間的關(guān)系，需要給每個結(jié)點附加指針字段，用于存放后繼元素的存儲地址。所以鏈?zhǔn)酱鎯Y(jié)構(gòu)通常借助于程序設(shè)計語言的指針類型來描述。5選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)答案：C（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的（ ）。A存儲結(jié)構(gòu) B存儲實現(xiàn)C邏輯結(jié)構(gòu) D運算實現(xiàn)答案：C（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ ）。 A數(shù)據(jù)具有同一特點B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相同，而且對應(yīng)

7、數(shù)據(jù)項的類型要一致C每個數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項的個數(shù)要相等答案：B（4）以下說法正確的是（ ）。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項是數(shù)據(jù)的基本單位C數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)答案：D解釋：數(shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。（5）算法的時間復(fù)雜度取決于（ ）。A問題的規(guī)模B待處理數(shù)據(jù)的初態(tài)C計算機的配置DA和B答案：D解釋：算法的時間復(fù)雜度不僅與問題的規(guī)模有關(guān)，還與問題的其他因素有關(guān)。如某些排序的算法，其執(zhí)行時間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時會對算法有最好、最壞以及

8、平均時間復(fù)雜度的評價。（6）以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)A樹 B字符串 C隊列 D棧答案：A6試分析下面各程序段的時間復(fù)雜度。（1）x=90; y=100;?while(y>0)if(x>100) x=x-10;y-;else x+;答案：O(1)解釋：程序的執(zhí)行次數(shù)為常數(shù)階。（2）for (i=0; i<n; i+)for (j=0; j<m; j+)aij=0;答案：O(m*n)解釋：語句aij=0;的執(zhí)行次數(shù)為m*n。（3）s=0; for i=0; i<n; i+)for(j=0; j<n; j+) s+=Bij;sum=s;答案：O(n2

9、)解釋：語句s+=Bij;的執(zhí)行次數(shù)為n2。（4）i=1; while(i<=n) i=i*3;答案：O(log3n) 解釋：語句i=i*3;的執(zhí)行次數(shù)為?log3n?。（5）x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+)x+;答案：O(n2)解釋：語句x+;的執(zhí)行次數(shù)為n-1+n-2+1= n(n-1)/2。（6）x=n; ext=s; (*s).next=(*p).next;Cs->next=p->next; p->next=s->next;Ds->next=p->next; p->next

10、=s; 答案：D (14) 在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點時須修改指針（ ）。Ap->next->prior=p->prior; p->prior->next=p->next;Bp->next=p->next->next; p->next->prior=p;Cp->prior->next=p; p->prior=p->prior->prior;Dp->prior=p->next->next; p->next=p->prior->prior;答案：A(15)

11、 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點后插入q所指向的新結(jié)點，其修改指針的操作是（ ）。Ap->next=q; q->prior=p; p->next->prior=q; q->next=q;Bp->next=q; p->next->prior=q; q->prior=p; q->next=p->next;Cq->prior=p; q->next=p->next; p->next->prior=q; p->next=q;Dq->prior=p; q->next=p->next

12、; p->next=q; p->next->prior=q;答案：C2算法設(shè)計題（1）將兩個遞增的有序鏈表合并為一個遞增的有序鏈表。要求結(jié)果鏈表仍使用原來兩個鏈表的存儲空間, 不另外占用其它的存儲空間。表中不允許有重復(fù)的數(shù)據(jù)。題目分析合并后的新表使用頭指針Lc指向，pa和pb分別是鏈表La和Lb的工作指針,初始化為相應(yīng)鏈表的第一個結(jié)點，從第一個結(jié)點開始進行比較，當(dāng)兩個鏈表La和Lb均為到達表尾結(jié)點時，依次摘取其中較小者重新鏈接在Lc表的最后。如果兩個表中的元素相等，只摘取La表中的元素，刪除Lb表中的元素，這樣確保合并后表中無重復(fù)的元素。當(dāng)一個表到達表尾結(jié)點，為空時，將非空表

13、的剩余元素直接鏈接在Lc表的最后。算法描述void MergeList(LinkList &La,LinkList &Lb,LinkList &Lc)想摘除棧頂結(jié)點，并將刪除結(jié)點的值保存到x中,則應(yīng)執(zhí)行操作（ ）。Ax=top->data;top=top->link； Btop=top->link;x=top->link； Cx=top;top=top->link； Dx=top->link；答案：A解釋：x=top->data將結(jié)點的值保存到x中，top=top->link棧頂指針指向棧頂下一結(jié)點，即摘除棧頂結(jié)點。（5）

14、設(shè)有一個遞歸算法如下? ? int fact(int n) ? n存儲，初始棧頂指針top設(shè)為n+1，則元素x進棧的正確操作是( )。Atop+; Vtop=x;BVtop=x; top+;Ctop-; Vtop=x;DVtop=x; top-;答案：C解釋：初始棧頂指針top為n+1，說明元素從數(shù)組向量的高端地址進棧，又因為元素存儲在向量空間V1.n中，所以進棧時top指針先下移變?yōu)閚，之后將元素x存儲在Vn。（10）設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲結(jié)構(gòu) B隊列 C. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) D. 棧答案：D解釋：利用棧的后進先出原則。

15、（11）用鏈接方式存儲的隊列，在進行刪除運算時（）。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改答案：D解釋：一般情況下只修改頭指針，但是，當(dāng)刪除的是隊列中最后一個元素時，隊尾指針也丟失了，因此需對隊尾指針重新賦值。（12）循環(huán)隊列存儲在數(shù)組A0.m中，則入隊時的操作為（）。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D解釋：數(shù)組A0.m中共含有m+1個元素，故在求模運算時應(yīng)除以m+1。（13）最大容量為n的循環(huán)隊列，隊尾指針

16、是rear，隊頭是front，則隊空的條件是（）。 A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front答案：B解釋：最大容量為n的循環(huán)隊列，隊滿條件是(rear+1)%n=front，隊空條件是rear=front。（14）棧和隊列的共同點是（）。A. 都是先進先出 B. 都是先進后出 C. 只允許在端點處插入和刪除元素 D. 沒有共同點答案：C解釋：棧只允許在棧頂處進行插入和刪除元素，隊列只允許在隊尾插入元素和在隊頭刪除元素。（15）一個遞歸算法必須包括（）。A. 遞歸部分 B. 終止條件和遞歸部分C. 迭代

17、部分 D. 終止條件和迭代部分答案：B2算法設(shè)計題（1）將編號為0和1的兩個棧存放于一個數(shù)組空間Vm中，棧底分別處于數(shù)組的兩端。當(dāng)?shù)?號棧的棧頂指針top0等于-1時該棧為空，當(dāng)?shù)?號棧的棧頂指針top1等于m時該棧為空。兩個棧均從兩端向中間增長。試編寫雙棧初始化，判斷棧空、棧滿、進棧和出棧等算法的函數(shù)。雙棧數(shù)據(jù)結(jié)構(gòu)的定義如下：Typedef structint top2,bot2; IOIIOIOO B. IOOIOIIO C. IIIOIOIO D. IIIOOIOO通過對的分析，寫出一個算法，判定所給的操作序列是否合法。若合法，返回true，否則返回false（假定被判定的操作序列已存入

18、一維數(shù)組中）。答案：A和D是合法序列，B和C 是非法序列。設(shè)被判定的操作序列已存入一維數(shù)組A中。int Judge(char A) M-1實現(xiàn)循環(huán)隊列，其中M是隊列長度。設(shè)隊頭指針 front和隊尾指針rear，約定front指向隊頭元素的前一位置，rear指向隊尾元素。定義front=rear時為隊空，(rear+1)%m=front 為隊滿。約定隊頭端入隊向下標(biāo)小的方向發(fā)展，隊尾端入隊向下標(biāo)大的方向發(fā)展。算法描述#define M 隊列可能達到的最大長度typedef structelemtp dataM;int front,rear;cycqueue;elemtp delqueue (

19、cycqueue Q) 100,1.100，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10，則LOC5,5=（ ）。A808 B818 C1010 D1020答案：B解釋：以行序為主，則LOC5,5=（5-1）*100+（5-1）*2+10=818。（7）設(shè)有數(shù)組Ai,j，數(shù)組的每個元素長度為3字節(jié)，i的值為1到8，j的值為1到10，數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A5,8的存儲首地址為（ ）。ABA+141 BBA+180 CBA+222 DBA+225答案：B解釋：以列序為主，則LOC5,8=（8-1）*8+（5-1）*3+BA=BA+180。（8）設(shè)有一個10階的對

20、稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（ ）。A13 B32 C33 D40答案：C（9）若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B1.(n(n+1)/2中，則在B中確定aij（i<j）的位置k的關(guān)系為（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i答案：B（10）二維數(shù)組A的每個元素是由10個字符組成的串，其行下標(biāo)i=0,1,8,列下標(biāo)j=1,2,10。若A按行先存儲，元素A8,5的起始地址

21、與當(dāng)A按列先存儲時的元素（ ）的起始地址相同。設(shè)每個字符占一個字節(jié)。AA8,5 BA3,10 C. A5,8 DA0,9答案：B解釋：設(shè)數(shù)組從內(nèi)存首地址M開始順序存放，若數(shù)組按行先存儲，元素A8,5的起始地址為：M+（8-0）*10+（5-1）*1=M+84；若數(shù)組按列先存儲，易計算出元素A3,10的起始地址為：M+（10-1）*9+（3-0）*1=M+84。故選B。（11）設(shè)二維數(shù)組A1. m，1. n（即m行n列）按行存儲在數(shù)組B1. m*n中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1答案：A解釋

22、：特殊值法。取i=j=1，易知A1,1的的下標(biāo)為1，四個選項中僅有A選項能確定的值為1，故選A。（12）數(shù)組A0.4,-1.-3,5.7中含有元素的個數(shù)（ ）。A55 B45 C36 D16答案：B解釋：共有5*3*3=45個元素。（13）廣義表A=(a,b,(c,d),(e,(f,g)，則Head(Tail(Head(Tail(Tail(A)的值為（ ）。A(g) B(d) Cc Dd答案：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(T

23、ail(A)=(d)；Head(Tail(Head(Tail(Tail(A)=d。（14）廣義表(a,b,c,d)的表頭是（ ），表尾是（ ）。Aa 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的長度和深度分別為（ ）。A1和1 B1和3 C1和2 D2和3 答案：C解釋：廣義表的深度是指廣義表中展開后所含括號的層數(shù)，

24、廣義表的長度是指廣義表中所含元素的個數(shù)。根據(jù)定義易知L的長度為1，深度為2。2應(yīng)用題 （1）已知模式串t=abcaabbabcab寫出用KMP法求得的每個字符對應(yīng)的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a(chǎn) b c a a b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 5（2）設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa” 計算模式p的naxtval函數(shù)值； 不

25、寫出算法,只畫出利用KMP算法進行模式匹配時每一趟的匹配過程。答案： p的nextval函數(shù)值為。（p的next函數(shù)值為）。 利用KMP(改進的nextval)算法，每趟匹配過程如下： 第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaabbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)（3）數(shù)組A中，每個元素Ai,j的長度均為32個二進位,行下標(biāo)從-

26、1到9，列下標(biāo)從1到11，從首地址S開始連續(xù)存放主存儲器中，主存儲器字長為16位。求： 存放該數(shù)組所需多少單元？ 存放數(shù)組第4列所有元素至少需多少單元？ 數(shù)組按行存放時，元素A7,4的起始地址是多少？ 數(shù)組按列存放時，元素A4,7的起始地址是多少？答案：每個元素32個二進制位，主存字長16位，故每個元素占2個字長，行下標(biāo)可平移至1到11。（1）242 （2）22 （3）s+182 （4）s+142(4)請將香蕉banana用工具 H( )Head( )，T( )Tail( )從L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)答案：H

27、（H（T（H（T（H（T（L）3算法設(shè)計題（1）寫一個算法統(tǒng)計在輸入字符串中各個不同字符出現(xiàn)的頻度并將結(jié)果存入文件（字符串中的合法字符為A-Z這26個字母和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（） 是字符串輸入

28、結(jié)束標(biāo)志InvertStore(A); Ai+ = ch;m, 1.n 含有m*n 個整數(shù)。 寫一個算法判斷a中所有元素是否互不相同?輸出相關(guān)信息(yes/no)； 試分析算法的時間復(fù)雜度。題目分析判斷二維數(shù)組中元素是否互不相同，只有逐個比較,找到一對相等的元素，就可結(jié)論為不是互不相同。如何達到每個元素同其它元素比較一次且只一次？在當(dāng)前行，每個元素要同本行后面的元素比較一次（下面第一個循環(huán)控制變量p的for循環(huán)），然后同第i+1行及以后各行元素比較一次，這就是循環(huán)控制變量k和p的二層for循環(huán)。算法描述int JudgEqual(ing amn,int m,n) 算法討論對數(shù)組中元素各比較一次

29、，比較次數(shù)為n。最佳情況(已排好,正數(shù)在前,負數(shù)在后)不發(fā)生交換，最差情況(負數(shù)均在正數(shù)前面)發(fā)生n/2次交換。用類c編寫，數(shù)組界偶是0.n-1?？臻g復(fù)雜度為O(1).第5章 樹和二叉樹1選擇題（1）把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是（ ）。 A唯一的 有多種C有多種，但根結(jié)點都沒有左孩子 有多種，但根結(jié)點都沒有右孩子答案：A 解釋：因為二叉樹有左孩子、右孩子之分，故一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是唯一的。（2）由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹？（ ）A2 B3 C4 D5 答案：D解釋：五種情況如下：（3）一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ ）。A

30、250 B 500 C254 D501 答案：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為（ ）。A11 B10 C11至1025之間 D10至1024之間答案：C解釋：若每層僅有一個結(jié)點，則樹高h為1025；且其最小樹高為?log21025?+?1=11，即h在11至1025之間。（5）深度為h的滿m叉樹的第k層有（ ）個結(jié)點。(1=<

31、k=<h) Amk-1 Bmk-1 Cmh-1 Dmh-1答案：A解釋：深度為h的滿m叉樹共有mh-1個結(jié)點，第k層有mk-1個結(jié)點。（6）利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空答案：C解釋：利用二叉鏈表存儲樹時，右指針指向兄弟結(jié)點，因為根節(jié)點沒有兄弟結(jié)點，故根節(jié)點的右指針指向空。（7）對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（ ）遍歷實現(xiàn)編號。A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷答案：C解釋：根據(jù)題意可知按照先左孩子

32、、再右孩子、最后雙親結(jié)點的順序遍歷二叉樹，即后序遍歷二叉樹。（8）若二叉樹采用二叉鏈表存儲結(jié)構(gòu)，要交換其所有分支結(jié)點左、右子樹的位置，利用（ ）遍歷方法最合適。A前序 B中序 C后序 D按層次答案：C解釋：后續(xù)遍歷和層次遍歷均可實現(xiàn)左右子樹的交換，不過層次遍歷的實現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。（9）在下列存儲形式中，（ ）不是樹的存儲形式？A雙親表示法 B孩子鏈表表示法 C孩子兄弟表示法 D順序存儲表示法答案：D解釋：樹的存儲結(jié)構(gòu)有三種：雙親表示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹都能通過孩子兄弟表示法轉(zhuǎn)換為二叉樹進行存儲。（10）一棵非空的二叉樹

33、的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ ）。A所有的結(jié)點均無左孩子 B所有的結(jié)點均無右孩子C只有一個葉子結(jié)點 D是任意一棵二叉樹答案：C解釋：因為先序遍歷結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當(dāng)沒有左子樹時，就是“中右”和“右中”；當(dāng)沒有右子樹時，就是“中左”和“左中”。則所有的結(jié)點均無左孩子或所有的結(jié)點均無右孩子均可，所以A、B不能選，又所有的結(jié)點均無左孩子與所有的結(jié)點均無右孩子時，均只有一個葉子結(jié)點，故選C。（11）設(shè)哈夫曼樹中有199個結(jié)點，則該哈夫曼樹中有（ ）個葉子結(jié)點。A99B100C101D102答案：B解釋：在哈夫曼樹中沒有度為1的結(jié)點，只有度為0（葉

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

35、點有（ ）個。An?1BnCn + 1Dn + 2答案：C（15）n（n2）個權(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）試找出滿足下列條件的二叉樹 先序序列與后序序列相同 中序序列與后序序列相同 先序序列與中序序列相

36、同 中序序列與層次遍歷序列相同答案：先序遍歷二叉樹的順序是“根左子樹右子樹”，中序遍歷“左子樹根右子樹”，后序遍歷順序是：“左子樹右子樹根，根據(jù)以上原則有 或為空樹，或為只有根結(jié)點的二叉樹? 或為空樹，或為任一結(jié)點至多只有左子樹的二叉樹? 或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹 或為空樹，或為任一結(jié)點至多只有右子樹的二叉樹（2）設(shè)一棵二叉樹的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫出這棵二叉樹。畫出這棵二叉樹的后序線索樹。將這棵二叉樹轉(zhuǎn)換成對應(yīng)的樹（或森林）。答案：ABFDCEHG? （3） 假設(shè)用于通信的電文僅由8個字母組成，字母在電文

37、中出現(xiàn)的頻率分別為，。 試為這8個字母設(shè)計赫夫曼編碼。 試設(shè)計另一種由二進制表示的等長編碼方案。 對于上述實例，比較兩種方案的優(yōu)缺點。答案：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32（100）（40） （60）19 21 32 （28）（17） （11） 7 10 6 （5） 2 3 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3方案比較：字母編號對應(yīng)編碼出現(xiàn)頻率10002001301040115100610171108

38、111字母編號對應(yīng)編碼出現(xiàn)頻率111002003111104111051061111170181101方案1的WPL2+4+5+=+=方案2的WPL3+=3結(jié)論：哈夫曼編碼優(yōu)于等長二進制編碼?（4）已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫出其對應(yīng)哈夫曼樹HT的存儲結(jié)構(gòu)的初態(tài)和終態(tài)。答案：初態(tài):weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000終態(tài)：weightparentlchildrchild1380021212003

39、71000449005280068100071111008595199114810151236112013971227132101347011123算法設(shè)計題以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編寫以下算法：（1）統(tǒng)計二叉樹的葉結(jié)點個數(shù)。題目分析如果二叉樹為空，返回0，如果二叉樹不為空且左右子樹為空，返回1，如果二叉樹不為空，且左右子樹不同時為空，返回左子樹中葉子節(jié)點個數(shù)加上右子樹中葉子節(jié)點個數(shù)。算法描述 int LeafNodeCount(BiTree T)if(T=NULL)return 0; c; 隊列 C. 樹 D圖 答案：B解釋：廣度優(yōu)先遍歷通常借助隊列來實現(xiàn)算法，深度優(yōu)先遍歷通常借助棧

40、來實現(xiàn)算法。（9）用鄰接表表示圖進行深度優(yōu)先遍歷時，通常借助（ ）來實現(xiàn)算法。A棧 B. 隊列 C. 樹 D圖 答案：A解釋：廣度優(yōu)先遍歷通常借助隊列來實現(xiàn)算法，深度優(yōu)先遍歷通常借助棧來實現(xiàn)算法。（10）深度優(yōu)先遍歷類似于二叉樹的（ ）。A先序遍歷 B中序遍歷 C后序遍歷 D層次遍歷答案：A（11）廣度優(yōu)先遍歷類似于二叉樹的（ ）。A先序遍歷 B中序遍歷 C后序遍歷 D層次遍歷答案：D（12）圖的BFS生成樹的樹高比DFS生成樹的樹高（ ）。A小 B相等 C小或相等 D大或相等答案：C解釋：對于一些特殊的圖，比如只有一個頂點的圖，其BFS生成樹的樹高和DFS生成樹的樹高相等。一般的圖，根據(jù)圖的

41、BFS生成樹和DFS樹的算法思想，BFS生成樹的樹高比DFS生成樹的樹高小。（13）已知圖的鄰接矩陣如圖所示，則從頂點v0出發(fā)按深度優(yōu)先遍歷的結(jié)果是（ ）。 ? 圖 鄰接矩陣（14）已知圖的鄰接表如圖所示，則從頂點v0出發(fā)按廣度優(yōu)先遍歷的結(jié)果是（ ），按深度優(yōu)先遍歷的結(jié)果是（ ）。圖 鄰接表A0 1 3 2B0 2 3 1C0 3 2 1D0 1 2 3答案：D、D（15）下面（ ）方法可以判斷出一個有向圖是否有環(huán)。A深度優(yōu)先遍歷 B拓撲排序 C求最短路徑 D求關(guān)鍵路徑答案：B2應(yīng)用題（1）已知圖所示的有向圖，請給出： 每個頂點的入度和出度； 鄰接矩陣； 鄰接表； 逆鄰接表。 ? 圖 有向圖

42、圖 無向網(wǎng)答案：（2）已知如圖所示的無向網(wǎng)，請給出： 鄰接矩陣； 鄰接表； 最小生成樹答案： ab4c3ba4c5d5e9ca3b5d5h5db5c5e7f6g5h4eb9d7f3fd6e3g2gd5f2h6（3）已知圖的鄰接矩陣如圖所示。試分別畫出自頂點1出發(fā)進行遍歷所得的深度優(yōu)先生成樹和廣度優(yōu)先生成樹。圖 鄰接矩陣（4）有向網(wǎng)如圖所示，試用迪杰斯特拉算法求出從頂點a到其他各頂點間的最短路徑，完成表。? 圖 鄰接矩陣 圖 有向網(wǎng)表D終點i=1i=2i=3i=4i=5i=6b15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)15(a,b)c2(a,c)d12(a,d)12(

43、a,d)11(a,c,f,d)11(a,c,f,d)e10(a,c,e)10(a,c,e)f6(a,c,f)g16(a,c,f,g)16(a,c,f,g)14(a,c,f,d,g)S終點集a,ca,c,fa,c,f,ea,c,f,e,da,c,f,e,d,ga,c,f,e,d,g,b（5）試對圖所示的AOE-網(wǎng)： 求這個工程最早可能在什么時間結(jié)束； 求每個活動的最早開始時間和最遲開始時間； 確定哪些活動是關(guān)鍵活動圖 AOE-網(wǎng)答案：按拓撲有序的順序計算各個頂點的最早可能開始時間Ve和最遲允許開始時間Vl。然后再計算各個活動的最早可能開始時間e和最遲允許開始時間l，根據(jù)l - e = 0? 來確定關(guān)鍵活動，從而確定關(guān)鍵路徑。1 ? 2 ?3 ? 4 ?5 ?6 ?Ve019152938 43Vl01915373843<1, 2><1, 3><3, 2><2, 4><2, 5><3, 5><4, 6><5, 6>e00151919152938l170152719273738