電大【數(shù)據(jù)結(jié)構(gòu)(本)】期末綜合練習(xí)小抄參考

1、專業(yè)好文檔數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)2012年6月期末綜合練習(xí)一一、單項選擇題1深度為5的完全二叉樹共有20個結(jié)點，則第5層上有（ ）個結(jié)點(根所在結(jié)點為第一層)。a3 b8 c5 d62同一種邏輯結(jié)構(gòu)（ ）。 a只能有唯一的存儲結(jié)構(gòu) b可以有不同的存儲結(jié)構(gòu) c只能表示某一種數(shù)據(jù)元素之間的關(guān)系 d以上三種說法均不正確3已知一個圖的邊數(shù)為m，則該圖的所有頂點的度數(shù)之和為（ ）。a2m bm c2m+1 dm/24鏈表所具備的特點是（ ）。a可以隨機(jī)訪問任一結(jié)點 b占用連續(xù)的存儲空間c插入刪除元素的操作不需要移動元素結(jié)點 d可以通過下標(biāo)對鏈表進(jìn)行直接訪問5數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是數(shù)據(jù)的

2、（ ）結(jié)構(gòu)。 a物理 b存儲 c邏輯與物理 d邏輯6數(shù)據(jù)的物理結(jié)構(gòu)（ ）。 a與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān) b僅僅包括數(shù)據(jù)元素的表示c只包括數(shù)據(jù)元素間關(guān)系的表示 d包括數(shù)據(jù)元素的表示和關(guān)系的表示7鏈表所具備的特點是（ ）。a可以隨機(jī)訪問任一結(jié)點 b占用連續(xù)的存儲空間c插入刪除不需要移動元素結(jié)點 d可以通過下標(biāo)對鏈表進(jìn)行直接訪問8線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 a一對一 b一對多 c多對多 d每一個元素都有一個直接前驅(qū)和一個直接后繼 9線性表只要以（ ）方式存儲就能進(jìn)行折半查找。a鏈接 b順序 c關(guān)鍵字有序的順序 d二叉樹10以下表中可以隨機(jī)訪問的是（ ）。 a單向鏈表 b雙向鏈表 c單

3、向循環(huán)鏈表 d順序表11散列查找的原理是（ ）。a在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系b按待查記錄的關(guān)鍵字有序的順序方式存儲c按關(guān)鍵字值的比較進(jìn)行查找d基于二分查找的方法12算法的時間復(fù)雜度與（ ）有關(guān)。 a所使用的計算機(jī) b與計算機(jī)的操作系統(tǒng) c與算法本身 d與數(shù)據(jù)結(jié)構(gòu)13對n個元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（ ）次元素間的交換，則表明序列已經(jīng)排好序。 a1 b2 c0 dn-114設(shè)有一個長度為n的順序表，要刪除第i個元素需移動元素的個數(shù)為（ ）。 an-i+1 bn-i cn-i-1 di15排序過程中，每一趟從無序子表中將一個待排序的記錄按其關(guān)鍵字的大小放

4、置到已經(jīng)排好序的子序列的適當(dāng)位置，直到全部排好序為止，該排序算法是( )。 a直接插入排序 b快速排序c冒泡排序 d選擇排序 16在一個單鏈表中，p、q分別指向表中兩個相鄰的結(jié)點，且q所指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用的語句是（ ）。 ap=q-next bp-next=q cp-next=qnext dq-next=null17在對一組元素（64，48，106，33，25，82，70，55，93）進(jìn)行直接插入排序時，當(dāng)進(jìn)行到要把第7個元素70插入到已經(jīng)排好序的子表時，為找到插入位置，需進(jìn)行（ ）次元素間的比較（指由小到大排序）。a6 b2 c3 d418從一個棧頂指針為

5、top的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的值，則執(zhí)行（ ）。 ax=top-data; top=top-next; bx=top-data; ctop=top-next; x=top-data; dtop=top-next; x=data;19采用順序查找法對長度為n的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法），最壞的情況下要進(jìn)行（ ）次元素間的比較。 an+2 bn cn-1 dn/220在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運(yùn)算為（ ）。 ar=f-next; br=r-next; cf=f-next; df=r-next;21如圖1，若從頂點a出發(fā)按廣度

