自考數(shù)據(jù)結(jié)構(gòu)導(dǎo)論

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

2、O(log2n)B.O(n)C.O(n2)D.O(1)2. 數(shù)據(jù)的存儲(chǔ)方式中除了順序存儲(chǔ)方式和鏈?zhǔn)酱鎯?chǔ)方式之外，還有(D)A. 索引存儲(chǔ)方式和樹形存儲(chǔ)方式B.線性存儲(chǔ)方式和散列存儲(chǔ)方式C.線性存儲(chǔ)方式和索引存儲(chǔ)方式D.索引存儲(chǔ)方式和散列存儲(chǔ)方式3表長(zhǎng)為n的順序表中做刪除運(yùn)算的平均時(shí)間復(fù)雜度為(C)A. O(1)B.O(log2n)C.O(n)D.O(n2)4順序表中定位算法(查找值為x的結(jié)點(diǎn)序號(hào)最小值)的平均時(shí)間復(fù)雜度為(C)A. O(1)B.O(log2n)C.O(n)D.O(n2)5元素的進(jìn)棧次序?yàn)锳，B，C，D，E,出棧的第一個(gè)元素為E,則第四個(gè)出棧的元素為(C)A.DB.CC.BD.A

3、6帶頭結(jié)點(diǎn)的鏈隊(duì)列中，隊(duì)列頭和隊(duì)列尾指針分別為front和rear，則判斷隊(duì)列空的條件為(A)A.front=rearB.front!=NULLC.rear!=NULLD.front=NULL7.深度為5的二叉樹，結(jié)點(diǎn)個(gè)數(shù)最多為(A)A.31個(gè)B.32個(gè)C.63個(gè)D.64個(gè)8.如果結(jié)點(diǎn)A有2個(gè)兄弟結(jié)點(diǎn)，結(jié)點(diǎn)B為A的雙親，則B的度為(B)A.1B.3C.4D.59. 將題9圖所示的一棵樹轉(zhuǎn)換為二叉樹，結(jié)點(diǎn)C是(D)題9團(tuán)A.A的左孩子B. A的右孩子C. B的右孩子D. E的右孩子A.O(n)C.O(n-e)11. 無向圖的鄰接矩陣是(D)A. 對(duì)角矩陣C.上三角矩陣12. 在具有101個(gè)元素的

4、順序表中查找值為xA.50B. O(e)D.O(n+e)B. 稀疏矩陣D.對(duì)稱矩陣的元素結(jié)點(diǎn)時(shí)，平均比較元素的次數(shù)為(A)B. 5110. n為圖的頂點(diǎn)個(gè)數(shù)，e為圖中弧的數(shù)目，則圖的拓?fù)渑判蛩惴ǖ臅r(shí)間復(fù)雜度為(D)C. 100D.10113. 構(gòu)造散列函數(shù)的方法很多，常用的構(gòu)造方法有(D)A. 數(shù)字分析法、除留余數(shù)法、平方取中法B. 線性探測(cè)法、二次探測(cè)法、除留余數(shù)法C. 線性探測(cè)法、除留余數(shù)法、鏈地址法D. 線性探測(cè)法、二次探測(cè)法、鏈地址法14. 就平均時(shí)間性能而言，快速排序方法最佳，其時(shí)間復(fù)雜度為(B)A.O(n)B.O(nlog2n)C. O(n2)D.O(1og2n)15. 下述算法中

5、，不穩(wěn)定的排序算法是(C)A.直接插入排序B.冒泡排序C. 堆排序D.歸并排序非選擇題部分注意事項(xiàng)：用黑色字跡的簽字筆或鋼筆將答案寫在答題紙上，不能答在試題卷上。二、填空題（本大題共13小題，每小題2分，共26分）16. 數(shù)據(jù)的基本單位是_數(shù)據(jù)項(xiàng)。17. 雙向循環(huán)鏈表中，在p所指結(jié)點(diǎn)的后面插入一個(gè)新結(jié)點(diǎn)*t,需要修改四個(gè)指針，分別為t->prior=P；t->next=p->next；p->next->prior=t；p->next=t；。18. 在帶有頭結(jié)點(diǎn)的循環(huán)鏈表中，尾指針為rear，判斷指針P所指結(jié)點(diǎn)為首結(jié)點(diǎn)的條件是P=rear->next-&

