【正文】 圖合起來為完全圖），試證明G或G’是連通的。 7 （10分） 用序列（46，88，45，39，70，58，101，10，66，34）建立一個排序二叉樹，畫出該樹，并求在等概率情況下查找成功的平均查找長度。 8 （10分） 寫出下面程序段的運行結(jié)果。 Program Ex(Input, Output)。 type Ttt=Array[1..20] OF Integer。 Var I,J,K,L,N:Integer。 A:Ttt。 Function P (Var A:Ttt。 Var M,N:Integer):Integer。 var X,Y,Z:Integer。 Begin If N=1 Then Begin m:=1。 p:=a[1] End Else Begin X:=N。 N:=N1。 Y:=P(A,Z,N)。 N:=X。 If A[N]=Y Then Begin M:=N。 P:=A[N] End Else Begin M:=Z。 P:=Y End End End。 Begin Readln(N)。 For I:=1 To N Do Read(A[I])。 Readln。 L:=N。 For I:=1 To L Do Begin K=P9A,J,N)。 A[J]:=A[N]。 A[N]:=K。 N:=N1 End。 For I。=1 To L Do Write(A[I]:3)。 Writeln。 End。 輸入數(shù)據(jù)為： 8 6 1 8 4 3 5 2 7 9 （10分） 已知二叉樹用下面的順序結(jié)構(gòu)存儲，寫出中序遍歷該二叉樹的算法。 Type Array [1..maxn] of Record Data:Char。 //存結(jié)點值 Lc,Rc:Integer //左、右孩子下標(biāo)，0表示無左、右孩子 如樹T=A（B（D，E），C（，F(xiàn)（H，I）））存儲如表1所示：表1 樹T的存儲 1 2 3 4 5 6 7 8 9ABCDEFGHI240008000356079000 10 （10分） 試寫出以帶頭結(jié)點單鏈表為存儲結(jié)構(gòu)實現(xiàn)簡單選擇排序的算法。東北大學(xué)2000碩士入學(xué)數(shù)據(jù)結(jié)構(gòu)試題 1 （20分） 簡要回答下列問題 ① （3分） 內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m），提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當(dāng)這部分空間全滿時才發(fā)生上溢。 ②（5分） 假設(shè)字符a,b,c,d,e,,，寫出a,b,c,d,e,f的Huffman（哈夫曼）編碼。 ③（4分） 一棵共有n個結(jié)點的樹，其中所有分枝結(jié)點的度均為k，求該樹中葉子結(jié)點的子數(shù)。 ④（4分） 圖1表示一個地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費的代價，如何選擇能溝通每個城市且總代價最省的n1條線路，畫出所有可能的選擇。圖1 ⑤（4分） 在起泡（汽泡）排序過程中，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移動，試舉例說明之?？焖倥判蜻^程中有沒有這種現(xiàn)象？ 2 （15分） 設(shè)有一個由正整數(shù)組成的無序（向后）單鏈表，編寫完成下列功能的算法： ① 找出最小值結(jié)點，且打印該數(shù)值； ② 若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點的數(shù)值交換； ③若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點刪除； 3 （14分） 解答下列問題： ① (4分） 將算術(shù)表達(dá)式 ((a+b)+c*(d+e)+f)*(g+h) 轉(zhuǎn)化為二叉樹； ② (10分） 假設(shè)一個僅包含二元運算符的算術(shù)表達(dá)式以二叉鏈表形式存儲在二叉樹BT中，寫出計算該算術(shù)表達(dá)式值的算法。 4（21） 解答下列問題： ① （5分） 畫出有向圖的十字鏈表存儲結(jié)構(gòu)中頭結(jié)點和表結(jié)點的結(jié)點結(jié)構(gòu)。 ② (4分） 下面哪一個方法可以判斷出一個有向圖中是否有環(huán)（回路）？ (1)深度優(yōu)先遍歷 (2)拓樸排序 (3)求最短路徑 (4)求關(guān)鍵路徑 ③(12分） 假設(shè)一個有向圖g已經(jīng)以十字鏈表形式存儲在內(nèi)中，試寫一個判斷該有向圖中是否有環(huán)（回路）的算法。 5（15分） 寫出刪除二叉排序樹bt中值為x的結(jié)點的算法（二叉排序樹以二叉鏈表形式存儲，刪除后仍然保持二叉排序性質(zhì)）。 6（15分） 設(shè)有大小不等的n個數(shù)據(jù)組（n個數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m），順序存放在空間區(qū)D內(nèi)，每個數(shù)據(jù)占一個存儲單元，數(shù)據(jù)組的首地址由數(shù)組s給出（如下圖所示），試編寫將新數(shù)據(jù)x插入到第i個數(shù)據(jù)組的末尾且屬于第i個數(shù)據(jù)組的算法，插入后，空間區(qū)D和數(shù)組S的相互關(guān)系仍保持正確。 圖2 題6圖02年北京文考“數(shù)據(jù)結(jié)構(gòu)”試題一、判斷題 (每小題1分，共15分)，但算法不一定是程序。( )。( )。( )，數(shù)組的主要操作還有存取、修改、檢索和排序等。( )，因此可以采用三元組方法進(jìn)行壓縮存儲。( )，只要堆棧不空，可以任意刪除一個元素。( )。( ) 個結(jié)點。( )。( )。( )。( )。( )=(V,E)的拓?fù)湫蛄胁晃ㄒ?，則圖中必須有兩條弧和。( )。( )，泡排序法所進(jìn)行的元素之間的比較次數(shù)最多。( )二、單項選擇題 (每小題2分，共20分)( ) 2. 在由list所指的非空線性鏈表中刪除由p指的鏈結(jié)點的下一個鏈結(jié)點的過程是依次執(zhí)行q←link(p),____________,call RET(q)。( )(p)←q (q)←p(q)←link(p) (p)←link(q),b,c,d以后，緊接著作了兩次刪除操作，此時的隊頭元素是( ) 1，2，3，…，n1，n，輸出序列的第1個元素為n，則第個輸出元素為( )+1 。( ) ，樹中結(jié)點的數(shù)據(jù)信息依次存放在一個一維數(shù)組中，即 ABC□DEF□□G□□H□□ 該二叉樹的中序列遍歷序列為( ),D,B,A,F,E ,B,D,A,F,H,C,E,D,G,A,F,H,C,E ,G,D,A,F,H,C,E，度為3的結(jié)點有2個，度為2的結(jié)點有1個，度為1的結(jié)點有2個，那么，該樹有__________個葉結(jié)點。( ) =，其中V＝{v1,v2,v3,v4,v5,v6},E＝{,，，，}，G的拓?fù)湫蛄惺莀_____。( ),v1,v4,v5,v2,v6 ,v4,v1,v5,v2,v6,v3,v4,v5,v2,v6 ,v4,v3,v5,v2,v6(MON,TUE,WED,THU,FRI,SAT,SUN),散列函數(shù)為H(k)=i MOD 7，其中，i為關(guān)鍵字k的第一個字母在英文字母表中的序號，地址值域為 [0:6] ，采用線性再散列法處理沖突。插入后的散列表應(yīng)該如__________ 所示。( )A. 0 1 2 3 4 5 6THU TUE WED FRI SUN SAT MONB. 0 1 2 3 4 5 6TUE THU WED FRI SUN SAT MONC. 0 1 2 3 4 5 6TUE THU WED FRI SAT SUN MOND. 0 1 2 3 4 5 6TUE THU WED SUN SAT FRI MON10. 對數(shù)據(jù)元素序列(49，72，68，13，38，50，97，27)進(jìn)行排序，前三趟排序結(jié)束時的結(jié)果依次為：第一趟：13，72，68，49，50，97，27；第二趟：13，27，68，49，38，50，97，72；第三趟：13，27，38，49，68，50，97，72；該排序采用的方法是( ) 三、填空題 (每小題2分，共20分)，在其第i個位置插入一個新的數(shù)據(jù)元素前，需要先依次移動_________個數(shù)據(jù)元素。：llink(p)←q，rlink(p)←rlink(q)，rlink(q)←p,______________。(空白處為一條賦值語句)，每個元素占k個存儲單元，第一個元素的地址為LOC(a1)，那么，LOC(ai)=________________。，其深度至少為_________。 (Huffman) 的分支總數(shù)為_________。，則該圖的生成樹的邊數(shù)為_________。(2，5，8，11，15，16，22，24，27，35，40)中采用折半查找(二分查找)方法查找元素24，需要進(jìn)行_________次元素之間的比較。，并且索引表的表項按_________有序列排列。，整個排序過程中要進(jìn)行_________次元素之間的比較。、選擇排序法、拓?fù)渑判蚍ㄅc歸并排序法中，_________不是內(nèi)排序方法。四、問題求解題 (每小題10分，共20分)，并且鄰接矩陣采用三元組表表示，其中，第一個三元組 (5，5，16)分別表示鄰接矩陣的行數(shù)、列數(shù)字與非零元素的個數(shù)，從第二個三元組開始，依次按行序為主序的次序分別給出16個非零元素，它們依次為(1，2，7)，(1，3，6)，(1，4，9)，(2，1，7)，(2，3，8)，(2，4，4)，(2，5，4)，(3，1，6)，(3，2，8)，(3，4，6)，(4，1，9)，(4，2，4)，(4，3，6)，(4，5，2)，(5，2，4)，(5，4，2)；請分別畫出該帶權(quán)連通圖的兩棵最小生成樹。[0：9]，散列函數(shù)為H(key)=key MOD 9，處理沖突的方法為鏈地址法，請畫出依次插入關(guān)鍵字8,10,14,19,21,23,28,32以后的哈希表。五、算法題 (本題共25分)1. (10分)下面的算法將一維數(shù)組A[1:n]中所有奇數(shù)移到數(shù)組的左邊，所有偶數(shù)字移到數(shù)組的右邊。請在算法的空白處填入適當(dāng)內(nèi)容，使之能夠正常工作。(提示：用 x MOD y表示求x除以y的余數(shù))procedure EXCHANGE(A,n)i←1j←nrepeatwhile_________do // 當(dāng)A[i]為奇數(shù)時 //i←i+1endwhile_________do // 當(dāng)A[i]為偶數(shù)時 //j←j1endif(i [ temp←A[i]A{i}←A[j]______________ ] // 交換A[i]與A[j]的位置 //elseexituntil __________end2.(15分) 已知非空線性鏈表的鏈結(jié)點的構(gòu)造為 date | link，第一個鏈結(jié)點的指針為list，下面的算法在鏈表的第i個鏈結(jié)點(設(shè)i0)前插入一個數(shù)據(jù)信息為item的新結(jié)點。請在算法的空白處填入適當(dāng)內(nèi)容，使之能夠正常工作。procedure INSERT (list,i,item)if (i=1) then[ call GETNODE (p) // 申請一個新的鏈結(jié)點 //date (p) ←itemlink (p) ←list　 ________________ // 將新結(jié)點插在第1個鏈結(jié)點前 //else[ q←listfor j←1 to___________dor←qq←link (q)if__________then[call ERROR (i超過鏈表的長度!)return ]end // r與q分別指向第i1個與第i個鏈結(jié)點 //call GETNODE (p) // 申請一個新的鏈結(jié)點空間 //data (p) ←itemlink (p) ←q__________________] // 將新結(jié)點插在第i個結(jié)點前 //end