6、優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點序列為（ ）。abecdfg aacebdgf babecdgfcacfedgbdabecfdg 圖122一個棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能輸出序列是（ ）（進(jìn)棧出棧可以交替進(jìn)行）。adceab bedcba cdecba dabcde 23元素2，4，6，8按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。 a8，6，4，2 b2，4，6，8 c4，2，8，6 d8，6，2，424有一個長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。a26/10 b29/10 c29/9 d

7、31/1025排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）排序。 a歸并 b插入 c選擇 d快速 26排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ ）。 a冒泡 b直接插入 c折半插入 d選擇排序27一棵哈夫曼樹總共有23個結(jié)點，該樹共有（ ）個葉結(jié)點（終端結(jié)點）a10 b13 c11 d1228設(shè)有一個10階的對稱矩陣a，采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組b中（數(shù)組下標(biāo)從1開始），則矩陣中元素a8,5在一維數(shù)組b中的下

8、標(biāo)是（ ）。a33 b32 c85 d4129隊列的插入操作在（ ）進(jìn)行。 a隊頭 b隊尾 c隊頭或隊尾 d在任意指定位置30在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ ）倍。 a3 b2.5 c1.5 d2 二、填空題1一棵二叉樹沒有單分支結(jié)點，有6個葉結(jié)點，則該樹總共有_個結(jié)點。2棧和隊列的操作特點分別是_ _和 _ _。3設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點的編號為奇數(shù)，該葉節(jié)點的雙親結(jié)點的編號為10，該完全二叉樹一共有_個結(jié)點。4結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為_ _結(jié)構(gòu)。5按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有_ _ _ 、_ _、 _ _三種。6根據(jù)數(shù)據(jù)元素間

9、關(guān)系的不同特性，通?？煞譃榧?、線性、 、 四類基本結(jié)構(gòu)。7數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為_結(jié)構(gòu)。8要求在n個數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間的比較。則比較的次數(shù)和算法的時間復(fù)雜度分別為_和 _ 。9把數(shù)據(jù)存儲到計算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_結(jié)構(gòu)。10在一個單向鏈表中p所指結(jié)點之后插入一個s所指向的結(jié)點時，應(yīng)執(zhí)行_ _ _和p-next=s;的操作。11結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為_結(jié)構(gòu)。12在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)置三個域，它們是值域 、 。13如圖2所示的二叉樹，其后序遍歷序列為 。efgibachd 圖214一棵二叉樹中順

10、序編號為i的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為_、_。15n個元素進(jìn)行冒泡法排序，通常需要進(jìn)行_趟冒泡。16向一個棧頂指針為h的鏈棧中插入一個s所指結(jié)點時，可執(zhí)行s-next=h;和_。17二叉樹為二叉排序的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是_的。(回答正確或不正確) 18在一個鏈隊中，設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的操作為_和r=s; (結(jié)點的指針域為next)19圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_的。(回答正確或不正確) 20設(shè)有一棵深度為4的完全二叉樹，第四層上有5個結(jié)點，該樹共有_個結(jié)點。

11、（根所在結(jié)點為第1層）21根據(jù)搜索方法的不同，圖的遍歷有_ _、 _ _ 兩種方法22對稀疏矩陣進(jìn)行壓縮存儲，矩陣中每個非零元素對應(yīng)的三元組包括該元素的_、_ _和_ _三項信息。23按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字 的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。24在對一組記錄(55,39,97,22,16,73,65,47,88)進(jìn)行直接插入排序時，當(dāng)把第7個記錄65插入到有序表時，為尋找插入位置需比較_次。三、綜合題1（1）利用篩選過程把序列42，82，67，102，16，32，57，52建成堆（小根堆），畫出該堆（不要求中間過程）。 （2）寫出對上述

