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

《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的棧中，若要獲取棧底元素但不刪除，需要進行多少次操作？（）A.1B.n-1C.nD.n+12、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則存儲空間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)3、在一個具有n個節(jié)點的有向圖中，若存在多個入度為0的節(jié)點，進行拓撲排序時，應(yīng)該選擇哪個節(jié)點作為起始節(jié)點？A.任意一個入度為0的節(jié)點B.編號最小的入度為0的節(jié)點C.編號最大的入度為0的節(jié)點D.以上都不對4、在一個鏈式存儲的線性表中，若要刪除第i個元素（1<=i<=n），需要找到其前驅(qū)節(jié)點的時間復(fù)雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)5、對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則存儲空間的復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)6、在一個用鄰接表表示的無向圖中，若要刪除一條邊，需要進行哪些操作？A.在兩個相關(guān)頂點的鄰接表中刪除對應(yīng)的邊節(jié)點B.只在一個頂點的鄰接表中刪除對應(yīng)的邊節(jié)點C.重新構(gòu)建鄰接表D.以上都不對7、在一個具有n個元素的順序表中，若要在第i個元素之前插入一個新元素，平均需要移動多少個元素？（）A.n/2B.nC.iD.n-i8、對于一個循環(huán)隊列，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAX_SIZE，那么判斷隊空的條件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-19、以下關(guān)于字符串匹配的BM算法的描述，哪一項是不正確的？（）A.從模式串的尾部開始匹配B.利用了壞字符和好后綴規(guī)則C.在一般情況下比KMP算法效率低D.可以通過預(yù)處理提高匹配速度10、哈希表的沖突解決方法和性能優(yōu)化可以用于提高哈希表的效率，以下關(guān)于它們的說法中，錯誤的是？（）A.開放定址法和鏈地址法是哈希表的兩種主要沖突解決方法，它們各有優(yōu)缺點。B.可以通過調(diào)整哈希函數(shù)、增加哈希表的大小和采用二次探測等方法來優(yōu)化哈希表的性能。C.哈希表的性能優(yōu)化需要根據(jù)實際情況進行選擇，不同的應(yīng)用場景可能需要不同的優(yōu)化方法。D.哈希表的沖突解決方法和性能優(yōu)化只適用于理論研究，在實際應(yīng)用中沒有實際價值。11、若要對n個元素進行快速排序，在最壞情況下，其時間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(nlog?n)D.O(n2)12、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲其下三角部分，第一個元素A[1,1]存儲在數(shù)組B[0]中，若A[8,5]在數(shù)組B中的存儲位置為k，則A[7,5]在數(shù)組B中的存儲位置為（）。A.k-13B.k-12C.k-11D.k-1013、對于一個具有n個元素的堆，進行堆排序。以下關(guān)于堆排序的平均時間復(fù)雜度和空間復(fù)雜度的描述，哪一個是準確的？A.平均時間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)B.平均時間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(n)C.平均時間復(fù)雜度為O(logn)，空間復(fù)雜度為O(logn)D.平均時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)14、以下關(guān)于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的描述，哪一項是正確的？（）A.深度優(yōu)先搜索使用隊列實現(xiàn)B.廣度優(yōu)先搜索使用棧實現(xiàn)C.兩種搜索算法都可以用于判斷圖是否連通D.深度優(yōu)先搜索一定能找到最短路徑15、在循環(huán)鏈表中，尾指針rear指向鏈表的尾節(jié)點，若要在鏈表中插入一個新的節(jié)點，使其成為新的尾節(jié)點，以下操作正確的是？（）A.rear->next=new_node;new_node->next=rear;rear=new_node;B.new_node->next=rear;rear->next=new_node;rear=new_node;C.rear=new_node;new_node->next=rear->next;rear->next=new_node;D.new_node->next=rear->next;rear->next=new_node;16、對于一個具有n個元素的有序鏈表，若要在其中插入一個新元素并保持有序，平均需要移動的元素個數(shù)為？（）A.n/2B.nC.lognD.nlogn17、對于一個具有n個節(jié)點的二叉樹，其高度的最小值和最大值分別是多少？（）A.log?n,n-1B.1,nC.log?n,nD.1,n-118、在一個具有n個節(jié)點的圖中，使用深度優(yōu)先搜索算法遍歷所有節(jié)點，其時間復(fù)雜度主要取決于什么？A.邊的數(shù)量B.節(jié)點的數(shù)量C.圖的存儲方式D.以上都是19、對于一個具有n個節(jié)點的完全二叉樹，若底層從左到右填充，則第i個節(jié)點的左孩子節(jié)點的編號為？A.2iB.2i+1C.i*2D.i*2+120、對于一個具有n個元素的無序數(shù)組，使用冒泡排序進行排序，最壞情況下的比較次數(shù)為？A.n(n-1)/2B.nlognC.n^2D.2^n二、簡答題（本大題共4個小題，共40分)1、（本題10分）描述二叉樹的層次遍歷方法，并說明其實現(xiàn)思路。2、（本題10分）解釋一下什么是棧，并說明棧的基本操作（入棧、出棧）的實現(xiàn)原理。同時，舉例說明棧在表達式求值和括號匹配中的應(yīng)用。3、（本題10分）論述如何在一個有向圖中計算強連通分量，給出具體的算法步驟。4、（本題10分）解釋在平衡二叉搜索樹中，刪除操作后如何恢復(fù)樹的平