全國2012年10月自考數(shù)據(jù)結(jié)構(gòu)02331試題及答案

1、全國2012年10月高等教育自學(xué)考試數(shù)據(jù)結(jié)構(gòu)試題課程代碼：02331請考生按規(guī)定用筆將所有試題的答案涂、寫在答題紙上。選擇題部分注意事項(xiàng)：1 .答題前，考生務(wù)必將自己的考試課程名稱、姓名、準(zhǔn)考證號用黑色字跡的簽字筆或鋼筆填寫在答題紙規(guī)定的位置上。2 .每小題選出答案后， 用 2B 鉛筆把答題紙上對應(yīng)題目的答案標(biāo)號涂黑。 如需改動， 用橡皮擦干凈后， 再選涂其他答案標(biāo)號。不能答在試題卷上。、單項(xiàng)選擇題(本大題共 15 小題，每小題 2 分，共 30 分)在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請將其選出并將答題紙”的相應(yīng)代碼涂黑。錯涂、多涂或未涂均無分。1.一個(gè)算法的時(shí)間耗費(fèi)的數(shù)量級

2、稱為該算法的4 .設(shè)以數(shù)組 A0.m-1存放循環(huán)隊(duì)列，front 指向隊(duì)頭元素，rear 指向隊(duì)尾元素的下一個(gè)位置，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為A.(rear-front+m)%mB.rear-front+1C.(front-rear+m)%mD.(rear-front)%m5 .下列關(guān)于順序棧的敘述中，正確的是A.入棧操作需要判斷棧滿，出棧操作需要判斷?？誃.入棧操作不需要判斷棧滿，出棧操作需要判斷棧空C.入棧操作需要判斷棧滿，出棧操作不需要判斷棧空A.效率C.可實(shí)現(xiàn)性2.順序表便于A.插入結(jié)點(diǎn)C.按值查找結(jié)點(diǎn)3.設(shè)帶頭結(jié)點(diǎn)的單循環(huán)鏈表的頭指針為A.p-next-next=headC.p-nex

3、t-next=NULLB.難度D.時(shí)間復(fù)雜度B.刪除結(jié)點(diǎn)D.按序號查找結(jié)點(diǎn)head,指針變量 P 指向尾結(jié)點(diǎn)的條件是B.p-next=headD.p-next=NULLD.入棧操作不需要判斷棧滿，出棧操作不需要判斷?？?.A 是一個(gè) 10X10 的對稱矩陣，若米用行優(yōu)先的下二角壓縮存儲，A 個(gè)兀素a。,。的存儲地址為 1,每個(gè)兀素占一個(gè)存儲單元，則 a*的地址為A.25B. 26C.33D. 347.樹的后序遍歷等價(jià)于該樹對應(yīng)二 二叉樹的A.層次遍歷B. 前序遍歷C.中序遍歷D. 后序遍歷8.使用二叉線索樹的目的是便于A.二叉樹中結(jié)點(diǎn)的插入與刪除B. 在一叉樹中查找雙親C.確定二叉樹的高度D.

4、 查找一個(gè)結(jié)點(diǎn)的前趨和后繼9.設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為 n,則該圖邊的數(shù)目最多為A.n-lB. n(n-1)/2C.n(n+1)/2D.2n10.可進(jìn)行拓?fù)渑判虻膱D只能是A.后向圖B. 無向圖C.后向無外圖D. 無向連通圖11.下列排序方法中穩(wěn)定的是A.直接插入排序B. 直接選擇排序C.堆排序D. 快速排序12.卜列序夕 U 不為.堆的是A.75,45,65,30,15,25B. 75,65,45,30,25,15C.75,65,30,l5,25,45D. 75,45,65,25,30,1513.對線性表進(jìn)行二分查找時(shí)，要求線性表必須是A.順序存儲B. 鏈?zhǔn)酱鎯.順序存儲且按關(guān)鍵字后序D. 鏈?zhǔn)?/p>

