1、數據結構習題習題一一、選擇題1、算法分析的兩個主要方面是： （ B ） A正確性和簡明性 B時間復雜度和空間復雜度C數據復雜性和程序復雜性D可讀性和文檔性2、在數據結構中，從邏輯上可以把數據結構分成（C）。 A動態結構和靜態結構 B緊湊結構和非緊湊結構 C線性結構和非線性結構 D邏輯結構和存儲結構3、計算機算法具備輸入、輸出和（C ）等5個特性：A有窮性、確定性和穩定性B可行性、可移植性和可擴充性 C有窮性、確定性和可行性D易讀性、穩定性和安全性4、算法分析的目的是（C）。 A找出算法的合理性 B研究算法的輸人與輸出關系 C分析算法的有效性以求改進 D分析算法的易懂性二、填空題1、數據結構是一

2、門研究非數值計算的程序設計問題中計算機的 操作對象 以及它們之間的 關系 和運算等的學科。 2、線性結構中元素之間存在一對一 的關系，樹形結構中元素之間存在一對多 的關系，圖形結構中元素之間存在多對多 的關系。3、_數據項_是數據不可分割的最小單元，是具有獨立含義的最小標識單位。例如構成一個數據元素的字段、域、屬性等都可稱之為_數據項_。4、數據的_存儲結構_指數據元素及其關系在計算機存儲器內的表示。存儲結構_是邏輯結構在計算機里的實現，也稱之為映像。5、所謂算法（Algorithm）是對特定問題求解方法和步驟的一種描述，它是指令的一組_有限序列_，其中每個指令表示一個或多個操作。 三、問答題

