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

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績(jī)按零分記。…………密………………封………………線…………第1頁(yè)，共1頁(yè)南京傳媒學(xué)院

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