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

1、一、選擇題（共20分，每題1分）.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類，分別是（）。A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B.順序結(jié)構(gòu)、鏈?zhǔn)浇Y(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個(gè)（）的有限序列（n0）。A.表元素 B .字符 C .數(shù)據(jù)元素D .數(shù)據(jù)項(xiàng).在下面的程序段中，對(duì)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）.下述哪一條是順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)

2、？（）A.存儲(chǔ)密度大B .插入運(yùn)算方便 C .刪除運(yùn)算方便 D .可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示.棧是一種（）的線性表。A.先進(jìn)先出B.后進(jìn)先出C.后進(jìn)后出D.不分順序.設(shè)棧的輸入序列是1, 2, 3, 4,則（）不可能是其出棧序列。A. 4 , 3, 1, 2,B.2 , 1, 3, 4,C. 1,4, 3, 2, D. 1, 2, 4, 3,.雙向鏈表中有兩個(gè)指針域，llink 和rlink ,分別指回前驅(qū)及后繼，設(shè) p指向鏈表中的一 個(gè)結(jié)點(diǎn)，q指向一待插入結(jié)點(diǎn)，現(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;.設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用 （）最節(jié)省時(shí)間。A.單鏈表 B.單循環(huán)鏈表C.帶尾指針的單循環(huán)鏈表 D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表

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

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

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

7、2n-1 B . n2 C . （n2/2）+（n/2） D . （n2/2）+（n/2）-1.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為兩大類，分別是（）。A.動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)B .順序結(jié)構(gòu)、鏈?zhǔn)浇Y(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. 堆排序.設(shè)給定權(quán)值總數(shù)有n個(gè)，其哈夫曼樹的結(jié)點(diǎn)總數(shù)為（）A.不確定 B . 2n C , 2n+1 D . 2n-1.設(shè)森林F對(duì)應(yīng)的二叉樹為 B,它有m個(gè)結(jié)點(diǎn)，B的根為p,p的右子樹結(jié)點(diǎn)個(gè)數(shù)為 n,森林F 中第一棵樹的結(jié)點(diǎn)個(gè)數(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. 堆排序.如果待排序序列中兩個(gè)數(shù)據(jù)元素具有相同的值，在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。下列排序方法中，哪一個(gè)是穩(wěn)定的排序方法？（）A.直接選擇排序B .二分法插入排序C .希爾排序 D.快速排序.樹是結(jié)點(diǎn)的有限集合，一棵非空的樹它有（）根結(jié)點(diǎn)。A.有0個(gè)或1個(gè)B.有0個(gè)或多個(gè) C.有且只有一個(gè) D. 有1個(gè)或1個(gè)以上一、選擇題（共20分，每題1分） TOC o 1-5 h z .

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

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

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

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

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

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

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

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

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

18、ext 數(shù)組值為（）。A. 0123 B . 1123 C . 1231 D , 1211.有一個(gè)長(zhǎng)度為12的有序表，按二分查找法對(duì)該表進(jìn)行查找，在表內(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）.對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的

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

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

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

22、隊(duì)位 Cq_rear = (1)。一棵二叉機(jī)推I度為h,所有結(jié)點(diǎn)的度或?yàn)?0,或?yàn)?,則這棵二叉樹最少有(2)個(gè)結(jié)點(diǎn)對(duì)一組數(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é)點(diǎn)的有限集合，樹是由根結(jié)點(diǎn)和若干顆子樹構(gòu)成的。一個(gè)節(jié)點(diǎn)含有的子樹的個(gè)數(shù)稱為該節(jié)點(diǎn)(4); 一棵樹高為K的完全二叉樹至少有(5)個(gè)結(jié)點(diǎn);高度為 K的二叉樹最大 的結(jié)點(diǎn)數(shù)為(6)。.二叉樹中某一結(jié)點(diǎn)左子樹的深度減去右子樹

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

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

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

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

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

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

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

30、，那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？為什么？（10 分）已知關(guān)鍵字集合 19, 01,23, 14, 55, 68, 11,82, 36 ），設(shè)定哈希函數(shù) H（key） = key MOD 11 ,請(qǐng)構(gòu)造哈希表，利用線性探測(cè)再散列di = c i ,其中c=1解決沖突，并計(jì)算平均查找長(zhǎng)度ASL。三、簡(jiǎn)答題（共60分）（5分）畫出向小根堆中加入數(shù)據(jù)4, 2, 5, 8, 3時(shí)，每加入一個(gè)數(shù)據(jù)后堆的變化。（5分）如圖1所示的二叉樹，請(qǐng)分別寫出前序和中序遍歷序列。圖1第一題圖(10分)已知一個(gè)圖的頂點(diǎn)集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é)點(diǎn)的單鏈表的頭指針if(L&L-next)q=L ; L=L next; p=L ;S1:while(p next) p=p next;S2：pnext=q ; q next=NULL