數(shù)據(jù)結(jié)構(gòu)專升本模擬題及參考答案2

1、作業(yè)題(一)9、單項(xiàng)選擇題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)2. 鏈表不具有的特點(diǎn)是()A.插入、刪除不需要移動(dòng)元素B .可隨機(jī)訪問(wèn)任一元素C.不必事先估計(jì)存儲(chǔ)空間D .所需空間與線性長(zhǎng)度成正比3. 下面程序段的時(shí)間復(fù)雜度的量級(jí)為() 。For(i=1;i<=n;i+)For(j=1;j<=I;j+)For(k=1;k<=j;k+)X=x+1;A O(1)B O(n)C O(n2)D O(n3)4. 在一個(gè)帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表中，若要在 p 所指向的結(jié)點(diǎn)之前插入一個(gè)新結(jié)點(diǎn)

2、，則需要相繼修改()個(gè)指針域的值。A 2B 3C 4D 65、一個(gè)順序存儲(chǔ)線性表的第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度是2，則第6 個(gè)元素的存儲(chǔ)地址是( ) 。A 98B 100C 102D 1066、判定一個(gè)棧s (最多元素為 m。為空的條件是()。A s- top! =0B s- top= =0C s- top! =m0D s- top= =m07、循環(huán)隊(duì)列用數(shù)組 Am(下標(biāo)從0到m-1)存放其元素值，已知其頭尾指針?lè)謩e是front和rear ,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是() 。A ( rear-front+m ) %mB rear-front+1C rear-front-1D rea

3、r-front8、設(shè)有兩個(gè)串S1與S2,求串S2在S1中首次出現(xiàn)位置的運(yùn)算稱作()。A.連接B.求子串C.模式匹配D.判子串9、設(shè)串S1='ABCDEFG； S2='PQRST',函數(shù)con (x, y)返回x和y串的連接串，subs(s,i,j) 返回串S的 的 從 序 號(hào) i 的 字 符 開(kāi) 始 的 j 個(gè) 字 符 組 成 的 子 串 ， len(s) 返 回 串 S 的 長(zhǎng) 度 ， 則 con(subs(S1,2,len(S2),subs(S1,len(S2),2)的結(jié)果是() 。A BCDEFB BCDEFGBCDEFEFC BCPQRST10、數(shù)組常用的兩種基

4、本操作是（）。A.建立與查找B.刪除與查找C.插入與索引D.查找與修改二、填空題1 .所謂稀疏矩陣指的是 且分布沒(méi)有規(guī)律。2 .隊(duì)列是 的線性表，其運(yùn)算遵循 的原則。3 .空格串是。4 .簡(jiǎn)單選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無(wú)關(guān)的算法有 。5、設(shè)圖G有n個(gè)頂點(diǎn)和e條邊，則對(duì)用鄰接矩陣表示的圖進(jìn)行深度或廣度優(yōu)先搜索遍歷時(shí)的時(shí)間復(fù)雜度為,而對(duì)用鄰接表表示的圖進(jìn)行深度或廣度優(yōu)先搜索遍歷時(shí)的時(shí)間復(fù)雜度為 ,圖的深度或廣 度優(yōu)先搜索遍歷時(shí)的空間復(fù)雜度均為 。6、一個(gè)圖的 表示法是唯一的，而 表示法是不唯一的。 三、算法設(shè)二叉樹(shù)采用二叉鏈表結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法統(tǒng)計(jì)給定二叉樹(shù)中的一度結(jié)點(diǎn)數(shù)目。四、應(yīng)用

5、題1、對(duì)關(guān)鍵字無(wú)序序列（36, 25, 48, 12, 65, 43, 20, 58）進(jìn)行直接選擇排序，請(qǐng)寫出每一趟排序的結(jié)果。（10 分）2、對(duì)無(wú)向帶權(quán)圖，用克魯斯卡爾算法構(gòu)造最小生成樹(shù)。（10分）3、已知記錄關(guān)鍵字集合為（53,17,19,61,98,75,79,63,46,49）要求散列到地址區(qū)間（ 100,101,102,103,104,105,106,107,108,109）內(nèi)，若產(chǎn)生沖突用開(kāi)型尋址法的線性探測(cè)法解決。要求寫出選用的散列函數(shù)；形成的散列表；計(jì)算出查找成功時(shí)平均查找長(zhǎng)度與查找不成功的平均查找長(zhǎng)度。（設(shè)等概率情況）4、設(shè)被查找文件有 4095個(gè)記錄，對(duì)每個(gè)記錄查找記錄概率

