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

1、全國2012年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題及答案最新2012版教材全國2012年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題課程代碼：02142一、單項選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個備選項中只有一個是符合題目要求的。錯選、多選或未選均無分。1.下面幾種算法時間復(fù)雜度階數(shù)中，值最大的是(nlog2n)(n2)(n)(2n)2.即使輸入非法數(shù)據(jù)，算法也能適當?shù)刈龀龇磻?yīng)或進行處理，不會產(chǎn)生預(yù)料不到的運行結(jié)果，這種算法好壞的評價因素稱為A.正確性B.易讀性C.健壯性D.時空性3.設(shè)順序表的長度為100,則在第40個元素之后插入一個元素所需移動元素的解法：41至1

2、00共需要移動60次4.設(shè)帶頭結(jié)點的單循環(huán)鏈表的頭指針為head,則判斷該鏈表是否為空的條件是A.head-next=headB.head-next=NULLC.head!=NULLD.head=NULL5.在鏈棧的運算中)不需要判斷棧是否為空的是A.出棧B.進棧C.取棧頂元素D.求鏈棧的元素個數(shù)6.一個隊列的輸入序列 是A,B,C,D,則 該 隊 列 的 輸 出 序 列是)B)C)D)C,D,AA,D,B,A7.以行序為主序的二維數(shù)組a35中,第一個元素a00的存儲地址是100,每個元素占2個存儲單元，則a12的存儲地址是解法：loci,j=loc(0,0)+(n*i+j)*k100+(5*

3、1+2)*2=14叉樹若葉結(jié)點數(shù)為的結(jié)點個數(shù)為D.無法確定解法：n0=n2+1就有5=x+1精選公文范文，管理類，工作總結(jié)類，工作計劃類文檔，感謝閱讀下載28.對任何一棵二5個，則度為2個葉結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為+1解法：2m-110.二叉樹的中序遍歷序列中，結(jié)點P排在結(jié)點Q之前的條件是A.在二叉樹中P在Q的左邊B.在二叉樹中P在Q的右邊C.在二叉樹中P是Q的祖先D.在二叉樹中P是Q的子孫解法：中順遍歷順序：左中右11.有10個頂點的無向完全圖的邊數(shù)是最新2012版教材解法：n(n-1)2-=102-=4512.在帶權(quán)有向圖中求兩個結(jié)點之間的最短路徑可以采用的算法是A.迪杰斯特拉算法B

4、.克魯斯卡爾算法C.普里姆算法D.深度優(yōu)先搜索算法13.二分查找算法的時間復(fù)雜度是14.在一棵初始時為空的二叉樹中，依次38,45,65,60,構(gòu)造對應(yīng)的二叉排序樹以后，查找元素60要進行的比較次數(shù)插入鍵值序列50,72,43,5,75,20,解法：畫二叉樹后得出：5072656015.快速排序?qū)儆贏.插入排序B.交換排序C.選擇排序D.歸并排序非選擇題部分注意事項： 用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題(本大題共13小題，每小題2分，共26分)16.下面算法程序段的時間復(fù)雜度為。for(i=1;ifor(k=1;k17.所有存儲結(jié)點存放在一個連續(xù)的存儲區(qū)里

5、， 利用結(jié)點在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關(guān)系。 這種存儲方式是順序存儲方式18.單鏈表中指針p指向結(jié)點A,若要刪除A之后的結(jié)點，則需要修改指針的操作為p-next=p-next-next19.在帶有頭結(jié)點的單鏈表head中,首結(jié)點的指針為_head-next_20.在棧結(jié)構(gòu)中,盛許插入和麗花一端稱陣APnPn的下三角元素壓縮存儲到為棧頂。程序中，將對稱矩n(n+1)/2個元素的一維數(shù)組M中，設(shè)ai口存放在數(shù)組Mk中，則k的值為k=i(i+1)/2+j。22.具有64個結(jié)點的 完 全 二 叉 樹 的 深 度 為Llog(2,n)+1=6+1=7。23.某二叉樹的先序遍歷序列為AJ

6、KLMNO,中序遍歷序列為JLKANMO,則根結(jié)點A的右子樹中的結(jié)點個數(shù)為_3個分別為：NMO。24.三個頂點v1,v2,v3的圖的鄰接矩陣為，則該圖中頂點v2的出度為_2(即v2行之和)。25.除第一個頂點和最后一個頂點相同外， 其余頂點不重復(fù)的回路， 稱為簡單回路或簡單環(huán)。最新2012版教材26.在順序查找、二分查找、 散列查找和索引順序查找四種查找方法中， 平均查找長度與元素個數(shù)沒有關(guān)系的查找方法是果要將序列60,18,28,69,99,75,78建成堆，則只需把60與_18(最小散列查找。27.堆排序算法的時間復(fù)雜度為_O(nlog2n)28.如大題共5小題，每小題6分，共30分)29

7、.如題29圖所示，在棧的輸入端依次輸入元素A,B,C,試寫出在棧的輸出端可以得到的所有輸出序列，并給出每個序列的操作過程表示A進棧，pop(A)表示A出棧)。題29圖解：(A),pop(A),push(B),pop(B),push(C),pop(C)輸出序列為：ABC(A),push(B),pop(B),pop(A),push(C),pop(C)輸出序列為：BAC(A),push(B),push(C),pop(C),pop(B),pop(A)輸出序列為：CBA(A),pop(A),push(B),push(C),pop(C),pop(B)輸出序列為：ACB(A),push(B),pop(B),

8、push(C),pop(C),pop(A)輸出序列為：BCA30.將題30圖所示的一棵樹轉(zhuǎn)換為對應(yīng)的二叉樹。解：題30圖31.已知含五個頂點A,B,C,D,E的連通帶權(quán)圖的鄰接矩陣如題31圖所示，試畫出它所表示的連通帶權(quán)圖及該連通帶權(quán)圖的最小生成樹。題31圖解：聯(lián)通堆)相互交換。入應(yīng)用題(本圖最小生成樹32.題32圖所示二叉排序樹的各結(jié)點的值為110中的數(shù)，試標出各結(jié)點的數(shù)值。題32圖33.設(shè)散列函數(shù)H=keymod11（mod表 示 求 余 運 算）， 給 出 鍵 值 序 列 為66,13,41,15,44,6,68,17,26,31,39,46用鏈地址法解決沖突，試畫出相應(yīng)的散列表,并計算在等概率情況下查找成功時的平均查找長度。四、算法設(shè)計題（本大題共2小題，每小題7分，共14分）34.帶頭結(jié)點的單鏈