6、gt;next_。19. 若線性表中最常用的操作是求表長(zhǎng)和讀表元素，則順序表和鏈表這兩種存儲(chǔ)方式中，較節(jié)省時(shí)間的是順序表。20. 不含任何數(shù)據(jù)元素的棧稱為空棧。21. 稀疏矩陣一般采用的壓縮存儲(chǔ)方法是三元組。22.100個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存儲(chǔ)時(shí)，用來指向左、右孩子結(jié)點(diǎn)的指針域有N-1_個(gè)。23. 已知完全二叉樹的第5層有5個(gè)結(jié)點(diǎn)，則整個(gè)完全二叉樹有20個(gè)結(jié)點(diǎn)。24. n個(gè)頂點(diǎn)的有向圖G用鄰接矩陣A1.n，1.n存儲(chǔ)，其第i列的所有元素之和等于頂點(diǎn)Vi的入度。25. 具有10個(gè)頂點(diǎn)的有向完全圖的弧數(shù)為90。26. 要完全避免散列所產(chǎn)生的“堆積''現(xiàn)象，通常采用公共溢出區(qū)解

7、決沖突。27. 在長(zhǎng)度為n的帶有崗哨的順序表中進(jìn)行順序杳找，杳找不成功時(shí)，與關(guān)鍵字的比較次數(shù)為N+1_。28.歸并排序算法的時(shí)間復(fù)雜度是_O（NLOG2N）。三、應(yīng)用題（本大題共5小題，每小題6分，共30分）29.稀疏矩陣A如題29圖所示，05000-1000000A=000002000008000005000_0700000_題29圖寫出該稀疏矩陣A的三元組表示法艇氫5）1,-1）（'3-廳2）（£5,1近£5）需2,7）30.設(shè)二叉樹的中序遍歷序列為BDCEAFHG，后序遍歷序列為DECBHGFA，試畫出該二叉樹。31.寫出題31圖所示無向圖的鄰接矩陣，并寫出每

8、個(gè)頂點(diǎn)的度。32.已知散列表的地址空間為0至13,散列函數(shù)H(k)=kmodll,(mod為求余運(yùn)算)，待散列序列為(26,61,49),用二次探測(cè)法解決沖突，構(gòu)造該序列的散列表，要求寫出處理沖突的過程。138,84,4263861784因?yàn)閐O二11=5沖突所以dl二(dO+12)mod11-6沖突d2=(dO-12)mod11二4沖突d3=：IdO+22)mod11所以49的散列地址為9。91933.將一組鍵值(80,50,65,13,86,35,96,57,39,79,59,15)應(yīng)用二路歸并排序算法從小到大排序,試寫出初始列表SO-50-6513'S53596573979591

9、5第一趟50,001：6535,0657,9639,791亦59第二趟1-50,65,0035,57,86,9615/39,59,79第三趟13/35,50,57,65,00,86,961亦39申9,79第四趟1.15/'35/'39,50,57,59,65,79,磚86,96各趟的結(jié)果。四、算法設(shè)計(jì)題(本大題共2小題，每小題7分，共14分)34設(shè)單鏈表及鏈棧S的結(jié)構(gòu)定義如下：typedefstructnodeDataTypedata；structnode*next；linkstack；編寫一個(gè)算法voidReverseList(linkstack*head),借助于棧S將帶頭

10、結(jié)點(diǎn)單鏈表head中序號(hào)為奇數(shù)的結(jié)點(diǎn)逆置，序號(hào)為偶數(shù)的結(jié)點(diǎn)保持不變。(例如：?jiǎn)捂湵淼倪壿嫿Y(jié)構(gòu)為q,a2，a3，a4，a5，a6)，逆置后變?yōu)?a5，a2，a3，a4，a1，a6)。說明：棧的初始化運(yùn)算用InitStack(S)；進(jìn)棧運(yùn)算用Push(S,x)；判?？者\(yùn)算用EmptyStack(S)；出棧運(yùn)算用Pop(S)；取棧頂元素運(yùn)算用Gettop(S)。voidReverseList(linkstack*head)InitStack(S);linkstack*p=head,*q=head;inti=0;DataTypex;while(p->next!=NULL)i+;if(i%2!=0)Push(S,p->next->data);p=p->next;while(q->next!=NULL)i+;if(i%2!=0)if(!EmptyStack(S)x=Gettop(S);q->next->data=x;Pop(S);35.以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試編寫遞歸算法實(shí)現(xiàn)求二叉樹中葉子結(jié)點(diǎn)個(gè)數(shù)I