保山學(xué)院《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁保山學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、已知一個棧的進(jìn)棧序列為1,2,3,4，出棧序列為3,2,4,1，則棧的容量至少為（）。A.2B.3C.4D.52、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），需要移動多少個元素？（）A.n-iB.iC.n-i+1D.n-i-13、在一棵二叉樹中，若每個節(jié)點的左子樹和右子樹的高度最多相差1，則該二叉樹被稱為平衡二叉樹。對于一個平衡二叉樹，進(jìn)行插入操作后，為了保持平衡，可能需要進(jìn)行多少次旋轉(zhuǎn)調(diào)整？A.0次B.1次C.最多2次D.不確定4、以下關(guān)于堆的描述，正確的是：A.大頂堆中每個父節(jié)點的值都大于其子節(jié)點的值B.小頂堆中每個父節(jié)點的值都小于其子節(jié)點的值C.堆可以用順序存儲也可以用鏈?zhǔn)酱鎯.堆是完全二叉樹5、在一個用數(shù)組實現(xiàn)的堆中，若要刪除堆底的元素，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一個具有n個頂點的帶權(quán)有向圖中，使用迪杰斯特拉（Dijkstra）算法求單源最短路徑。以下關(guān)于該算法的時間復(fù)雜度的描述，哪一項是準(zhǔn)確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)7、對于一個具有n個元素的直接插入排序，在最好情況下，需要進(jìn)行多少次比較操作？（）A.n-1B.nC.n(n-1)/2D.08、在數(shù)據(jù)結(jié)構(gòu)中，哈弗曼編碼是一種用于數(shù)據(jù)壓縮的編碼方式，以下關(guān)于哈弗曼編碼的描述，錯誤的是（）A.出現(xiàn)頻率高的字符編碼較短B.編碼是唯一的C.解碼過程簡單D.對所有數(shù)據(jù)都能達(dá)到很好的壓縮效果9、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實現(xiàn)字典操作（添加、刪除、查找），且平均時間復(fù)雜度較低？A.數(shù)組B.鏈表C.二叉搜索樹D.哈希表10、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)優(yōu)先級隊列？A.鏈表B.隊列C.棧D.堆11、在圖的遍歷算法中，深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）是兩種常見的方法。以下關(guān)于它們的描述，錯誤的是（）A.DFS使用棧來保存未訪問的節(jié)點B.BFS使用隊列來保存未訪問的節(jié)點C.DFS可能會陷入死循環(huán)D.BFS一定能找到最短路徑12、對于一個具有n個元素的有序單鏈表，若要在其中查找一個特定元素，其平均時間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)13、對于一個具有n個元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調(diào)整B.直接使用快速排序C.先構(gòu)建大頂堆再調(diào)整D.以上方法效率相同14、在一個具有n個頂點的圖中，若存在回路，則深度優(yōu)先遍歷可能會出現(xiàn)什么情況？（）A.訪問某些頂點多次B.無法完成遍歷C.結(jié)果不正確D.以上都有可能15、在一個具有n個頂點的強(qiáng)連通圖中，至少有多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)16、在一個具有n個節(jié)點的圖中，使用深度優(yōu)先搜索算法遍歷所有節(jié)點，其時間復(fù)雜度主要取決于什么？A.邊的數(shù)量B.節(jié)點的數(shù)量C.圖的存儲方式D.以上都是17、已知一個有序表為{12,25,30,45,50,60,70,80}，若采用折半查找法查找值為45的元素，需要比較多少次？（）A.1B.2C.3D.418、若對線性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲結(jié)構(gòu)，則插入和刪除操作的時間復(fù)雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)19、在一個用鄰接矩陣存儲的無向圖中，若要刪除一條邊，需要修改矩陣中的幾個元素？A.1個B.2個C.3個D.4個20、在一個用鄰接表表示的無向圖中，若要刪除一條邊，需要進(jìn)行的操作是？（）A.在兩個頂點的鄰接表中刪除對應(yīng)的邊節(jié)點B.只在一個頂點的鄰接表中刪除對應(yīng)的邊節(jié)點C.重新構(gòu)建鄰接表D.以上都不對二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述如何在一個圖中使用弗洛伊德算法求解所有頂點對之間的最短路徑。2、（本題10分）論述在Trie樹中，如何節(jié)省存儲空間，例如采用壓縮存儲或節(jié)點合并等方法。3、（本題10分）解釋如何在一個字符串中查找所有長度為k的子串，并判斷是否為回文串。4、（本題10分）說明二叉樹的遍歷算法在二叉樹的葉子節(jié)點之和問題、樹的直徑問題中的應(yīng)用。三、設(shè)計題（本