數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(xí)

1、-作者xxxx-日期xxxx數(shù)據(jù)結(jié)構(gòu)(本)期末綜合練習(xí)【精品文檔】數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)綜合練習(xí)一一、單項(xiàng)選擇題 1設(shè)有頭指針為head的帶有頭結(jié)點(diǎn)的非空單向循環(huán)鏈表, 指針p指向其尾結(jié)點(diǎn), 要?jiǎng)h除頭結(jié)點(diǎn),并使其仍為單向循環(huán)鏈表,則可利用下述語(yǔ)句head =head-next ;（ ）。 Ap =head; Bp=NULL; Cp-next =head; Dhead=p; 2在一個(gè)單鏈表中p指向結(jié)點(diǎn)a, q指向結(jié)點(diǎn)a的直接后繼結(jié)點(diǎn)b，要?jiǎng)h除結(jié)點(diǎn)b，可執(zhí)行（ ）。 Ap-next=q-next ; Bp=q-next; Cp-next=q; Dp-next=q; 3. 以下說(shuō)法不正確的是 A

2、. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間 B一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu) C. 一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu) D線性表的順序存儲(chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間4在一個(gè)單向鏈表中,在p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ ）;和p-next=s; Ap= s; B p-next=s-next; Cp=s-next; D s-next=p-next; 5把數(shù)據(jù)存儲(chǔ)到計(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è)有一個(gè)長(zhǎng)度為23的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（ ）。 A16 B14 C15 D1

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

4、3，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è)有一個(gè)14階的對(duì)稱矩陣A(第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a4,3在一維數(shù)組B中的下標(biāo)是（ ）。 A9 B10 C11 D8 14元素111，113，115，117按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 A117，

5、115，113，111 B111，113，115，117 C113，111，117，115 D117，115，111，113 15在一棵二叉樹(shù)中，若編號(hào)為8的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為（ ）。 A18 B16 C15 D17 16以下說(shuō)法不正確的是（ ）。 A棧和隊(duì)列都是線性結(jié)構(gòu) B棧的特點(diǎn)是后進(jìn)先出 C. 棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出 D隊(duì)列的特點(diǎn)是先進(jìn)先出17設(shè)一棵哈夫曼樹(shù)共有14個(gè)非葉結(jié)點(diǎn)，則該樹(shù)總共有（ ）個(gè)結(jié)點(diǎn)。 A29 B.27 C30 D28 18設(shè)有一個(gè)15階的對(duì)稱矩陣A(第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三 角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下

6、標(biāo)從1開(kāi)始），則矩陣中元素a4,2 在一維數(shù)組B中的下標(biāo)是（ ）。A9 B8 C7 D10 19如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得 到的一種頂點(diǎn)序列為（ ）。 Aabecdf Bacfebd Caebcfd Daedbfc bdfeca圖1 20如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能 得到的一種頂點(diǎn)序列為（ ）。 Aacedbf Bacebfd Caebcfd Daedfcb bdfcea圖2 二、填空題 1. 隊(duì)列的特點(diǎn)之一是：元素進(jìn)、出隊(duì)的次序是:先進(jìn)_。 2. 序列13,11,14,12,17,15,采用冒泡排序算法,經(jīng)一

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

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

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

10、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”, 四個(gè)串中最 小的是 _ 。 三、綜合題 1設(shè)查找表為 序號(hào)1234567891011序列4121819375565778586117 （1）畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)（樹(shù)中結(jié)點(diǎn)用下標(biāo)表示）（2）說(shuō)明成功查找到元素86需要經(jīng)過(guò)多少次比較？（3）求在等概率條件下，成功查找的平均

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

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

13、, 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 1.(1) low=high (2)( low+high)/2 (3) mid; (4) amid.keydata （2）p=p-next （3）p!=NULL3.以下程序是前序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、 右指針域分別為left和right，數(shù)據(jù)域dat

14、a為字符型，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 3. （1） printf(“%c”,BT-data) （2）Inorder(BT-left) （3）a b d f e c4.以下程序是后序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、 右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。完成程序中 空格部分。 void Inorder (

15、struct BTreeNode *BT) if( BT!=NULL) Inorder(BT-left); _(1)_ _(2)_ 4 （1） Inorder(BT-right) （2） printf(“%c”,BT-data) 5. 順序查找算法如下, 完成程序中空格部分。 int search (NODE a ,int n , int k ) /* 在a0,a1an-1,中查找關(guān)鍵字等于k的記錄，查找成功返回記錄的下標(biāo)，失敗時(shí)返回 -1*/ int i=0; while( inext = =NULL Bp= =NULL Cp-next= =head Dp= =head 2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包

16、括數(shù)據(jù)元素的表示和（ ）。 A . 數(shù)據(jù)處理的方法 C . 相關(guān)算法 D. 數(shù)據(jù)元素的類型 D. 數(shù)據(jù)元素間的關(guān)系的表示3一種邏輯結(jié)構(gòu)（ ）。 A可以有不同的存儲(chǔ)結(jié)構(gòu) B只能有唯一的存儲(chǔ)結(jié)構(gòu) C是指某一種數(shù)據(jù)元素之間的存儲(chǔ)關(guān)系 D是指某一種數(shù)據(jù)元素的性質(zhì)4在一個(gè)頭指針為head的單向鏈表中，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ī)訪問(wèn)任一結(jié)點(diǎn) B占用連續(xù)的存儲(chǔ)空間 C插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn) D可

