【正文】 2．編寫函數(shù)用于刪除元素遞增排列的帶首結(jié)點(diǎn)單鏈表L中值大于mink且小于maxk的所有元素，并給出其時(shí)間復(fù)雜度。 { if(w0) { print(w, )。 j=) ／* A、B表均末到表尾 */ {if([i]==[j]) ／* A表元素比B表元素小，A表下標(biāo)后移 *／______________________。 ／* 將查找區(qū)間定為左半邊 *／else________________。 5．己知下面二又排序樹各結(jié)點(diǎn)的值依次為1～9，請(qǐng)寫出該二叉排序樹按層次遍歷的結(jié)果。 5．已知二叉樹中葉子數(shù)為50，僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30，則總結(jié)點(diǎn)數(shù)為___________________。( )8．折半查找說法的前提之一是線性表有序。 (A)堆排序 (D)冒泡排序 (c)簡單選鋒排序 (D)快速排序二、判斷題(每小題1分，共10分。 (A)1140 (B)1145 (C)1120 (D)l1254．若用數(shù)組S[1..n]作為兩個(gè)棧S1和S2的共用存儲(chǔ)結(jié)構(gòu)，對(duì)任何一個(gè)棧，只有當(dāng)S全滿時(shí)才不能進(jìn)行人棧操作。提示：可先將數(shù)組排序。 ／* c將記錄小于0的元素個(gè)數(shù) *／for(i=0,c=0。 else ________________。下面的函數(shù)serach的功能是采用折半查找法查找值為e的元素，并返回其下標(biāo)，如果找不到，返回1。 free(p)。(5分)(2)畫出最終的最小生成樹。(5分) (2)在上述堆的堆頂元素去掉，把堆的最后一個(gè)元素放到堆頂位置，再調(diào)整為大頂堆(用二叉樹表示)。2．一個(gè)55的對(duì)稱矩陣采用壓縮存儲(chǔ)，需要存儲(chǔ)____________個(gè)元素。( )3．不論是行優(yōu)先還是列優(yōu)先，二維數(shù)組的最后一個(gè)元素的存儲(chǔ)位置是—樣的。(A)e (B)2e (C)n2一e (D)n2—2e4．在內(nèi)部排序中，排序時(shí)不穩(wěn)定的有( )。(8分)2．已知順序表的數(shù)據(jù)結(jié)構(gòu)如下，編寫算法．刪除順序表前面的10個(gè)元素。 Struct LinkNode *lchild, *rchild。Node *search_link(Node *head, int e){Node *p, *q。 j++) { if(____________________){tmp=a[j]。(4分)(2)畫出刪除值為46的結(jié)點(diǎn)后的二叉排序樹。（5分）3．已知下圖是一個(gè)有向圖。 4．如果某有向圖的所有頂點(diǎn)可以構(gòu)成一個(gè)拓?fù)渑判蛐蛄?，則說明該有向圖__________。( )4．進(jìn)棧操作時(shí)，必須判斷棧是否已滿。 (A)直接插入排序 (B)起泡排序 (c)快速排序 (D)直接選擇排序5．一棵Huffman樹總共有11個(gè)結(jié)點(diǎn)，則葉子結(jié)點(diǎn)有( )個(gè)。2．已知單鏈表結(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)如下，編寫算法判斷一個(gè)單鏈表中各結(jié)點(diǎn)的值是否由小到大排列。 p=pnext)。 else for(i=alength1。 int length。 *e=Qdata[Qfront]。(5分)5．(1)根據(jù)線性表(23，49，28，10，30，5，16)畫出二叉排序樹。 8．設(shè)無向圖G有100條邊，則G至少有_____________個(gè)頂點(diǎn)。( )8．如果某排序算法是穩(wěn)定的，那么該方法一定具有實(shí)際應(yīng)用價(jià)值。 (A)O(1) (B)O(n) (C)O(n2) (D)O(log2n)8．一棵完全二叉樹中根結(jié)點(diǎn)的編號(hào)為l，而且23號(hào)結(jié)點(diǎn)有左孩子但沒有右孩子，則完全二叉樹總共有( )個(gè)結(jié)點(diǎn)。 *rchild。t[i]!=0。 __________________。完成程序。(4分)Typedef struct { int data[100]。(5分)(2)如果下圖表示的是采用孩子—兄弟法轉(zhuǎn)換后的一棵樹。（ ）2．如果某有向圖的所有頂點(diǎn)可以構(gòu)成一個(gè)拓?fù)渑判颍瑒t說明有向圖存在回路。3．在求最小生成樹的兩種算法中，____________算法適合于稀疏圖。 (A)線性結(jié)構(gòu) (B)樹結(jié)構(gòu) (C)圖結(jié)構(gòu) (D)鏈表結(jié)構(gòu)2．設(shè)有二維數(shù)組A[50][60]，其元素長度為1字節(jié)，按列優(yōu)先順序存儲(chǔ)，首元素A[0][0]的地址為200，則元素A[10][20]的存儲(chǔ)地址為( )。4．判別以下序列是否為堆，如果不是，則把它調(diào)整為堆。( )7．哈希表的查找效率主要取決于哈希建表時(shí)所選取的哈希函數(shù)和處理沖突的方法。 4．一組記錄(50，40，95，20，15，70，60，45，80)進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄的交換次數(shù)為__________，在整個(gè)排序過程中共需進(jìn)行_________趟才可以完成。 (A)4 (B)5 (C)6 (D)710．在一個(gè)具有n個(gè)結(jié)點(diǎn)的無向完全圖中，包含有( )條邊。 snext=pnext。 snext=pnext。k++) c[i][j]= c[i][j]+ a[i][k]* b[k][j]。jt。(5分)3．樹與二叉樹之間有何區(qū)別?(5分)4．巳知圖如下所示。2．若字符串t＝‘a(chǎn)babcab’，前綴函數(shù)next[5]＝________________3．一個(gè)具有M個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為_________________。( )7．先序遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問序列不可能是鏈值遞增序列。10．設(shè)單鏈表中指針p指著結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(若存在)，則需要修改指針的操作為( )。 for(i＝l。( )7．進(jìn)棧操作時(shí)，必須判斷棧是否已滿。(10 分)2．編寫一個(gè)算法計(jì)算一個(gè)廣義表的原子結(jié)點(diǎn)個(gè)數(shù)。 ___________________。 bubble(Rectype R[n]) { int i，j，exchang； Rectype temp。2．雙向循環(huán)鏈表的主要優(yōu)點(diǎn)是______________。( )9．按中序遍歷一棵二叉排序樹所得到的中序遍歷序列是一個(gè)遞增序列10．進(jìn)棧操作push(x，s)作用于鏈接棧時(shí)，無需判滿。五、判斷題(10分)1．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位。 if(tkeyk)__________________。3．設(shè)有一空棧，棧頂指針為1000H(十六進(jìn)制)，現(xiàn)有輸入序列為1，2，3，4，5，經(jīng)過Push，Push，Pop，Push，Pop，Push，Push操作后，輸出序列為________________。 (A)r一f (B)n一(r一f) (C)(r—f十n)％n (D)(f一r十n)％n4．完成堆排序的全過程需要( )個(gè)記錄大小的輔助空間。( )6．連通分量是無向圖中的極小連通子圖。(13分) 2．設(shè)a＝(a1，a2，…am)和b＝(b1,b2，…，bn)是兩個(gè)循環(huán)鏈表寫出將這兩個(gè)表合并為循環(huán)鏈表c的算法。 7．設(shè)F是森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個(gè)非終端結(jié)點(diǎn)，B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有______________。{ i＝j(luò)＝0。 (A)線性表 (B)棧 (C)隊(duì)列 (D)樹4．二叉樹第i(i≥1)層最多有( )個(gè)結(jié)點(diǎn) (A)2i， (B)2i (C)2i1 (D)2i一1 5．設(shè)單鏈表中指針p指向結(jié)點(diǎn)A，若要?jiǎng)h除A之后的結(jié)點(diǎn)(若存在)，則修改指針的操作為( )。 (A)pnext＝pnextnext (B)p＝pnext (C)p＝pnextnext (D)pnext＝p 6．設(shè)一數(shù)列的輸入順序?yàn)?，2，3，4，5，6，通過棧操作不可能排成的輸出序列為( ) (A)3，2，5，6，4，1 (B)l，5，4，6，2，3 (C)2，4，3，5，1，6 (D)4，5，3，6，2，1 7．設(shè)字符中S1＝‘ASCDEFG’，S2＝‘PQRST’，則運(yùn)算S＝Concat(Sub(S1,2,Length(S2))，Sub(S1，Length(S2)，2))后結(jié)果為( )。 while((i＜s一＞len)＆＆(j＜t一＞len)) if (s一＞ch[i]==t一＞ch[j]){ i=i+1。 8．先序序列和中序序列相同的二叉樹為_________________。(15分) (a1，b1，a2，b2，…am，bm，bm+1，…，bn) m≤nc= (a1，b1，a2，b2，…an，bn，an+1，…，am) mn 3．已知一個(gè)單鏈表中每個(gè)結(jié)點(diǎn)存放一個(gè)整數(shù)，并且其結(jié)點(diǎn)數(shù)不少于2。( )7．先序遍歷一棵二叉排序樹所得的結(jié)點(diǎn)訪問序列不可能是鏈值遞增序列。 (A)1 (B)n (C)n log2 n (D)Ln log2 n J5．若結(jié)定的關(guān)鍵碼集合為{20，15，14，18，2l，36，40，10}，一趟快速排序結(jié)束時(shí)，鍵值的排列為( )。4．線索化二叉樹中某結(jié)點(diǎn)D，沒有左孩子的主要條件是______________。 else_________________。( )2．在單鏈表中任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系，因此可以從首結(jié)點(diǎn)進(jìn)行查找任何一個(gè)元素。( )模擬試題3一、選擇題(20分)1．組成數(shù)據(jù)的基本單位是( )。3．上三角矩陣壓縮存儲(chǔ)的下標(biāo)對(duì)應(yīng)關(guān)系k＝________________。 i＝1。 } _________________。(12分)3．設(shè)計(jì)一個(gè)算法，用于查找中序線索二叉樹中結(jié)點(diǎn)*p的中序前驅(qū)結(jié)點(diǎn)。( )8．如果某排序算法是穩(wěn)定的，那么該方法一定具有實(shí)際應(yīng)用價(jià)值。i=n。 (A)p一＞next＝p一＞next一＞next。( )8．不論adt棧是用數(shù)組實(shí)現(xiàn)，還是用指針實(shí)現(xiàn)，Pop(s)與Push(x’s)的時(shí)間復(fù)雜度均)(M)。4．有序字典是以______________為基礎(chǔ)的抽象數(shù)據(jù)類型。(5分)(1)要求用Kruskal算法求出最小生成樹(2)指出生成樹的第一條邊。j++) c[i][j]=0。 (A) O(mnt) (B) O(m+n+t) (C) O(m+n) (D) O(mt+n)2．從一個(gè)長度為n的順序表中刪除第i個(gè)真值表歸約（1≤i≤n），需向前移動(dòng)（ ）個(gè)元素。 (B) sprior=p。 (D) sprior=p。 (A) n(n1)/2 (B) n(n1) (C) n(n+1)/2 (D) nn11．采用順序查找法查找長度為n的線性表．則查找每個(gè)元素的平均比較次數(shù)為( ) (A) n (B) n/2 (C) (n+1)/2 (D) (n1)/212．已知一個(gè)有序表為(13，18，24，35，47，50，62，83，90，115，134)，當(dāng)二分查找值為90的元素時(shí)，需( )次比較可查找成功。5．在堆排序、快速排序和歸并排序中，若從節(jié)省存儲(chǔ)空間考慮，則應(yīng)首先選取_______方法，其次選__________方法，最后選取_________方法；若從排序結(jié)構(gòu)的穩(wěn)定性考慮，則應(yīng)選擇__________方法；若只從平均情況下排序的速度來考慮，則選擇__________方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)該取___________方法。（ ）8．因?yàn)樗惴ê统绦驔]有區(qū)別，所以在數(shù)據(jù)結(jié)構(gòu)中二者是通用的。 (1)(100，86，48，73，35．39，42，57，66，21)； (2)(12，70，33，65．z4，56，48，92，86，33)； (3)(103，97，56，38，66，242，12，30，52，06，20)。 (A)820 (B)720 (C)1210 (D)14103．一組記錄(50，40，95，20，15，70，60，45，80)進(jìn)行冒泡排序時(shí)，第一趟需進(jìn)行相鄰記錄交換的次數(shù)為( )。4．一顆Huffman樹是由5個(gè)葉子結(jié)點(diǎn)形成的，該Huffman樹總共有_________個(gè)結(jié)點(diǎn)。( )3．如果把一個(gè)大頂堆看成一顆二叉樹，根元素層次為1，則層次越大的元素值越?。? ）。試畫出原來的樹。 int top。(6分)Typedef struct LinkNode{ int data。 p=prchild)。 i++) if(s[i]!=t[i]) break。}Node。 (A)24 (B)45 [C)46 (D)47二、判斷題(每題1分，共8分。( )三、填空題(每題2分，共16分)1．?dāng)?shù)據(jù)結(jié)構(gòu)有線性結(jié)構(gòu)、樹結(jié)構(gòu)、_____________、____________等幾種邏輯結(jié)構(gòu)。四、簡答題(共38分)1．排序(1)寫出線性表(26，45，12，20，30)采用快速排序算