1、數據結構第一二章一 填空1. 衡量算法效率的兩個重要指標稱為算法的 時間復雜度_和 空間復雜度。2. 一個算法應具有 有窮性，確定性，可行性，輸入和 輸出這五個特性。3. 線性表的長度是指_表中元素的個數_。4. 在線性表的順序存儲中，元素之間的邏輯關系是通過 元素存儲的相對位置 決定的；在線性表的鏈接存儲中，元素之間的邏輯關系是通過 相關元素的存儲位置 決定的。5 在雙向鏈表中，每個結點包含兩個指針域，一個指向其直接前趨結點，另一個指向 其直接后繼 結點。二、 判斷題 1線性表的邏輯順序與存儲順序總是一致的。(FALSE) 2順序存儲的線性表可以按序號隨機存取。(TRUE) 3在線性表的順序

2、存儲結構中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。（FALSE） 4在線性表的鏈式存儲結構中，邏輯上相鄰的元素在物理位置上不一定相鄰。（TRUE） 5在線性表的順序存儲結構中，插入和刪除時，移動元素的個數與該元素的位置有關。（TRUE） 6線性表的鏈式存儲結構是用一組任意的存儲單元來存儲線性表中數據元素的。（TRUE） 三、 單選題 (請從下列A，B，C，D選項中選擇一項) 1線性表是(A) 。 (A) 一個有限序列，可以為空； (B) 一個有限序列，不能為空； (C) 一個無限序列，可以為空； (D) 一個無序序列，不能為空。 2對順序存儲的線性表，設其長度為n，在任何位置上插入或刪

3、除操作都是等概率的。插入一個元素時平均要移動表中的（A ）個元素。 (A) n/2 (B)（n+1）/2 (C) (n 1)/2 (D) n 3線性表采用鏈式存儲時，其地址( D ) 。 (A) 必須是連續的； (B) 部分地址必須是連續的； (C) 一定是不連續的； (D) 連續與否均可以。 4用鏈表表示線性表的優點是 （ C）。 (A)便于隨機存取 (B)花費的存儲空間較順序存儲少 (C)便于插入和刪除 (D)數據元素的物理順序與邏輯順序相同 5. 某鏈表中最常用的操作是在最后一個元素之后插入一個元素和刪除最后一個元素，則采用( D )存儲方式最節省運算時間。 (A)單鏈表 (B)雙鏈表

4、(C)單循環鏈表 (D)帶頭結點的雙循環鏈表 6. 循環鏈表的主要優點是( D ) 。 (A)不再需要頭指針了 (B)已知某個結點的位置后，能夠容易找到他的直接前趨 (C)在進行插入、刪除運算時，能更好的保證鏈表不斷開 (D)從表中的任意結點出發都能掃描到整個鏈表 7. 單鏈表中，增加一個頭結點的目的是為了（ C ）。 (A) 使單鏈表至少有一個結點 (B)標識表結點中首結點的位置 （C）方便運算的實現 (D) 說明單鏈表是線性表的鏈式存儲 8. 若某線性表中最常用的操作是取第i個元素和找第i個元素的前趨元素，則采用（ ）存儲方式最節省運算時間（B ）。 (A) 單鏈表 (B) 順序表 (C)

5、 雙鏈表 (D) 單循環鏈表 四、簡答題1何時選用順序表、何時選用鏈表作為線性表的存儲結構為宜?答：在實際應用中，應根據具體問題的要求和性質來選擇順序表或鏈表作為線性表的存儲結構，通常有以下幾方面的考慮：1.基于空間的考慮。當要求存儲的線性表長度變化不大，易于事先確定其大小時，為了節約存儲空間，宜采用順序表；反之，當線性表長度變化大，難以估計其存儲規模時，采用動態鏈表作為存儲結構為好。2.基于時間的考慮。若線性表的操作主要是進行查找，很少做插入和刪除操作時，采用順序表做存儲結構為宜；反之， 若需要對線性表進行頻繁地插入或刪除等的操作時，宜采用鏈表做存儲結構。并且，若鏈表的插入和刪除主

