數(shù)據(jù)結(jié)構(gòu)本試題集

1、數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)2017年5月有得看就不難綜合練習(xí)一一、單項選擇題 1設(shè)有頭指針為head的帶有頭結(jié)點(diǎn)的非空單向循環(huán)鏈表, 指針p指向其尾結(jié)點(diǎn), 要刪除頭結(jié)點(diǎn),并使其仍為單向循環(huán)鏈表,則可利用下述語句head =head->next ;（ ）。 Ap =head; Bp=NULL; Cp->next =head; Dhead=p; 2在一個單鏈表中p指向結(jié)點(diǎn)a, q指向結(jié)點(diǎn)a的直接后繼結(jié)點(diǎn)b，要刪除結(jié)點(diǎn)b，可執(zhí)行（ ）。 Ap->next=q->next ; Bp=q->next; Cp->next=q; Dp->next=q; 3. 以下說

2、法不正確的是 A. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)不必占用連續(xù)的存儲空間 B一種邏輯結(jié)構(gòu)只能有唯一的存儲結(jié)構(gòu) C. 一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu) D線性表的順序存儲結(jié)構(gòu)必須占用連續(xù)的存儲空間4在一個單向鏈表中,在p所指結(jié)點(diǎn)之后插入一個s所指的結(jié)點(diǎn)時，可執(zhí)行（ ）;和p->next=s; Ap= s; B p->next=s->next; Cp=s->next; D s->next=p->next; 5把數(shù)據(jù)存儲到計算機(jī)中，并具體體現(xiàn)( )稱為物理結(jié)構(gòu) 。 A. 數(shù)據(jù)元素間的邏輯關(guān)系B數(shù)據(jù)的處理方法 C數(shù)據(jù)的性質(zhì) D數(shù)據(jù)的運(yùn)算 6設(shè)有一個長度為23的順序表，要刪除第

3、8個元素需移動元素的個數(shù)為（ ）。 A16 B14 C15 D13 7鏈表所具備的特點(diǎn)之一是（ ）。 A可以隨機(jī)訪問任一結(jié)點(diǎn) B需要占用連續(xù)的存儲空間 C插入元素的操作不需要移動元素 D刪除元素的操作需要移動元素8設(shè)一棵有8個葉結(jié)點(diǎn)的二叉樹，度數(shù)為1的結(jié)點(diǎn)有3個,則該樹共有（ ） 個結(jié)點(diǎn)。 A20 B18 C17 D16 9圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 A一對一 B多對多 C一對多 D每一個元素都有一個直接前驅(qū)和一個直接后繼 10一棵具有5層的完全二叉樹，最后一層有4個結(jié)點(diǎn)，則該樹總共有（ ）個結(jié)點(diǎn)。 A14 B15 C19 D18 11元素15，9，11，13按順序依次進(jìn)棧

4、，則該棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A13，11，9，15 B15，9，11，13 C13，11，15，9 D9， 15，13，11 12.設(shè)主串為“FABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。 A. EFaBc B. ABCdE C. DABCC D .FAbcC 13設(shè)有一個14階的對稱矩陣A(第一個元素為a1,1)，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a4,3在一維數(shù)組B中的下標(biāo)是（ ）。 A9 B10 C11 D8 14元素111，113，115，117按順序依次進(jìn)棧，則該

5、棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A117，115，113，111 B111，113，115，117 C113，111，117，115 D117，115，111，113 15在一棵二叉樹中，若編號為8的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為（ ）。 A18 B16 C15 D17 16以下說法不正確的是（ ）。 A棧和隊列都是線性結(jié)構(gòu) B棧的特點(diǎn)是后進(jìn)先出 C. 棧和隊列的特點(diǎn)都是先進(jìn)后出 D隊列的特點(diǎn)是先進(jìn)先出17設(shè)一棵哈夫曼樹共有14個非葉結(jié)點(diǎn)，則該樹總共有（ ）個結(jié)點(diǎn)。 A29 B.27 C30 D28 18設(shè)有一個15階的對稱矩陣A(第一個元素為a1,1)，采用壓縮存