3、 1、用大O形式寫出下面算法的時間復雜度： i0； s=0； while(sn） i+; s+=i; O（n） 2、寫出以下算法的時間復雜度： for（i0; im; i）for（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; j<t; j+） for（k=0；kn；k） cijaik*bkj; O(m×n×t)習題二一、選擇題 1在一個長度為n的順序表中刪除第i個元素（0i<n）時，需要向前移動(A )個元素。 An-i Bn-i+1 Cn-i+1 Di+12從一個具有n個元素的線性表中查找其值等于x的結點時，在查找成功的情況

4、下，需平均比較( D )個元素結點。 An/2 Bn C(n-1)/2 D(n +1)/23若某表最常用的操作是在最后一個結點之后插入一個結點或刪除最后一個結點，則下列存儲方式最節省運算時間的是（A ）：A帶頭結點的雙循環鏈表B雙鏈表C給出表頭指針的單循環鏈表D單鏈表4如果最常用的操作是取第i個結點及其前驅結點，那么下列存儲方式最節省時間的是（C）：A單鏈表B單循環鏈表C順序表D雙鏈表5若某線性表最常用的操作是在最后一個結點之后插入一個結點或者刪除最后一個結點，則下列存儲方式最節省運算時間的是：（A ）A僅有尾指針的單循環鏈表B雙鏈表C僅有頭結點的單循環鏈表D單鏈表6線性表是(A )。 A一個

5、有限序列，可以為空 B一個有限序列，不可以為空 C一個無限序列，可以為空 D一個無限序列，不可以為空7在一個長度為n的順序表中，向第i個元素（0一1n1）之前捕人一個新元素時，需要向后移動(B )個元素。 An-i Bn-i1 Cni1 Di18一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（B）。 A98 B100 C102 D1069. 在以下敘述中，正確的是：（D）A線性表的線性存儲結構優于鏈式存儲結構B棧的操作方式是先進先出C隊列的操作方式是先進后出D二維數組是其數據元素為線性表的線性表二、填空題1線性表是具有n個數據元素的有限序列。2在單

6、鏈表中，要刪除某一個指定的結點，必須找到該結點的 直接前趨 結點。3向一個長度為n的順序表中的第i個數據元素（1in）之前插入一個元素時，需要向后移動 n-i+1 個數據元素。4在雙向鏈表中，每個結點都具有兩個指針域，一個指向直接前趨，另一個指向直接后繼 。5線性表中有且僅有一個開始結點，表中有且僅有一個終端結點，除開始結點外，其他每個元素有巨僅有一個直接前趨_，除終端結點外，其他每個元素有且僅有一個直接后繼_。6線性表的鏈式存儲結構的每一個結點（Node）需要包括兩個部分：一部分用來存放元素的數據信息，稱為結點的數據域；另一部分用來存放元素的指向直接后繼元素的指針(即直接后繼元素的地址信息)

7、，稱為指針域_或鏈域_。7寫出帶頭結點的雙向循環鏈表L為空表的條件(L=L->Next) && (L=L->Prior)。三、問答題1對鏈表設置頭結點的作用是什么？（至少說出兩條好處）由于開始結點的位置被存放在頭結點的指針域中，所以在鏈表的第一個位置上的操作就和在表的其他位置上操作一致，無需進行特殊處理。 無論鏈表是否為空，其頭指針是指向頭結點的非空指針，因此空表和非空表的處理也就一致了。2在單鏈表、雙鏈表中，如果僅知道指針p指向某結點，不知道頭指針，能否將結點*p從相應的鏈表中刪去？（不能）3如果頻繁地對一個線性表進行插入和刪除操作，那么該線性表應該采用何種存儲結

8、構？為什么？（采取鏈式存儲結構）順序存儲：插入或刪除運算不方便，除表尾的位置外，在表的其它位置上進行插入或刪除操作都必須移動大量結點，其效率較低；由于順序表要求占用連續的存儲空間，存儲分配只能預先進行（靜態分配），因此當表長變化較大時，難以確定合適的存儲規模。若按可能達到的最大長度預先分配空間，則可能造成一部分空間長期閑置而得不到充分利用；若事先對表長估計不足，則插入操作可能使表長超過預先分配的存儲空間而造成溢出。四、程序設計題1有一個帶頭結點的單鏈表（不同結點的數據域值可能相同），其頭指針為head，編寫一個函數計算數據域值為x的結點個數。int count_list(linklist *h

9、ead )/*在帶頭結點的單鏈表中計算所有數據域為x的結點的個數*/linklist *p;int n;p=head->next; /*p指向鏈表的第一個結點*/n=0;while (p!=NULL)if (p->data=x)n+;p=p->next;return(n);/*返回結點個數*/ /*count_list*/2設計一個算法，刪除單鏈表L中值為x的結點的直接前驅結點。DeleteNode( Node* L, int x) Node* p,q,r; p = q = r = L; while(p->next ! = NULL) p = p ->next;

10、if(p->data = x) break; r = q; q = p; delete q; r->next = p; 3設計一個算法，將一個不帶頭結點的單鏈表L（至少有一個結點）逆置，即最后一個結點變成第一個結點，原來倒數第二個結點變成第二個結點，如此等等。void reverse_list( linklist * head )/*逆置帶頭結點的單鏈表*/linklist *s, *p;p=head->next;/*p指向線性表的第一個元素*/head->next=NULL; /*初始空表*/while ( p != NULL ) s=p;p=p->next;s

11、->next=head->next;head->next=s; /*將s結點插入逆表*/ /*reverse_list*/4在一個帶頭結點的單鏈表中，頭指針為head，它的數據域的類型為整型，而且按由小到大的順序排列，編寫一個算法insertxlist（），在該鏈表中插人值為x的元素，并使該鏈表仍然有序。linklist *insertx_list(linklist *head, int x) /*在帶頭結點的單鏈表中插入值為x的元素，使該鏈表仍然有序*/linklist *s, *p, *q;s=(linklist *)malloc(sizeof(linklist); /*

12、建立數據域為x的結點*/s->data=x;s->next=NULL;if (head->next=NULL | x<head->next->data ) /*若單鏈表為空或x小于鏈表第一個結點的數據域*/ s->next=head->next;head->next=s;elseq=head->next;p=q->next;while( p != NULL && x>p->data )q=p;p=p->next;s->next=p;q->next=s; /*if*/ /*insert

13、x_list習題三一、選擇題 l一個棧的序列是：a，b，c，d，e，則棧的不可能輸出的序列是（C）。Aa，b，c，d，e Bd，e，c，b，a Cd，c，e，a，b De，d，c，b，a2判定一個棧S（最多元素為MaxSize）為棧滿的條件是：（ D ）AStop!= -1 BStop=-1CStop=MaxSize-1DStop!=MaxSize-13若一進棧序列為1，2，3，n，其出棧序列為P1,P2,P3,Pn，如果Pn=n,則Pi （1i<n）的值為：（ A ）AiBn-i+1C不確定Dn-i4在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則插入s所指結點的運算是（A）Ar-&g

14、t;next=s；r=s；Br->next=s；f=s；Cs->next=r；r=s； Ds->next=f；f=s；5若用一個大小為8的一維數組來實現循環隊列，且當前front和rear的值分別為4和1，當從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別是（B）：A3和5B5和3C2和6 D6和26判斷一個循環隊列Q（最多元素為MaxSize）為空的條件是：（A ）AQ->front=Q->rear BQ->front=（Q->rear +1）%MaxSizeCQ->front!=Q->rearDQ->front

15、!=（Q->rear +1）%MaxSize 7向一個帶頭結點、棧頂指針為top的鏈棧中插人一個*S結點的時候，應當執行語句（ C ）。 Atop->next=S； BS->next=top；top=S； CS->next=top->next；top->next=S； DS->next=top；top=S->next；8在一個鏈隊列中，假定front和rear分別為頭指針和尾指針，則插入一個結點*S的操作是（ C ）。 Afrontfront->next BS->next=rear；rear=S Crear->next=S；re

16、ar=S DS->next=front；frontS9棧與隊列都是（C ）。 A鏈式存儲的線性結構 B鏈式存儲的非線性結構 C限制存取點的線性結構 D限制存取點的非線性結構10若進棧序列為l，2，3，4，則（ C ）不可能是一個出棧序列。 A3，2，4，1 Bl，2，3，4 C4，2，3，1 D4，3，2，l11在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫人該緩沖區，而打印機則從該緩沖區中取走數據打印。該緩沖區應該是一個（ B ）結構。 A堆棧 B隊列 C數組 D線性表二、填空題 1棧和隊列的共同點是都是限制存取點的線性結構。2通常元素

17、進棧的操作是先進后出或后進先出 。3棧（stack）是限定在表尾 一端進行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為棧頂_，而另一端稱為棧底_。不含元素的棧稱為_空棧_。4隊列（Queue）也是一種特殊的線性表_，但它與棧不同，隊列中所有的插人均限定在表的一端進行，而所有的刪除則限定在表的另一端進行。允許插人的一端稱為隊尾_，允許刪除的一端稱為隊頭_。5隊列中允許進行刪除的一端稱為隊頭_；允許進行插入的一端稱為_隊尾_。三、問答題1設有一個數列的輸入順序為abcdef，若采用棧結構，并以J和C分別表示進棧和出棧操作，試問下列輸出序列是否是合法序列？如是，請用進棧和出棧操作表示

18、其合法序列。（1）能否得到輸出順序為cbefda的序列？J(a),J(b),J(c),C( ),C( ),J(d),J(e),C( ),J(f),C( ),C( ),C( )（2）能否得到輸出順序為aedfbc154623的序列？不能2設輸入元素為4、5、6、B、A，入棧次序為456BA，元素經過棧后到達輸出序列，當所有元素均到達輸出序列后，有哪些序列可以作為高級語言的變量名？3假設Q010是一個線性隊列，初始狀態為front=rear=0，畫出做完下列操作后隊列的頭尾指針的狀態變化情況，若不能入隊，請指出其元素，并說明理由。（1）d，e，b，g，h入隊（2）d，e出隊（3）i，j，k，l，m

19、入隊（4）b 出隊（5）n，o，p入隊4設有4個元素A、B、C和D進棧，給出它們所有可能的出棧秩序。14種A、B、C、D A、B、D、C A、C、B、D A、C、D、B A、D、C、BB、A、C、D B、A、D、C B、C、A、D B、C、D、A B、D、C、AC、B、A、D C、B、D、A C、D、B、A D、C、B、A四、程序設計題1假設表達式中有三種括號：圓括號“（）”、方括號“ ”和花括號“ ”用C語言編寫程序判斷讀人的表達式中不同括號是否正確配對，假定讀人的表達式以”#”結束。#include "stdio.h"#include "stdlib.h&qu

20、ot;#define FALSE 0#define TRUE 1#define LEN sizeof( struct node )struct nodechar data;struct node *next;typedef struct node *stack;void push_stack(stack *, char );int pop_stack(stack *);void main()stack s;int valid=TRUE;char ch,symble;symble=getchar();s=NULL;push_stack(&s, '#');while (sy

21、mble != '#' ) && (valid =TRUE) )if ( symble !='(' && symble !=')' && symble != '' && symble != '' && symble !='' && symble != '' )symble=getchar();else if (symble='(' | symble='' |

22、 symble='' )push_stack(&s, symble );symble=getchar();else if ( s=NULL )valid=FALSE;elsech=pop_stack(&s);if ( (ch='(' && symble=')') | (ch='' && symble='') | ch=('' && symble='') )valid=TRUE;symble=getchar();elsev

23、alid=FALSE;if ( valid = TRUE )printf(" The string is valid. n");elseprintf("The string is valid. n");void push_stack( stack *topptr, char ch )stack newptr;newptr=(struct node * ) malloc( LEN );newptr->data=ch;newptr->next=*topptr;*topptr=newptr;int pop_stack( stack topptr )

24、stack tempptr;char popvalue;if (topptr!=NULL )tempptr=topptr;popvalue=topptr->data;topptr=topptr->next;free( tempptr );return popvalue;else return 0;習題四一、選擇項4設有兩個串 S2，S1，那么求串S2在S1 中首次出現的位置的運算稱為：（ C ）A求子串B求串長C模式匹配D串連接4設有串S=Computer，則其子串的數目是（ B ）。 A36 B37 C8 D94下列是C語言中“ASDF567HJKL”子串的是：（ C ）AASD

25、FBDF56C“F567HJ”D“DFHJ”5空串與空格串（ B ）。 A相同 B不相同 C可能相同 D無法確定二、境空題1串是由零個或多個字符組成的有限序列。通常記作：s“c1，c2，cn”(n=>0)，其中，S稱為串名_；串中的Ci（1<=i<=n）可以是字母、數字 字格或其他字符。用雙引號括起來的部分是串值_即串S的內容。2串中字符的個數稱為串的長度_。3不含有任何字符的串稱為空串_，它的長度為_0_。4由一個或多個空格構成的串稱為空白串_，它的長度為所含空格的個數_。5串中任意多個連續字符組成的子序列稱為該串的字串_；包含字串_的串稱為主串。三、問答題1、現有串s1=

26、ABCD123，s2=abcde，假設函數con(x,y)返回x和y串的連接串，函數subs(s,i,j) 返回串s的從序號i的字符開始的j個字符組成的子串，函數len(s)返回串s的長度，求：（1）L1=subs(s1,2,len(s2) ( BCD12）（2）L2=subs(s1,len(s2),2) ( 12)(3)con(L1,L2) (ABCD123abcde)四、程序設計題l編寫算法實現將竄S1中的第 i個字符到第 j個字符之間的字符(不包括第 i個字符和第j個字符)之間的字符用串S2替換。假設串的存儲結構為： define MAXSIZE 81 struct string int

27、 len； char chMAXSIZE； stringtype；void replace (stringtype s1, int i, int j, stringtype s2)stringtype s100;int h,k;if ( i<=h && i<s1.len && j<s1.len )for (h=1; h<=i; h+ )s.chh=s1.chh;/*把s1的前i個字符賦值給s*/s.len=i;h=1;while(h<s2.len)/*連接串s2*/s.chs.len+h=s2.chh;h+;s.len=s.len+

28、s2.len;for ( k=s.len+1; h=j; h<=s1.len; h+,k+ )s.chk=s1.chh; /*將s1串中從第j個字符開始到結束的字符連接到s串*/s.len=k;s.chs.len='0'return(s);習題五一、選擇題 l數組常用的兩種基本操作是（ D ）。A建立與查找 B刪除與查找 C插人與索引 D查找與修改2對稀疏矩陣進行壓縮存儲，常用的兩種方法是（ B ）。A二元組和散列表 B三元組和十字鑄表 C三角矩陣和對角矩陣 D對角矩陣和十字鏈表3數組A中，每個數據元素的長度為2個字節，行下標m從1到10，列下標n從1到8，從首地址SA開

29、始連續存放在存儲器內，存放該數組至少需要的單元數是：（D ）A20B80C240D1604數組A中，每個數據元素的長度為3個字節，行下標m從1到8，列下標n從1到10，從首地址SA開始連續存放在存儲器內，該數組按行存儲時，元素A83的起始地址是：（D） ASA+222BSA+141CSA+44DSA+2195若廣義表L滿足Head（L）= Tail（L），則廣義表L為：（ A ）A（）B（）C（），（）D（），（），（）6廣義表(a)的表頭是（ C ）。 A（ ） Ba C（a） D（a）7廣義表（a）的表尾是（ A ）。 A（） Ba C（a） D（a）8廣義表（a），a）的表頭是（ C ）

30、。 A（ ） Ba C（a） D（a）9廣義表（a），a）的表尾是（ C ）。 A( ) Ba C（a） D（a）10廣義表（a，b，c）的表頭是（ A ）。 Aa B（a） Ca，b D（a，b）11廣義表（a，b，c）的表尾是（ B ）。 Ab，c B（b，c） ab，c D（a，b，c）二、填空題9 head（），（）是 （） ，tail（），（）是 （） ，表的長度是2 。10 head（(a)，(b),c)，(d)）是 （a） ，tail（(a)，(b),c)，(d)）是(b),c),(d) 。11現有廣義表L=（(a)，(b),c)，d，e,(i,j),k)），則該廣義表的長度是