6、要發生在表的首尾兩端，則采用尾指針表示的單循環鏈表為宜。2在順序表中插入和刪除一個結點需平均移動多少個結點?具體的移動次數取決于哪兩個因素?答：在等概率情況下，順序表中插入一個結點需平均移動n/2個結點。刪除一個結點需平均移動(n-1)/2個結點。具體的移動次數取決于順序表的長度n以及需插入或刪除的位置i。i越接近n則所需移動的結點數越少。3 為什么在單循環鏈表中設置尾指針比設置頭指針更好?答：尾指針是指向終端結點的指針，用它來表示單循環鏈表可以使得查找鏈表的開始結點和終端結點都很方便，設一帶頭結點的單循環鏈表，其尾指針為rear，則開始結點和終端結點的位置分別是rear->next-&

7、gt;next和rear,查找時間都是O(1)。若用頭指針來表示該鏈表，則查找終端結點的時間為O(n)。五、分別設計算法，實現線性表的順序存儲結構和鏈式存儲結構的原地置逆。順序存儲結構的原地置逆typedef struct ElemType *elem; /存儲空間基址 int length; /線性表的實際長度 int listsize； /當前分配的存儲容量， /（以sizeof（ElemType）為單位sqList;void reverse(SqList &A) /順序表的就地逆置   int i; int j; for(i=1,j=A.length;i<

8、;j;i+,j-)     A.elemi<->A.elemj;/reverse鏈式存儲結構的原地置逆。算法：ypedef struct LNodeElemType data; /結點值 struct LNode *next; /指針域，存儲下一個結點的地址LNode,*LinkList;void ReverseList( LinkList &L )/ 將L 所指的帶頭結點的單鏈表逆置if( L->next && L->next->next)/當鏈表不是空表或單結點時 p=L->next;q=p

9、->next; p -> next=NULL; /將開始結點變成終端結點 while (q) /每次循環將后一個結點變成開始結點 p=q; q=q->next ; p->next = L-> next ;L->next = p;作業2.1,2.2答案見習題冊后面答案2.6答案：解答：a.（4）（1）b.（7）（11）(8)（4）（1） c.（5）（12）d.（11）（9）（1）（6） 或 (11)（9）（4）（1）2.7答案：解答：a.（11）（3）（4） b.（10）（12）（8）（10）（3）（4） c. （10）（12）（7）（3）（4）d.（12）（

10、11）（3）（14） e.（9）（11）（3）(14)2.8 已知P結點是雙向鏈表的中間結點，試從下列提供的答案中選擇合適的語句序列。 a在P結點后插入S結點的語句序列是-。 b在P結點前插入S結點的語句序列是-。 c刪除P結點的直接后繼結點的語句序列是-。 d刪除P結點的直接前驅結點的語句序列是-。 e刪除P結點的語句序列是-。 (1)P->next=P->next->next; (10) P->prior->next=P; (2)P->prior=P->prior->prior; (11) P->next->prior =P; (

11、3) P->next=S; (12)P->next->prior=S; (4) P->prior=S; (13) P->prior->next=S; (5)S->next=P; (14) P->next->prior=P->prior (6)S->prior=P; (15)Q=P->next; (7) S->next= P->next; (16)Q= P->prior; (8) S->prior= P->prior; (17)free(P); (9) P->prior->next=

12、p->next; (18)free(Q);解答：a.（12）（7）（3）（6） 3必須在12和7的后面，其余的順序可變b.（13）（8）（4）（5） 同上c.（15）（1）（11）（18） 不可變d.（16）（2）（10）（18） 不可變e.（9）（14）（17）2.31答案： ypedef struct LNode ElemType data; /結點值 struct LNode *next; /指針域，存儲下一個結點的地址LNode,*LinkList;Status Delete_Pre(linklist s ElemType e) /刪除單循環鏈表中結點s的直接前驅 &#

13、160;p=s;  while(p->next->next!=s) p=p->next; /找到s的前驅的前驅p  q=p->next; p->next =s; e=q ->data; free(q);  return OK;/Delete_Pre第三章一 、單項選擇題1.棧中元素的進出原則是 （B ）先進先出 后進先出 棧空則進 棧滿則出 2.若已知一個棧的入棧序列是1，2，3，n，其輸出序列為p1，p2，p3，pn，若p1=n，則pi為 （C）I n=i n-i+1 不確定 解釋：當p1=n，即

