樂山師范學院《數(shù)據結構與算法設計》2022-2023學年期末試卷

自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁樂山師范學院《數(shù)據結構與算法設計》

2022-2023學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、已知一個棧的進棧序列為1,2,3,4，出棧序列為3,2,4,1，則棧的容量至少為（）。A.2B.3C.4D.52、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），需要移動的元素個數(shù)最多為（）。A.i-1B.n-iC.n-i+1D.n-13、在一個具有n個元素的有序雙向鏈表中，若要在指定位置插入一個新元素，以下關于插入操作的時間復雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在數(shù)據結構中，優(yōu)先隊列可以用堆來實現(xiàn)，以下關于堆調整的描述，錯誤的是（）A.插入元素時，從下往上調整堆B.刪除堆頂元素時，從上往下調整堆C.調整堆的過程中，節(jié)點的值可能會交換D.調整堆的時間復雜度與堆的大小無關5、以下哪種數(shù)據結構常用于實現(xiàn)字典操作，并且能夠快速查找、插入和刪除元素？（）A.棧B.隊列C.二叉搜索樹D.數(shù)組6、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為（）。A.CEABDB.CEDBAC.CABDED.CEDAB7、在一個具有n個元素的順序存儲的線性表中，要在第i個位置插入一個新元素（1<=i<=n+1），需要移動的元素個數(shù)約為？A.n-iB.iC.n-i+1D.n-i-18、在一個具有n個節(jié)點的二叉樹中，若采用中序遍歷得到的節(jié)點序列是有序的，則該二叉樹可能是什么類型？A.滿二叉樹B.完全二叉樹C.二叉搜索樹D.以上都有可能9、以下關于圖的存儲結構的描述，錯誤的是：A.鄰接矩陣適合存儲稠密圖B.鄰接表適合存儲稀疏圖C.十字鏈表是鄰接表和逆鄰接表的結合D.鄰接多重表只適合無向圖10、對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則存儲空間的復雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)11、在一個具有n個元素的線性表中，采用順序查找法查找一個特定元素，若查找成功，平均查找長度為？（）A.(n+1)/2B.n/2C.lognD.n12、對于一個用數(shù)組實現(xiàn)的小根堆，進行刪除堆頂元素操作后，需要重新調整堆以保持堆的性質。以下關于刪除操作的時間復雜度的描述，哪一個是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則下列不可能的出棧序列是：A.54321B.45321C.12345D.3142514、在一個具有n個頂點和e條邊的帶權有向圖中，使用弗洛伊德算法求所有頂點對之間的最短路徑，其時間復雜度為？（）A.O(n)B.O(n2)C.O(n3)D.O(e3)15、在一個具有n個元素的最大堆中，插入一個新元素后，為了恢復堆的性質，需要進行的調整操作的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、以下哪種數(shù)據結構常用于實現(xiàn)圖的深度優(yōu)先遍歷的棧？A.順序棧B.鏈棧C.共享棧D.以上均可17、在一個具有n個節(jié)點的有向圖中，若存在多個入度為0的節(jié)點，進行拓撲排序時，應該選擇哪個節(jié)點作為起始節(jié)點？A.任意一個入度為0的節(jié)點B.編號最小的入度為0的節(jié)點C.編號最大的入度為0的節(jié)點D.以上都不對18、在一個具有n個元素的雙向鏈表中，要在指定節(jié)點之后插入一個新節(jié)點，需要修改幾個指針？A.2B.3C.4D.519、對于一個具有n個元素的有序單鏈表，若要在其中查找一個特定元素，其平均時間復雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)20、在一個具有n個頂點和e條邊的無向圖中，使用克魯斯卡爾（Kruskal）算法生成最小生成樹。以下關于該算法的時間復雜度的描述，哪一項是正確的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述基數(shù)排序在處理負數(shù)和小數(shù)時的擴展方法。2、（本題10分）詳細論述在二叉樹的中序遍歷過程中，如何利用遞歸算法和非遞歸算法來實現(xiàn)，以及兩種方法的特點。3、（本題10分）論述AVL樹在頻繁更新操作下的性能瓶頸和可能的解決方案。4、（本題10分）詳細說明如何在一個具有n個頂點的有向圖中計算每個頂點的強連通分量大小。三、設計題（本大題共2個小題，共2