學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)北京聯(lián)合大學(xué)

《數(shù)據(jù)結(jié)構(gòu)A》2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，且rear<front，則隊(duì)列中的元素個(gè)數(shù)為？A.rear-frontB.front-rearC.(rear-front+n)%nD.(front-rear+n)%n2、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，采用鄰接表存儲(chǔ)，其時(shí)間復(fù)雜度為？（）A.O(n+e)B.O(n2)C.O(e2)D.O(ne)3、若要對(duì)一組無(wú)序的整數(shù)進(jìn)行排序，使其最終變?yōu)橐粋€(gè)遞增的有序序列，以下哪種排序算法在平均情況下性能最優(yōu)？A.冒泡排序B.插入排序C.選擇排序D.希爾排序4、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向連通圖，利用Prim算法構(gòu)造最小生成樹(shù)時(shí)，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)5、在一個(gè)用鄰接矩陣存儲(chǔ)的圖中，若要判斷兩個(gè)節(jié)點(diǎn)是否相鄰，時(shí)間復(fù)雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)6、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向完全圖，其弧的條數(shù)為（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/27、以下關(guān)于串的描述，錯(cuò)誤的是：A.串是一種特殊的線性表B.串的長(zhǎng)度是指串中字符的個(gè)數(shù)C.空串和空格串是相同的概念D.串的存儲(chǔ)方式有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)8、在一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無(wú)向圖中，若采用普里姆（Prim）算法生成最小生成樹(shù)，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)9、對(duì)于一個(gè)具有n個(gè)元素的有序鏈表，進(jìn)行二分查找的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.不能進(jìn)行二分查找10、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行堆排序。以下關(guān)于堆排序的平均時(shí)間復(fù)雜度和空間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.平均時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)B.平均時(shí)間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(n)C.平均時(shí)間復(fù)雜度為O(logn)，空間復(fù)雜度為O(logn)D.平均時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)11、在數(shù)據(jù)結(jié)構(gòu)中，跳表的索引層數(shù)是根據(jù)數(shù)據(jù)量動(dòng)態(tài)調(diào)整的，以下關(guān)于索引層數(shù)調(diào)整的描述，錯(cuò)誤的是（）A.當(dāng)數(shù)據(jù)量增加時(shí)，可能增加索引層數(shù)B.索引層數(shù)越多，查找效率越高C.調(diào)整索引層數(shù)的過(guò)程比較復(fù)雜D.索引層數(shù)的調(diào)整不會(huì)影響數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)12、在圖的遍歷算法中，深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）是兩種常見(jiàn)的方法。以下關(guān)于它們的描述，錯(cuò)誤的是（）A.DFS使用棧來(lái)保存未訪問(wèn)的節(jié)點(diǎn)B.BFS使用隊(duì)列來(lái)保存未訪問(wèn)的節(jié)點(diǎn)C.DFS可能會(huì)陷入死循環(huán)D.BFS一定能找到最短路徑13、在一個(gè)具有n個(gè)元素的順序表中，若要在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素，需要向后移動(dòng)多少個(gè)元素？（）A.n-iB.iC.n-i+1D.n-i-114、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉排序樹(shù)中，刪除一個(gè)節(jié)點(diǎn)后，為了保持二叉排序樹(shù)的性質(zhì)，可能需要進(jìn)行哪些操作？A.僅調(diào)整刪除節(jié)點(diǎn)的子樹(shù)B.從根節(jié)點(diǎn)開(kāi)始重新調(diào)整C.調(diào)整整個(gè)樹(shù)的結(jié)構(gòu)D.以上都有可能15、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的最長(zhǎng)公共子序列問(wèn)題？A.二維數(shù)組B.棧C.隊(duì)列D.樹(shù)16、設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE17、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？A.鏈表B.隊(duì)列C.棧D.堆18、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的深度優(yōu)先遍歷的棧？A.順序棧B.鏈棧C.共享?xiàng).以上均可19、在一個(gè)長(zhǎng)度為n的順序表中，刪除第i個(gè)元素（1<=i<=n）時(shí)，需要移動(dòng)的元素個(gè)數(shù)為：A.n-iB.i-1C.n-i+1D.i20、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的每個(gè)節(jié)點(diǎn)通常包含數(shù)據(jù)域和指針域。若要在一個(gè)單向鏈表中刪除一個(gè)指定節(jié)點(diǎn)，以下哪種操作是關(guān)鍵步驟？A.修改被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針B.修改被刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)的指針C.釋放被刪除節(jié)點(diǎn)的內(nèi)存D.以上都是二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）在一個(gè)二叉搜索樹(shù)中，如何查找值在給定范圍內(nèi)的所有元素？2、（本題10分）解釋數(shù)據(jù)結(jié)構(gòu)中棧的應(yīng)用場(chǎng)景，如括號(hào)的嵌套深度問(wèn)題、表達(dá)式的括號(hào)匹配高級(jí)問(wèn)題等，并說(shuō)明其原理。3、（本題10分）深入解釋在具有n個(gè)元素的鏈表中，如何實(shí)現(xiàn)鏈表的奇偶節(jié)點(diǎn)分離，將奇數(shù)位置的節(jié)點(diǎn)和偶數(shù)位置的節(jié)點(diǎn)分別連接成兩個(gè)鏈表。4、（本題10分）詳細(xì)闡述在堆的實(shí)現(xiàn)細(xì)節(jié)中，如何處理堆的擴(kuò)容和縮容