湖南財政經(jīng)濟學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準考證號學(xué)校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁湖南財政經(jīng)濟學(xué)院

《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），需要移動的元素個數(shù)最多為（）。A.i-1B.n-iC.n-i+1D.n-12、在一個哈希表中，負載因子越大，說明什么？A.哈希沖突越少B.存儲空間利用率越高C.查找效率越高D.以上都不對3、在一個具有n個元素的二叉排序樹中，查找一個不存在的元素，其時間復(fù)雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)4、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則矩陣中非零元素的個數(shù)至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/25、對于一個具有n個元素的冒泡排序，若元素基本有序，其時間復(fù)雜度接近？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)6、在一個具有n個元素的順序存儲的循環(huán)隊列中，隊滿的條件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front7、設(shè)有一個長度為n的順序表，要在第i個元素之前插入一個新元素，并且移動元素的平均次數(shù)為n/2，則插入算法的平均時間復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)8、在一個具有n個元素的隊列中，若要獲取隊頭元素的前一個元素但不刪除，以下操作不可行的是？（）A.遍歷整個隊列B.使用輔助數(shù)據(jù)結(jié)構(gòu)C.直接獲取D.以上都不可行9、以下哪種數(shù)據(jù)結(jié)構(gòu)可以高效地支持集合的并、交、差等操作？A.二叉搜索樹B.哈希表C.并查集D.平衡二叉樹10、若一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBDAEGF，則其后序遍歷序列為？（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEAGF11、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），需要移動多少個元素？（）A.n-iB.iC.n-i+1D.n-i-112、在一個具有n個元素的最小堆中，插入一個新元素后，為了重新調(diào)整為最小堆，最壞情況下需要比較多少次？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)13、對于一個具有n個節(jié)點的紅黑樹，插入一個新節(jié)點后，調(diào)整樹的結(jié)構(gòu)以保持紅黑樹性質(zhì)，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、在一個帶頭結(jié)點的單鏈表中，若要刪除表中所有值為x的結(jié)點，最優(yōu)的算法時間復(fù)雜度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)15、已知一個圖的鄰接表存儲結(jié)構(gòu)，若要判斷任意兩個頂點之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索16、在一棵度為4的樹中，若有20個度為4的節(jié)點，10個度為3的節(jié)點，1個度為2的節(jié)點，10個葉子節(jié)點，那么這棵樹的總節(jié)點數(shù)是多少？A.82B.81C.79D.7817、棧和隊列的操作可以用棧和隊列的基本操作來實現(xiàn)，以下關(guān)于它們的操作實現(xiàn)的說法中，錯誤的是？（）A.可以用兩個棧實現(xiàn)一個隊列，也可以用兩個隊列實現(xiàn)一個棧。B.用棧實現(xiàn)隊列時，需要考慮隊列的先進先出特性，可能需要使用輔助棧。C.用隊列實現(xiàn)棧時，需要考慮棧的后進先出特性，可能需要使用輔助隊列。D.棧和隊列的操作只能用棧和隊列的基本操作來實現(xiàn)，不能用其他數(shù)據(jù)結(jié)構(gòu)來輔助實現(xiàn)。18、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)圖的廣度優(yōu)先遍歷的輔助隊列？A.循環(huán)隊列B.鏈隊列C.優(yōu)先隊列D.雙端隊列19、對于一個具有n個元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調(diào)整B.直接使用快速排序C.先構(gòu)建大頂堆再調(diào)整D.以上方法效率相同20、圖的存儲方式和遍歷方式可以用于解決很多實際問題，以下關(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)用中沒有實際價值。二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述AVL樹在空間利用效率方面的特點和優(yōu)化方法。2、（本題10分）論述哈希表的沖突解決方法，如線性探測法、二次探測法和鏈地址法，并分析它們的優(yōu)缺點。3、（本題10分）詳細說明如何對一個二叉搜索樹進行中序遍歷的非遞歸實現(xiàn)，分析其時間和空間復(fù)雜度。4、（本題10分）對于一個用鄰接矩陣存儲的有向圖，說明如何判斷圖是否強連通，給出一種有效的算法并分析其時間復(fù)