南京工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)C》2021-2022學(xué)年期末試卷

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績(jī)按零分記。…………密………………封………………線…………第1頁(yè)，共1頁(yè)南京工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)C》

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