學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁湖南財政經濟學院

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