17、以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wè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，111，117，115 7線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 A一對(duì)一 B一對(duì)多 C多對(duì)多 D每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 8以下說(shuō)法正確的是（ ）。 A棧的特點(diǎn)是先進(jìn)后出B棧的特點(diǎn)是先進(jìn)先出 C隊(duì)列的特點(diǎn)是先進(jìn)后出 D. 棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出 9在一個(gè)單向鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行（ ）。 A

18、p-next= s; s-next= p-next Bp-next=s-next; Cp=s-next Ds-next=p-next; p-next=s; 10設(shè)有一個(gè)20階的對(duì)稱矩陣A(第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三 角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素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è)一

19、棵有2n+1個(gè)結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，則該樹(shù)共有（ ） 個(gè)葉結(jié)點(diǎn)。 An Bn+1 Cn+2 Dn-1 13設(shè)有一個(gè)20階的對(duì)稱矩陣A(第一個(gè)元素為a1,1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），則矩陣中元素a5,2在一維數(shù)組B中的下標(biāo)是（ ）。 A11 B12 C13 D10 14已知如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能 得到的一種頂點(diǎn)序列為（ ）。 Aabecdf Baecbdf Caebcfd Daedfcb bdfeca 圖115設(shè)一棵哈夫曼樹(shù)共有11個(gè)非葉結(jié)點(diǎn)，則該樹(shù)有（ ）個(gè)葉結(jié)點(diǎn)

20、。 A22 B10 C11 D12 16線性表以（ ）方式存儲(chǔ)，能進(jìn)行折半查找。 A關(guān)鍵字有序的順序 B順序 C鏈接 D二叉樹(shù) 17一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（ ）個(gè)結(jié)點(diǎn)。 A7 B5 C6 D8 18一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，最后一層有（ ）個(gè)結(jié)點(diǎn)。 A7 B5 C6 D8 19已知如圖2所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。 Aabecdf Bacfebd Caebcfd Daedfcb bdfeca圖220 .對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行出棧操作，用變量e保存棧頂元素的值，則執(zhí)行 （ ）。 A. e= top-

21、next; top-data=e; B. top=top-next; e=top-data;C. e=top-data; top=top-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中存放的是_字符串的結(jié)束符。3把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為_(kāi)物理結(jié)構(gòu)(存儲(chǔ)結(jié)構(gòu))。 4設(shè)有串p1=”ABADF”,P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”, 四個(gè)串

22、中最大的是_。 5設(shè)有一個(gè)長(zhǎng)度為22的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為_(kāi) _。6在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為_(kāi)。7在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號(hào)為_(kāi) _。 8設(shè)有一個(gè)長(zhǎng)度為20的順序表，要插入一個(gè)元素，并作為第8個(gè)元素，需移動(dòng)元素的 個(gè) 數(shù)為_(kāi)。9設(shè)一棵有n個(gè)葉結(jié)點(diǎn)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，則該樹(shù)共有_ _ 個(gè)結(jié)點(diǎn)。 10結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_(kāi)結(jié)構(gòu)。11在對(duì)一組序列 (45,29,87,12,6,63,55,37,78)進(jìn)行直接插入排序時(shí)，當(dāng)把第8個(gè)記錄37 插 入到有序表時(shí)，為尋找插入

23、位置需比較_次。（由小到大排序）12設(shè)有一棵深度為4的完全二叉樹(shù)，第四層上有5個(gè)結(jié)點(diǎn)，該樹(shù)共有_個(gè)結(jié)點(diǎn)。 （根所在結(jié)點(diǎn)為第1層）13 n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行_ _趟冒泡。14一棵二叉樹(shù)中有n個(gè)非葉結(jié)點(diǎn)，每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹(shù)共有_ 個(gè)葉結(jié)點(diǎn)。15一棵有21個(gè)結(jié)點(diǎn)的哈夫曼樹(shù),該樹(shù)中有 _ 個(gè)葉結(jié)點(diǎn)。16在對(duì)一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65 插 入到有序表時(shí)，為尋找插入位置需比較_次。(由小到大排序17_遍歷二叉排序樹(shù)可得到一個(gè)有序序列。18. n個(gè)元素進(jìn)行冒泡法排序， 第j趟冒泡要進(jìn)行_ _次元素間的

24、比較。19. 廣義表( a , (a ,b) , d , e ,( (i ,j ) ,k ) )的長(zhǎng)度是_。20一棵有n個(gè)葉結(jié)點(diǎn)的哈夫曼樹(shù)，則該樹(shù)共有_個(gè)結(jié)點(diǎn)。21. 廣義表的( a , (a ,b) , d , e ,( (i ,j ) ,k ) )深度是_ 。 22中序遍歷_可得到一個(gè)有序序列。 23. 序列14,12,15,13,18,16,采用冒泡排序算法(升序),經(jīng)一趟冒泡后,序列的結(jié)果 是 _ _。24廣義表( (a ,b) , d , e ,( (i ,j ) ,k ) )的長(zhǎng)度是_ 。 三、綜合題1設(shè)查找表為(7,15,21,22,40,58,68,80,88,89,120)

25、,元素的下標(biāo)依次為1,2,3,，11. （1）畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)（樹(shù)中結(jié)點(diǎn)用下標(biāo)表示）（2）說(shuō)明成功查找到元素40需要經(jīng)過(guò)多少次比較？（3）求在等概率條件下，成功查找的平均比較次數(shù)？2. （1）設(shè)有數(shù)據(jù)集合40，29，7，73，101，4，55，2，81，92，39，依次取集合 中各數(shù)據(jù)構(gòu)造一棵二叉排序樹(shù)。 (2)一組記錄的關(guān)鍵字序列為（5，8，6，3，4，7），利用堆排序（堆頂元素是最 小元素）的方法建立初始堆。(要求用完全二叉樹(shù)表示)3. (1) 一組記錄的關(guān)鍵字序列為（47，80，57，39，41，46），給出利用堆排序（堆頂 元素是最小元素）的方法建立的初始堆（

26、要求以完全二叉樹(shù)描述 ）。 (2) 對(duì)關(guān)鍵字序列( 47,80,57,39,41,85)采用快速排序，給出以第一個(gè)關(guān)鍵字為分割 元素，經(jīng)過(guò)一次劃分后的結(jié)果。 (3) 如圖3所示的二叉樹(shù)，給出其前序遍歷序列。gfabdec圖3 4 (1) 以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù) (2) 給出上述哈夫曼樹(shù)葉結(jié)點(diǎn)的哈夫曼編碼。 (3)一組記錄的關(guān)鍵字序列為（37，70，47，29，31，85），利用快速排序，以第一 個(gè)關(guān)鍵字為分割元素，給出經(jīng)過(guò)一次劃分后結(jié)果。（由小到大排序）四、程序填空題1以下程序是中序遍歷二叉樹(shù)的遞歸算法的程序，完成程序中空格部分（樹(shù)結(jié)構(gòu)中左、右指針域分別為le

