復習題庫答案

1、數(shù)據(jù)結(jié)構(gòu)習題習題一一、選擇題1、算法分析的兩個主要方面是： （ B ） A正確性和簡明性 B時間復雜度和空間復雜度C數(shù)據(jù)復雜性和程序復雜性D可讀性和文檔性2、在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（C）。 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邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)3、計算機算法具備輸入、輸出和（C ）等5個特性：A有窮性、確定性和穩(wěn)定性B可行性、可移植性和可擴充性 C有窮性、確定性和可行性D易讀性、穩(wěn)定性和安全性4、算法分析的目的是（C）。 A找出算法的合理性 B研究算法的輸人與輸出關(guān)系 C分析算法的有效性以求改進 D分析算法的易懂性二、填空題1、數(shù)據(jù)結(jié)構(gòu)是一

2、門研究非數(shù)值計算的程序設計問題中計算機的 操作對象 以及它們之間的 關(guān)系 和運算等的學科。 2、線性結(jié)構(gòu)中元素之間存在一對一 的關(guān)系，樹形結(jié)構(gòu)中元素之間存在一對多 的關(guān)系，圖形結(jié)構(gòu)中元素之間存在多對多 的關(guān)系。3、_數(shù)據(jù)項_是數(shù)據(jù)不可分割的最小單元，是具有獨立含義的最小標識單位。例如構(gòu)成一個數(shù)據(jù)元素的字段、域、屬性等都可稱之為_數(shù)據(jù)項_。4、數(shù)據(jù)的_存儲結(jié)構(gòu)_指數(shù)據(jù)元素及其關(guān)系在計算機存儲器內(nèi)的表示。存儲結(jié)構(gòu)_是邏輯結(jié)構(gòu)在計算機里的實現(xiàn)，也稱之為映像。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的結(jié)點時，在查找成功的情況

4、下，需平均比較( D )個元素結(jié)點。 An/2 Bn C(n-1)/2 D(n +1)/23若某表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或刪除最后一個結(jié)點，則下列存儲方式最節(jié)省運算時間的是（A ）：A帶頭結(jié)點的雙循環(huán)鏈表B雙鏈表C給出表頭指針的單循環(huán)鏈表D單鏈表4如果最常用的操作是取第i個結(jié)點及其前驅(qū)結(jié)點，那么下列存儲方式最節(jié)省時間的是（C）：A單鏈表B單循環(huán)鏈表C順序表D雙鏈表5若某線性表最常用的操作是在最后一個結(jié)點之后插入一個結(jié)點或者刪除最后一個結(jié)點，則下列存儲方式最節(jié)省運算時間的是：（A ）A僅有尾指針的單循環(huán)鏈表B雙鏈表C僅有頭結(jié)點的單循環(huán)鏈表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線性表的線性存儲結(jié)構(gòu)優(yōu)于鏈式存儲結(jié)構(gòu)B棧的操作方式是先進先出C隊列的操作方式是先進后出D二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表二、填空題1線性表是具有n個數(shù)據(jù)元素的有限序列。2在單

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

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

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