5、存儲且按關(guān)鍵字后序14.分別用以下序列生成二叉排序樹，其中三個(gè)序列生成的二叉排序樹是相同的，不同的序列是A.(4,1,2,3,5)B.(4,2,3,l,5)C.(4,5,2,1,3)D.(4,2,1,5,3)15 .下列關(guān)于 m 階 B 樹的敘述中，錯誤.的是A.每個(gè)結(jié)點(diǎn)至多有 m 個(gè)關(guān)鍵字B.每個(gè)結(jié)點(diǎn)至多有 m 棵子樹C.插入關(guān)鍵字時(shí)，通過結(jié)點(diǎn)分裂使樹高增加D.刪除關(guān)鍵字時(shí)通過結(jié)點(diǎn)合并使樹高降低非選擇題部分注意事項(xiàng)：用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題（本大題共 10 小題，每小題 2 分，共 20 分）16 .數(shù)據(jù)元素之間的邏輯關(guān)系稱為數(shù)據(jù)的結(jié)構(gòu)。17

6、.在線性表中，表的長度定義為。18 .用 S 表示入棧操作，X 表示出棧操作，若元素入棧的順序?yàn)?1、2、3、4,為了得到1、3、4、2 的出棧順序，相應(yīng)的 S 和 X 的操作序列為。19 .在二叉樹中，帶權(quán)路徑長度最短的樹稱為。20 .已知廣義表 G,head（G）與 tail（G）的深度分別為 4 和 6,則 G 的深度是。21 .一組字符（a,b,c,d）在文中出現(xiàn)的次數(shù)分別為（7,6,3,5）,字符/d，的哈夫曼編碼的長度為22 .在一個(gè)具有 n 個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要條邊。23 .直接選擇排序算法的時(shí)間復(fù)雜度是。24 .對于長度為 81 的表，若采用分塊查找，每塊的

7、最佳長度為。25 .用二叉鏈表保存有 n 個(gè)結(jié)點(diǎn)的二叉樹，則結(jié)點(diǎn)中有個(gè)空指針域。三、解答題（本大題共 4 小題，每小題 5 分，共 20 分）26 .假設(shè) Q 是一個(gè)具有 11 個(gè)元素存儲空間的循環(huán)隊(duì)列（隊(duì)尾指針指向隊(duì)尾元素的下一個(gè)位置，隊(duì)頭指針指向隊(duì)頭元素）,初始狀態(tài) Q.front=Q.rear=0;寫出依次執(zhí)行下列操作后頭、尾指針的當(dāng)前值。a,b,c,d,e,f 入隊(duì),a,b,c,d 出隊(duì)；（1）Q.front=;Q.rear=。g,h,i,j,k,l 入隊(duì)，e,f,g,h 出隊(duì)；（2）Q.front=;Q.rear=。M,n,o,P 入隊(duì)，i,j,k,l,m 出隊(duì)；（3）Q.front

8、=;Q.rear=。27. .已知一個(gè)無向圖如題 2727 圖所示，以為起點(diǎn)，用普里姆（PrimPrim）算法求其最小生成樹，畫出最小生成樹的構(gòu)造過程。題2727圖28 .用歸并排序法對序列(98,36,-9,0,47,23,1,8)進(jìn)行排序，問：(1) 一共需要幾趟歸并可完成排序。(2)寫出第一趟歸并后數(shù)據(jù)的排列次序。29 .一組記錄關(guān)鍵字(55,76,44,32,64,82,20,16,43),用散列函數(shù) H(key)=key%11 將記錄散列到散列表 HT0.12中去，用線性探測法解決沖突。(1)畫出存入所有記錄后的散列表。(2)求在等概率情況下，查找成功的平均查找長度。四、算法閱讀題(

9、本大題共 4 小題，每小題 5 分，共 20 分)30 .順序表類型定義如下：#defineListSize100typedefstructintdataListSize;intlength;SeqList;閱讀下列算法，并回答問題：voidf30(SeqList*L)inti,j；i=0;while(ilength)if(L-datai%2!=0)for(j=i+1;jlength;j+L-dataj-1=L-dataj;L-length-;elsei+(1)若 L-data 中的數(shù)據(jù)為(22,4,63,0,15,29,34,42,3),則執(zhí)行上述算法后 L-data 中的數(shù)據(jù)以及 L-le

