呼倫貝爾學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

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

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的順序表中，刪除第i個(gè)元素（1<=i<=n），需要移動(dòng)的元素個(gè)數(shù)最多為（）。A.i-1B.n-iC.n-i+1D.n-12、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB3、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)4、在二叉樹的序列化和反序列化過程中，以下方法不能保證唯一性的是（）A.先序遍歷序列化B.中序遍歷序列化C.后序遍歷序列化D.層序遍歷序列化5、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的線索二叉樹，若n個(gè)節(jié)點(diǎn)中有m個(gè)空指針域，則線索的數(shù)量為？A.mB.m/2C.n+1D.n-16、對(duì)于一個(gè)有向無環(huán)圖（DAG），進(jìn)行拓?fù)渑判虻姆椒ú恢挂环N。以下關(guān)于拓?fù)渑判虻拿枋?，錯(cuò)誤的是（）A.可以使用深度優(yōu)先搜索實(shí)現(xiàn)B.結(jié)果不唯一C.可以用于判斷圖中是否存在環(huán)D.所有節(jié)點(diǎn)的入度在排序過程中不會(huì)改變7、設(shè)有一個(gè)具有n個(gè)元素的最大堆，若要獲取堆中的最大元素，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向連通圖，若要判斷其是否存在環(huán)，以下哪種算法的時(shí)間復(fù)雜度最低？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓?fù)渑判駾.以上算法時(shí)間復(fù)雜度相同9、在圖的存儲(chǔ)結(jié)構(gòu)中，鄰接多重表主要用于存儲(chǔ)無向圖，以下關(guān)于鄰接多重表的特點(diǎn)，描述錯(cuò)誤的是（）A.可以方便地刪除邊B.存儲(chǔ)空間比鄰接矩陣節(jié)省C.對(duì)于判斷兩點(diǎn)之間是否有邊，效率較高D.不適合用于有向圖的存儲(chǔ)10、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)文件系統(tǒng)中的目錄結(jié)構(gòu)？（）A.棧B.隊(duì)列C.樹D.哈希表11、在一個(gè)具有n個(gè)元素的順序表中，進(jìn)行插入操作時(shí)，平均移動(dòng)元素的個(gè)數(shù)為：A.n/2B.(n+1)/2C.nD.n-112、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結(jié)構(gòu)13、對(duì)于一個(gè)具有n個(gè)元素的雙向循環(huán)鏈表，若要?jiǎng)h除第i個(gè)節(jié)點(diǎn)（1<=i<=n），平均需要修改多少個(gè)指針？（）A.2B.3C.4D.514、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實(shí)現(xiàn)集合的交集運(yùn)算，并具有較低的時(shí)間復(fù)雜度？A.鏈表B.二叉搜索樹C.哈希表D.并查集15、若一個(gè)圖的鄰接矩陣對(duì)角線以下（不包括對(duì)角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖16、已知一個(gè)有序表為{12,25,30,45,50,60,70,80}，若采用折半查找法查找值為45的元素，需要比較多少次？（）A.1B.2C.3D.417、在一個(gè)B樹中，每個(gè)節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-118、在一個(gè)具有n個(gè)元素的有序單鏈表中，進(jìn)行插入操作時(shí)，平均需要移動(dòng)的元素個(gè)數(shù)約為？A.n/2B.nC.lognD.119、以下哪種排序算法在元素基本有序的情況下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序20、設(shè)有一個(gè)帶權(quán)有向圖G=(V,E)，采用拓?fù)渑判蛩惴▽?duì)其進(jìn)行排序，若得到的拓?fù)湫蛄形ㄒ唬瑒t圖G一定是？（）A.有環(huán)圖B.無環(huán)圖C.強(qiáng)連通圖D.弱連通圖二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入解釋在具有n個(gè)頂點(diǎn)和e條邊的無向圖中，如何使用普里姆（Prim）算法求解最小生成森林，并說明算法的基本思想和關(guān)鍵步驟。2、（本題10分）解釋如何在一個(gè)鏈表中判斷是否存在值連續(xù)的節(jié)點(diǎn)段。3、（本題10分）詳細(xì)闡述在一個(gè)具有n個(gè)元素的堆中，如何利用堆進(jìn)行Top-K問題的求解。4、（本題10分）比較選擇排序和插入排序在移動(dòng)元素次數(shù)上的差異，并說明原因。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分