長春理工計算機數(shù)據(jù)結(jié)構(gòu)考研模擬整合版

1、一、選擇題（共20分，每題1分）.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類，分別是（）。A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈式結(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D ,初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu).下面給出的四種排序法中（）排序法是不穩(wěn)定的排序法。A.插入 B. 冒泡 C.二路歸并D. 堆排序.線性表是具有n個（）的有限序列（n0）。A.表元素 B .字符 C .數(shù)據(jù)元素D .數(shù)據(jù)項.在下面的程序段中，對x的賦值語句的頻度為（）FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+50;A. O（2n） B . O（n） C . O（n2）D . O（log J）.下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點

2、？（）A.存儲密度大B .插入運算方便 C .刪除運算方便 D .可方便地用于各種邏輯結(jié)構(gòu)的存儲表示.棧是一種（）的線性表。A.先進先出B.后進先出C.后進后出D.不分順序.設棧的輸入序列是1, 2, 3, 4,則（）不可能是其出棧序列。A. 4 , 3, 1, 2,B.2 , 1, 3, 4,C. 1,4, 3, 2, D. 1, 2, 4, 3,.雙向鏈表中有兩個指針域，llink 和rlink ,分別指回前驅(qū)及后繼，設 p指向鏈表中的一 個結(jié)點，q指向一待插入結(jié)點，現(xiàn)要求在p前插入q,則正確的插入為（）p A .llink:=q; q 人.rlink:=p; p 人.llink 人.rl

3、ink:=q; qA.llink:=pA.llink;q A .llink:=pA.llink;p 人.llinkA.rlink:=q;q 人.rlink:=p;pA.llink:=qA.rlink;qA.rlink:=p; pA.rlink:=q; pA.llinkA.rlink:=q; qA.rlink:=p;pA.llinkA.rlink:=q; qA.rlink:=p; qA.llink:=pA.llink; pA.llink:=q;.設一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用 （）最節(jié)省時間。A.單鏈表 B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點的雙循環(huán)鏈表

4、.樹是結(jié)點的有限集合，一棵非空的樹它有（）根結(jié)點。A.有0個或1個B.有0個或多個 C.有且只有一個D. 有1個或1個以上 TOC o 1-5 h z .設有兩個串p和q,其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）A.求子串 B .聯(lián)接 C .求串長 D .匹配.已知串S= aaab,其Next數(shù)組值為（）。A 0123 B . 0012 C . 1231 D , 1211.設給定權(quán)值總數(shù)有 n個，其哈夫曼樹的結(jié)點總數(shù)為（）A.不確定 B . 2n C , 2n+1 D . 2n-1.設森林F對應的二叉樹為 B,它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為 n,森林 F中第一棵

5、樹的結(jié)點個數(shù)是（）A. m-n B . m-n-1 C . n+1 D .條件不足，無法確定.深度為h的滿m叉樹的第k層有（）個結(jié)點。（1=k=h）A.箭-1B . mTC . m-1D . ni-1.樹的后根遍歷序列等同于t樹對應的二叉樹的（）.A.先序序列B.中序序列C. 后序序列 D. 沒有對應關(guān)系.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF中序遍歷結(jié)果為 CBAEDF則后序遍歷的結(jié)果為（）。A. FEDCBA B . CBEFDA C . CBEDFA D ,不確定 TOC o 1-5 h z .在圖的理論與應用中，關(guān)鍵路徑是事件結(jié)點網(wǎng)絡中（）。A.從源點到匯點的最長路徑B .從源點到

6、匯點的最短路徑C.最長回路D.最短回路.在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（）倍。A. 1/2 B . 2 C . 1D. 4.下列哪一種圖的鄰接矩陣是對稱矩陣？（）A.有向圖 B ,無向圖 C . AOV網(wǎng) D . AOER一、選擇題（共20分，每題2分）.棧是一種（）的線性表。A.先進先出B.后進先出C. 后進后出 D.不分順序.串的長度是指（）A.串中所含不同字母的個數(shù)B .串中所含字符的個數(shù)C.串中所含不同字符的個數(shù)D .串中所含非空格字符的個數(shù).設S為一個長度為n的字符串，其中的字符各不相同，則 S中的互異的非平凡子串（非 空且不同于S本身）的個數(shù)為（）。A.