12、堆對應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列。2 (1)以2，3，4，7，8，9作為葉結(jié)點的權(quán)，構(gòu)造一棵哈夫曼樹( 要求每個結(jié)點的左子樹根結(jié)點的權(quán)小于等于右子樹根結(jié)點的權(quán))，給出相應(yīng)權(quán)重值葉結(jié)點的哈夫曼編碼。(2) 一棵哈夫曼樹有n個葉結(jié)點，它一共有多少個結(jié)點？簡述理由？3設(shè)查找表為(16,15,20,53,64,7), (1)用冒泡法對該表進(jìn)行排序（要求升序排列），要求寫出每一趟的排序過程。(2)在排序后的有序表的基礎(chǔ)上，畫出對其進(jìn)行折半查找所對應(yīng)的判定樹.(要求以數(shù)據(jù)元素作為樹結(jié)點)(3)求在等概率條件下,對上述有序表成功查找的平均查找長度.4一組記錄的關(guān)鍵字序列為（46，79，56，38，4

13、0，84）（1）利用快速排序的方法，給出以第一個記錄為基準(zhǔn)得到的一次劃分結(jié)果（給出逐次交換元素的過程，要求以升序排列）（2）對上述序列用堆排序的方法建立大根堆，要求以二叉樹逐次描述建堆過程。5（1）設(shè)有一個整數(shù)序列50，38，16，82，110，13，64，依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹 （2）利用上述二叉排序樹，為了查找110，經(jīng)多少次元素間的比較能成功查到，為了查找15，經(jīng)多少次元素間的比較可知道查找失敗6設(shè)查找表為(50,60,75,85,96,98,105,110,120,130) (1) 說出進(jìn)行折半查找成功查找到元素120需要進(jìn)行多少次元素間的比較？(2) 為了折半查找元素

14、95，經(jīng)過多少次元素間的比較才能確定不能查到？（3）畫出對上述有序表進(jìn)行折半查找所對應(yīng)的判定樹(要求以數(shù)據(jù)元素作為樹結(jié)點)四、程序填空題1以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結(jié)點的數(shù)據(jù)域的值，front、rear分別是鏈隊列的隊頭、隊尾指針struct node elemtype data;struct node *next;struct node *front，*rear; void inqueue(elemtype x) struct node *p; p= (struct node*) _(1)_; p-data=x; p-next=null; _(2)_; rear= _(3)_;

