南京傳媒學院《數(shù)據(jù)結(jié)構(gòu)B》2022-2023學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁南京傳媒學院

《數(shù)據(jù)結(jié)構(gòu)B》2022-2023學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、已知一個帶權(quán)無向圖的鄰接矩陣表示，若要計算圖中兩個頂點之間的最短路徑，可以使用的算法是？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法2、對于一個具有n個元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調(diào)整B.直接使用快速排序C.先構(gòu)建大頂堆再調(diào)整D.以上方法效率相同3、在一個有序的單鏈表中，若要刪除一個重復出現(xiàn)的元素，使得鏈表中不再有重復元素，應如何操作？（）A.從頭遍歷，遇到重復元素就刪除B.從尾遍歷，遇到重復元素就刪除C.先排序，再刪除重復元素D.建立一個新鏈表，將不重復元素插入4、對于一個用鄰接矩陣存儲的圖，若要判斷兩個頂點之間是否存在邊，時間復雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)5、在一個具有n個節(jié)點的圖中，若要找出所有的連通分量，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.并查集D.以上都可以6、在一個具有n個元素的小根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進行調(diào)整，其時間復雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)7、若要對一個具有n個元素的數(shù)組進行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、在一個用鄰接表表示的無向圖中，若要刪除一條邊，需要進行的操作是？（）A.在兩個頂點的鄰接表中刪除對應的邊節(jié)點B.只在一個頂點的鄰接表中刪除對應的邊節(jié)點C.重新構(gòu)建鄰接表D.以上都不對9、堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，分為大頂堆和小頂堆。對于大頂堆，以下描述不正確的是（）A.根節(jié)點的值大于其左右子節(jié)點的值B.可以用于實現(xiàn)優(yōu)先隊列C.構(gòu)建大頂堆的時間復雜度為O(nlogn)D.每次刪除堆頂元素后，需要重新調(diào)整堆以保持大頂堆的性質(zhì)10、在一個具有n個元素的最小堆中，若要將堆頂元素與堆底元素交換，然后調(diào)整堆的結(jié)構(gòu)，需要的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一個用數(shù)組實現(xiàn)的小根堆中，若要插入一個元素，應該將其插入到數(shù)組的哪個位置？A.數(shù)組末尾B.堆頂C.任意位置D.以上都不對12、在一個具有n個頂點的無向完全圖中，每個頂點的度為多少？（）A.n-1B.nC.2(n-1)D.2n13、在一個帶頭結(jié)點的循環(huán)鏈表中，若要判斷鏈表是否為空，應檢查？（）A.頭結(jié)點的指針是否為空B.頭結(jié)點的下一個結(jié)點的指針是否指向頭結(jié)點C.尾結(jié)點的指針是否為空D.尾結(jié)點的下一個結(jié)點的指針是否指向頭結(jié)點14、在一個用數(shù)組實現(xiàn)的堆中，若要刪除堆底的元素，需要的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、以下關(guān)于快速排序的描述，錯誤的是：A.快速排序在平均情況下的時間復雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時間復雜度為O(n^2)D.快速排序不需要額外的存儲空間16、在一棵二叉搜索樹中，刪除一個節(jié)點后，為了保持二叉搜索樹的性質(zhì)，需要進行的調(diào)整操作可能包括（）A.左旋B.右旋C.左右旋結(jié)合D.以上都有可能17、對于一個具有n個元素的冒泡排序，若元素基本有序，其時間復雜度接近？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)18、對于一個用鏈表實現(xiàn)的棧，若要在棧頂插入一個元素，時間復雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)19、在數(shù)據(jù)結(jié)構(gòu)中，使用隊列來實現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點開始入隊B.隊列為空時結(jié)束遍歷C.訪問節(jié)點時將其未訪問的鄰接節(jié)點入隊D.節(jié)點不會被重復訪問20、在一棵度為4的樹中，若有20個度為4的節(jié)點，10個度為3的節(jié)點，1個度為2的節(jié)點，10個葉子節(jié)點，那么這棵樹的總節(jié)點數(shù)是多少？A.82B.81C.79D.78二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細說明如何在一個具有n個頂點的無向圖中找出所有頂點之間的最短路徑長度之和。2、（本題10分）深入探討在一個具有n個元素的循環(huán)隊列中，如何有效地判斷隊列是否已滿。3、（本題10分）請詳細闡述在順序表中進行插入操作時，平均移動元素次數(shù)的計算方法，并說明在什么情況下移動元素的次數(shù)最多。4、（本題10分）論述哈希表的沖突解決方法，如線性探測法、二次探測法和鏈地址法，