14、n是最先出棧的，根據棧的原理，n必定是最后入棧的（事實上題目已經表明了），那么輸入順序必定是1，2，3，n，則出棧的序列是n，3，2，1。 （若不要求順序出棧，則輸出序列不確定） 3.判定一個棧ST（最多元素為m0）為空的條件是 （B ）ST->top<>0 ST->top= =0 ST->top<>m0 ST->top= =m0 4. 在作進棧運算時,應先判別棧是否( B ),在作退棧運算時應先判別棧是否( A )。當棧中元素為n個,作進棧運算時發生上溢,則說明該棧的最大容量為( B )。為了增加內存空間的利用率和減少溢出的可能性,由兩個棧共享

15、一片連續的內存空間時,應將兩棧的 ( D )分別設在這片內存空間的兩端,這樣,當( C )時，才產生上溢。 : A. 空 B. 滿 C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 : A. 長度 B. 深度 C. 棧頂 D. 棧底:A. 兩個棧的棧頂同時到達棧空間的中心點.B. 其中一個棧的棧頂到達棧空間的中心點.C. 兩個棧的棧頂在棧空間的某一位置相遇.D. 兩個棧均不空,且一個棧的棧頂到達另一個棧的棧底.5. 某堆棧的輸入序列為a, b，c ，d,下面的四個序列中，不可能是它的輸出序列的是（ D ）。 A. a，c，b，d B. b, c，d，a C. c,

16、 d，b, a D. d, c，a，b6. 若棧采用順序存儲方式存儲，現兩棧共享空間V1.m，topi代表第i個棧( i =1,2)棧頂，棧1的底在v1，棧2的底在Vm，則棧滿的條件是（ B ）。A. |top2-top1|=0 B. top1+1=top2 C. top1+top2=m D. top1=top27. 設計一個判別表達式中左，右括號是否配對出現的算法，采用（ D ）數據結構最佳。A線性表的順序存儲結構 B. 隊列 C. 線性表的鏈式存儲結構 D. 棧8. 用不帶頭結點的單鏈表存儲隊列時,其隊頭指針指向隊頭結點,其隊尾指針指向隊尾結點，則在進行刪除操作時( A )。A僅修改隊頭指

