全國(guó)2019年4月自考02142數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題及答案

1、一、草項(xiàng)迭擇題：*大亀共15小題每小& 2分共30分。在每小通列出的備選項(xiàng)中只有一項(xiàng) 是符合題目要求的請(qǐng)將其選出。I.下列幾種時(shí)間復(fù)雜度中，階數(shù)呂小的是A.O（log2n）B.O（n）2 棧和隊(duì)列的共同待點(diǎn)是A.都是線性表B.先進(jìn)先出C.O(n:)D.O(l)C.后進(jìn)先出D只能插入操作絕老啟用前2019年4月高等教育自學(xué)考試全國(guó)統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論（課程代碼02142）注意事項(xiàng)：1. 本試卷分為兩部分，第一部分為選擇題，第二部分為非選擇題。2. 應(yīng)考者必須按試亀順序在答!卡（紙）指定位上作答，答在試卷上無效。3. 涂寫部分畫圖都分必須便用2B鉛筆，書寫部分必須便用黑色字跡簽字筆。第

2、一部分選擇題3.假設(shè)一個(gè)10X10的上三角矩陣A按照列優(yōu)先順序壓編存儲(chǔ)在一維數(shù)組B中，則B效組的 大小應(yīng)為D.101A.50B.55C.1004一個(gè)棧的入棧序列是a, b. c, d. s則?？赡艿妮攲缧蛄惺荄.dceabA.edcabB.deabcC.abcde5假定一個(gè)順序存儲(chǔ)的循環(huán)隊(duì)列的隊(duì)頭和隊(duì)尾折針分別為f和“則判斷隊(duì)空的條件為A.f = = NULLB.f = rCr+1 = = fDf+1 = = r6如果結(jié)點(diǎn)A有2個(gè)兄弟結(jié)點(diǎn)結(jié)點(diǎn)B為A的雙親，則結(jié)點(diǎn)B的度為A.2B.3C.4D.57二叉樹的中序遍歷中結(jié)點(diǎn)P排在結(jié)點(diǎn)Q之前的條件是在二叉樹中A.P在Q的左邊B.P在Q的右邊C.P是Q的

3、祖先 D.P是Q的子孫&二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為A.2k-1B2+C.2klD.2®9.A是7X4的二維數(shù)組按行優(yōu)先方式順序存儲(chǔ)元素A00的存儲(chǔ)地址為1000若每個(gè)元 索占2個(gè)字節(jié)則元素A33的存儲(chǔ)地址為D.1032A.1O26B.1028C.1030數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第1頁(yè)（共3頁(yè)）10在表長(zhǎng)為n的順序表上做刪除運(yùn)算其平均時(shí)間復(fù)雜度為A.O(l)B.O(n)C.O(nIog:n)D.O(n,)11. 莊含n個(gè)頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，零元素的個(gè)數(shù)為A.eB.2eC.n:eD.n1 2e12. 設(shè)順序表的長(zhǎng)度為n,則插入算法的平均移動(dòng)次數(shù)約為A.nB.n/2C.n-

4、1D.(n-l)/213 設(shè)一組初始記錄關(guān)犍字序列為(13,18.24.35.47.5O.62.83.90,115.134).則利用二分査找算法査找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為A.1B.2C.3D.414.以下排序方法中，穩(wěn)定的是A.直接插入排序和快速排序B.快速排序和胃泡排序C.直接選擇排序和冒泡排序D.H泡排序和克接插入排序15對(duì)D個(gè)記錄的文件進(jìn)行快速排序所需耍的輔助存儲(chǔ)空間的空間復(fù)雜度為, i .：.v .； j -； .? , .t r ： >.A.O(1)B.O(n)C.O(log:n)D.OCn1)s第二部分非選擇題二、填空題：本大題共13空，毎空2分，共26分。16.1

5、976年瑞士計(jì)算機(jī)科學(xué)家Niklaus Wirth忡提出一個(gè)著名公式：程序=數(shù)據(jù)結(jié)構(gòu)+ 個(gè)利黑t 廿厶17.簡(jiǎn)單地說，數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)_厶_數(shù)據(jù)和存儲(chǔ)數(shù)據(jù)的方式.1&線性表中結(jié)點(diǎn)個(gè)數(shù)n稱為 ,19.線性表上的插入和制除運(yùn)算限定在表的某一端進(jìn)行的數(shù)據(jù)結(jié)構(gòu)是.A20 對(duì)稀嫌矩陣進(jìn)行壓縮存儲(chǔ)的目的是節(jié)省21 個(gè)具有n個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為巴= 22構(gòu)造最小生成樹的算法冇兩種：Prim算法和 _算法.23. 棵樹的結(jié)點(diǎn)個(gè)數(shù)最少為24. 有K個(gè)葉子結(jié)點(diǎn)的哈夫曼樹，其結(jié)點(diǎn)的總數(shù)為_ _25由二叉樹的后序序列和 序列可以唯一確定一棵二叉樹26 二分査找算法的平均時(shí)間復(fù)雜度為A_.27 若待排序的

6、序列中存在多個(gè)記錄具有相同的鍵值經(jīng)過排序這些記錄的相對(duì)次序仍然保持不變則稱這種排序方法是 的.28在最壞悄況下即對(duì)幾乎已是排好序的入序列快速排序算法的效率較低此時(shí)其時(shí)間復(fù)雜度近似為數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題第2頁(yè)(共3頁(yè))三、應(yīng)用&：本大BS共5小&毎小聽6分共30分。29. 有一個(gè)轅數(shù)序列其輸入順序?yàn)?0,30.90, 10,45,78.試?yán)脳⑵漭攲缧蛄懈淖優(yōu)?0,10.45.90.78.20.寫出諫糧數(shù)序列進(jìn)棧和出棧的操作步驟。(用push(x)表示x進(jìn)棧, pop(x)表示X出棧)/30. 分別寫出題30圖所示的二叉樹的先序遍歷、中序遍歷和后序遍歷三種訪問方式的結(jié)點(diǎn)訪問序列C；£ 訂題30圖31 設(shè)有字符集 A. B, C, D, E, F ,各字符使用頻率對(duì)應(yīng)為2. 4, 5, 13, 9, 18,試畫出哈 夫曼樹(要求任一結(jié)點(diǎn)的左孩子權(quán)值小于右孩子).32.已知散列表的長(zhǎng)度為11,散列阪數(shù)H(key) = key%ll,采用線性探測(cè)法解決沖突，試用關(guān) 鍵字值的序列：75,25,80,35,60,46.50,55建立散列表。33試用冒泡法對(duì)數(shù)列(45. 73, 12, 23, 52, 5, 38)進(jìn)行遞增排序，寫出第1、2、3、4趙排序結(jié) 果，并給出冒泡排序算法的時(shí)間