西安電子科技大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁西安電子科技大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個元素的直接插入排序，在最好情況下，需要進(jìn)行多少次比較操作？（）A.n-1B.nC.n(n-1)/2D.02、在一個具有n個元素的順序表中，要在中間位置插入一個新元素，平均移動元素的個數(shù)約為？A.n/2B.nC.lognD.13、對于一棵二叉樹，先序遍歷序列為ABC，中序遍歷序列為BAC，則其后序遍歷序列為？A.BCAB.CBAC.ACBD.ABC4、在一個具有n個元素的有序單鏈表中，若要查找一個特定元素，以下關(guān)于查找操作的時間復(fù)雜度的描述，哪一項是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、棧和隊列在計算機科學(xué)中有很多應(yīng)用，以下關(guān)于它們的應(yīng)用場景的說法中，錯誤的是？（）A.?？梢杂糜趯崿F(xiàn)表達(dá)式求值、括號匹配等。B.隊列可以用于實現(xiàn)任務(wù)調(diào)度、消息隊列等。C.棧和隊列可以用于實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊列只能在編程語言的底層實現(xiàn)中使用，不能在實際應(yīng)用中直接使用。6、對于一個具有n個元素的堆，進(jìn)行插入操作的時間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、在一個具有n個頂點和e條邊的帶權(quán)無向圖中，使用Prim算法生成最小生成樹。若采用鄰接矩陣存儲圖，以下關(guān)于算法的空間復(fù)雜度的描述，哪一項是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)8、若一棵二叉樹的層次遍歷序列為ABCDEFGHI，則其可能的中序遍歷序列有多少種？（）A.1B.n!C.2^nD.不確定9、對于一個具有n個元素的有序單鏈表，若要在其中查找一個特定元素，平均需要比較的次數(shù)為？（）A.n/2B.nC.lognD.nlogn10、在一個帶權(quán)的有向圖中，使用迪杰斯特拉算法求從源點到其他頂點的最短路徑，每次選擇的頂點是？（）A.距離源點最近的頂點B.距離源點最遠(yuǎn)的頂點C.未確定最短路徑的頂點中權(quán)值最小的頂點D.未確定最短路徑的頂點中權(quán)值最大的頂點11、對于一個棧，進(jìn)行入棧和出棧操作時，若棧頂指針top初始值為-1，當(dāng)進(jìn)行5次入棧和3次出棧操作后，top的值為多少？（）A.1B.2C.3D.412、對于一個具有n個頂點和e條邊的帶權(quán)有向圖，使用弗洛伊德（Floyd）算法求所有頂點對之間的最短路徑。以下關(guān)于該算法的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.O(n)B.O(n^2)C.O(n^3)D.O(e^3)13、以下哪種數(shù)據(jù)結(jié)構(gòu)可以快速查找一個有序數(shù)組中的中位數(shù)？A.二叉搜索樹B.堆C.哈希表D.鏈表14、在一個有向無環(huán)圖中，進(jìn)行拓?fù)渑判虻慕Y(jié)果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對15、對于一個m行n列的二維數(shù)組，按行優(yōu)先存儲時，元素a[i][j]（0<=i<m,0<=j<n）的地址計算公式為：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i16、在一個用數(shù)組實現(xiàn)的小根堆中，若要插入一個元素，應(yīng)該將其插入到數(shù)組的哪個位置？A.數(shù)組末尾B.堆頂C.任意位置D.以上都不對17、以下關(guān)于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的描述，哪一項是正確的？（）A.深度優(yōu)先搜索使用隊列實現(xiàn)B.廣度優(yōu)先搜索使用棧實現(xiàn)C.兩種搜索算法都可以用于判斷圖是否連通D.深度優(yōu)先搜索一定能找到最短路徑18、在一個具有n個節(jié)點的二叉樹中，若采用中序遍歷得到的節(jié)點序列是有序的，則該二叉樹可能是什么類型？A.滿二叉樹B.完全二叉樹C.二叉搜索樹D.以上都有可能19、在數(shù)據(jù)結(jié)構(gòu)中，桶排序是一種外部排序算法，以下關(guān)于桶排序的描述，錯誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時間復(fù)雜度為O(n)C.空間復(fù)雜度較高D.適用于大規(guī)模數(shù)據(jù)排序20、一棵哈夫曼樹中，葉子節(jié)點的編碼長度一定（）非葉子節(jié)點的編碼長度。A.大于B.等于C.小于D.不小于二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細(xì)闡述如何在一個鏈表中實現(xiàn)節(jié)點的排序，要求空間復(fù)雜度為O(1)。2、（本題10分）對于一個具有n個頂點的有向圖，如何使用拓?fù)渑判蛩惴ń鉀Q課程安排問題？3、（本題10分）深入分析在具有n個元素的數(shù)組中，如何實現(xiàn)歸并排序的非遞歸版本，并比較其與遞歸版本的性能差異。4、（本題10分）論述在二叉搜索樹的迭代器實現(xiàn)中，如何按照中序遍歷的順序訪問節(jié)點。三、設(shè)計題（本大題共2個小題，共20分)1