6、儲的方式，將其下三 角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a4,2 在一維數(shù)組B中的下標(biāo)是（ ）。A9 B8 C7 D10 19如圖1所示的一個圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得 到的一種頂點(diǎn)序列為（ ）。 Aabecdf Bacfebd Caebcfd Daedbfc bdfeca圖1 20如圖2所示的一個圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能 得到的一種頂點(diǎn)序列為（ ）。 Aacedbf Bacebfd Caebcfd Daedfcb bdfcea圖2 二、填空題 1. 隊列的特點(diǎn)之一是：元素進(jìn)、出隊的次序是:先進(jìn)_。 2.

7、 序列13,11,14,12,17,15,采用冒泡排序算法,經(jīng)一趟冒泡后,序列的結(jié)果是_。3 _結(jié)構(gòu)中，數(shù)據(jù)元素間存在一對多的關(guān)系。 4. 對16個元素的序列用冒泡排法進(jìn)行排序，通常需要進(jìn)行_趟冒泡。5對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的 三項信息是_ _。 6. 對9個元素的一組記錄（58，35，93，20，12，78，56，41，79）進(jìn)行直接插入排 序(由小到大排序) ，當(dāng)把第7個記錄56插入有序表，為尋找插入位置需比較 _次。7在對11個記錄的序列(12，35, 9, 7 ,2, 11 ,56 , 95 ,37,58 ,60)進(jìn)行直接插入排序時，當(dāng)把第6個

8、記錄11 插入到有序表時，為尋找插入位置，元素間需比較_次。（由小到大排列） 8結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_結(jié)構(gòu)。 9哈希函數(shù)是記錄關(guān)鍵字的值與該記錄_ _之間所構(gòu)造的對應(yīng)關(guān)系。10設(shè)有一棵深度為5的完全二叉樹，第5層上有3個結(jié)點(diǎn)，該樹共有_個結(jié)點(diǎn)。 （根所在結(jié)點(diǎn)為第1層） 1120個元素進(jìn)行冒泡法排序，通常需要進(jìn)行19趟冒泡 ,其中第10趟冒泡共需要進(jìn)行 _ _次元素間的比較。 12 一棵二叉樹中每一個非葉結(jié)點(diǎn)的度數(shù)都為2，共有10個非葉結(jié)點(diǎn)，則該樹共有 _ 個結(jié)點(diǎn)。13一棵有19個結(jié)點(diǎn)的二叉樹,采用鏈?zhǔn)浇Y(jié)構(gòu)存儲,該樹結(jié)構(gòu)中有 _ 個指針 域為空。 14. 序列3,1,7,18,6