31、5 ，深度是 3 。1數組（array）是n（n1）個相同類型數據的有序組合，數組中的數據是按順序存儲在一塊_地址連續_的存儲單元中。2數組中的每一個數據通常稱為數組元素_，_數組元素_用下標區分，其中下標的個數由數組的維數決定。3廣義表是n（n>=0）個元素的序列。記作：A（a1，a2，an），其中，A是廣義表的名稱，n是它的長度_，當n=0的時候稱為空表_。4廣義表的深度一般定義為廣義表元素最大的層數_，或者說是廣義表括號的層數_。利用遞歸的定義，廣義表的深度就是所有子表中最大深度加1_。三、問答題1現有一個稀疏矩陣如下圖所示，寫出其對應的三元組表示，并求出其轉置矩陣的三元組表示。（

32、1,2,2），（2，3，-3），（3,1,1），（3,4,4）（1,3,1），（2,1,2）,(3,2,-3),(4,3,4)）2寫一個創建稀疏矩陣相應三元組的算法。#define MAXSIZE 1000 /*假設非零元個數的最大值是1000*/typedef struct int i, j;elemtype v;triple;typedef structtriple dataMAXSIZE+1; /*data0用于存放稀疏矩陣行，列和非零元個數*/int mu, nu, tu; /*稀疏矩陣行、列和非零元的個數*/ spmatrix;spmatrix a;void CreatTripleT

