昆明理工大學2010年碩士研究生招生入學考試試題A卷

1、昆明理工大學2010年碩士研究生招生入學考試試題（A卷）考試科目代碼：835考試科目名稱：數(shù)據(jù)結構教程試題適用招生專業(yè)：系統(tǒng)理論、系統(tǒng)分析與集成考生答題須知1. 所有題目（包括填空、選擇、圖表等類型題目）答題答案必須做在考點發(fā)給的答題紙上，做在本試題冊上無效。 請考生務必在答題紙上寫清題號。2. 評卷時不評閱本試題冊，答題如有做在本試題冊上而影響成績的，后果由考生自己負責。3. 答題時一律使用藍、黑色墨水筆或圓珠筆作答（畫圖可用鉛筆），用其它筆答題不給分。4. 答題時不準使用涂改液等具有明顯標記的涂改用品。一、單項選擇題：（每題3分，共30分）1. 非線性結構中每個結點 。A.無直接前驅(qū)結點B

2、.只有一個直接前驅(qū)和直接后繼結點C.無直接后繼結點D.可能有多個直接前驅(qū)和多個直接后繼結點2. 在表長為n的單鏈表中，算法時間復雜度為O（n）的操作是。A.查找單鏈表中第i個結點 B.在p結點之后插入一個結點C.刪除表中第一個結點D. 刪除p結點的直接后繼結點3 .在鏈表中最常用的操作是在最后一個數(shù)據(jù)元素之后插入一個數(shù)據(jù)元素和刪除第一個數(shù)據(jù)元素， 則最節(jié)省運算時間的存儲方式是 。A.僅有頭指針的單鏈表B.僅有頭指針的單循環(huán)鏈表C.僅有頭指針的雙向鏈表D.僅有尾指針的單循環(huán)鏈表4. 設有10階矩陣A，其對角線以上的元素aij（1 j w 10，1i1）的二叉樹的前序序列和后序序列正好相反，則該二

3、叉樹中除葉子結點外每個結點。A.僅有左孩子B.僅有右孩子C. 僅有一個孩子 D.都有左、右孩子7. 關于連通圖的BFS和DFS生成樹高度論述正確的是 。A. BFS生成樹高度DFS生成樹高度D. BFS生成樹高度DFS生成樹高度&對線性表用二分法查找時要求線性表必須是 。A.順序表 B. 單鏈表 C. 順序存儲的有序表 D. 散列表9. 在采用線性探查法處理沖突的散列表中進行查找，查找成功時所探測位置上的健值。A. 一定都是同義詞B.一定都不是同義詞C.不一定是同義詞D.無任何關系10. 堆排序是一種。A）插入排序B） 選擇排序 C）交換排序D） 歸并排序、判斷題（每題 2分，共20 分）1

4、在單鏈表中存取某個元素，只要知道指向該元素的指針，因此單鏈表是隨機存取的存儲結構。（）則該圖的拓撲序列必定存在。（）2 .若一個有向圖的鄰接矩陣中對角線以下的元素均為零,3 .消除遞歸必須用棧來實現(xiàn)。（）4 .稀疏矩陣壓縮存儲后必會失去隨機存取的功能。（）5 .堆排序所需要附加空間數(shù)取決于待排序的記錄的個數(shù)。（）6 在二叉排序樹上刪除一個結點時，不必移動其他結點，只要將該結點相應的指針域置空 即可。（）7 采用線性探測法處理沖突時，當從散列表中刪除一個記錄時，不應將這個記錄的所在位置置為空，因為這將會影響以后的查找。（）8 對于n個頂點的無向圖，若其邊數(shù)大于或等于n-1，則其必是連通圖。（）9

5、 一棵完全二叉樹中的結點若無左孩子，則其必是葉結點。（）10.將二叉排序樹的中序序列中的關鍵字依次插入初始為空的樹中，所得到的二叉排序樹與原二叉排序樹是相同的。（）三、簡答題（共50分）1對n個頂點的無向圖和有向圖，采用鄰接矩陣和鄰接表表示時，如何判別下列有關問題：（1）圖中有多少條邊？（ 2）任意兩個頂點i和j是否有邊相連？（ 3）任意一個頂點的度是多少？ （18分）2判斷下列序列是否為堆，若不是堆則把它們調(diào)整為堆。（12分）(1) (100, 86, 48, 73, 35, 39, 42, 57, 66, 21)(2) (12, 70, 33, 65, 24, 56, 48, 92, 86

6、, 33)3. 特殊矩陣和稀疏矩陣哪一種壓縮存儲會失去隨機存儲功能？為什么（10分）4. 設棧s和隊列q初始狀態(tài)為空，元素 a、b、c、d、e、f依次通過棧s, 個元素出棧后即進入隊列，若6個元素出隊的序列是 bdcfea，則棧s的容量至少應該存多少個元素？（10分）四、已知一組記錄的關鍵字為18, 2, 10, 6, 78, 56, 45, 50, 110, 8。（1）按輸入順序畫出此組記錄的平衡二叉樹，求等概率情況下查找成功的平均查找長度。若查找每個元素的概率不等時，這時的平衡二叉樹是否是最佳查找樹？為什么？（2） 設裝填因子a =0.77，散列函數(shù)H （ key） =key MOD 11 ,用線性探測再散列方法解決沖突, 試構造散列表，并求出在等概率情況下查找成功和查找不成功的平均查找長度。（15分）五、設圖中的頂點表示村莊，有向邊代表交通路線，若要建立一家醫(yī)院，試問建在哪一個村莊能使各村莊總體交通代價最小。（10分）六、 已知線性表（a0, a1，an-1）按順序存儲于內(nèi)存，每個元素都是整數(shù)，用C或類Pascal語言編寫一個函數(shù)，用最少的時間把所有值為負數(shù)的元素移到全部正數(shù)值元素前面的算法。（10 分）七、某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構成了一個單鏈表