2010年云南昆明理工大學數據結構教程考研真題A卷

1、2010年云南昆明理工大學數據結構教程考研真題A卷一、單項選擇題：（每題3分，共30分）1非線性結構中每個結點 。A. 無直接前驅結點 B. 只有一個直接前驅和直接后繼結點C. 無直接后繼結點 D. 可能有多個直接前驅和多個直接后繼結點2在表長為n的單鏈表中，算法時間復雜度為O(n)的操作是 。A. 查找單鏈表中第i個結點 B. 在p結點之后插入一個結點C. 刪除表中第一個結點 D. 刪除p結點的直接后繼結點3在鏈表中最常用的操作是在最后一個數據元素之后插入一個數據元素和刪除第一個數據元素，則最節(jié)省運算時間的存儲方式是 。 A. 僅有頭指針的單鏈表 B. 僅有頭指針的單循環(huán)鏈表C. 僅有頭指針

2、的雙向鏈表 D. 僅有尾指針的單循環(huán)鏈表4. 設有10階矩陣A，其對角線以上的元素aij(1j10，1<i<j)均取值為3，其它矩陣元素為正整數。現將矩陣壓縮存放在一維數組Fm中，則m為 。A. 45 B. 46 C. 55 D. 565前序序列為ABC的不同二叉樹有 種不同形態(tài)。 A. 3 B. 4 C. 5 D. 66具有n個結點（n>1）的二叉樹的前序序列和后序序列正好相反，則該二叉樹中除葉子結點外每個結點 。A. 僅有左孩子 B. 僅有右孩子 C. 僅有一個孩子 D. 都有左、右孩子7. 關于連通圖的BFS和DFS生成樹高度論述正確的是 。A. BFS生成樹高度<

3、;DFS生成樹高度 B. BFS生成樹高度DFS生成樹高度C. BFS生成樹高度>DFS生成樹高度 D. BFS生成樹高度DFS生成樹高度8對線性表用二分法查找時要求線性表必須是 。A. 順序表 B. 單鏈表 C. 順序存儲的有序表 D. 散列表9. 在采用線性探查法處理沖突的散列表中進行查找，查找成功時所探測位置上的健值 。A. 一定都是同義詞 B. 一定都不是同義詞 C. 不一定是同義詞 D. 無任何關系10堆排序是一種 。 A) 插入排序 B) 選擇排序 C) 交換排序 D) 歸并排序二、判斷題（每題2分，共20分） 1在單鏈表中存取某個元素，只要知道指向該元素的指針，因此單鏈表是

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

5、）10將二叉排序樹的中序序列中的關鍵字依次插入初始為空的樹中，所得到的二叉排序樹與原二叉排序樹是相同的。（ ）三、簡答題（共50分）1對n個頂點的無向圖和有向圖，采用鄰接矩陣和鄰接表表示時，如何判別下列有關問題：（1）圖中有多少條邊？ （2）任意兩個頂點i和j是否有邊相連？ （3）任意一個頂點的度是多少？（18分）2判斷下列序列是否為堆，若不是堆則把它們調整為堆。（12分）（1）（100，86，48，73，35，39，42，57，66，21）（2）（12，70，33，65，24，56，48，92，86，33）3特殊矩陣和稀疏矩陣哪一種壓縮存儲會失去隨機存儲功能？為什么（10分）4設棧s和隊列q

6、初始狀態(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）設裝填因子=0.77，散列函數H（key）=key MOD 11，用線性探測再散列方法解決沖突，試構造散列表，并求出在等概率情況下查找成功和查找不成功的平均查找長度。（15分）五、設圖中的頂點表示村莊，有向邊代表交通路線，若要建立一家醫(yī)院，試問建在哪一個村莊能使各村莊總體交通代價最小。（10分）六、已知線性表（a0，a1，an-1）按順序存儲于內存，每個元素都是整數，用C或類Pascal語言編寫一個函數，用最少的時間把所有值為負數的元素移到全部正數值元素前面的算法。（10分）七、某百貨公司倉庫中有一批電視機，按其價格從低到高的次序構成了一個單鏈