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

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

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