33、able (int array_aMN,spmatrix a)/*array_a是一個稀疏矩陣,a是產生的相對應的三元組存儲*/int i,j,k=1;for (i=0;i<M;i+) /*按行優先順序掃描array_a的元素,不為0者存入B中*/for (j=0;j<N;j+)if (array_aij!=0)a.datak.i=i;a.datak.j=j;a.datak.v = array_aij; k+;a.data00=M; a.data01=N;a.data02=k-1;/*存入非0元素個數*/ 四、程序設計題1假設三元組元素值為整型，寫一個查找三元組元素值為n的算法。習

34、題六一、選擇題1設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含節點數至少有：（ D ）A2hB2h+1 Ch+1 D2h-12現有一二叉樹，若其先序遍歷序列為ABCDE，中序遍歷序列為CBDAE，那么其后序遍歷序列為：（ D ）ABDAECBEDCBACDABECDCDBEA3在線索化二叉樹中，t所指結點沒有左子樹的充要條件是：（ D ）At->left=NULLBt->left=0Ct->ltag=1 Dt->left=NULL且 t->ltag=14設深度為h的二叉樹上只有葉子結點和同時具有左右子樹的結點，則此類二叉樹中所包含的結點數目至少

35、為（ D ）。 A2h B2h C2h1 D2h-l5二叉村第k層上最多有（ C ）個結點。 A2k B2k-1 C2k-1 D2k-16二叉樹的深度為k，則二叉樹最多有（ D ）個結點。 A2k B2k-1 C2k-1 D2k -17設某一二叉樹先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹后序遍歷的順序是（ C ）。 Aabdec Bdebac Cdebca Dabedc8設某一二叉樹中序遍歷為badce，后序遍歷為bdeca，則該三叉樹先序遍歷的順序是（D ）。 Aadbec Bdecab Cdebac Dabode9N個結點的線索二叉樹中，線索的數目是（B ）。 AN-1 BN

