站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁南京工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)C》

2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的順序表中，進(jìn)行插入操作時，平均移動元素的個數(shù)為：A.n/2B.(n+1)/2C.nD.n-12、在一個具有n個元素的無序數(shù)組中，使用選擇排序進(jìn)行排序。以下關(guān)于選擇排序的時間復(fù)雜度的描述，哪一項是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)3、對于一個采用鏈表存儲的棧，若要獲取棧的大?。ㄔ財?shù)量），以下關(guān)于操作的時間復(fù)雜度的描述，哪一個是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在一個具有n個元素的循環(huán)雙鏈表中，若要在表頭插入一個新元素，以下關(guān)于插入操作的時間復(fù)雜度的描述，哪一項是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、在一個帶頭結(jié)點(diǎn)的單鏈表中，若要刪除表中所有值為x的結(jié)點(diǎn)，最優(yōu)的算法時間復(fù)雜度是？（）A.O(1)B.O(n)C.O(nlogn)D.O(n^2)6、對于一個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+i7、線段樹是一種用于處理區(qū)間查詢和更新的數(shù)據(jù)結(jié)構(gòu)。對于線段樹的應(yīng)用，以下說法錯誤的是（）A.可以快速計算給定區(qū)間內(nèi)元素的和B.可以用于查找區(qū)間內(nèi)的最大值和最小值C.構(gòu)建線段樹的時間復(fù)雜度為O(n)D.線段樹的空間復(fù)雜度與節(jié)點(diǎn)數(shù)量成正比8、在一個B樹中，每個節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-19、在圖的最短路徑算法中，Dijkstra算法適用于帶權(quán)有向圖，以下關(guān)于Dijkstra算法的描述，錯誤的是（）A.以起始節(jié)點(diǎn)為中心向外層層擴(kuò)展B.每次選擇距離起始節(jié)點(diǎn)最近的未訪問節(jié)點(diǎn)C.可以處理負(fù)權(quán)邊D.時間復(fù)雜度為O(n^2)10、在圖的存儲結(jié)構(gòu)中，十字鏈表主要用于存儲有向圖，以下關(guān)于十字鏈表的特點(diǎn)，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲空間比鄰接表節(jié)省C.對于刪除邊的操作比較復(fù)雜D.不適合用于稀疏有向圖11、一棵哈夫曼樹中，葉子節(jié)點(diǎn)的編碼長度一定（）非葉子節(jié)點(diǎn)的編碼長度。A.大于B.等于C.小于D.不小于12、對于一個具有n個頂點(diǎn)的連通圖，其生成樹中邊的數(shù)量為：A.n-1B.nC.n+1D.不確定13、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD14、在一個具有n個頂點(diǎn)的帶權(quán)無向圖中，若采用普里姆（Prim）算法生成最小生成樹，其時間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)15、在一個具有n個頂點(diǎn)的有向強(qiáng)連通圖中，至少需要多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)16、在一個大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個元素交換，然后從堆頂向下調(diào)整D.無需調(diào)整17、對于一個具有n個頂點(diǎn)和e條邊的帶權(quán)有向圖，使用弗洛伊德（Floyd）算法求所有頂點(diǎn)對之間的最短路徑。以下關(guān)于該算法的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.O(n)B.O(n^2)C.O(n^3)D.O(e^3)18、在一個具有n個頂點(diǎn)的無向圖中，使用廣度優(yōu)先遍歷算法。以下關(guān)于遍歷過程中使用的輔助隊列的空間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(n^2)19、對于一個具有n個節(jié)點(diǎn)的無向連通圖，其生成樹的邊數(shù)為（）A.n-1B.nC.n+1D.2n20、對于一個具有n個節(jié)點(diǎn)的帶權(quán)連通圖，其最小生成樹一定包含圖中的所有節(jié)點(diǎn)嗎？A.一定包含B.不一定包含C.視情況而定D.以上都不對二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細(xì)闡述在并查集的數(shù)據(jù)結(jié)構(gòu)改進(jìn)中，如何使用樹的高度或節(jié)點(diǎn)數(shù)量來優(yōu)化合并操作。2、（本題10分）深入探討在一個具有n個元素的二叉搜索樹中，如何進(jìn)行范圍查詢。3、（本題10分）詳細(xì)說明在圖的遍歷中，如何處理帶有權(quán)值的邊，例如在最短路徑算法中的應(yīng)用。4、（本題10分）論述如何在一個字符串中查找最長回文子串，給出至少兩種算法思路和實(shí)現(xiàn)步