北京聯(lián)合大學《數(shù)據(jù)結構》2021-2022學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁北京聯(lián)合大學《數(shù)據(jù)結構》

2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種數(shù)據(jù)結構常用于實現(xiàn)LRU（最近最少使用）緩存淘汰策略？（）A.隊列B.棧C.哈希表D.雙向鏈表2、在一個不帶頭結點的單鏈表中，若要刪除表頭結點，需要修改幾個指針？（）A.0B.1C.2D.33、對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則存儲空間的復雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)4、在一個具有n個元素的順序表中，若要查找一個元素，平均需要比較多少次？（）A.n/2B.nC.lognD.不確定5、若要在一個具有n個元素的有序鏈表中插入一個新元素，使其仍然有序，平均時間復雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)6、對于一個有向圖，使用鄰接矩陣存儲，判斷是否存在從頂點i到頂點j的邊的時間復雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)7、以下哪種數(shù)據(jù)結構常用于實現(xiàn)并查集？（）A.數(shù)組B.鏈表C.樹D.哈希表8、若對線性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲結構，則插入和刪除操作的時間復雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)9、對于一個具有n個頂點的帶權有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時間復雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)10、以下哪種數(shù)據(jù)結構能夠在O(1)的時間復雜度內實現(xiàn)元素的隨機訪問？（）A.鏈表B.隊列C.棧D.數(shù)組11、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為（）。A.CEABDB.CEDBAC.CABDED.CEDAB12、在一個具有n個元素的二叉排序樹中，查找一個不存在的元素，其時間復雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)13、在一個用鄰接表表示的無向圖中，若要刪除一條邊，需要進行哪些操作？A.在兩個相關頂點的鄰接表中刪除對應的邊節(jié)點B.只在一個頂點的鄰接表中刪除對應的邊節(jié)點C.重新構建鄰接表D.以上都不對14、二叉樹是一種重要的數(shù)據(jù)結構。對于一個滿二叉樹，若其高度為h，則節(jié)點總數(shù)為多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-115、對于一個用數(shù)組實現(xiàn)的最小堆，若要刪除堆頂元素并調整堆，以下操作正確的是？（）A.將堆尾元素移到堆頂，然后從堆頂向下調整B.將堆頂元素與堆尾元素交換，然后從堆頂向下調整C.將堆頂元素刪除，然后重新構建堆D.以上都不對16、數(shù)據(jù)結構的應用非常廣泛，以下關于它們的應用場景的說法中，錯誤的是？（）A.數(shù)組可以用于存儲和處理大量的相同類型的數(shù)據(jù)。B.鏈表可以用于實現(xiàn)動態(tài)數(shù)據(jù)結構，如棧、隊列和鏈表等。C.樹可以用于實現(xiàn)文件系統(tǒng)、數(shù)據(jù)庫索引和表達式求值等。D.數(shù)據(jù)結構只在計算機科學領域有應用，在其他領域沒有實際價值。17、對于一個用鄰接矩陣存儲的圖，若要判斷兩個頂點之間是否存在邊，時間復雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)18、若對一棵二叉排序樹進行中序遍歷，得到的節(jié)點序列是一個遞增序列，則該二叉排序樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空19、在一個具有n個頂點的強連通圖中，至少有（）條邊。A.n-1B.nC.n(n-1)D.n(n-1)/220、在一個具有n個節(jié)點的圖中，使用弗洛伊德算法求所有節(jié)點對之間的最短路徑，其時間復雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)二、簡答題（本大題共4個小題，共40分)1、（本題10分）在一個具有n個頂點的無向圖中，如何找出所有的割點，給出一種有效的算法并分析其時間復雜度。2、（本題10分）在一個鏈表中，如何實現(xiàn)鏈表的復制操作？3、（本題10分）論述如何使用隨機化快速排序優(yōu)化普通快速排序在某些特殊情況下的性能。4、（本題10分）詳細闡述在堆的應用拓展中，如何使用堆進行數(shù)據(jù)流中的中