保山學院《數據結構》2021-2022學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁保山學院

《數據結構》2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個節(jié)點的線索二叉樹，若n個節(jié)點中有m個空指針域，則線索的數量為？A.mB.m/2C.n+1D.n-12、若要對一個具有n個元素的有序鏈表進行二分查找，是否可行？（）A.可行B.不可行C.有時可行D.取決于鏈表長度3、以下哪種數據結構在查找、插入和刪除操作的綜合性能上表現較好？（）A.二叉搜索樹B.紅黑樹C.B樹D.哈希表4、以下關于圖的最短路徑算法的描述，哪一項是正確的？（）A.Dijkstra算法不能處理負權邊B.Floyd算法的時間復雜度低于Dijkstra算法C.所有最短路徑算法都能在有向圖和無向圖中使用D.最短路徑一定是唯一的5、若對一棵二叉搜索樹進行先序遍歷，得到的節(jié)點序列是一個遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空6、在一個具有n個頂點的無向完全圖中，每個頂點的度為多少？（）A.n-1B.nC.2(n-1)D.2n7、在一個鏈式存儲的棧中，進行入棧和出棧操作時，以下關于時間復雜度的描述，哪一個是準確的？A.入棧和出棧的時間復雜度均為O(1)B.入棧的時間復雜度為O(n)，出棧的時間復雜度為O(1)C.入棧的時間復雜度為O(1)，出棧的時間復雜度為O(n)D.入棧和出棧的時間復雜度均為O(n)8、設有一個循環(huán)隊列，存儲空間為Q[0..m-1]，初始時front=rear=m。現經過一系列入隊與退隊操作后，front=20，rear=15，則此時隊列中的元素個數為（）。A.5B.6C.m-5D.m+59、隊列是另一種特殊的線性數據結構，它遵循先進先出（FIFO）的原則。以下關于隊列的說法中，錯誤的是？（）A.隊列可以用數組或鏈表實現。B.隊列的插入操作在隊尾進行，刪除操作在隊首進行。C.隊列可以用于實現任務調度、消息傳遞等。D.隊列的容量是無限的，可以存儲任意數量的元素。10、在一個容量為10的順序存儲的循環(huán)隊列中，若front=4，rear=8，則此時隊列中元素的個數為：A.4B.5C.6D.711、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲時，其空間復雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)12、對于一個采用順序存儲的棧，若要判斷棧是否為空，以下哪種方法是最有效的？A.檢查棧頂元素是否為NULLB.檢查棧頂指針是否為-1C.檢查棧頂指針是否等于棧的最大容量D.檢查棧中元素的數量是否為013、對于一個具有n個節(jié)點的無向連通圖，其生成樹的邊數為（）A.n-1B.nC.n+1D.2n14、對于一個大根堆，若將堆中所有元素按照層次遍歷的順序存儲到一個數組中，以下關于數組元素的排列，哪一項是正確的？A.完全無序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對15、以下哪種排序算法在最壞情況下的時間復雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序16、在一個具有n個節(jié)點的二叉樹中，若采用后序遍歷得到的節(jié)點序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定17、以下關于哈夫曼樹的描述，正確的是：A.哈夫曼樹一定是完全二叉樹B.哈夫曼樹中不存在度為1的節(jié)點C.哈夫曼樹的帶權路徑長度是唯一的D.哈夫曼樹的構建過程不需要進行節(jié)點的比較和交換18、在二叉搜索樹中，每個節(jié)點的值都大于其左子樹中所有節(jié)點的值，小于其右子樹中所有節(jié)點的值。以下關于二叉搜索樹的操作，不正確的是（）A.插入操作需要按照節(jié)點值的大小找到合適的位置B.查找操作的時間復雜度在最壞情況下為O(n)C.刪除節(jié)點時，如果該節(jié)點有兩個子節(jié)點，可以選擇其左子樹中的最大節(jié)點或右子樹中的最小節(jié)點進行替換D.二叉搜索樹總是平衡的，即左右子樹的高度差不超過119、以下關于并查集的描述，錯誤的是：A.并查集可以用于判斷兩個元素是否在同一個集合中B.并查集的查找操作時間復雜度較低C.并查集的合并操作時間復雜度較高D.并查集通常采用樹形結構存儲20、對于一個用數組實現的小根堆，進行刪除堆頂元素操作后，需要重新調整堆以保持堆的性質。以下關于刪除操作的時間復雜度的描述，哪一個是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）說明隊列的先進先出（FIFO）特性對解決哪些問題有幫助，并舉例說明。2、（本題10分）詳細論述在利用二叉搜索樹進行范圍查詢時，如何實現查找給定范圍內的節(jié)點，并給出具體的算法步驟和代碼實現。3、（本題10分）論述伸展樹在處理隨機數據時的性能表現和優(yōu)化措施。4、（本題10分）在一個具有n個頂點的無向圖中，如何找出所有的生成樹