10、ngth 的值各是什么？(2)該算法的功能是什么？31 .有向圖的鄰接矩陣類型定義如下：#defineMVN100/最大頂點(diǎn)數(shù)typedefintEType;/邊上權(quán)值類型typedefstructETypeedgesMVNMVN;/鄰接矩陣，即邊表/圖的頂點(diǎn)數(shù)/圖類型例如，一個(gè)有向圖的鄰接矩陣如下所示：0100010001A=010101000000011閱讀下列算法，并回答問題：Voidf31(MGraphG)(Inti,j,k=0;Step1:for(i=0;iG.n;i+)for(j=0;jG.n;j+)if(G.edgesij=1)k+;printf(%dn,k);step2:for

11、(j=0;jG.n;j+)k=0;for(i=0;iG.n;j+)if(G.edgesij=1)k+;printf(%&n,k);(1)stepl 到 step2 之間的二重循環(huán)語句的功能是什么(2)step2 之后的二重循環(huán)語句的功能是什么？32 .閱讀下列算法，并回答問題：voidf32(intr,intn)Inti,j;for(i=2;in;i+)r0=ri;j=i-l；intn;MGraph;while(r0rj)rj+l=rj;j=j-1；)rj+l=r0;)(1)這是哪一種插入排序算法？該算法是否穩(wěn)定？(2)設(shè)置 r0的作用是什么？33 .順序表類型定義如下：typedefintS

12、eqList100;閱讀下列算法，并回答問題：voidf33(SeqListr,intn)inta,b,i;if(r0elsea=r1;b=r0;for(i=2;in;i+)if(rib)b=ri；printf(a=%d,b=%d。n,a,b)；(1)給出該算法的功能；(2)給出該算法的時(shí)間復(fù)雜度。五、算法設(shè)計(jì)題(本題 10 分)34 .二叉樹的存儲結(jié)構(gòu)類型定義如下typedefstructnodeintdata;structnodelchild,rchild;BinNode;typedefBinNodeBinTree;編寫遞歸算法，求只有一個(gè)孩子結(jié)點(diǎn)的結(jié)點(diǎn)總數(shù)，并計(jì)算這些結(jié)點(diǎn)的數(shù)據(jù)值的和。*

13、函數(shù)的原型為：voidf34(BinTreeT,intcount,intsum)count 和 sum 的初值為 0。域雷啟用苗20122012年1010月高等教育自學(xué)考試全國統(tǒng)一命題考試數(shù)據(jù)結(jié)構(gòu)試題答案及評分參考課程代碼0233102331）一.單貨選擇總（本大共】5 小題，每小 M2 分，共 3。分）二、填空比（本大跑共 1。小能，博小隨 2 分，其州分）16.生輯 17.數(shù)據(jù)元素的個(gè)數(shù)18,SXSSX5XX99,哈夫里周 4 或是優(yōu)二又用成最優(yōu)兩）散娥造構(gòu)試赳答案區(qū)分叁考第 I 貪九二孤）C 分)供蛔鼻 0.2J,47,L 町仃分祝門)下標(biāo),0,I,m,34.5.6_.g._嗎 II_況冷拈春|55|44：43|啟|64|7 歹方面味臺次數(shù) 126121)-2i（J*J（2）ASL*-（+2t+2+1+!+2+49-2W9C2 分）四、算法閨讀 IS（軍大題共 4 小題，每小圖 5 分.共劉分）30.該苴法稔定打分）cnH。）的作用是 51 把暗布房.（2 分）31（I）算法的功能最求暈小也和最大近.（3JH仃）詼其法的時(shí)何 1E 盤度為 Q（n）-門分）五.算法設(shè)計(jì)題（本哽加分）34.voidf3H（BinTiteLini*coun*,tnt）H只有一個(gè)孩子結(jié)點(diǎn)的轉(zhuǎn)苴粒*s