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

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁湖北恩施學(xué)院

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種數(shù)據(jù)結(jié)構(gòu)在查找、插入和刪除操作的綜合性能上表現(xiàn)較好？（）A.二叉搜索樹B.紅黑樹C.B樹D.哈希表2、以下關(guān)于圖的存儲結(jié)構(gòu)的描述，哪一項(xiàng)是正確的？（）A.鄰接矩陣適合存儲稀疏圖B.鄰接表在存儲稠密圖時空間效率較高C.十字鏈表適合存儲有向圖D.以上都不正確3、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進(jìn)行先序遍歷，比較節(jié)點(diǎn)值B.同時進(jìn)行中序遍歷，比較節(jié)點(diǎn)值C.同時進(jìn)行后序遍歷，比較節(jié)點(diǎn)值D.比較兩棵樹的節(jié)點(diǎn)數(shù)量4、在圖的遍歷算法中，深度優(yōu)先搜索（DFS）和廣度優(yōu)先搜索（BFS）是兩種常見的方法。以下關(guān)于它們的描述，錯誤的是（）A.DFS使用棧來保存未訪問的節(jié)點(diǎn)B.BFS使用隊(duì)列來保存未訪問的節(jié)點(diǎn)C.DFS可能會陷入死循環(huán)D.BFS一定能找到最短路徑5、對于一個具有n個頂點(diǎn)和e條邊的帶權(quán)無向圖，使用克魯斯卡爾（Kruskal）算法構(gòu)造最小生成樹，其時間復(fù)雜度主要取決于：A.邊數(shù)eB.頂點(diǎn)數(shù)nC.n和e的和D.n和e的乘積6、對于一棵二叉搜索樹，進(jìn)行中序遍歷得到的序列是一個有序序列。若對其進(jìn)行刪除操作，以下關(guān)于時間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.平均時間復(fù)雜度為O(logn)，最壞情況為O(n)B.時間復(fù)雜度始終為O(logn)C.平均時間復(fù)雜度為O(n)，最壞情況為O(nlogn)D.時間復(fù)雜度始終為O(n)7、對于一個具有n個元素的有序單鏈表，若要在其中查找一個特定元素，其平均時間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)8、若一個棧的輸入序列為1,2,3,4,5，不可能得到的輸出序列是？（）A.5,4,3,2,1B.4,5,3,2,1C.4,3,5,1,2D.1,2,3,4,59、在一個具有n個元素的單鏈表中，若要在第i個位置（1<=i<=n）插入一個新元素，平均需要遍歷多少個節(jié)點(diǎn)？（）A.i-1B.iC.(i-1)/2D.i/210、若一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB11、已知一個帶權(quán)有向圖G=(V,E)，頂點(diǎn)集合V={1,2,3,4,5}，邊集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求從頂點(diǎn)1到頂點(diǎn)5的最短路徑，經(jīng)過的中間頂點(diǎn)依次為？（）A.2,4B.3,4C.2,3D.3,512、對于一個用鏈表實(shí)現(xiàn)的棧，若要獲取棧中元素的個數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護(hù)一個計(jì)數(shù)器C.以上效率相同D.以上都不對13、若一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的后序遍歷序列為？（）A.BCAB.CBAC.ABCD.ACB14、以下關(guān)于平衡二叉樹旋轉(zhuǎn)調(diào)整的描述，正確的是：A.旋轉(zhuǎn)調(diào)整一定會改變樹的中序遍歷結(jié)果B.左旋操作是將右子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)樽笞庸?jié)點(diǎn)C.右旋操作是將左子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)橛易庸?jié)點(diǎn)D.平衡二叉樹不需要進(jìn)行旋轉(zhuǎn)調(diào)整15、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)LRU（最近最少使用）頁面置換算法？A.隊(duì)列B.棧C.哈希表D.雙鏈表16、在一個具有n個元素的順序表中，進(jìn)行插入操作時，平均移動元素的個數(shù)為：A.n/2B.(n+1)/2C.nD.n-117、在一個具有n個頂點(diǎn)的有向完全圖中，邊的數(shù)量為：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)18、在一個長度為n的順序表中，刪除第i個元素（1<=i<=n）時，需要移動的元素個數(shù)為：A.n-iB.i-1C.n-i+1D.i19、對于一個具有n個頂點(diǎn)的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時間復(fù)雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)20、對于一個棧，進(jìn)行入棧和出棧操作時，以下哪種情況會導(dǎo)致棧溢出？A.入棧元素過多B.出棧元素過多C.連續(xù)進(jìn)行入棧操作且存儲空間已滿D.連續(xù)進(jìn)行出棧操作且棧為空二、簡答題（本大題共4個小題，共40分)1、（本題10分）對于一個具有n個元素的數(shù)組，如何使用快速排序算法處理數(shù)據(jù)元素值范圍較小的情況？2、（本題10分）對于一個用鄰接表存儲的有向圖，詳細(xì)闡述如何進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，給出兩種遍歷算法的步驟和實(shí)現(xiàn)代碼框架。3、（本題10分）論述跳表中多層結(jié)構(gòu)的構(gòu)建原理和對查找性能的影響。4、（本題10分）隊(duì)列是一種常見的數(shù)據(jù)結(jié)構(gòu)，論述其先進(jìn)先出的特性，以及如何用