全國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一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的。錯(cuò)選、多選或未選均無分。1.下面幾種算法時(shí)間復(fù)雜度階數(shù)中，值最大的是(nlog2n)(n2)(n)(2n)2.即使輸入非法數(shù)據(jù)，算法也能適當(dāng)?shù)刈龀龇磻?yīng)或進(jìn)行處理，不會(huì)產(chǎn)生預(yù)料不到的運(yùn)行結(jié)果，這種算法好壞的評(píng)價(jià)因素稱為A.正確性B.易讀性C.健壯性D.時(shí)空性3.設(shè)順序表的長(zhǎng)度為100,則在第40個(gè)元素之后插入一個(gè)元素所需移動(dòng)元素的解法：41至1

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

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

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

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

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

7、.如題29圖所示，在棧的輸入端依次輸入元素A,B,C,試寫出在棧的輸出端可以得到的所有輸出序列，并給出每個(gè)序列的操作過程表示A進(jìn)棧，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)換為對(duì)應(yīng)的二叉樹。解：題30圖31.已知含五個(gè)頂點(diǎn)A,B,C,D,E的連通帶權(quán)圖的鄰接矩陣如題31圖所示，試畫出它所表示的連通帶權(quán)圖及該連通帶權(quán)圖的最小生成樹。題31圖解：聯(lián)通堆)相互交換。入應(yīng)用題(本圖最小生成樹32.題32圖所示二叉排序樹的各結(jié)點(diǎn)的值為110中的數(shù)，試標(biāo)出各結(jié)點(diǎn)的數(shù)值。題32圖33.設(shè)散列函數(shù)H=keymod11（mod表 示 求 余 運(yùn) 算）， 給 出 鍵 值 序 列 為66,13,41,15,44,6,68,17,26,31,39,46用鏈地址法解決沖突，試畫出相應(yīng)的散列表,并計(jì)算在等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。四、算法設(shè)計(jì)題（本大題共2小題，每小題7分，共14分）34.帶頭結(jié)點(diǎn)的單鏈