6、相等，若采用順序查找，成功查找平均比較次 數(shù)為多少?作業(yè)題（二）!、單項(xiàng)選擇題1 .有六個(gè)元素6, 5, 4, 3, 2, 1的順序進(jìn)棧，問(wèn)下列哪一個(gè)不是合法的出棧序列？（）A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 62 .棧和隊(duì)都是（）A.順序存儲(chǔ)的線性結(jié)構(gòu)B.鏈?zhǔn)酱鎯?chǔ)的非線性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)3、順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（）的線形表。A.散列存儲(chǔ)B.順序存儲(chǔ)或鏈接存儲(chǔ)D.索引存儲(chǔ)C.壓縮存儲(chǔ)4、分別以下列序列構(gòu)造二叉排序樹(shù)，與用其它三個(gè)序列所構(gòu)造的結(jié)果不同的是（）(100, 12

7、0, 110, 130, 80, 60 , 90 )A. ( 100, 80, 90, 60 , 120 , 110, 130) B.C. ( 100, 60, 80 , 90 , 120 , 110, 130) D.(100 , 80, 60 , 90 ,120 , 130, 110)A. nC. log2n查找速度（）A.必定快C.在大部分情況下要快B.不一定D.取決于表遞增還是遞減5、折半查找的平均比較次數(shù)為（）。B. n/2D. log2(n+1)6、當(dāng)在一個(gè)有序的順序存儲(chǔ)表上查找一個(gè)數(shù)據(jù)時(shí)，即可用折半查找，也可用順序查找，但前者比后者的v1出發(fā)，所得B. v1, v2, v3, v4

8、 , v5C. v1, v3, v4, v5, v2D. v1, v4, v3, v5 , v27、已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如下圖如示。根據(jù)有向圖的深度優(yōu)先遍歷算法，從頂點(diǎn)到的頂點(diǎn)序列是（）。A. v1, v2, v3, v5, v48、為了方便地對(duì)圖狀結(jié)構(gòu)的數(shù)據(jù)進(jìn)行存取操作，則其中數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)宜采用（B.鏈?zhǔn)酱鎯?chǔ)D.散列存儲(chǔ)A.順序存儲(chǔ)C.索引存儲(chǔ)9、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為s,則所有頂點(diǎn)的入度之和為（）。B. s-1D. nA. sC. s+110、如圖所示，給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)A出發(fā)，對(duì)它進(jìn)行深度優(yōu)先搜索得到的頂點(diǎn)序列是B. A G B F

9、D E CD. A B D G F E CA. A E C D B F GC. A C E D B G F二、填空題1 .設(shè)n0為哈夫曼樹(shù)的葉子結(jié)點(diǎn)數(shù)目，則該哈夫曼樹(shù)共有 個(gè)結(jié)點(diǎn)。2 .有數(shù)據(jù)WG=7 19, 2, 6, 32, 3, 21, 10,則所建Huffman樹(shù)的樹(shù)高是,帶權(quán)路徑長(zhǎng)度 WPL 為。3 .設(shè)一棵完全二叉樹(shù)葉子結(jié)點(diǎn)數(shù)為k,最后一層結(jié)點(diǎn)數(shù)2,則該二叉樹(shù)的高度為 。4 .采用分塊查找時(shí)，若線性表中共有 625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來(lái)確定 結(jié)點(diǎn)所在的塊時(shí)，每塊應(yīng)分 個(gè)結(jié)點(diǎn)最佳。5、設(shè)G為具有N個(gè)頂點(diǎn)的無(wú)向連通圖，則 G中至少有 條邊。6、哈夫曼樹(shù)(Hu

10、ffman Tree )又稱。它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中，帶權(quán)路徑 長(zhǎng)度wpl。7、樹(shù)的先序遍歷過(guò)程如下：若樹(shù)為空，則進(jìn)行空操作；若樹(shù)非空，則訪問(wèn)樹(shù)的;依次先序遍歷樹(shù)的。三、應(yīng)用題1、給定權(quán)值集合1,4, 2, 6, 9,構(gòu)造相應(yīng)的哈夫曼樹(shù)，并計(jì)算它的帶權(quán)路徑長(zhǎng)度。2、對(duì)關(guān)鍵字序列10, 6, 3, 2, 5, 4,構(gòu)造一棵平衡二叉(排序)樹(shù)并畫圖(要求畫出建樹(shù)過(guò)程)。3、設(shè)有一個(gè)有序文件，其中各記錄的關(guān)鍵字為(1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15),當(dāng)用折半查找算法查找關(guān)鍵字為3, 8, 19時(shí)，其比較次數(shù)分別為多少？