27、ft和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。 efabcd圖4void Inorder (struct BTreeNode *BT)if(BT!=NULL) Inorder(BT-left); （1） ; （2） ;利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是 （3） ; 四、程序填空題1. （1） printf(“%c”,BT-data) （2） Inorder(BT-right) （3）dbeafc2.設(shè)線性表為（6，10，16，4），以下程序用說(shuō)明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。 #define NULL 0 void main( ) NODE a,b,

28、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é)束建表過(guò)程*/p=head; /*p為工作指針，準(zhǔn)備輸出鏈表*/ do printf(“%dn”, （3） ); （4） ; while( （5） ); 2 （1）&a（2）d-next=NULL（3）p-data（4）p=p-next（5）p!=NULL3以下冒泡法程序?qū)Υ娣旁赼1，a2，an中的序列進(jìn)行排序，完成程序中 的空格部分，其中n是元素個(gè)數(shù)，要求按升序排列。

29、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.keyai+1.key)flag=1; temp=ai; （3） ; （4） ;if(flag= =0)break;程序中flag的功能是（5） 3 （1）j=n-1（2）iright); 利用上述程序?qū)τ覉D進(jìn)行遍歷，結(jié)果是 （3） ;4 （1）Inorder(BT-left)（2） printf(“%c”,BT-data)（3）bedafc綜合練習(xí)二答案一、單項(xiàng)選擇題1C 2 D 3A

30、4D 5 C 6C 7 A 8A 9 D 10B 11C 12B 13B 14B 15. D 16A 17. A 18A 19.D 二、填空題1. a22. 字符串的結(jié)束符3. 物理結(jié)構(gòu)(存儲(chǔ)結(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. 521. 322二叉排序樹(shù)23. 12,14,13,15,16,18 244 7411852101396圖6三、綜合題1(1) 39559281410172407329圖7(2)4次(3)ASL=(1+2*2+3*4+4*4)

31、/11=32(1) (2) 3,4,6,8,5,7 394658567圖8 3(1) 39，41，46，80，47，57 394146478057圖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 綜合練習(xí)三一、單項(xiàng)選擇題 1.數(shù)據(jù)的存儲(chǔ)結(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

32、指向其尾結(jié)點(diǎn), 要 刪除第一個(gè)結(jié)點(diǎn),則可利用下述語(yǔ)句 head=head-next;和（ ）。 Ap =head; Bp=NULL; Cp-next =head; Dhead=p;3樹(shù)狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 A每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 B一對(duì)一 C多對(duì)多 D一對(duì)多 4. 以下說(shuō)法正確的是( )。 A. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間 B. 一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu) C一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu) D線性表的順序存儲(chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間5設(shè)有一個(gè)長(zhǎng)度為26的順序表，要插入一個(gè)元素,并使它成為新表的第6個(gè)元素,需 移動(dòng)元素的個(gè)數(shù)為（ ）。 A21 B22 C20 D196把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)