36、1 C2N D2N110將一棵樹T轉換為一棵二叉樹T2，則T的先序遍歷是T2的（ A ）。A先序 B中序 C后序 D無法確定11將一棵樹T轉換為一棵二叉樹T2，則T的后序遍歷是T2的（B ）。A先序 B中序 C后序 D無法碉定12 設一棵二叉樹度2的結點數是7，度為1的結點數是6，則葉子結點數是（C ）。A6 B7 C8 D913一棵非空的二叉樹，先序遍歷與后序遍歷正好相反，則該二叉樹滿足（ C ）。 A無左孩子 B無右孩子 C只有一個葉子結點 D任意二叉樹 14線索二叉樹是一種（ D ）。 A邏輯結構 B線性結構 C邏輯和線性結構 D物理結構 15權值為l，2，6，8的四個結點構成的哈夫曼樹

37、的帶權路徑長度是（ A ）。 A29 B31 C17 D20二、填空題 1樹(Tree)是n(n0)個結點的_有限_集。 2深度為5的二叉樹至多有31 個結點。3樹中任意結點允許有零個或多個孩子結點，除根結點以外,其余結點都有 雙親結點。4在一棵二叉樹中，度為零的結點個數為n0，度為2的結點個數為n2,那么n0=n2+1 。 5結點的度是指結點所擁有的子樹的數目_。 6一個結點的子樹中的任一結點都稱為該結點的子孫結點_。 7從根到該結點所經分支上的所有結點稱為該結點的祖先結點_。 8具有同一雙親_的結點互稱為兄弟結點，簡稱為兄弟。9從根結點開始定義，根為_第一_層，根的孩子為_第二_層，依次往