15、 2以下是用尾插法建立帶頭結(jié)點且有n個結(jié)點的單向鏈表的程序，結(jié)點中的數(shù)據(jù)域從前向后依次為1,2,3,n，完成程序中空格部分。node *create(n)node *head , *p, *q; int i; p=(node*)malloc(sizeof(node);head= （1） ; （2） ;pnext=null; /*建立頭結(jié)點*/for(i=1; inext; free(_(5)_); return(1);4以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，bt指向根結(jié)點）。void inorder

16、 (struct btreenode *bt) if(bt!=null) （1） ; （2） ; （3） ; 期末綜合練習(xí)一答案一、單項選擇題1c 2b 3 a 4c 5d 6d 7c 8a 9c 10d 11a 12c 13c 14b 15a 16c 17c 18a 19b 20c 21b 22a 23d 24b 25c 26c 27d 28a 29b 30d 二、填空題1112后進(jìn)先出、先進(jìn)先出 3214圖狀 （網(wǎng)狀）5先序；中序；后序6樹形 圖狀 7樹形8n-1,o(n) 9物理（存儲） 10s-next=p-next;11線性 12左指針 右指針13gdbeihfca142i 2i+1

17、15n-116h=s; 17不正確18r-next=s; 19正確2012 21深度優(yōu)先搜索遍歷 廣度優(yōu)先搜索遍歷22行下標(biāo)、列下標(biāo)、非零元素值23相等243三、綜合應(yīng)用題1（1）16423252576782102 （2）102，52，42，82，16，67，32，57233 (1)151879985432 2：11103: 11114：1107：008：019：10（2）2n-1個，因為非葉結(jié)點數(shù)比葉結(jié)點數(shù)少一個。 3(1)原序列16 15 20 53 64 7 15 16 20 53 7 64 15 16 20 7 53 64 15 16 7 20 53 64 15 7 16 20 53

18、64 7 15 16 20 53 64715206416535(2)(3)平均查找長度=（1*1+2*2+3*3）/6=14/64(1)初始序列 46，79，56，38，40，8440，79，56，38，40，8440，79，56，38，79，8440，38，56，38，79，8440，38，56，56，79，8440，38，46，56，79，845679384084468479384046566567938404679384084845646(2) 5038821311064165（1）（2）三次；四次6 (1)3次 (2)4次 (3)96759813010585501100512060 四

19、、程序填空題1（1）malloc(sizeof (struct node)（2）rear-next=p（3）p2 （1）p（2）q=p（3）(node*)malloc(sizeof(node)（4）p（5）q=p3（1）jnext（3）q-next（4）q-next（5）p4 （1）inorder(bt-left)（2）printf(“%c”,bt-data)（3） inorder(bt-right)期末綜合練習(xí)二一、單項選擇題1在c語言中，順序存儲長度為3的字符串，需要占用（ ）個字節(jié)。 a4 b3 c6 d122數(shù)據(jù)的物理結(jié)構(gòu)（ ）。 a與數(shù)據(jù)的邏輯結(jié)構(gòu)無關(guān) b僅僅包括數(shù)據(jù)元素的表示c只包

20、括數(shù)據(jù)元素間關(guān)系的表示 d包括數(shù)據(jù)元素的表示和關(guān)系的表示3串函數(shù)strcat（a,b）的功能是進(jìn)行串（ ）。 a比較 b復(fù)制 c賦值 d連接4從n個數(shù)中選取最大元素（ ）。 a基本操作是數(shù)據(jù)元素間的交換 b算法的時間復(fù)雜度是o(n2)c算法的時間復(fù)雜度是o(n) d需要進(jìn)行(n+1)次數(shù)據(jù)元素間的比較5一棵有n個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄渲?，共有?）個指針域為空。 an+1 bn cn-1 dn-26線性表的順序結(jié)構(gòu)中，（ ）。a邏輯上相鄰的元素在物理位置上不一定相鄰b數(shù)據(jù)元素是不能隨機(jī)訪問的c邏輯上相鄰的元素在物理位置上也相鄰d進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高7設(shè)一棵哈夫曼樹共有n個非葉結(jié)點

21、，則該樹有（ ）個葉結(jié)點。 an bn+1 cn-1 d2n8帶頭結(jié)點的單向鏈表為空的判斷條件是（ ）（設(shè)頭指針為head）。ahead = =null bhead-next= =null chead-next= =head dhead!=null9從一個棧頂指針為top的鏈棧中刪除一個結(jié)點時，用變量x保存被刪結(jié)點的值，則執(zhí)行（ ）。 ax=top-data; top=topnext; bx=top-data; ctop=top-next; x=top-data; dtop=top-next; x=data;10線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 a一對一 b一對多 c多對多 d每

22、一個元素都有一個直接前驅(qū)和一個直接后繼11一棵完全二叉樹共有5層，且第5層上有六個結(jié)點，該樹共有（ ）個結(jié)點。 a30 b20 c21 d2312設(shè)順序存儲的線性表長度為n，要刪除第i個元素，按課本的算法，當(dāng)i=（ ）時，移動元素的次數(shù)為3a3 bn/2 cn-3 d413在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的（ ）倍。 a3 b2.5 c1.5 d214 .以下說法不正確的是（ ）。a棧的特點是后進(jìn)先出 b隊列的特點是先進(jìn)先出c棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行d隊列的插入操作在隊尾進(jìn)行，刪除操作在隊頭進(jìn)行15已知如圖1所示的一個圖，若從頂點v1出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，

23、則可能得到的一種頂點序列為（ ）。 av1v2v4v8v5v3v6v7 bv1v2v4v5v8v3v6v7cv1v2v4v8v3v5v6v7 dv1v3v6v7v2v4v5v8v6v7v1v2v3v8v4v5 圖1 16一個棧的進(jìn)棧序列是a，b，c，d，則棧的不可能的出棧序列是（ ）。aadbc bbcadccbad ddcba17已知如圖2所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（ ）。 aabcedf babcefd caebcfd dacfdebbdfeca 圖218設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組

24、成，設(shè)用x接收棧頂元素，則出棧操作為（ ）。ax=top-data;top=top-next; btop=top-next;x=top-data; cx=top- next;top=top- data; dtop-next =top; x=top-data;19對二叉排序樹進(jìn)行（ ）遍歷，可以使遍歷所得到的序列是有序序列。 a按層次 b后序 c中序 d前序20設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結(jié)點類型的指針，可執(zhí)行如下操作：p=front-next;x

25、=p-data; 然后執(zhí)行（ ）。afront=p-next; bfront-next=p-next;cfront=p; dfront-next =p;21在有序表2，4，7，14，34，43，47，64，75，80，90，97，120中，用折半查找法查找值80時，經(jīng)（ ）次比較后查找成功。a4 b2 c3 d522以下說法正確的是（ ）。a隊列是后進(jìn)先出 b棧的特點是后進(jìn)后出c棧的刪除和插入操作都只能在棧頂進(jìn)行d隊列的刪除和插入操作都只能在隊頭進(jìn)行23有一個長度為9的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（ ）。a25/10 b25/9 c20/9 d17/

26、924空串的長度為（ ）。a0 b1 c2 d325排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（ ）。 a冒泡 b直接插入 c折半插入 d選擇排序26串函數(shù)strcmp(“aba”,”aba”)的值為（ ）。a1 b0 c“abaaba” d-127一組記錄的關(guān)鍵字序列為（46，79，56，38，40，84），利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（ ）。 a40，38，46，79，56，84 b40，38，46，56，79，84c40，38，46，84，56，79 d38

27、，40，46，56，79，8428設(shè)有一個10階的對稱矩陣a，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。（矩陣a的第一個元素為a1,1，數(shù)組b的下標(biāo)從1開始），則矩陣元素a5,3對應(yīng)一維數(shù)組b的數(shù)組元素是（ ）。ab18 bb8 cb13 db1029排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法，稱為（ ）排序。 a歸并 b插入 c快速 d選擇30已知如圖3所示的一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為（ ）。 aabecdf bacfebd caebcfd daedfcb bdfeca 圖3二、

28、填空題1在二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，通常每個結(jié)點中設(shè)置三個域，它們是_、 、右指針。2通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、線性、_ _、_ _四種類型。3一棵二叉樹中順序編號為i的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為_ _、_ _。4通常可以把某城市中各公交站點間的線路圖抽象成_ _結(jié)構(gòu)。5串的兩種最基本的存儲方式是_ _和 _ _。6設(shè)有一個單向鏈表，結(jié)點的指針域為next，頭指針為head，p指向尾結(jié)點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句_ _。7一棵有2n-1個結(jié)點的二叉樹，其每一個非葉結(jié)點的度數(shù)都為2，則該樹共有_個葉結(jié)點。8循環(huán)隊列的隊頭指針為f，隊尾指針為r，當(dāng)_時表明隊

29、列已空。9對于一棵具有n個結(jié)點的二叉樹，其相應(yīng)的鏈?zhǔn)酱鎯Y(jié)構(gòu)中共有_個指針域為空。10設(shè)有一個鏈棧，棧頂指針為hs，現(xiàn)有一個s所指向的結(jié)點要入棧，則可執(zhí)行操作_ _ 和hs=s；11_遍歷二叉排序樹可得到一個有序序列。12在一個鏈隊中，f和r分別為隊頭和隊尾指針，隊結(jié)點的指針域為next，則插入一個s所指結(jié)點的操作為_ _；r=s；13如圖4所示的二叉樹，其后序遍歷序列為 。efgibachd 圖414串的兩種最基本的存儲方式分別是_ _和 _ _。15如圖5所示的二叉樹，其先序遍歷序列為_ _。gfabdec 圖516一棵二叉樹中順序編號為i的結(jié)點，若它存在左、右孩子，則左、右孩子編號分別為

30、_ _、_ _。17圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_的。(回答正確或不正確) 18兩個串相等的充分必要條件是 。19二叉樹為二叉排序的充分必要條件是其任一結(jié)點的值均大于其左孩子的值、小于其右孩子的值。這種說法是_的。(回答正確或不正確) 20一棵二叉樹葉結(jié)點（終端結(jié)點）數(shù)為5，單分支結(jié)點數(shù)為2，該樹共有_個結(jié)點。21對記錄序列排序是指按記錄的某個關(guān)鍵字排序，記錄序列按_排序結(jié)果是唯一的。22根據(jù)搜索方法的不同，圖的遍歷有_ _、 _ _ 兩種方法。23按某關(guān)鍵字對記錄序列排序，若 在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。24一個有序

31、表3，4，10，14，34，43，46，64，75，78，90，96，130用折半查找法查找值為90的結(jié)點，經(jīng)_次比較后查找成功。三、綜合題1設(shè)查找表為(16,15,20,53,64,7), (1)用冒泡法對該表進(jìn)行排序（要求升序排列），寫出每一趟的排序過程，通常對n個元素進(jìn)行冒泡排序要進(jìn)行多少趟冒泡？第j趟要進(jìn)行多少次元素間的比較？ (2)在排序后的有序表的基礎(chǔ)上，畫出對其進(jìn)行折半查找所對應(yīng)的判定樹.(要求以數(shù)據(jù)元素作為樹結(jié)點)2（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫出該二叉樹 （2）若上述二叉樹的各個結(jié)點的字符分別代表不同的整數(shù)（其中沒有相等的），并恰

32、好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系。 （3）給出該樹的前序遍歷序列3 (1) 設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。（2）說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序遍歷的結(jié)果。4（1）一組記錄的關(guān)鍵字序列為45，40，65，43，35，95，寫出利用快速排序的方法，以第一個記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（要求給出一趟劃分中每次掃描和交換的結(jié)果） （2）對序列45，40，65，43，35，95利用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素）。5（1）對給定權(quán)值2，1，3，

33、3，4，5，構(gòu)造哈夫曼樹。（2）同樣用上述權(quán)值構(gòu)造另一棵哈夫曼樹，使兩棵哈夫曼樹有不同的高度，并分別求兩棵樹的帶權(quán)路徑長度。6 (1) 設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹.（2）說明如何通過序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果。 四、程序填空題1設(shè)線性表為（6，10，16，4），以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點中的數(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é)點*

34、/head= （1） ;a.next=&b;b.next=&c;c.next=&d; （2） ; /*以上結(jié)束建表過程*/p=head; /*p為工作指針，準(zhǔn)備輸出鏈表*/do printf(“%dn”, （3） ); （4） ; while( （5） );2以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時返回-1，完成程序中的空格typedef struct int key;node;int binary_search(node a,int n, int k) int low,mid,high; low=0; high=n-1; while(

35、_(1)_) mid=(low+high)/2; if(amid.key=k) return _(2)_; else if(_(3)_) low=mid+1; else _(4)_; _(5)_; 3以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中，左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，bt指向根結(jié)點）。void postorder (struct btreenode *bt) if(bt!=null) （1） ; （2） ; （3） ; 4以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點的數(shù)據(jù)域，top為棧頂指針struct node elemtyp

36、e data;struct node *next;struct node *top ;void push(elemtype x) struct node *p; p=(struct node*)malloc(_(1)_); p-data=x; _(2)_; _(3)_; 綜合練習(xí)二答案一、單項選擇題1a 2d 3d 4c 5a 6c 7b 8b 9a 10a 11c 12c 13d 14c 15a 16a 17b 18a 19c 20b 21a 22d 23b 24a 25c 26d 27b 28c 29d 30d二、填空題1值域 左指針2樹形；圖狀32i和2i+1 4圖狀5順序存儲 鏈?zhǔn)酱鎯?/p>

37、 6p-next=head;7n 8r=f9n+1 10s-next=hs;11中序12r-next=s13gdbeihfca14順序存儲 鏈?zhǔn)酱鎯?5abdefcg162i和2i+1 17正確 18串長度相等且對應(yīng)位置的字符相等19不正確 201121主關(guān)鍵字22深度優(yōu)先搜索遍歷 廣度優(yōu)先搜索遍歷23關(guān)鍵字相等的記錄244三、綜合應(yīng)用題1(1)原序列16 15 20 53 64 7 15 16 20 53 7 64 n-1趟 15 16 20 7 53 64 n-j次 15 16 7 20 53 64 15 7 16 20 53 64 7 15 16 20 53 6471520641653(2) (3)平均查找長度=（1*1+2*2+3*3）/6=14/6abced2（1）（2）dbeadata（4）p=p-next（5）p!=null2（1）low=high（2）mid（3）amid.keyleft)（2）postorder(bt-right)（3） printf(“%c”,bt-data)4（1）sizeof (struct node)（2）p-next=top（3）t