9、,9,13,12經(jīng)一趟歸并排序的結(jié)果為_ _ _。15中序遍歷一棵 _樹可得到一個有序序列。 16 一棵有16個葉結(jié)點(diǎn)的哈夫曼樹，則該樹共有_個非葉結(jié)點(diǎn)。17二叉排序樹插入操作中,新插入的結(jié)點(diǎn)總是以樹的_ 結(jié)點(diǎn)被插入的 18_遍歷二叉排序樹可得到一個有序序列。 19. 廣義表的( a , (d,a ,b) , h , (e ,( (i ,j ) ,k ) )深度是_ 。 20. 廣義表( f , h , (a ,b, d, c) , d , e ,( (i ,j ) ,k ) )的長度是_ _。 21. 序列4 , 2 , 5 , 3 , 8 , 6 , 7, 9,采用歸并排序算法(升序),經(jīng)

10、一趟歸并后,序列的結(jié)果 _ _。 22. 廣義表的( h ,c，g, a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ _。 23. 字符串a(chǎn)1=teijing, a2 =tef , a3= teifang, a4=“tefi最小的 是 _。 24設(shè)有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”, 四個串中最 小的是 _ 。 三、綜合題 1設(shè)查找表為 序號1234567891011序列4121819375565778586117 （1）畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹（樹中結(jié)點(diǎn)用下標(biāo)表示）（2）說明成功查找到元

11、素86需要經(jīng)過多少次比較？（3）求在等概率條件下，成功查找的平均比較次數(shù)？2.（1）設(shè)有數(shù)據(jù)集合50，39，17，83，111，14，65，13，91，102，49，依次取 集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。 (2) 一組記錄的關(guān)鍵字序列為（6，9，7，4，5，8），利用堆排序（堆頂元 素 是最小元素）的方法建立初始堆。(要求用完全二叉樹表示)3.(1) 一組記錄的關(guān)鍵字序列為（26，59，36，18，20，25），給出利用堆排序（堆頂 元素是最小元素）的方法建立的初始堆（要求以完全二叉樹描述 ）。 (2) 對關(guān)鍵字序列(26,59,36,18,20,64)采用快速排序，給出以第一個關(guān)鍵字為分割

12、 元素，經(jīng)過一次劃分后的結(jié)果。4. (1) 如下表為一個長度為10的有序表，給出按折半查找對該表進(jìn)行查找的判定樹 (2) 按折半查找對該表進(jìn)行查找，求在等概率情況下查找成功的平均比較次數(shù)。 為了成功查找72 ,給出元素的比較次數(shù)。序號12345678910序列234939182560728455595(1) 以1，2，3 ，6，7，8作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹 (2) 給出具有相應(yīng)權(quán)重值的葉結(jié)點(diǎn)的哈夫曼編碼。四、程序填空題1以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回-1，完成程序中的空格typedef struct int ke

13、y;NODE;int Binary_Search(NODE a , int n, int k) int low, mid, high; low=0; high=n-1; while(_(1)_) mid=(_(2)_) if(amid.key=k) return _(3)_; else if (_(4)_) low=mid+1; else _(5)_; return -1 2.設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲，鏈表頭指針為head,以下程序的功能是 輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data。完成程序中空格部分。#define NULL 0void main( ) NODE *head ,*p ;p

14、=head; /*p為工作指針*/ do printf(“%dn”, _(1)_); _(2)_ ; while(_(3)_); 3.以下程序是前序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、 右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 void Inorder (struct BTreeNode *BT) if(BT!=NULL) _(1)_; _(2)_; Inorder(BT- >right); 利用上述程序?qū)τ覉D進(jìn)行前序遍歷，結(jié)果是_(3)_;eabcdf圖3 4.以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹

15、結(jié)構(gòu)中左、 右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中 空格部分。 void Inorder (struct BTreeNode *BT) if( BT!=NULL) Inorder(BT->left); _(1)_ _(2)_ 5. 順序查找算法如下, 完成程序中空格部分。 int search (NODE a ,int n , int k ) /* 在a0,a1an-1,中查找關(guān)鍵字等于k的記錄，查找成功返回記錄的下標(biāo)，失敗時返回 -1*/ int i=0; while( i< n && ai.key _(1)_)

16、_(2)_ if (_(3)_) return i; else return -1; 綜合練習(xí)一答案 一、單項選擇題1 C 2 A 3 B 4D 5A 6C 7 C 8B 9 B 10C 11 C 12 A 13 A 14D 15D 16C 17 A 18B 19D 20B 二、填空題1先出 211,13,12,14,15,17 3樹型 415 5行下標(biāo) 列下標(biāo) 數(shù)組元素64次 73 8樹形9存儲位置1018111012. 2113 20 14. 1，3，7，18，6，9，12，1315 二叉排序樹161517. 葉18. 中序19.4206 21.2，4，3，5，6，8，7，9223 23.

17、a224. P1 三、綜合題17411852101396圖4(1) 55 18 85 4 19 65 86 12 37 77 117 (2) 3次(3) 平均查找長度 =(1+2*2+3*4+4*4)/11=3 496510291141111713508339圖52(1) (2) 4 , 5 , 7 , 9 , 6 , 8 49575965568圖6 3. (1) 18，20，25，59，26，36 1820255936圖7(2) 20，18，26，36，59，64 7252813647910圖84. (1) (2) (1+2*2+3*4+4*3)/10=29/10 4次5 (1)673861

18、32271512圖9 (2)1 0000 2 00013 0016 017 10 8 11四、程序填空題1.(1) low<=high (2)( low+high)/2 (3) mid; (4) amid.key<k (5) high=mid-1; 2 （1）p->data（2）p=p->next（3）p!=NULL3. （1） printf(“%c”,BT->data) （2）Inorder(BT->left) （3）a b d f e c4 （1） Inorder(BT->right)（2） printf(“%c”,BT->data)5. (

19、1) !=k (2) i+; (3) ai.key= =k綜合練習(xí)二一、單項選擇題1設(shè)頭指針為head的非空的單向循環(huán)鏈表, 指針p指向尾結(jié)點(diǎn),則滿足表達(dá)式（ ） 為真。 Ap->next = =NULL Bp= =NULL Cp->next= =head Dp= =head 2.數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（ ）。 A . 數(shù)據(jù)處理的方法 C . 相關(guān)算法 D. 數(shù)據(jù)元素的類型 D. 數(shù)據(jù)元素間的關(guān)系的表示3一種邏輯結(jié)構(gòu)（ ）。 A可以有不同的存儲結(jié)構(gòu) B只能有唯一的存儲結(jié)構(gòu) C是指某一種數(shù)據(jù)元素之間的存儲關(guān)系 D是指某一種數(shù)據(jù)元素的性質(zhì)4在一個頭指針為head的單向鏈表中

20、，p指向尾結(jié)點(diǎn)，要使該鏈表成為單向循環(huán)鏈表 可執(zhí)行（ ）。 Ap= head->next; B head->next=p; Chead->next=p->next; D p->next=head;5鏈表所具備的特點(diǎn)之一是（ ）。 A可以隨機(jī)訪問任一結(jié)點(diǎn) B占用連續(xù)的存儲空間 C插入刪除元素的操作不需要移動元素結(jié)點(diǎn) D可以通過下標(biāo)對鏈表進(jìn)行直接訪問6元素111，113，115，117按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A117，115，113，111 B111，113，115，117 C117，115，111，113 D113，

21、111，117，115 7線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 A一對一 B一對多 C多對多 D每一個元素都有一個直接前驅(qū)和一個直接后繼 8以下說法正確的是（ ）。 A棧的特點(diǎn)是先進(jìn)后出B棧的特點(diǎn)是先進(jìn)先出 C隊列的特點(diǎn)是先進(jìn)后出 D. 棧和隊列的特點(diǎn)都是先進(jìn)后出 9在一個單向鏈表中p所指結(jié)點(diǎn)之后插入一個s所指的結(jié)點(diǎn)時，可執(zhí)行（ ）。 Ap->next= s; s->next= p->next Bp->next=s->next; Cp=s->next Ds->next=p->next; p->next=s; 10設(shè)有一個20階的對

22、稱矩陣A(第一個元素為a1,1)，采用壓縮存儲的方式，將其下三 角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a6,2 在一維數(shù)組B中的下標(biāo)是（ ）。A24 B17 C16 D23 11元素11，13，15，17按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A17，15，13，11 B11，13，15，17 C17，15，11，13 D13，11，17，15 12設(shè)一棵有2n+1個結(jié)點(diǎn)的二叉樹，除葉結(jié)點(diǎn)外每個結(jié)點(diǎn)度數(shù)都為2，則該樹共有（ ） 個葉結(jié)點(diǎn)。 An Bn+1 Cn+2 Dn-1 13設(shè)有一個20階的對稱矩陣A(第一個元素為a1,1)

23、，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a5,2在一維數(shù)組B中的下標(biāo)是（ ）。 A11 B12 C13 D10 14已知如圖1所示的一個圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能 得到的一種頂點(diǎn)序列為（ ）。 Aabecdf Baecbdf Caebcfd Daedfcb bdfeca 圖115設(shè)一棵哈夫曼樹共有11個非葉結(jié)點(diǎn)，則該樹有（ ）個葉結(jié)點(diǎn)。 A22 B10 C11 D12 16線性表以（ ）方式存儲，能進(jìn)行折半查找。 A關(guān)鍵字有序的順序 B順序 C鏈接 D二叉樹 17一棵具有38個結(jié)點(diǎn)的完全二叉樹，最后一層有（

24、）個結(jié)點(diǎn)。 A7 B5 C6 D8 18一棵具有38個結(jié)點(diǎn)的完全二叉樹，最后一層有（ ）個結(jié)點(diǎn)。 A7 B5 C6 D8 19已知如圖2所示的一個圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 Aabecdf Bacfebd Caebcfd Daedfcb bdfeca圖220 .對一個棧頂指針為top的鏈棧進(jìn)行出棧操作，用變量e保存棧頂元素的值，則執(zhí)行 （ ）。 A. e= top->next; top->data=e; B. top=top->next; e=top->data;C. e=top->data; top=top-

25、>next; D. top=top->next; e=data; 二、填空題1. 字符串a(chǎn)1=BEIJING, a2 =BEF , a3= BEFANG, a4=“BEI最小的 是_ _。2. 數(shù)組a經(jīng)初始化 char a =“English”; a7中存放的是_。3把數(shù)據(jù)存儲到計算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為_ _。 4設(shè)有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”, 四個串中最大的是_。 5設(shè)有一個長度為22的順序表，要刪除第8個元素需移動元素的個數(shù)為_ _。6在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號

26、為_。7在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號為_ _。 8設(shè)有一個長度為20的順序表，要插入一個元素，并作為第8個元素，需移動元素的 個 數(shù)為_。9設(shè)一棵有n個葉結(jié)點(diǎn)的二叉樹，除葉結(jié)點(diǎn)外每個結(jié)點(diǎn)度數(shù)都為2，則該樹共有_ _ 個結(jié)點(diǎn)。 10結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_結(jié)構(gòu)。11在對一組序列 (45,29,87,12,6,63,55,37,78)進(jìn)行直接插入排序時，當(dāng)把第8個記錄37 插 入到有序表時，為尋找插入位置需比較_次。（由小到大排序）12設(shè)有一棵深度為4的完全二叉樹，第四層上有5個結(jié)點(diǎn)，該樹共有_個結(jié)點(diǎn)。 （根所在結(jié)點(diǎn)為第1層）13 n個元素進(jìn)行冒泡法

27、排序，通常需要進(jìn)行_ _趟冒泡。14一棵二叉樹中有n個非葉結(jié)點(diǎn)，每一個非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹共有_ 個葉結(jié)點(diǎn)。15一棵有21個結(jié)點(diǎn)的哈夫曼樹,該樹中有 _ 個葉結(jié)點(diǎn)。16在對一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時，當(dāng)把第7個記錄65 插 入到有序表時，為尋找插入位置需比較_次。(由小到大排序17_遍歷二叉排序樹可得到一個有序序列。18. n個元素進(jìn)行冒泡法排序， 第j趟冒泡要進(jìn)行_ _次元素間的比較。19. 廣義表( a , (a ,b) , d , e ,( (i ,j ) ,k ) )的長度是_。20一棵有n個葉結(jié)點(diǎn)的哈夫曼樹，則該樹共有_

28、個結(jié)點(diǎn)。21. 廣義表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 。 22中序遍歷_可得到一個有序序列。 23. 序列14,12,15,13,18,16,采用冒泡排序算法(升序),經(jīng)一趟冒泡后,序列的結(jié)果 是 _ _。24廣義表( (a ,b) , d , e ,( (i ,j ) ,k ) )的長度是_ 。 三、綜合題1設(shè)查找表為(7,15,21,22,40,58,68,80,88,89,120) ,元素的下標(biāo)依次為1,2,3,，11. （1）畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹（樹中結(jié)點(diǎn)用下標(biāo)表示）（2）說明成功查找到元素40需要經(jīng)過多少次

29、比較？（3）求在等概率條件下，成功查找的平均比較次數(shù)？2. （1）設(shè)有數(shù)據(jù)集合40，29，7，73，101，4，55，2，81，92，39，依次取集合 中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。 (2)一組記錄的關(guān)鍵字序列為（5，8，6，3，4，7），利用堆排序（堆頂元素是最 小元素）的方法建立初始堆。(要求用完全二叉樹表示)3. (1) 一組記錄的關(guān)鍵字序列為（47，80，57，39，41，46），給出利用堆排序（堆頂 元素是最小元素）的方法建立的初始堆（要求以完全二叉樹描述 ）。 (2) 對關(guān)鍵字序列( 47,80,57,39,41,85)采用快速排序，給出以第一個關(guān)鍵字為分割 元素，經(jīng)過一次劃分后的結(jié)

30、果。 (3) 如圖3所示的二叉樹，給出其前序遍歷序列。gfabdec圖3 4 (1) 以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹 (2) 給出上述哈夫曼樹葉結(jié)點(diǎn)的哈夫曼編碼。 (3)一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85），利用快速排序，以第一 個關(guān)鍵字為分割元素，給出經(jīng)過一次劃分后結(jié)果。（由小到大排序）四、程序填空題1以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 efabcd圖4void Inorder (struct BTreeNode *BT)if

31、(BT!=NULL) Inorder(BT->left); （1） ; （2） ;利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是 （3） ; 2.設(shè)線性表為（6，10，16，4），以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。 #define NULL 0 void main( ) NODE a,b,c,d,*head,*p;a.data=6;b.data=10;c.data=16;d.data=4; /*d是尾結(jié)點(diǎn)*/head= （1） ;a.next=&b;b.next=&c;c.next=&d; （2） ; /*以上結(jié)束建表過程*/p=hea

32、d; /*p為工作指針，準(zhǔn)備輸出鏈表*/ do printf(“%dn”, （3） ); （4） ; while( （5） );3以下冒泡法程序?qū)Υ娣旁赼1，a2，an中的序列進(jìn)行排序，完成程序中 的空格部分，其中n是元素個數(shù)，要求按升序排列。void bsort (NODE a , int n) NODE temp; int i,j,flag; for(j=1; （1） ;j+); flag=0; for(i=1; （2） ;i+) if(ai.key>ai+1.key)flag=1; temp=ai; （3） ; （4） ;if(flag= =0)break;程序中flag的功能是（

33、5） 4.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、 右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 efabcd圖5 void Inorder (struct BTreeNode *BT) if(BT!=NULL) （1） ; （2） ; Inorder(BT->right); 利用上述程序?qū)τ覉D進(jìn)行遍歷，結(jié)果是 （3） ;綜合練習(xí)二答案一、單項選擇題1C 2 D 3A 4D 5 C 6C 7 A 8A 9 D 10B 11C 12B 13B 14B 15. D 16A 17. A 18A 19.D 20.C 二、填空題1