11、4、對(duì)有五個(gè)結(jié)點(diǎn) A,B, C, D, E的圖的鄰接矩陣，100 30 10-0goo g60020g1080co二 50 0(1) .畫出邏輯圖；(2) .畫出圖的十字鏈表存儲(chǔ)；(3) .基于鄰接矩陣寫出圖的深度、廣度優(yōu)先遍歷序列；(4) .計(jì)算圖的關(guān)鍵路徑。作業(yè)題(三)一、單項(xiàng)選擇題1 串的長(zhǎng)度是指（A.串中所含不同字母的個(gè)數(shù)C.串中所含不同字符的個(gè)數(shù)B 串中所含非空格字符的個(gè)數(shù)D 串中所含字符的個(gè)數(shù)2設(shè)有數(shù)組Ai,j ，數(shù)組的每個(gè)元素長(zhǎng)度為3 字節(jié)， i 的值為 1 到 8 ， j 的值為 1 到10，數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)，元素 A5, 8的存儲(chǔ)首地址為（

12、）A. BA+141 B. BA+180 C. BA+222 D. BA+2253算法分析的兩個(gè)主要方面是（） 。A.空間復(fù)雜性和時(shí)間復(fù)雜性BC.可讀性和文檔性D4算法分析的目的是（） 。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性BC.分析算法的效率以求改進(jìn)D5. 下面程序段的時(shí)間復(fù)雜性的量極為（Int fun（int n） int i=1,s=1;While（s<n）S+= +I;Return I;A O（n/2）BC O（n）D6. 線性表是（） 。A. 一個(gè)有限序列，可以為空BC. 一個(gè)無(wú)限序列，可以為空D7. 帶頭結(jié)點(diǎn)的單鏈表L 為空的判定條件是（A L= =NULLBC L- next= =LD

13、,正確性和簡(jiǎn)明性.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性.研究算法中的輸入和輸出的關(guān)系.分析算法的易懂性和文檔性 O（lbn） O（ ）一個(gè)有限序列，不能為空一個(gè)無(wú)限序列，不能為空）。 L- next= =NULL L! =NULL8. 在一個(gè)長(zhǎng)度為n 的線性表中，刪除值為x 的元素時(shí)需要比較元素和移動(dòng)元素的總次數(shù)為（A （ n+1） /2B n/2n+1C n9. 一個(gè)順序存儲(chǔ)線性表的第一個(gè)元素的存儲(chǔ)地址是90，每個(gè)元素的長(zhǎng)度是2，則第6 個(gè)元素的存儲(chǔ)地址是（ ） 。A 98B 100C 102D 10610. 如果某鏈表中最常用的操作是取第i 個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用（）存儲(chǔ)方式最節(jié)省時(shí)間。A,單鏈表C.單

