全國2012年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題及答案

1、20122012版教材201210數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題02142一、單項選擇題(本大題共 15 小題，每小題 2 分，共 30 分)在每小題列出的四個備選項中只有一個是符合題目要求的。錯選、多選或未選均無分。下面幾種算法時間復(fù)雜度階數(shù)中，值最大的是A.O(nlog2n)C.O(n)D.O(2n)這種算法好壞的評價因素稱為正確性B.易讀性C.健壯性D.時空性10040個元素之后插入一個元素所需移動元素的個數(shù)為A.40B.60C.61D.100解法：41 至 100 共需要移動 60 次設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表head，則判斷該鏈表是否為空的條件是A. head-next=headB. head-nex

2、t=NULLC. head!=NULLD. head=NULL 5.在鏈棧的運(yùn)算中，不需要判斷棧是否為空的是出棧進(jìn)棧C.取棧頂元素D.求鏈棧的元素個數(shù)6.一個隊列的輸入序列是 則該隊列的輸出序列A.A，B，C，DB.B，C，D，AC.D，C，B，AD.C，D，B，A以行序為主序的二維數(shù)組 中，第一個元素 1002 a12的存儲地址是A.100B.108C.114D.116解法：loci,j=loc(0,0)+(n*i+j)*k = 100+(5*1+2)*2=14T5 2 的結(jié)點(diǎn)個數(shù)為A.4B.5C.6D.無法確定解法：n0=n2+1 就有 5=x+19.m 個葉結(jié)點(diǎn)的哈夫曼樹中，其結(jié)點(diǎn)總數(shù)為

3、A.mB.2m+1C.2mD.2m-1解法：2m-1二叉樹的中序遍歷序列中，結(jié)點(diǎn)P Q 之前的條件是在二叉樹中P 在Q 的左邊在二叉樹中P 在Q 的右邊C.在二叉樹中P 是Q 的祖先D.在二叉樹中P 是Q 的子解法：中順遍歷順序：左中右10 個頂點(diǎn)的無向完全圖的邊數(shù)是A.11B.45C.55D.90解法：n(n-1)2 = 10（10-1）2 =45在帶權(quán)有向圖中求兩個結(jié)點(diǎn)之間的最短路徑可以采用的算法是迪杰斯特拉（Dijkstra）算法克魯斯卡爾算C.普里姆（Prim）算法D.深度優(yōu)先搜索（DFS）算法13.二分查找（Binary Search）算法的時間復(fù)雜度是B.O（nlog2n）C.O（

4、n）14.在一棵初始時為空的二叉樹中，依次插入鍵值序列 50，72，43，85，75，20，38，45，65，60，構(gòu)造對應(yīng)的二叉排序樹以后，查找元素 60 要進(jìn)行的比較次數(shù)是A.2B.3C.4D.5解法：畫二叉樹后得出：50726560 15.快速排序?qū)儆诓迦肱判蚪粨Q排序C.選擇排序D.歸并排序非選擇題部分注意事項：用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題(本大題共 13 小題，每小題 2 分，共 26 分)下面算法程序段的時間復(fù)雜度為 O(n3) for (i=1; i=n; i+)for (j=1; j=n; j+) for (k=1;knext=p-ne

5、xt-next。在帶有頭結(jié)點(diǎn)的單鏈表head 中，首結(jié)點(diǎn)的指針為head-next。在棧結(jié)構(gòu)中，允許插入和刪除的一端稱為棧頂。21.C 程序中，將對稱矩陣的下三角元素壓縮存儲到n(n+1)/2 個元素的一維數(shù)組M 中設(shè)a （存放在數(shù)組中則k 的（用i,j表示為 k = i(i+1)/2+ 22.具有64 個結(jié)點(diǎn)的完全二叉樹的深度為log(2，n)+1=6+1=7。JLKANMOA 的右子樹中的結(jié)點(diǎn)個數(shù)為3 個分別為。三個頂點(diǎn)v1,v2,v3 的圖的鄰接矩陣為則該圖中頂點(diǎn)v2 的出度為即v2行之和)。除第一個頂點(diǎn)和最后一個頂點(diǎn)相同外，其余頂點(diǎn)不重復(fù)的回路，稱簡單回路或簡環(huán)。在順序查找、二分查找、

6、散列查找和索引順序查找四種查找方法中，平均查找長度與素個數(shù)沒有關(guān)系的查找方法是散列查找。堆排序算法的時間復(fù)雜度為_ O(nlog2n)。28.如果要將序列60，18，28，69，99，75，78建成堆，則只需把60 與18(最小堆) 相互交換。三、應(yīng)用題(本大題共 5 小題，每小題 6 分，共 30 分)29.如題 29 的所有輸出序列，并給出每個序列的操作過程（push（A）A 進(jìn)棧，pop(A)A 出棧）。題 29 圖解：push(A),pop(A),push(B),pop(B),push(C),pop(C) 輸出序列為：ABCpush(A),push(B),pop(B),pop(A),p

7、ush(C),pop(C) 輸出序列為：BACpush(A),push(B),push(C),pop(C),pop(B),pop(A) 輸出序列為：CBApush(A),pop(A),push(B),push(C),pop(C),pop(B) 輸出序列為：ACBpush(A),push(B),pop(B),push(C),pop(C),pop(A) 30.30 圖所示的一棵樹轉(zhuǎn)換為對應(yīng)的二叉樹。解：題 30 圖 31 表示的連通帶權(quán)圖及該連通帶權(quán)圖的最小生成樹。題 31 圖解：聯(lián)通圖最小生成樹32 110 中的數(shù)，試標(biāo)出各結(jié)點(diǎn)的數(shù)值。題 32 圖 mod 11(mod )，給出鍵值序列為66,13,41,15,44,6,68,17,26,31,39,46, 概率情況下查找成功時的平均查找長度。四、算法設(shè)計題(本大題共 2 小題，每小題 7 分，共 14 分)帶頭結(jié)點(diǎn)的單鏈表的結(jié)點(diǎn)結(jié)構(gòu)如下：typedef struct n