7、2n-1 B . n2 C . （n2/2）+（n/2） D . （n2/2）+（n/2）-1.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類，分別是（）。A.動態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B .順序結(jié)構(gòu)、鏈式結(jié)構(gòu)C.線性結(jié)構(gòu)、非線性結(jié)構(gòu)D ,初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu).下面給出的四種排序法中（）排序法是不穩(wěn)定性排序法。A. 插入 B. 冒泡 C.二路歸并D. 堆排序.設給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)為（）A.不確定 B . 2n C , 2n+1 D . 2n-1.設森林F對應的二叉樹為 B,它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為 n,森林F 中第一棵樹的結(jié)點個數(shù)是（）A. m-n B . m-n-1 C

8、 . n+1 D .條件不足，無法確定.數(shù)據(jù)序列（8, 9, 10, 4, 5, 6, 20, 1, 2）只能是下列排序算法中的（）的兩趟排序后的結(jié)果。A.選擇排序B.冒泡排序C.插入排序D. 堆排序.如果待排序序列中兩個數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。下列排序方法中，哪一個是穩(wěn)定的排序方法？（）A.直接選擇排序B .二分法插入排序C .希爾排序 D.快速排序.樹是結(jié)點的有限集合，一棵非空的樹它有（）根結(jié)點。A.有0個或1個B.有0個或多個 C.有且只有一個 D. 有1個或1個以上一、選擇題（共20分，每題1分） TOC o 1-5 h z .

9、在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是（）。A. G中有弧B, G中有一條從 Vi至ij Vj的路徑C. G中沒有弧D. G中有一條從 Vj至ij Vi的路徑.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（）倍。A. 1/2 B. 2 C. 1 D. 4. n個頂點的強連通圖中至少含有（）。A. n-1條有向邊 B . n條有向邊 C . n（n-1）/2 條有向邊 D . n（n-1）條有 向邊.在一棵度為3的樹中，度為3的結(jié)點個數(shù)為2,度為2的結(jié)點個數(shù)為1,則度為0的結(jié)點個 數(shù)為（）A. 4 B . 5 C . 6 D . 7.圖的逆鄰接表存儲結(jié)構(gòu)只適

10、用于（）圖A.有向 B .無向 C .森林 D .連通.若查找每個記錄的概率均等，則在具有 n個記錄的連續(xù)順序文件中采用順序查找法查找 一個記錄，其平均查找長度人$1為（）。A. （n-1）/2 B. n/2 C. n D. （n+1）/2.下面關(guān)于二分查找的敘述正確的是（）。A.表必須有序，表可以順序方式存儲，也可以鏈表方式存儲.表必須有序，而且只能從小到大排列C.表必須有序，且表只能以順序方式存儲D.表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型.在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設最低的不平衡結(jié)點為A,并已知A無左孩子的平衡因子為，右孩子的平衡因子為1,則應作()型調(diào)整以使其平衡。

11、A. LL B. LR C RL D RR.散列表的地址區(qū)間為 0-17,散列函數(shù)為H(K)=K mod17o采用線性探測法處理沖突，并將 關(guān)鍵字序列26, 25, 72, 38, 8, 18, 59依次存儲到散列表中。存放元素59需要搜索的次 TOC o 1-5 h z 數(shù)是()。A. 2 B. 3C.4D.5.設要排序(Sort)的數(shù)據(jù)為：5, 1, 10, 2,15, 3,若采用堆排序法(Heap Sort )排為升序，則當堆樹(Heap tree )第三次建成時，其樹根節(jié)點數(shù)據(jù)內(nèi)容是()。A. 3 B. 10C.15D.5.在對n個元素進行冒泡排序的過程中，最好情況下的時間復雜度為()

