2012年云南昆明理工大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題A卷

1、2012年云南昆明理工大學(xué)數(shù)據(jù)結(jié)構(gòu)考研真題A卷一、單項(xiàng)選擇題：（每題3分，共30分） 1長度為n的順序表，等概率情況下插入一個(gè)元素時(shí)平均要移動(dòng)表中的（ ）個(gè)元素。 An/2 B（n+1）/2 C（n-l）/2 Dn 2循環(huán)隊(duì)列Q的存儲(chǔ)空間為0至m-1，用front表示隊(duì)頭，用rear表示隊(duì)尾，采用少用一個(gè)單元的方法來區(qū)分隊(duì)列空和滿，那么循環(huán)隊(duì)列滿的條件是（ ）。 AQ.rearlQ.front B（Q.rear1）%mQ.front C QfrontlQrear D（Q.frontl）%mQ.rear 3若從二叉樹的任意結(jié)點(diǎn)出發(fā)到根的路徑上所經(jīng)過的結(jié)點(diǎn)序列按其關(guān)鍵字有序，則該二叉樹是（ ）。

2、A二叉排序樹 B完全二叉樹 C堆 D平衡二叉樹 4給定關(guān)鍵字的集合為20，15，14，18，21，36，40，10，一趟快速排序結(jié)束時(shí)鍵值的排列為（ ）。 A10，15，14，18，20，36，40，21 B10，15，14，18，20，40，36，21 C10，15，14，20，18，40，36，21 D15，10，14，18，20，36，40，21 5在一棵度為3的樹中，度為3的結(jié)點(diǎn)有2個(gè)，度為2的結(jié)點(diǎn)有1個(gè)，度為1的結(jié)點(diǎn)有3個(gè)，那么該樹有（ ）個(gè)葉結(jié)點(diǎn)。 A4 B5 C6 D7 6下列排序方法在排序過程中，關(guān)鍵碼比較的次數(shù)與記錄的初始排列順序無關(guān)的是（ ）。 A直接插入排序和快速排序 B

3、快速排序和歸并排序 C直接選擇排序和歸并排序 D直接插入排序和歸并排序 7具有4層結(jié)點(diǎn)的二叉平衡樹至少有（ ）個(gè)結(jié)點(diǎn)。 A8 B6 C15 D7 8當(dāng)輸入數(shù)據(jù)非法時(shí)，一個(gè)好的算法應(yīng)該作出適當(dāng)?shù)奶幚?，而不?huì)產(chǎn)生莫名其妙的結(jié)果，這稱做算法的（ ）。 A正確性 B可讀性 C健壯性 D有窮性 9三元組表用于表示（ ）。 A線性表 B索引表 C廣義表 D稀疏矩陣 10對于初始狀態(tài)遞增有序的表按從小到大的次序排序，時(shí)間效率最高的是（ ）。 A快速排序 B插人排序 C堆排序 D基數(shù)排序二、判斷題（每題2分，共20分） 1在單鏈表中存取某個(gè)元素，只要知道指向該元素的指針，因此單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。（ ）

4、 2若一個(gè)有向圖的鄰接矩陣中對角線以下的元素均為零，則該圖的拓?fù)湫蛄斜囟ù嬖?。?） 3消除遞歸必須用棧來實(shí)現(xiàn)。（ ） 4稀疏矩陣壓縮存儲(chǔ)后必會(huì)失去隨機(jī)存取的功能。（ ） 5堆排序所需要附加空間數(shù)取決于待排序的記錄的個(gè)數(shù)。（ ） 6在二叉排序樹上刪除一個(gè)結(jié)點(diǎn)時(shí)，不必移動(dòng)其他結(jié)點(diǎn)，只要將該結(jié)點(diǎn)相應(yīng)的指針域置空即可。（ ） 7采用線性探測法處理沖突時(shí)，當(dāng)從散列表中刪除一個(gè)記錄時(shí)，不應(yīng)將這個(gè)記錄的所在位置置為空，因?yàn)檫@將會(huì)影響以后的查找。（ ） 8對于n個(gè)頂點(diǎn)的無向圖，若其邊數(shù)大于或等于n-1，則其必是連通圖。（ ） 9一棵完全二叉樹中的結(jié)點(diǎn)若無左孩子，則其必是葉結(jié)點(diǎn)。（ ）10將二叉排序樹的中序序

5、列中的關(guān)鍵字依次插入初始為空的樹中，所得到的二叉排序樹與原二叉排序樹是相同的。（ ）三、簡答題（共55分）1線性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，在作插入或刪除操作時(shí)，需移動(dòng)大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充分利用；其三，表的容量難以擴(kuò)充。線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是否一定都能夠克服上述三個(gè)弱點(diǎn)，試討論之。（共10分）2. 一棵二叉樹的先序、中序和后序序列分別如下，其中有一部分未顯示出來。試求出空格處的內(nèi)容，并畫出該二叉樹。（共15分，每個(gè)序列3分，畫出二叉樹6分） 先序序列： _ _ CDE _ G HI _ K中序序列：CB _ _ FA _ JKI

6、G后序序列：_ EFDB _ JIH _ A3.（共15分）（1）什么叫AOE網(wǎng)？（4分）（2）對如下圖所示的AOE網(wǎng)，計(jì)算每個(gè)事件的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間以及每個(gè)活動(dòng)的最早發(fā)生時(shí)間和最遲發(fā)生時(shí)間。（7分）（3）請畫出關(guān)鍵路徑，并回答提高哪些活動(dòng)的效率可以縮短工期？（4分）圖二4. 設(shè)用于通訊的電文僅由8個(gè)字母C1,C2,C8構(gòu)成，字母在電文中出現(xiàn)的頻率分別為：5、25、3、6、10、11、36、4。試為這8個(gè)字母設(shè)計(jì)哈夫曼編碼。（共15分，畫圖10分，寫出編碼5分）四、以關(guān)鍵字序列29，18，25，47，58，12，51，10為例，試寫出執(zhí)行大根堆排序算法的各趟排序結(jié)果時(shí)，關(guān)鍵字序列的狀態(tài)。（共10分，創(chuàng)建堆2分，其余每步驟1分）五、設(shè)有一個(gè)由正整數(shù)組成的無序單鏈表，編寫完成下列功能的算法：（共15分，每小題5分） （1）找出最小值結(jié)點(diǎn)，且打印該數(shù)值； （2）若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點(diǎn)的值交換； （3）若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點(diǎn)刪除。六、快速排序算法中