9、ead )/*在帶頭結(jié)點的單鏈表中計算所有數(shù)據(jù)域為x的結(jié)點的個數(shù)*/linklist *p;int n;p=head->next; /*p指向鏈表的第一個結(jié)點*/n=0;while (p!=NULL)if (p->data=x)n+;p=p->next;return(n);/*返回結(jié)點個數(shù)*/ /*count_list*/2設計一個算法，刪除單鏈表L中值為x的結(jié)點的直接前驅(qū)結(jié)點。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設計一個算法，將一個不帶頭結(jié)點的單鏈表L（至少有一個結(jié)點）逆置，即最后一個結(jié)點變成第一個結(jié)點，原來倒數(shù)第二個結(jié)點變成第二個結(jié)點，如此等等。void reverse_list( linklist * head )/*逆置帶頭結(jié)點的單鏈表*/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結(jié)點插入逆表*/ /*reverse_list*/4在一個帶頭結(jié)點的單鏈表中，頭指針為head，它的數(shù)據(jù)域的類型為整型，而且按由小到大的順序排列，編寫一個算法insertxlist（），在該鏈表中插人值為x的元素，并使該鏈表仍然有序。linklist *insertx_list(linklist *head, int x) /*在帶頭結(jié)點的單鏈表中插入值為x的元素，使該鏈表仍然有序*/linklist *s, *p, *q;s=(linklist *)malloc(sizeof(linklist); /*

12、建立數(shù)據(jù)域為x的結(jié)點*/s->data=x;s->next=NULL;if (head->next=NULL | x<head->next->data ) /*若單鏈表為空或x小于鏈表第一個結(jié)點的數(shù)據(jù)域*/ 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所指結(jié)點的運算是（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的一維數(shù)組來實現(xiàn)循環(huán)隊列，且當前front和rear的值分別為4和1，當從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別是（B）：A3和5B5和3C2和6 D6和26判斷一個循環(huán)隊列Q（最多元素為MaxSize）為空的條件是：（A ）AQ->front=Q->rear BQ->front=（Q->rear +1）%MaxSizeCQ->front!=Q->rearDQ->front

15、!=（Q->rear +1）%MaxSize 7向一個帶頭結(jié)點、棧頂指針為top的鏈棧中插人一個*S結(jié)點的時候，應當執(zhí)行語句（ 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分別為頭指針和尾指針，則插入一個結(jié)點*S的操作是（ C ）。 Afrontfront->next BS->next=rear；rear=S Crear->next=S；re

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

17、進棧的操作是先進后出或后進先出 。3棧（stack）是限定在表尾 一端進行插人或刪除操作的線性表。在棧中，允許插人和刪除操作的一端稱為棧頂_，而另一端稱為棧底_。不含元素的棧稱為_空棧_。4隊列（Queue）也是一種特殊的線性表_，但它與棧不同，隊列中所有的插人均限定在表的一端進行，而所有的刪除則限定在表的另一端進行。允許插人的一端稱為隊尾_，允許刪除的一端稱為隊頭_。5隊列中允許進行刪除的一端稱為隊頭_；允許進行插入的一端稱為_隊尾_。三、問答題1設有一個數(shù)列的輸入順序為abcdef，若采用棧結(jié)構(gòu)，并以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，元素經(jīng)過棧后到達輸出序列，當所有元素均到達輸出序列后，有哪些序列可以作為高級語言的變量名？3假設Q010是一個線性隊列，初始狀態(tài)為front=rear=0，畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化情況，若不能入隊，請指出其元素，并說明理由。（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語言編寫程序判斷讀人的表達式中不同括號是否正確配對，假定讀人的表達式以”#”結(jié)束。#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 中首次出現(xiàn)的位置的運算稱為：（ C ）A求子串B求串長C模式匹配D串連接4設有串S=Computer，則其子串的數(shù)目是（ 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）可以是字母、數(shù)字 字格或其他字符。用雙引號括起來的部分是串值_即串S的內(nèi)容。2串中字符的個數(shù)稱為串的長度_。3不含有任何字符的串稱為空串_，它的長度為_0_。4由一個或多個空格構(gòu)成的串稱為空白串_，它的長度為所含空格的個數(shù)_。5串中任意多個連續(xù)字符組成的子序列稱為該串的字串_；包含字串_的串稱為主串。三、問答題1、現(xiàn)有串s1=

26、ABCD123，s2=abcde，假設函數(shù)con(x,y)返回x和y串的連接串，函數(shù)subs(s,i,j) 返回串s的從序號i的字符開始的j個字符組成的子串，函數(shù)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編寫算法實現(xiàn)將竄S1中的第 i個字符到第 j個字符之間的字符(不包括第 i個字符和第j個字符)之間的字符用串S2替換。假設串的存儲結(jié)構(gòu)為： 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個字符開始到結(jié)束的字符連接到s串*/s.len=k;s.chs.len='0'return(s);習題五一、選擇題 l數(shù)組常用的兩種基本操作是（ D ）。A建立與查找 B刪除與查找 C插人與索引 D查找與修改2對稀疏矩陣進行壓縮存儲，常用的兩種方法是（ B ）。A二元組和散列表 B三元組和十字鑄表 C三角矩陣和對角矩陣 D對角矩陣和十字鏈表3數(shù)組A中，每個數(shù)據(jù)元素的長度為2個字節(jié)，行下標m從1到10，列下標n從1到8，從首地址SA開

29、始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元數(shù)是：（D ）A20B80C240D1604數(shù)組A中，每個數(shù)據(jù)元素的長度為3個字節(jié)，行下標m從1到8，列下標n從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存儲時，元素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現(xiàn)有廣義表L=（(a)，(b),c)，d，e,(i,j),k)），則該廣義表的長度是

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

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寫一個創(chuàng)建稀疏矩陣相應三元組的算法。#define MAXSIZE 1000 /*假設非零元個數(shù)的最大值是1000*/typedef struct int i, j;elemtype v;triple;typedef structtriple dataMAXSIZE+1; /*data0用于存放稀疏矩陣行，列和非零元個數(shù)*/int mu, nu, tu; /*稀疏矩陣行、列和非零元的個數(shù)*/ spmatrix;spmatrix a;void CreatTripleT

33、able (int array_aMN,spmatrix a)/*array_a是一個稀疏矩陣,a是產(chǎn)生的相對應的三元組存儲*/int i,j,k=1;for (i=0;i<M;i+) /*按行優(yōu)先順序掃描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元素個數(shù)*/ 四、程序設計題1假設三元組元素值為整型，寫一個查找三元組元素值為n的算法。習

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

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

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

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

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

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

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

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

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

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

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

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

46、非全零行的行數(shù)等于圖中的頂點數(shù)3采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的： （ 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在圖中，任何兩個數(shù)據(jù)元素之間都可能存在關(guān)系，因此圖的數(shù)據(jù)元素之間是多對多的關(guān)系。2在有n個頂點的有向圖中，至多有 N(N-1) 條邊。3具有10個頂點的無向圖，邊的總數(shù)最多為 45 。4在一個具有n個頂點的無向圖中，要連通全部頂點至少需要 n-1 條邊。 5具有n (n-1)/2條邊的無向圖稱為_無向完全圖_，簡稱為完全圖_，其中n表示無向圖中頂點的個數(shù)，n(n-1)/2是具有n個頂點無向圖所擁有邊的最大數(shù)目_。 6具有n個頂點的有向圖，如果它同時具有n(n-1)條弧，則稱該圖為有向完全圖_，其中n(n-1)是具有n個頂點有向圖所擁有弧的最大數(shù)目_。 7 如果圖中的邊或弧帶有權(quán)，則稱這種圖為網(wǎng)絡_。8頂點v的度定義為_