12、。A. O(1) B . O(log 2n)C . O(sqt(n) D . O(n).有一個100*90的稀疏矩陣，非0元素有10個，設每個整型數(shù)占2字節(jié)，則用三元組表 示該矩陣時，所需的字節(jié)數(shù)是()。A. 60 B . 66 C . 18000 D . 33.設給定權(quán)值總數(shù)有n個，其哈夫曼樹的結(jié)點總數(shù)為()A.不確定 B . 2n C , 2n+1 D . 2n-1. 已知廣義表：A=(a,b),B=(A,A),C=(a,(b,A),B), 求下列運算的結(jié)果：tail(head(tail(C)=()。A. (a) B . A C . a D . (A)15.設有一個8階的對稱矩陣 A,采用

13、以行優(yōu)先的方式壓縮存儲。a11為第1個元素，其存儲地址為1,每個元素占一個地址空間。試問元素a85的地址為()。A. 33 B . 30 C16.下面說法不正確的是()cA.廣義表的表頭總是一個廣義表C.廣義表難以用順序存儲結(jié)構(gòu)13 D . 23B.廣義表的表尾總是一個廣義表D.廣義表可以是一個多層次的結(jié)構(gòu)17.在下述結(jié)論中，正確的是(只有一個結(jié)點的二叉樹的度為0；二叉樹的度為2;二叉樹的左右子樹可任意交換；深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。A. B . C . D .對于有n個結(jié)點的二叉樹，其高度為()A. nlog 2n B . log 2n C . |log 2

14、n|+1 D .不確定.設給定權(quán)值總數(shù)有 n個，其哈夫曼樹的結(jié)點總數(shù)為()A.不確定B 2n.2n+1.2n-120.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF中序遍歷結(jié)果為CBAEDF則后序遍歷的結(jié)果A. CBEFDAB . FEDCBA C.CBEDFA、選擇題（共20分，每題1分）1.線性表（a1,a2,an）以鏈接方式存儲時,訪問第 i位置元素的時間復雜性為（）。A. O (i ) B . O (1)C. O (n) D . O (i-1 )2.設森林F對應的二叉樹為B,它有m個結(jié)點,B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（A. m-n B.m-n-1 C.n

15、+1 D.條件不足，無法確定3.非空的循環(huán)單鏈表 head的尾結(jié)點p滿足（A. p.link=head B.p.link=NIL C.p=NIL D . p=head4. 一個長度為n的順序存儲的線性表中，向第i個元素（1 w i w n+1）位置插入一個新元素時,需要從后面向前依次后移（）個元素。A. n-in-i+1n-i-1 D5.在一個單鏈表中，若要在 p 個指針域的值。所指向的結(jié)點之后插入一個新結(jié)點，則需要相繼修改（6.在一個帶有頭結(jié)點的雙向循環(huán)鏈表中，若要在 向的結(jié)點，則需要對 q-next賦值為（）。p所指向的結(jié)點之后插入一個q指針所指A. p-prior B.p-next C.

16、p-next-next D.p-prior -prior7.由3個結(jié)點可以構(gòu)造出多少種不同的二叉樹?A2 B 3 C 48.關(guān)鍵路徑是事件結(jié)點網(wǎng)絡中（A.從源點到匯點的最長路徑B.從源點到匯點的最短路徑最長回最短回路. n個結(jié)點的完全有向圖含有邊的數(shù)目A. n*nB. n(n+ 1 )C.n /2D.n*.鏈棧與順序棧相比，一個較為明顯的優(yōu)點是便利A.通常不會出現(xiàn)?？盏那樾蜝.插入操作更加便利C.刪除操作更加D.通常不會出現(xiàn)棧滿的情形11.若已知一個棧的入棧序列是1,2,3,n,其輸出序列為p1,p 2,p3,，pN,若pN是n,則pi 是（）。A. i Bn-i C . n-i+1.不確定.

17、最大容量為n的循環(huán)隊列，隊尾指針是rear ,隊頭是front ,則隊空的條件是 （）。A. （rear+1） MO=front B . rear=front C . rear+1=front D . （rear-l）MODi=front.設有兩個串p和q ，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法稱為（）。A.求子串 B .聯(lián)接 C .匹配 D .求串長 TOC o 1-5 h z .下面關(guān)于串的的敘述中，哪一個是不正確的？（）。A.串是字符的有限序列B .空串是由空格構(gòu)成的串C.模式匹配是串的一種重要運算D .串既可以采用順序存儲，也可以采用鏈式存儲.已知串S= aaab , 其N

18、ext 數(shù)組值為（）。A. 0123 B . 1123 C . 1231 D , 1211.有一個長度為12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（）/12。A. 35 B. 37 C. 39 D. 43.數(shù)列（21,19, 37, 5, 2）經(jīng)由冒泡排序法（bubble sort ）由小到大排序，在第一次執(zhí)行交換（swap）的后所得結(jié)果為（）。A.（19 , 21 , 37,5,2）B. （21 , 19, 5, 37,2）C .（21 , 19, 37,2,5）D, （2, 21, 19, 37,5）.對于一個頭指針為head的帶頭結(jié)點的

19、單鏈表，判定該表為空表的條件是（）。A. head=NULL B . headnext=NULL C . head next=head D . head!=NULL.在下列存儲形式中，哪一個不是樹的存儲形式？（）A.雙親表示法B .孩子鏈表表示法C.孩子兄弟表示法D.順序存儲表示法.已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF中序遍歷結(jié)果為 CBAEDF則后序遍歷的結(jié)果為（）。A. CBEFDA B . FEDCBA C . CBEDFA D ,不定二、填空題（共 30分，每空2分）. 一棵具有n個結(jié)點的完全二叉樹的樹高度（深度）是 （1）。.數(shù)據(jù)結(jié)構(gòu)分別為邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)（物理結(jié)構(gòu)），邏輯結(jié)

20、構(gòu)有分為四類基本結(jié)構(gòu)，分別是（2）、（3）、（4）、（5）。存儲結(jié)構(gòu)（物理結(jié)構(gòu)）又分為（6）存儲結(jié)構(gòu)和（7）存儲結(jié)構(gòu)。邏輯上（邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系）可以把數(shù)據(jù)結(jié)構(gòu)分成結(jié)構(gòu)和工9上結(jié)構(gòu)。.若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（10） 4.樹是結(jié)點的有限集合，樹是由根結(jié)點和若干顆子樹構(gòu)成的。一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點（11）; 一棵樹高為K的完全二叉樹至少有（12）個結(jié)點:高度為 K的二叉樹最 大的結(jié)點數(shù)為（13）。5.霍夫曼樹是一種帶權(quán)路徑最(14)的樹,在一個度為 m的霍夫曼樹中，其葉結(jié)點個數(shù)為n,則非葉結(jié)點的個數(shù)為(15)。二、填空題

21、(共 20分，每空2分).樹是結(jié)點的有限集合，樹是由根結(jié)點和若干顆子樹構(gòu)成的。樹中含有的最大的子樹的個數(shù)稱為(1)； 一棵樹高為K的完全二叉樹至少有(2)個結(jié)點；高度為 K的二叉樹最大的結(jié) 點數(shù)為(3)。.二叉樹由(4), (4), (6)三個基本單元組成。.空格串是指CZ)，其長度等于(8)。. 一棵具有n個結(jié)點的完全二叉樹的樹高度(深度)是(9)。.在排序算法中，每次從未排序的記錄中挑出最小(或最大)關(guān)鍵碼字的記錄，加入到已排序記錄的末尾，該排序方法是(10)二、填空題(共 30分，每空2分)一個循環(huán)隊列的最大容量為m Cq_front為隊首指針，Cq_rear為隊尾指針。那么進隊操作時求

22、隊位 Cq_rear = (1)。一棵二叉機推I度為h,所有結(jié)點的度或為 0,或為2,則這棵二叉樹最少有(2)個結(jié)點對一組數(shù)據(jù)(84, 47, 25, 15, 21)排序，數(shù)據(jù)的排列次序在排序的過程中的變化為(1) 84 47 25 15 21(2) 15 47 25 84 21(3) 15 21 25 84 47(4) 15 21 2547 84則采用的排序是(3)排序。.樹是結(jié)點的有限集合，樹是由根結(jié)點和若干顆子樹構(gòu)成的。一個節(jié)點含有的子樹的個數(shù)稱為該節(jié)點(4); 一棵樹高為K的完全二叉樹至少有(5)個結(jié)點;高度為 K的二叉樹最大 的結(jié)點數(shù)為(6)。.二叉樹中某一結(jié)點左子樹的深度減去右子樹

23、的深度稱為該結(jié)點的(7 )。.具有256個結(jié)點的完全二叉樹的深度為(8 )。.就希爾排序的穩(wěn)定性而言，是一種(9 )的排序方法。.字符串a(chǎn)babaabab的nextval為(10 )(答案數(shù)值用逗號隔開，勿添加空格和括號)。.數(shù)據(jù)結(jié)構(gòu)分別為邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)(物理結(jié)構(gòu))，邏輯結(jié)構(gòu)有分為四類基本結(jié)構(gòu)，分別是(11)、(12)、(13)、(14)。.去除廣義表LS=(a1,a2,a3,，an)中第1個元素，由其余元素構(gòu)成的廣義表稱為LS的(15 )。二、填空題(共 30分，每空2分).通常從四個方面評價算法的質(zhì)量：(1 )、 ( 2 ) 、 ( 3 )和(4 ) _。. 一個算法的時間復雜度為 (

24、n3+n210g2n+14n)/n2 ,其數(shù)量級表示為_ ( 5 )。.假定一棵樹的廣義表表示為A (C, D (E, F, G) , H (I , J),則樹中所含的結(jié)點數(shù)為 ( 6 )個，樹的深度為 ( 5 ),樹的度為 ( 6 )。.后綴算式9 2 3 +- 10 2 / - 的值為（7 ）。中綴算式（3+4X） -2Y/3對應的后綴 算式為（8 ） _。.二叉樹中某一結(jié)點左子樹的深度減去右子樹的深度稱為該結(jié)點的（9 ）。.具有256個結(jié)點的完全二叉樹的深度為（10 ）。.若用鏈表存儲一棵二叉樹時，每個結(jié)點除數(shù)據(jù)域外，還有指向左孩子和右孩子的兩個指針。在這種存儲結(jié)構(gòu)中，n個結(jié)點的二叉樹共

25、有（11 ）。個指針域，其中有（12 ）。個指 針域是存放了地址，有（13 ）個指針是空指針。.對于一個具有n個頂點和e條邊的有向圖和無向圖，在其對應的鄰接表中，所含邊結(jié)點分別有（14 ）個和 （ 15 ）個。三、簡答題（共60分）915 *1. （5分）如圖1所示的二叉樹，請分別寫出中序和后序遍歷序列。12圖1第一題圖圖2第二題圖. （5分）對于圖2所示的無向帶權(quán)圖，構(gòu)造最小生成樹。（8分）什么是拓撲排序？簡述 AOV網(wǎng)的含義。（ 8分）有一份電文中共使用 6個字符：a,b,c,d,e,f,它們的出現(xiàn)頻率依次為 2,3,4,7,8,9 ,試構(gòu)造一棵哈夫曼樹，并1t算其加權(quán)路徑長度WPL（8分

26、）（1）.如果G1是一個具有n個頂點的連通無向圖，那么 G1最多有多少條邊？G1最少有多少條邊？（2）.如果G2是一個具有n個頂點的強連通有向圖，那么G2最多有多少條邊？ G2最少有多少條邊？（8分）關(guān)鍵字序列 T=（21 , 25, 49, 25* , 16, 08）,請寫出一趟快速排序的結(jié)果。該排 序方法是穩(wěn)定的嗎？為什么？（8分）簡述關(guān)鍵路徑的求解步驟。（10 分）已知關(guān)鍵字集合 19, 01,23, 14, 55, 68, 11,82, 36 ，設定哈希函數(shù) H（key） = key MOD 11 ,請構(gòu)造哈希表，利用線性探測再散列di = c i ,其中c=1解決沖突，并計算平均查找

27、長度ASL。三、簡答題（60分）（5分）棧是一種后進先出的線性表，如果一個棧的輸入序列為1 , 2, 3請寫出所有可 能的出棧序列。（5分）按照廣義表的定義，已知已知廣義表LS= （a,b,c）,（d,e,f）, 請寫出運用head和tail函數(shù)取出LS中原子e的運算。（5分）設單鏈表結(jié)點指針域為next ,試寫出刪除鏈表中指針 p所指結(jié)點的直接后繼的CtH 日 句 （10分）關(guān)鍵字序列 T= （21, 25, 49, 25*, 16, 08）,請寫出直接插入排序的具體實現(xiàn) 過程。（10分）線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：如果有 n個線性表同 時并存，并且在處理過程中各表的長

28、度會動態(tài)變化，線性表的總數(shù)也會自動地改變。 在此情況下，應選用哪種存儲結(jié)構(gòu)？為什么？（10分）簡述起冒泡排序的基本思路及優(yōu)點。（10分）如圖所示，將下圖的森林轉(zhuǎn)換到二叉樹，分別寫出二叉樹的前序和中序遍歷序列。圖1第7題圖（ 10分）證明二叉樹的性質(zhì)，任一二叉樹，若葉結(jié)點數(shù)是n0 ,度為2的結(jié)點數(shù)是n2，則n0=n2 +1（10分）如圖1所示，樹的存儲結(jié)構(gòu)可以有雙親法，孩子表示法等，請分別畫出雙親法和帶雙親的孩子表示法對該樹的存儲示意圖。圖2第9題圖三、簡答題（共60分）（5分）如圖1所示的二叉樹，請分別寫出前序和中序遍歷序列。圖1第一題圖圖2第二題圖. （5分）對于圖2所示的無向帶權(quán)圖，構(gòu)造最

29、小生成樹。（8分）關(guān)鍵字序列 T=（20, 25, 49, 49* , 13, 05）,請寫出快速排序的結(jié)果。該排序方 法是穩(wěn)定的嗎？為什么？（8分）根據(jù)給定集合15,3,14,2,6,9,16,17）,構(gòu)造相應的huffman樹，給出計算它的帶權(quán)路徑長度，以及集合中每個元素對應的huffman編碼。（8分）簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點。（8分）給出一組關(guān)鍵字 T=（12,2,16,30,8,28,4,10,20,6,18）,寫出用希爾排序（第一趟排序的 增量為5）從小到大排序時第一趟結(jié)束時的序列。（8分）若線性表的總數(shù)基本穩(wěn)定，且很少進行插入和刪除，但要求以最快的速度存取線 性表中的元素

30、，那么應采用哪種存儲結(jié)構(gòu)？為什么？（10 分）已知關(guān)鍵字集合 19, 01,23, 14, 55, 68, 11,82, 36 ），設定哈希函數(shù) H（key） = key MOD 11 ,請構(gòu)造哈希表，利用線性探測再散列di = c i ,其中c=1解決沖突，并計算平均查找長度ASL。三、簡答題（共60分）（5分）畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時，每加入一個數(shù)據(jù)后堆的變化。（5分）如圖1所示的二叉樹，請分別寫出前序和中序遍歷序列。圖1第一題圖(10分)已知一個圖的頂點集V和邊集E分別為：V=1,2,3,4,5,6,7);E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25); 用克 魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。(10分)閱讀算法1. LinkList mynote(LinkList L)/L是不帶頭結(jié)點的單鏈表的頭指針if(L&L-next)q=L ; L=L next; p=L ;S1:while(p next) p=p next;S2：pnext=q ; q next=NULL