14、循環(huán)鏈表D.順序表二、填空題1 .高度為2的二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有 個(gè)，高度為3的二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有 個(gè)。2 .在順序表(8,11,15,19,25,26,30,33,42,48,50)中，用折半查找關(guān)鍵字值20,需做的關(guān)鍵字比較次數(shù)為。3 .在有n個(gè)頂點(diǎn)的無(wú)向圖中，每個(gè)頂點(diǎn)的度最大可達(dá) 。4 .已知廣義表 A= (a, b, c), (d, e, f),則廣義表運(yùn)算 head (tail (tail (A) =。5、數(shù)組(Array )是n(n>1)個(gè) 的有序組合，數(shù)組中的數(shù)據(jù)是按順序存儲(chǔ)在一塊 的存儲(chǔ)單元中。6 .采用順序存儲(chǔ)結(jié)構(gòu)表示三元組表( Triple Table ),來(lái)實(shí)現(xiàn)對(duì)

15、稀疏矩陣的一種壓縮存儲(chǔ)形式，就稱為,簡(jiǎn)稱 表。7 .運(yùn)算是矩陣運(yùn)算中最基本白一項(xiàng)，它是將一個(gè) m x n的矩陣變成另外一個(gè) n x m的矩陣，同時(shí) 使原來(lái)矩陣中元素的行和列的位置互換而值保持不變。三、應(yīng)用題1、對(duì)于下圖所示的二叉樹(shù)，畫出二叉鏈表存儲(chǔ)結(jié)構(gòu)圖。2、請(qǐng)畫出下圖所示的樹(shù)所對(duì)應(yīng)的二叉樹(shù)。3.已知一個(gè)無(wú)向圖如下圖所示，要求分別用Prim和Kruskal算法生成最小樹(shù)(假設(shè)以為起點(diǎn)，試畫出構(gòu)造過(guò)程)。4.已知完全二叉樹(shù)的第8層有8個(gè)結(jié)點(diǎn)，則其葉子結(jié)點(diǎn)是多少?5.畫出如圖所示中樹(shù)的二叉樹(shù)的表示形式。作業(yè)題(四)一、單項(xiàng)選擇題1 .將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少得比較次數(shù)是(

16、A. nB. 2n-1C. 2nD. n-12 . 一個(gè)有n個(gè)頂點(diǎn)的無(wú)向連通圖，它所包含的連通分量個(gè)數(shù)為()。A.0B.1C.nD.n+13 .數(shù)據(jù)文件的基本操作中最重要的操作是()。A.插入B.刪除C.修改D.檢索4 .對(duì)關(guān)鍵碼序列28, 16, 32, 12, 60, 2, 5, 72快速排序，從小到大一次劃分結(jié)果為()。A.(2,5,12,16)26(60,32,72)B. (5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D. (5,16,2,12)28(32,60,72)5 .如果只想得到1000個(gè)元素組成的序列中第5個(gè)最小元素之前的部分

17、排序的序列，用( )方法最快。A.堆排序B.快速排序C.插入排序D.歸并排序6 .算法分析的目的是()。A.找出數(shù)據(jù)結(jié)構(gòu)的合理性B.研究算法中的輸入和輸出的關(guān)系C.分析算法的效率以求改進(jìn)D .分析算法的易懂性和文檔性7 .二叉樹(shù)的第I層上最多含有結(jié)點(diǎn)數(shù)為()A. 2I B . 2 I-1 -1C . 2 I-1 D . 2I -18 .循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A中，長(zhǎng)度為m則入隊(duì)時(shí)的操作為()。A. rear=rear+1 B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod m D. rear=(rear+1)mod(m+1)9 .廣義表滿足 Head(A尸

18、Tail(A)，則人為()。A. ()B.()C. () , 0)D.(),(),()10.在一棵度為3的樹(shù)中，度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的 結(jié)點(diǎn)數(shù)為()個(gè)。A. 3B. 4C. 5D. 6二、填空題1 .在一個(gè)循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 。2 .數(shù)組中每一個(gè)數(shù)據(jù)通常稱為 2 用下標(biāo)區(qū)分，其中下標(biāo)的個(gè)數(shù)由數(shù)組的決定。3 .一個(gè)圖的 表示法是唯一的，而 表示法是不唯一的。4 .在一個(gè)10階的B-樹(shù)上，每個(gè)數(shù)根結(jié)點(diǎn)中所含的關(guān)鍵字?jǐn)?shù)目最多允許 個(gè)，最少允許 個(gè)5 .對(duì)關(guān)鍵字序列(52, 80, 63, 44, 48, 91)進(jìn)行一趟快速排序之后

19、的得到結(jié)果為 。10. 高度為 1 的平衡二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有個(gè)，高度為2 的平衡二叉樹(shù)的結(jié)點(diǎn)數(shù)至少有個(gè)。三 判斷1. 順序存儲(chǔ)結(jié)構(gòu)屬于靜態(tài)結(jié)構(gòu)，鏈?zhǔn)浇Y(jié)構(gòu)屬于動(dòng)態(tài)結(jié)構(gòu)。（）2. 即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（）3. 帶權(quán)無(wú)向圖的最小生成樹(shù)必是唯一的。（）4. B-樹(shù)和B+樹(shù)都可用于文件的索引結(jié)構(gòu)。（）5. 在用堆排序算法排序時(shí)，如果要進(jìn)行增序排序，則需要采用"大根堆"。 （）四、應(yīng)用題1 .模式串p="abaabcac"的next函數(shù)值序列為多少？2. 設(shè)二維數(shù)組A56 的每個(gè)元素占

20、4個(gè)字節(jié)，已知LOC（ a0,0） =1000， A 共占多少個(gè)字節(jié)？A 的終端結(jié)點(diǎn) a4,5 的起始地址為多少？按行和按列優(yōu)先存儲(chǔ)時(shí)，a2,5 的起始地址分別為多少？3. 設(shè)a,b,c,d,e五個(gè)字符的編碼分別為1,2,3,4,5,并設(shè)標(biāo)識(shí)符依以下次序出現(xiàn)：ac,bd,aa,be,ab,ad,cd,bc,ae,ce）要求用口希（Hash）方法將它們存入具有10個(gè)位置的表中。（ 1）將上述關(guān)鍵字（標(biāo)識(shí)符）構(gòu)造一個(gè)哈希函數(shù)，使得發(fā)生沖突盡可能地少；（ 2）線性探測(cè)再散列法解決沖突。寫出上述各關(guān)鍵字在表中位置。4. 給定一個(gè)關(guān)鍵字序列24 ， 19， 32， 43， 38， 6， 13， 22，請(qǐng)

21、寫出快速排序第一趟的結(jié)果；堆排序時(shí)所建的初始堆；歸并排序的全過(guò)程。然后回答上述三中排序方法中那一種方法使用的輔助空間最少？在最壞情況下那種方法的時(shí)間復(fù)雜度最差？作業(yè)題（五）、單項(xiàng)選擇題1 . 一組記錄的關(guān)鍵碼為（46, 79, 56, 38, 40, 84）,則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為（）。A. (38,40,46,56,79,84)B. (40,38,46,79,56,84)C. (40,38,46,56,79,84)D. (40,38,46,84,56,79)2 . 廣義表 A=(a,b,(c,d),(e,(f,g),則下面式子的值為 ()GetHead(

22、GetTail(GetHead(GetTail(GetTail(A)A. (g) B. (d) C. c D. d3 .對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其高度為()A. nlog 2n B . log 2n C . Jog 2n_+1 D ,不確定4 .如圖所示，給出由7個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn) 1出發(fā)，對(duì)它進(jìn)行深度優(yōu)先搜索得到的頂點(diǎn)序列是( )。B. 1 3 4 7 6 2 5D. 1 2 4 7 6 5 3A. 1 3 5 4 2 6 7C. 1 5 3 4 2 7 6無(wú)時(shí)圖A. N+1C. log2N8.下面關(guān)于m階B樹(shù)說(shuō)法正確的是（ 每個(gè)結(jié)點(diǎn)至少有兩棵非空子樹(shù)； 所有葉子在同一層上；A.C.

23、5 .采用鄰接表存儲(chǔ)的圖，其深度優(yōu)先遍歷類似于二叉樹(shù)的（）。B.先序遍歷A.中序遍歷C.后序遍歷D.按層次遍歷6 . 已 知 有 向 圖 G=(V,E), 其 中 V=V 1,V2,V3,V4,V5,V6,V7E=<V 1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>,G 的拓?fù)?序列是 （ ）。A. V1,V3,V4,V6,V2,V5,V7B. V1,V3,V2,V6,V4,V5,V7C. V1,

24、V3,V4,V5,V2,V6,V7D. V1,V2,V5,V3,V4,V6,V77.順序查找法適用于查找順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)的線性表，平均比較次數(shù)為（）。在此假定N為線性表中結(jié)點(diǎn)數(shù)，且每次查找都是成功的。B. 210g2ND. N）°樹(shù)中每個(gè)結(jié)點(diǎn)至多有 m 1個(gè)關(guān)鍵字；當(dāng)插入一個(gè)數(shù)據(jù)項(xiàng)引起 B樹(shù)結(jié)點(diǎn)分裂后，樹(shù)長(zhǎng)高一層。B.D.9.已知一個(gè)線性表（38, 25, 74, 63, 52, 48）,假定采用h（k尸k%7計(jì)算Hash地址進(jìn)行散列存儲(chǔ)，若利用鏈地址法處理沖突，則在該Hash表上進(jìn)行查找的平均查找長(zhǎng)度為（）。1、C 2、B 3、D 4、C 5、B 6、B 7、A 8、C 9、D

25、10、DA. 1.0B. 7/6C. 4/3D. 3/210.在排序算法的實(shí)施過(guò)程中，使用輔助存儲(chǔ)空間為O （1）的有（）。A .簡(jiǎn)單排序法B.快速排序法C.歸并排序法D.基數(shù)排序法二、填空題1. n （n大于1）個(gè)結(jié)點(diǎn)的各棵樹(shù)中，其中深度最大的那棵樹(shù)的深度是n,它共有 個(gè)葉子結(jié)點(diǎn)和個(gè)非葉子結(jié)點(diǎn)。2 .設(shè)一棵后序線索樹(shù)的高是50,結(jié)點(diǎn)x是樹(shù)中的一個(gè)結(jié)點(diǎn)，其雙親是結(jié)點(diǎn)y,y的右子樹(shù)高度是60, x是y的左孩子。則確定 x的后繼最多需經(jīng)過(guò) 中間結(jié)點(diǎn)（不含后繼及 x本身）3 .高度為2 （第2層為葉子）的3階B-樹(shù)中，最多有 個(gè)關(guān)鍵字。4 .分別采用堆排序，快速排序，冒泡排序和歸并排序，對(duì)初態(tài)為無(wú)序

26、的表，則平均情況下最省時(shí)間的是 算法。5 .簡(jiǎn)單選擇排序和起泡排序中比較次數(shù)與序列初態(tài)無(wú)關(guān)的算法有 。6 .串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是將存儲(chǔ)區(qū)域分成一系列大小相同的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有兩個(gè)域 域和域。其中 域用于用于存放數(shù)據(jù)， 域用于存放下一個(gè)結(jié)點(diǎn)的指針三.判斷1 .順序存儲(chǔ)的線性表可以隨機(jī)存取。（）2 .即使對(duì)不含相同元素的同一輸入序列進(jìn)行兩組不同的、合法的入棧和出棧組合操作，所得的輸出序列也一定相同。（）3 .十字鏈表是無(wú)向圖的一種存儲(chǔ)結(jié)構(gòu)。（）4 .折半查找方法適用于排列連續(xù)順序文件的查找。（）5 .在執(zhí)行某個(gè)排序算法過(guò)程中，出現(xiàn)了排序碼朝著最終排序序列位置相反方向移動(dòng)，則該算法是不穩(wěn) 定的。（）四

27、、應(yīng)用題 1.用十字鏈表表示一個(gè)有 k個(gè)非零元素的m x n的稀疏矩陣，則其總的結(jié)點(diǎn)數(shù)為多少?2 . G=（V,E）是一個(gè)帶有權(quán)的連通圖，則：（1）.請(qǐng)回答什么是G的最小生成樹(shù)；（2）. G為下圖所示，請(qǐng)找出G的所有最小生成樹(shù)。3 .請(qǐng)分別敘述在一個(gè)連續(xù)順序文件中采用順序查找法，折半查找法和分塊查找法查找一個(gè)記錄，該文件中記錄應(yīng)該滿足什么條件？4 .設(shè)待排序文件之排序碼為（88, 33, 22, 55, 99, 11, 66）,采用順序存儲(chǔ)。請(qǐng)用直接選擇排序算法 對(duì)上述文件進(jìn)行排序，用圖示說(shuō)明排序過(guò)程。作業(yè)題一參考答案: 二、填空題1、非零元很少2、操作受限(或限定僅在表尾進(jìn)行插入和限定僅在表

28、頭進(jìn)行刪除操作或限制存取點(diǎn)或特殊) 后進(jìn)后出)3、簡(jiǎn)單選擇排序4、O(n2), O(e), O(n)5、鄰陣矩陣，鄰接表三、算法答：int count = 0;void onechild ( Btree t) if ( t!=NULL) onechild (t->lchild );onechild ( t->rchild );if ( t->lchild!=NULL && (t->rchild!=NULL | t->lchild!=NULL && t->rchild=NULL )count+;四、應(yīng)用題1、答：(0)36t_2

29、54B1265432053(1)122L433665432053122048t_366543255812202536654348581220253665 43 t_i48531220253643L65 485312202536434365 53 ti1220253S434858652、答:(1)(2)#一、單項(xiàng)選擇題13(5)(6)3、答：由于地址空間為 10,且從100開(kāi)始，故散列函數(shù)選為 H (key) =key%7+100。散列地址100101102103104105106107108109關(guān)鍵字98637917531961754649比較次數(shù)111113510用線性探測(cè)再散列解決沖突，

30、ASLsucc=27/104、答：成功查找平均比較查找長(zhǎng)度為：(n+1) /nlog2 (n+1)卜1 。作業(yè)題二參考答案:二、填空題1、2n0-1 2 、6, 261 3 、 log 2k*1 4、25 5、N-17、根結(jié)點(diǎn)，各子樹(shù)三、應(yīng)用題1、答：不唯一，型對(duì)即可© ©此樹(shù)的帶權(quán)路徑長(zhǎng)度 WPL =9*1+6*2+4*3+(1+2)*4=452、答：(1)插入10(2)插入6(3)插入3CDCD/調(diào)事QBi(5)插入2(6)插入5插入46、最優(yōu)二叉樹(shù)，最小的二叉樹(shù)(4) 小,軍C3 CD(8)I G 、！1、C 2、C 3、B 4、C 5、D 6、C 7、C 8、B 9

31、、A 10、CCO CD3J £ 建3、答：當(dāng)關(guān)鍵字為3時(shí)，比較次數(shù)為4;當(dāng)關(guān)鍵字為8時(shí)，比較次數(shù)為1;當(dāng)關(guān)鍵字為19時(shí)，查找不成功；4、答：(2)略(3)深度優(yōu)先遍歷序列： ABCDC度優(yōu)先遍歷序列：0xz。ABCED( 4)關(guān)鍵路徑 A-B (長(zhǎng) 100)作業(yè)題三參考答案:一、單項(xiàng)選擇題151、 2, 3 27.矩陣轉(zhuǎn)置1、應(yīng)用題答：2、答:3、E答：Prim算法構(gòu)造最小生成樹(shù)的步驟如24題所示，為節(jié)省篇幅，這里僅用Kruskal算法,構(gòu)造最小生成(下圖也可選(2,4)代替(3,4),(5,6)代替(1,5)樹(shù)過(guò)程如下:g102111、D 2、B 3、A 4、C 5、D 6、A

32、7、B 8、C 9、B 10、D二、填空題、4 3、n-1 4 、e 5、相同類型數(shù)據(jù)，地址連續(xù) 6.三元組順序表，三元組一、單項(xiàng)選擇題19d層，則除4 .答：由完全二叉樹(shù)的定義可知，除最后一層外，其他各層的結(jié)點(diǎn)是滿的。設(shè)該完全二叉樹(shù)有。這里第8層有最后一層外各層的結(jié)點(diǎn)個(gè)數(shù)分別為：1, 2, 4, 8, 16, 32,，即第i層的結(jié)點(diǎn)個(gè)數(shù)為2i-1 8個(gè)結(jié)點(diǎn)，顯然第8/層是最后的一層，那么第 7層的結(jié)點(diǎn)個(gè)數(shù)為27-1=64個(gè)，其中的4個(gè)結(jié)點(diǎn)有8個(gè)葉子結(jié)點(diǎn),余下的為葉子結(jié)點(diǎn)，個(gè)數(shù)為64-4=60,所以該完全二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)為60+8=68個(gè)。5 .答：對(duì)應(yīng)的二叉樹(shù)形式如圖所示:作業(yè)題四參考答案:一、單項(xiàng)選擇題1. A 2. B 3. D 4. B 5. D 6、C 7、C 8、C 9、B 10、D二、填空題1 .答：前一個(gè)位置 2.答：數(shù)組元素，數(shù)組元素，維數(shù)3.答：鄰陣矩陣，鄰接表4.答：9, 45.答：48 44 52 64 80 916、1 , 2三.判斷1 .答：V2 .答：X3 .答：X4 .答：V5 .答：V四、應(yīng)用題1 .答：模式p的next函數(shù)值如下：-1 0 0 1 1 2 0 12 .答：A共120個(gè)字節(jié)。a4,5的起始地址為：11