樂山師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)》2022-2023學(xué)年期末試卷

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

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