34、. a22. 字符串的結(jié)束符3. 物理結(jié)構(gòu)(存儲結(jié)構(gòu))4. p2 5. 1462i+1 7 2i 8. 139. 2n-1 10圖狀 11. 5 1212 13 n-114n+1 15 11 16317 中序18. n-j19. 520.2n-121. 322二叉排序樹23. 12,14,13,15,16,18 244 三、綜合題17411852101396圖6(1) (2)4次39559281410172407329圖7(3)ASL=(1+2*2+3*4+4*4)/11=32(1) (2) 3,4,6,8,5,7 394658567圖8 3(1) 39，41，46，80，47，57 3941

35、46478057圖9(2) 41，39，47，57，80，85(3)abdefcg97589243331518圖104 (1)(2） 2：00004 00015 0018 109 1110 01(3) 31,29,37,47,70,85 四、程序填空題1. （1） printf(“%c”,BT->data) （2） Inorder(BT->right) （3）dbeafc 2 （1）&a（2）d->next=NULL（3）p->data（4）p=p->next（5）p!=NULL3 （1）j<=n-1（2）i<=n-j（3）ai=ai+1（4）

36、ai+1=temp（5）當(dāng)某趟冒泡中沒有出現(xiàn)交換則已排好序，結(jié)束循環(huán)4 （1）Inorder(BT->left)（2） printf(“%c”,BT->data)（3）bedafc綜合練習(xí)三一、單項選擇題 1.數(shù)據(jù)的存儲結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（ ）。 A . 數(shù)據(jù)處理的方法 B. 數(shù)據(jù)元素的類型 C . 相關(guān)算法 D. 數(shù)據(jù)元素間的關(guān)系的表示 2設(shè)有頭指針為head的不帶頭結(jié)點(diǎn)的非空的單向循環(huán)鏈表, 指針p指向其尾結(jié)點(diǎn), 要 刪除第一個結(jié)點(diǎn),則可利用下述語句 head=head->next;和（ ）。 Ap =head; Bp=NULL; Cp->next =head; Dhead=p;3樹狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 A每一個元素都有一個直接前驅(qū)和一個直接后繼 B一對一 C多對多 D一對多 4. 以下說法正確的是( )。 A. 線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)必須占用連續(xù)的存儲空間 B. 一種邏輯結(jié)構(gòu)可以有不同的存儲結(jié)構(gòu) C一種邏輯結(jié)構(gòu)只能有唯一的存儲結(jié)構(gòu) D線性表的順序存儲結(jié)構(gòu)不必占用連續(xù)