湖南城市學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁湖南城市學(xué)院

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一棵平衡二叉樹中，插入一個新節(jié)點后可能導(dǎo)致失衡，需要進(jìn)行調(diào)整。以下哪種調(diào)整操作可能涉及到旋轉(zhuǎn)次數(shù)最多？（）A.LL型調(diào)整B.RR型調(diào)整C.LR型調(diào)整D.RL型調(diào)整2、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，以下關(guān)于二叉樹的性質(zhì)的說法中，錯誤的是？（）A.二叉樹的每個節(jié)點最多有兩個子節(jié)點。B.二叉樹的左子樹和右子樹是有順序的。C.滿二叉樹是一種特殊的二叉樹，所有的葉節(jié)點都在同一層。D.完全二叉樹是一種特殊的滿二叉樹，所有的節(jié)點都在同一層。3、棧和隊列的操作可以用棧和隊列的基本操作來實現(xiàn)，以下關(guān)于它們的操作實現(xiàn)的說法中，錯誤的是？（）A.可以用兩個棧實現(xiàn)一個隊列，也可以用兩個隊列實現(xiàn)一個棧。B.用棧實現(xiàn)隊列時，需要考慮隊列的先進(jìn)先出特性，可能需要使用輔助棧。C.用隊列實現(xiàn)棧時，需要考慮棧的后進(jìn)先出特性，可能需要使用輔助隊列。D.棧和隊列的操作只能用棧和隊列的基本操作來實現(xiàn)，不能用其他數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn)。4、以下關(guān)于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的描述，哪一項是正確的？（）A.深度優(yōu)先搜索使用隊列實現(xiàn)B.廣度優(yōu)先搜索使用棧實現(xiàn)C.兩種搜索算法都可以用于判斷圖是否連通D.深度優(yōu)先搜索一定能找到最短路徑5、對于一個具有n個節(jié)點的平衡二叉樹，插入一個新節(jié)點并調(diào)整平衡，其平均時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一個具有n個元素的大根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進(jìn)行調(diào)整，其時間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)7、在一個有向無環(huán)圖中，進(jìn)行拓?fù)渑判虻慕Y(jié)果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對8、對于一個具有n個元素的有序鏈表，若要在其中查找一個特定元素，其平均時間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)9、圖的存儲方式和遍歷方式對圖的操作效率有很大影響，以下關(guān)于它們的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，查找邊的時間復(fù)雜度為O(1)，但空間復(fù)雜度較高。B.鄰接表適合存儲稀疏圖，插入邊和刪除邊的時間復(fù)雜度為O(1)，但查找邊的時間復(fù)雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時間復(fù)雜度都為O(n+m)，其中n是頂點數(shù)，m是邊數(shù)。D.圖的存儲方式和遍歷方式一旦確定，就不能再改變，否則會影響圖的操作效率。10、對于一個具有n個頂點的帶權(quán)連通圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(e^2)11、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)優(yōu)先級隊列？（）A.二叉樹B.鏈表C.堆D.棧12、對于一個具有n個元素的堆，進(jìn)行插入操作的時間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、在一個鏈?zhǔn)酱鎯Φ木€性表中，若要刪除第i個元素（1<=i<=n），需要找到其前驅(qū)節(jié)點的時間復(fù)雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)14、在一個帶頭結(jié)點的循環(huán)鏈表中，若要判斷鏈表是否為空，應(yīng)檢查？（）A.頭結(jié)點的指針是否為空B.頭結(jié)點的下一個結(jié)點的指針是否指向頭結(jié)點C.尾結(jié)點的指針是否為空D.尾結(jié)點的下一個結(jié)點的指針是否指向頭結(jié)點15、以下關(guān)于哈希沖突解決方法中二次探測法的描述，哪一項是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)16、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)表達(dá)式求值？A.二叉樹B.棧C.隊列D.哈希表17、圖的存儲方式和遍歷方式可以用于解決很多實際問題，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，適用于社交網(wǎng)絡(luò)分析和交通網(wǎng)絡(luò)規(guī)劃等。B.圖的鄰接表可以用于表示稀疏圖，適用于地圖繪制和電路圖設(shè)計等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問題和最小生成樹問題等，適用于物流配送和通信網(wǎng)絡(luò)優(yōu)化等。D.圖的存儲方式和遍歷方式只適用于理論研究，在實際應(yīng)用中沒有實際價值。18、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)操作系統(tǒng)中的進(jìn)程調(diào)度？A.隊列B.棧C.樹D.圖19、對于一個具有n個節(jié)點的完全二叉樹，若按層序編號，則編號為i的節(jié)點，其雙親節(jié)點的編號為？A.i/2B.(i-1)/2C.2iD.2i+120、在一個用鏈表實現(xiàn)的棧中，若要獲取棧底元素的值，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）深入分析在具有n個元素的數(shù)組中，如何實現(xiàn)快速選擇算法，用于查找第k小的元素，并給出時間復(fù)雜度的分析。2、（本題10分）在數(shù)據(jù)結(jié)構(gòu)中，闡述如何使用跳表進(jìn)行范圍查詢，給出算法步驟和實現(xiàn)代碼，并分析其性能特點。3、（本題10分）對于一個具有n個頂點和e條邊的帶權(quán)無向圖，如何使用克魯斯卡爾（Kruskal）算法構(gòu)造最小生成樹？4、（本題1