17、針 B. 僅修改隊尾指針 C. 隊頭、隊尾指針都要修改 D. 隊頭,隊尾指針都可能要修改9. 遞歸過程或函數調用時，處理參數及返回地址，要用一種稱為（ C ）的數據結構。A隊列 B多維數組 C棧 D. 線性表10. 若用一個大小為6的數組來實現循環隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( B ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 二 填空題1. 線性表、棧和隊列都是 線性 結構，可以在線性表的 任意 位置插入和刪除元素；對于棧只能在 棧頂 插入和刪除元素；對于隊列只能在 隊尾 插入

18、元素， 在 隊頭 刪除元素。2. 棧是一種特殊的線性表，允許插入和刪除運算的一端稱為 棧頂 。不允許插入和刪除運算的一端稱為 棧底 。3. 一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是_3 1 2_。4. 循環隊列的引入，目的是為了克服_隊列的假溢出_。 5用下標0開始的N元數組實現循環隊列時，為實現下標變量M加1后在數組有效下標范圍內循環，可采用的表達式是：M=_(M+1)%N_；6.隊列的特點是_先進先出_。7表達式求值是_棧_應用的一個典型例子。3.1 鐵路進行列車調度時, 常把站臺設計成棧式結構的站臺，如右圖所示。試問：(1) 設有編號為1,2,3,4,5,6的六輛列車, 順序

19、開入棧式結構的站臺, 則可能的出棧序列有多少種?(2) 若進站的六輛列車順序如上所述, 那么是否能夠得到435612, 325641, 154623和135426的出站序列, 如果不能, 說明為什么不能; 如果能, 說明如何得到(即寫出"進棧"或"出棧"的序列)。【解答】(1) 可能的不同出棧序列有 種。(2) 不能得到435612和154623這樣的出棧序列。因為若在4, 3, 5, 6之后再將1, 2出棧，則1, 2必須一直在棧中，此時1先進棧，2后進棧，2應壓在1上面，不可能1先于2出棧。154623也是這種情況。出棧序列325641和135426

20、可以得到。3562244 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 1354260 m-13-15 將編號為0和1的兩個棧存放于一個數組空間Vm中，棧底分別處于數組的兩端。當第0號棧的棧頂指針top0等于-1時該棧為空，當第1號棧的棧頂指針top1等于m時該棧為空。兩個棧均從兩端向中間增長。當向第0號棧插入一個新元素時，使top0增1得到新的棧頂位置，當向第1號棧插入一個新元素時，使top1減1得到新的棧頂位置。當top0+1 = top1時或top0 = top1-1時

21、，棧空間滿，此時不能再向任一棧加入新的元素。試定義這種雙棧(Double Stack)結構的類定義，并實現判棧空、判棧滿、插入、刪除算法。【解答】bot0 top0 top1 bot1雙棧的類定義如下：#include <assert.h>template <class Type> class DblStack /雙棧的類定義 private: int top2, bot2;/雙棧的棧頂指針和棧底指針 Type *elements; /棧數組 int m;/棧最大可容納元素個數 public: DblStack ( int sz =10 );/初始化雙棧, 總體積m的默

22、認值為10 DblStack ( ) delete elements; /析構函數 void DblPush ( const Type& x, int i );/把x插入到棧i的棧頂 int DblPop ( int i );/退掉位于棧i棧頂的元素 Type * DblGetTop ( int i );/返回棧i棧頂元素的值 int IsEmpty ( int i ) const return topi = boti; /判棧i空否, 空則返回1, 否則返回0 int IsFull ( ) const return top0+1 = top1; /判棧滿否, 滿則返回1, 否則返回0

23、 void MakeEmpty ( int i ); /清空棧i的內容template <class Type> DblStack<Type> : DblStack ( int sz ) : m(sz), top0 (-1), bot0(-1), top1(sz), bot1(sz) /建立一個最大尺寸為sz的空棧, 若分配不成功則錯誤處理。 elements = new Typem;/創建棧的數組空間 assert ( elements != NULL );/斷言: 動態存儲分配成功與否template <class Type> void DblStack

24、<Type> : DblPush ( const Type& x, int i ) /如果IsFull ( )，則報錯；否則把x插入到棧i的棧頂 assert ( !IsFull ( ) );/斷言: 棧滿則出錯處理，停止執行 if ( i = 0 ) elements +top0 = x;/棧0情形：棧頂指針先加1, 然后按此地址進棧 else elements-top1 = x;/棧1情形：棧頂指針先減1, 然后按此地址進棧template <class Type> int DblStack<Type> : DblPop ( int i ) /如

25、果IsEmpty ( i )，則不執行退棧，返回0；否則退掉位于棧i棧頂的元素，返回1 if ( IsEmpty ( i ) ) return 0;/判棧空否, 若棧空則函數返回0 if ( i = 0 ) top0-;/棧0情形：棧頂指針減1 else top1+; /棧1情形：棧頂指針加1 return 1;template <class Type> Type * DblStack<Type> : DblGetTop ( int i ) /若棧不空則函數返回該棧棧頂元素的地址。 if ( IsEmpty ( int i ) ) return NULL;/判棧i空否,

26、 若棧空則函數返回空指針 return& elements topi ;/返回棧頂元素的值template <class Type> void MakeEmpty ( int i ) if ( i = 0 ) top0 = bot0 = -1; else top1 = bot1 = m; 或S1.base S2.base S1Sm 進棧：S1.top+ S2.top- 出棧：S1.top- S2.top+ 棧滿：S1.top=-S2.top或+S1.top=S2.top3.1【解答】(1) 可能的不同出棧序列有5種：123，132，213，231，321。(2) 不能得到4

27、35612和154623這樣的出棧序列。因為若在4, 3, 5, 6之后再將1, 2出棧，則1, 2必須一直在棧中，此時1先進棧，2后進棧，2應壓在1上面，不可能1先于2出棧。154623也是這種情況。出棧序列325641和135426可以得到。 3.15 畫出兩個棧共享存儲空間S 1.m示意圖，并說明兩個棧進棧、出棧操作時棧頂指針變化情況及棧滿的條件。進棧：S1.top+ S2.top- 出棧：S1.top- S2.top+ 棧滿：S1.top=-S2.top或+S1.top=S2.topS1.base s1.top s2.top s2.base s1 sm3.28 假設以帶頭結點的循環鏈表

28、表示隊列，并且只設一個指針指向隊尾元素（注意不設頭指針）， 試編寫相應的隊列初始化、入隊列和出隊列的算法。 typedef struct QNode QElemType data; struct QNode *next;QNode,*QueuePtr;void InitQueue(Queue &Q) /初始化循環鏈表表示的隊列Q  Q=(QueuePtr)malloc(sizeof(QNode);  Q->next=Q;/InitQueueStatus EnQueue(QueuePtr &tail,QElemType e ） q =

29、 (QueuePtr)malloc(sizeof(QNode); /分配空間，構造入隊列元素結點 q->data = e; /元素賦值 q->next = tail ->next; /入隊列 tail ->next = q; tail = tail ->next; /隊尾指針后移 return OK;Status DeQueue(QueuePtr & tail,QElemType &e）  if(tail = tail ->next) return ERROR; /隊列已空 q = tail ->next->next;

30、/q指向帶頭結點鏈表的第一個元素 e = q->data; /返回出隊列元素 tail ->next->next = q ->next; /元素出隊列 free(q); /釋放空間 return OK;3.30 假設將循環隊列定義為：以rear和length分別指示環形隊列中的隊尾元素的位置和隊列中所含元素的個數。試給出該循環隊列的隊空條件和隊滿條件, 并寫出相應的入隊列和出隊列元素的算法（在出隊列的算法中要返回隊頭元素）。隊空條件:Q.length=0隊滿條件： Q.length=MAXSIZEStatus EnCyQueue(CyQueue &Q,int x

31、) /帶length域的循環隊列入隊算法  if(Q.length=MAXSIZE) return OVERFLOW;  Q.rear=(Q.rear+1)%MAXSIZE;  Q.baseQ.rear=x;  Q.length+;  return OK;/EnCyQueue Status DeCyQueue(CyQueue &Q,int &x) /帶length域的循環隊列出隊算法  if(Q.length=0) return ERROR; 

32、60;head=(Q.rear+ MAXSIZE -Q.length+1)%MAXSIZE; /詳見書后注釋  x=Q.basehead;  Q.length-;/DeCyQueue 第四五章 一、填充題1、一個串中任意個 連續 的字符組成的子序列稱為該串的子串。 2、串的靜態存儲結構中的兩種不同的存儲方式分別是 非緊縮 格式和 緊縮 格式。3、兩個串的相等，是指兩個兩串的 長度 相等， 對應位置的字符 相同。4、已知二維數組A有m行n列，采用行優先方式存儲，每個數據元素占k個存儲單元，并且第一個元素的存儲地址是LOC(A1,1)，則數據元素Ai,j的地

33、址是 LOC(A1,1)+(n(i-1)+(j-1)k 。5、有一個10階的對稱矩陣，采用以行優先的壓縮存儲方式，已知元素A1,1的地址為1，則元素A8,5的地址是 33 ，元素A5,8的地址是 33 。6、廣義表(a,(a,b),d,e,(i,j),k)的長度是 5 ，深度是 3 。二、單選題1、給出字符串A=abcd，它的子串個數是 C 。 A、10 B、9 C、11 D、142、給出兩個串A=ABCDE，B=ABCdE，它們的關系是不是 A 。 A、B串大于A串 B、B串等于A串 C、B串小于A串 D、B串是A串的子串 3、設有兩個串A和B，求B在A中首次出現的位置的操作稱作 C 。 A

34、、連接 B、求串長 C、模式匹配 D、求子串 4、設串S1=ABCDEFG，串S2=PQRST，函數con(x,y)返回x和y串的連接串，函數subs(s,i,j) 返回串s的從序號i的字符開始的j個字符組成的子串，而函數len(s) 則返回串s 的長度。那么，表達式con(subs(S1,2,len(S2),subs(S1,len(S2),2)的結果串是 D 。 A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 5、數組通常具有的兩種基本操作是 C 。 A、建立與刪除 B、索引與修改 C、查找與修改 D、查找與索引 6、在數組A中，每個數據元素Ai,j的長度為3個字節

35、，數組A的行下標i從1到8，而列下標j從1到10，從首地址SA開始連續存放在存儲器中，若該數組按行優先存放時，數據元素A8,5的起始地址為 D 。 A、SA+141 B、SA+144 C、SA+225 D、SA+2227.設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占一個地址空間，則a85的地址為（B ）。A. 13 B. 33 C. 18 D. 40 E.12 8. 將一個A100100的三對角矩陣，按行優先存入一維數組B1298中，A中元素A6665（即該元素下標i=66，j=65），在B數組中的位置K為（ A ）。A. 198

36、B. 195 C. 1979. 若對n階對稱矩陣A以行序為主序方式將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數組B1.(n(n+1)/2中，則在B中確定aij（i<j）的位置k的關系為( A )。A. i*(i-1)/2+j B. j*(j-1)/2+i C. i*(i+1)/2+j D. j*(j+1)/2+i10. 對稀疏矩陣進行壓縮存儲目的是（ C ）。A便于進行矩陣運算 B便于輸入和輸出 C節省存儲空間 D降低運算的時間復雜度11. 已知廣義表LS(a,b,c),(d,e,f),運用head和tail函數取出LS中原子e的運算是( C )。 A. head(tai

37、l(LS) B. tail(head(LS)C. head(tail(head(tail(LS) D. head(tail(tail(head(LS)12. 廣義表（a,(b,c),d,e）的表頭為（ A ）。 A. a B. a,(b,c) C. (a,(b,c) D. (a)4.24void HString_Concat(HString &t ,HString s1,HString s2) /將堆結構表示的串s1和s2連接為新串t  if(t.ch) free(t.ch);  if(!(t.ch=(char*)malloc(s1.length

38、+s2.length)*sizeof(char);  exit (OVERFLOW); for(i=1;i<=s1.length;i+) t.chi-1=s1.chi-1;  for(j=1;j<=s2.length;j+,i+) t.chi-1=s2.chj-1;  t.length=s1.length+s2.length;/HString_Concat 5.23typedef struct            

39、;     int j;                 int e;                DSElem; typedef struct         

40、60;DSElem dataMAXSIZE;           int cpotMAXROW; /這個向量存儲每一行在二元組中的起始位置            int mu,nu,tu;  DSMatrix; /二元組矩陣類型 Status DSMatrix_Locate(DSMatrix A,int i,int j,int &e)/求二元組矩陣的

41、元素Aij的值e  for(s=A.cpoti;s<A.cpoti+1&&A.datas.j!=j;s+);/注意查找范圍  if(s<A.cpoti+1&&A.datas.j=j) /找到了元素ij      e=A.datas;    return OK;    return ERROR;/DSMatrix_Locate第六章一、 填空題1. 不相交的樹的聚集稱之為 森

42、林 。2. 從概念上講，樹與二叉樹是兩種不同的數據結構，將樹轉化為二叉樹的基本目的是_樹可采用孩子-兄弟鏈表（二叉鏈表）做存儲結構，目的是利用二叉樹的已有算法解決樹的有關問題。3. 深度為k的完全二叉樹至少有2 k-1個結點。至多有2 k-1個結點，若按自上而下，從左到右次序給結點編號（從1開始），則編號最小的葉子結點的編號是2k-2+1。4. 在一棵二叉樹中，度為零的結點的個數為n 0，度為2的結點的個數為 n 2，則有n0=n2+1。5. 一棵二叉樹的第i（i1）層最多有2 i-1個結點；一棵有n（n>0）個結點的滿二叉樹共有（n+1）/2個葉子和（n-1）/2個非終端結點。6. 現

43、有按中序遍歷二叉樹的結果為abc，問有5種不同形態的二叉樹可以得到這一遍歷結果。7. 哈夫曼樹 是帶權路徑最小的二叉樹。8. 前綴編碼是指任一個字符的編碼都 不是 另一個字符編碼的前綴的一種編碼方法，是設計不等長編碼的前提。9. 以給定的數據集合4，5，6，7，10，12，18為結點權值構造的Huffman樹的加權路徑長度是 165 。10. 樹被定義為連通而不具有 回路 的（無向）圖。11. 若一棵根樹的每個結點最多只有 兩個 孩子，且孩子又有 左、右 之分，次序不能顛倒，則稱此根樹為 二叉樹 。12. 高度為k，且有 2k-1 個結點的二叉樹稱為 滿 二叉樹。13. 帶權路徑長度最小的二叉

44、樹稱為最優二叉樹，它又被稱為 Huffman 樹。14. 在一棵根樹中，樹根是 入度 為零的結點，而 出度 為零的結點是 樹葉 結點。15. Huffman樹中，結點的帶權路徑長度是指由 節點 到 樹根 之間的路徑長度與結點權值的乘積。16. 滿二叉樹是指高度為k，且有 2k-1 個結點的二叉樹。二叉樹的每一層i上，最多有 2i-1 個結點。二、單選題1. 具有10個葉結點的二叉樹中有 (B) 個度為2的結點。(A)8(B)9(C)10(D)112 對二叉樹的結點從1開始進行連續編號，要求每個結點的編號大于其左右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，則可采用_（3

45、）次序的遍歷實現編號。（1）先序 （2）中序（3）后序 （4）從根開始按層遍歷3. 由2、3、4、7作為結點權值構造的樹的加權路徑長度 B 。 A、33 B、30 C、36 D、40 4. 高度為6的滿二叉樹，總共有的結點數是 B 。 A、15 B、63 C、20 D、25 5. 下面描述根樹轉換成二叉樹的特性中，正確的是 C 。 A、根樹轉換成的二叉樹是唯一的，二叉樹的根結點有左、右孩子。 B、根樹轉換成的二叉樹是不唯一的，二叉樹的根結點只有左孩子。 C、根樹轉換成的二叉樹是唯一的，二叉樹的根結點只有左孩子。 D、根樹轉換成的二叉樹是不唯一的，二叉樹的根結點有左、右孩子。6. 如圖所示的4棵

46、二叉樹中，不是完全二叉樹的是 C 。 A、 B、 C、 D、 7.某二叉樹先序遍歷的結點序列是abdgcefh，中序遍歷的結點序列是dgbaechf，則其后序遍歷的結點序列是 D 。 A、bdgcefha B、gdbecfha C、bdgaechf D、gdbehfca8. 已知二叉樹按中序遍歷所得到的結點序列為DCBGEAHFIJK， 按后序遍歷所得到的結點序列為DCEGBFHKJIA， 按先序遍歷所得到的結點序列為 ABCDGEIHFJK 。9. 設n，m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是 C 。 A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孫10.

47、二叉樹第i 層結點的結點個數最多是（設根的層數為1） ：A A）2i-1 B）2i-1 C）2i D） 2i-1 11. 樹的后根遍歷序列等同于該樹對應的二叉樹的： B A）先序序列 B）中序序列 C）后序序列12. 樹最適合用來表示_C_。A. 有序數據元素           B. 無序數據元素 C. 元素之間具有分支層次關系的數據  D. 元素之間無聯系的數據13. 由于二叉樹中每個結點的度最大為2，所以二叉樹是一種特殊的樹，這種說法_B_。  A. 正確&#

48、160;         B. 錯誤14. 假定在一棵二叉樹中，雙分支結點數為15，單分支結點數為30個，則葉子結點數為 B   個。  A15        B16     C17     D4715. 按照二叉樹的定義，具有3個結點的不同形狀的二叉樹有_C_種。  A. 3     &

49、#160;  B. 4       C. 5       D. 616. 深度為5的二叉樹至多有_C_個結點。  A. 16      B. 32     C. 31      D. 1017. 對一個滿二叉樹，m個樹葉，n個結點，深度為h，則_D_ 。  A. n=h+m   

50、    B. h+m=2n       C. m=h-1        D. n=2 h-118. 任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序_A_。  A.不發生改變    B.發生改變      C.不能確定     D.以上都不對19. 如果某二叉樹的前根次序遍歷結果為stuwv，中序

51、遍歷為uwtvs，那么該二叉樹的后序為_C_。 A. uwvts        B. vwuts        C. wuvts      D. wutsv20. 二叉樹的前序遍歷序列中，任意一個結點均處在其子女結點的前面，這種說法_A_。 A. 正確         B. 錯誤21. 在一非空二叉樹的中序遍歷序列中，根結點的右邊_A_。  A. 只有右子