38、下類推，若某結點在第k層，則其子樹的根就在_第k+1_層。 10如果樹中各結點的各子樹無排列順序，即可以互換位置，則稱為該樹為無序樹 11二又樹（Binary Tree）是結點的有限集合，這個集合或者是空，或者是由一個根結點和兩棵互不相交_的稱為_左子樹_和_右子樹_的二叉樹構成。 12二叉樹第i層上最多有_2*i-1_個結點。 13深度為k的二又樹最多有_個結點(kl)。 14在任意二叉樹中，葉子結點的數目(即度為0的結點數)等于度為2的結點數加1_。15一棵深度為k且具有2k-1個結點的二叉樹稱為滿二叉樹 ，這類二叉樹的特點是，二叉樹中每一層結點的個數都是_最大結點的個數。16_完全二叉樹

39、是那種在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者所缺少的結點都在右邊。 17具有n個結點的完全二叉樹的深度是_。 18先序遍歷二叉樹的操作定義為：若二叉樹為空，則為空操作；否則進行如下操作：訪問二叉樹根結點_；先序遍歷二叉樹左子樹_；先序遍歷二叉樹_右子樹_。 19中序遍歷二叉樹的操作定義為：若二叉樹為空，則為空操作；否則進行如下操作：中序遍歷二叉樹_左子樹_；訪問二又樹_根結點_；中序遍歷二又樹_右子樹_。 20后序遍歷二叉樹的操作定義為：若二叉樹為空，則為空操作；否則進行如下操作：后序遍歷二叉樹_左子樹_；后序遍歷二叉樹_右子樹_；訪問二叉樹_根結點_。

