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

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

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