40、21線索二叉樹（Threaded Binary Tree）是充分利用二義鏈表的 n+1個空的指針域作為線索來標志每一個結點的前驅_和_后繼_信息。當某個結點有左孩子的時候，使其_左指針域_指向其左孩子，無左孩子的時候，使其左指針域指向該結點的直接前驅結點_；當某個結點有有孩子的時候，使其右指針域指向該結點的右孩子_，無右孩子的時候，使其有指針域指向該結點的直接后繼結點_。 22線索二叉樹的線索鏈表中，指向結點前驅和后繼的指針稱為線索_；加上線索的二叉樹稱為線索二叉樹_；對二叉樹以某種次序進行遍歷使其成為線索二叉樹的過程稱為線索化_。 23哈夫曼樹（Huffman Tree）又稱最優二叉樹 。它

41、是n個帶權葉子結點構成的所有二叉樹中，帶權路徑長度WPL_最小的二叉樹_。 三、問答題1一棵樹表達成如下形式：DA，B，C，D，E，F，G， H，I，J，K，L，M，N，OR=A，B，A，C，A，D，B，E，B，F，C，G，D，H，D，I，D，J，K，F，K，L，F，M，I，N，I，O其中D為結點集合，R為邊的集合。請根據以上內容回答以下問題：(1) 畫出這棵樹。(2) 該樹的根結點是哪一個？(3) 哪些是葉子結點？(4) F結點的雙親是誰？(5) F結點的祖先是哪些？(6) F結點的孩子是哪些？(7) F結點的兄弟是哪些？(8) F結點的堂兄弟是哪些？(9) F結點的度是多少？(10)F結點

42、的層次是多少？(11)D結點的子孫有哪些？(12) 以結點D為根的子樹度是多少？(13) 以結點D為根的子樹層是多少？(14) 該樹的層是多少？(15) 該樹的度是多少？2畫出圖6-1中樹的二叉樹表示形式。 （a） （b） （c） 圖6-l3已知某二叉樹的先序遍歷的結果是：A，B，D，QC，E，H，L，I，K，M，F和J，它的中序遍歷的結果是：QD，B，A，L，H，E，K，LM，C，F和J，請畫出這棵二叉樹，并且寫出該二叉樹后序通歷的結果。4設A、B、C、D、E、F六個字母出現的概率分別為7,19,2,6,32,3，構建哈夫曼樹（請按左子樹根結點的權小于等于右子樹根結點的權的次序構造），計算出

43、帶權路徑長度WPL，并設計每個字母的哈夫曼編碼5假設一棵二叉樹的后序序列為DCEGBFHKJIA，中序序列為DCBGEAHFIJK，請完成下列操作：（1）畫出該二叉樹；(2)寫出該二叉樹的先序遍歷序列；（3）畫出該二叉樹的中序遍歷線索二叉樹。6假設一棵二叉樹的先序序列為ABDGCEHLIKMFJ，中序序列為GDBALHEKIMCFJ，請完成下列操作。(1)畫出該二叉樹；(2)寫出該二叉樹的后序遍歷序列；(3)畫出該二叉樹的中序遍歷線索二叉樹。7假設通訊電文中只用到A，B，C，D，E，F六個字母，它們在電文中出現的相對頻率分別為：7，2，15，9，4，19，要求畫出哈夫曼樹（請按左子樹根結點的權

44、小于等于右子樹根結點的權的次序構造），并計算出帶權路徑長度WPL，試設計每個字母的哈夫曼編碼。8有七個帶權結點,其權值分別為2,6,7,1,5,9,13,試以它們為葉子結點構造一棵哈夫曼樹（請按照每個結點的左子樹根結點的權小于等于右子樹根結點的權的次序構造）,并計算出帶權路徑長度WPL。9假設一棵哈夫曼樹共有n0個葉子結點，試證明樹中共有2no-l個結點。10假設通信用的報文由9個字母A、B、C、D、E、F、G、H和I構成，它們出現的頻率分別是：10、20、5、15、8、2、3、7和30。請用這9個字母出現得頻率作為權值求：（l）設計一棵哈夫曼樹。（2）計算其帶權路徑長度WPL值。（3）寫出每

45、個字符的哈夫曼編碼。四、程序設計題 1. 自己設計一棵二叉樹，編寫一個完整的程序，輸出該二叉樹的先序、中序和后序序列。（程序中應包括二叉樹的生成函數，先序、中序、后序遍歷函數）。2已知一棵二叉樹的先序遍歷序列和中序遍歷序列，請寫出根據二又樹先序遍歷序列和中序遍歷序列構造一棵二叉樹的算法。習題七一、選擇題 1在一個無向圖G中，所有頂點的度數之和等于所有邊數之和的（ C ）倍。 Al/2 B1 C2 D42對某個無向圖的鄰接矩陣來說：（A ）A第i行上的非零元素的個數和第i列上的非零元素的個數一定相等B矩陣中的非零元素的個數等于圖中的邊數C第i行上、第i列上非零元素的總數等于頂點Vi的度數D矩陣中

46、非全零行的行數等于圖中的頂點數3采用鄰接表存儲的圖的深度優先遍歷算法類似于二叉樹的： （ A ）A先序遍歷 B中序遍歷 C后序遍歷 D按層遍歷4在一個具有n個頂點的無向圖中，要連通全部頂點至少需要 條邊： （ A ）An-1BnCn+1Dn/25在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的（B ）倍。 Al/2 B1 C2 D4 6一個具有n個頂點的無向圖包含（ C ）條邊。 An Bn1 Cn-1 Dn/2 7一個具有n個頂點的無向完全圖包含（ C ）條邊。 An(n-l) Bn(n+l) Cn(n-l)/2 Dn(n-l)/2 8. 一個具有n個頂點的有向完全圖包含（ A ）

47、條邊。 An(n-1) Bn(n+l) Cn(n-l)/2 Dn(n+l)/2 9無向圖的鄰接矩陣是一個（ A ）。 A對稱矩陣 B零矩陣 C上三角矩陣 D對角矩陣二、填空題1在圖中，任何兩個數據元素之間都可能存在關系，因此圖的數據元素之間是多對多的關系。2在有n個頂點的有向圖中，至多有 N(N-1) 條邊。3具有10個頂點的無向圖，邊的總數最多為 45 。4在一個具有n個頂點的無向圖中，要連通全部頂點至少需要 n-1 條邊。 5具有n (n-1)/2條邊的無向圖稱為_無向完全圖_，簡稱為完全圖_，其中n表示無向圖中頂點的個數，n(n-1)/2是具有n個頂點無向圖所擁有邊的最大數目_。 6具有n個頂點的有向圖，如果它同時具有n(n-1)條弧，則稱該圖為有向完全圖_，其中n(n-1)是具有n個頂點有向圖所擁有弧的最大數目_。 7 如果圖中的邊或弧帶有權，則稱這種圖為網絡_。8頂點v的度定義為_