學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁湖北第二師范學院《數(shù)據(jù)結構》

2021-2022學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個用數(shù)組實現(xiàn)的循環(huán)隊列中，若隊頭指針front=5，隊尾指針rear=2，隊列容量為10，則隊列中的元素個數(shù)是多少？A.7B.6C.5D.42、已知一個棧的進棧序列為1,2,3,4，出棧序列為3,2,4,1，則棧的容量至少為（）。A.2B.3C.4D.53、對于一個具有n個元素的棧，若要實現(xiàn)將棧中元素逆置，需要借助的輔助數(shù)據(jù)結構為？（）A.隊列B.棧C.鏈表D.數(shù)組4、對于一個采用鏈表存儲的隊列，若要刪除隊尾元素，以下關于操作的時間復雜度的描述，哪一個是恰當?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、對于一個用鄰接矩陣存儲的圖，若要判斷兩個頂點之間是否存在邊，時間復雜度為？（）A.O(1)B.O(n)C.O(log?n)D.O(n2)6、在一個鏈式存儲的隊列中，若隊頭指針為front，隊尾指針為rear，要刪除隊頭元素，需要進行的操作是？（）A.front=front->next;B.rear=front;C.rear=rear->next;D.front=NULL;7、在一個具有n個元素的單鏈表中，若要在第i個位置（1<=i<=n）插入一個新元素，平均需要遍歷多少個節(jié)點？（）A.i-1B.iC.(i-1)/2D.i/28、對于一個具有n個元素的無序鏈表，若要對其進行排序，以下哪種排序算法較為合適？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序9、對于一個具有n個節(jié)點的完全二叉樹，若按層序編號，則編號為i的節(jié)點，其雙親節(jié)點的編號為？A.i/2B.(i-1)/2C.2iD.2i+110、以下哪種數(shù)據(jù)結構常用于實現(xiàn)LRU（最近最少使用）頁面置換算法？A.隊列B.棧C.哈希表D.雙鏈表11、若要對一個具有n個元素的無序數(shù)組進行排序，以下哪種排序算法在最壞情況下的時間復雜度最低？A.冒泡排序B.插入排序C.選擇排序D.歸并排序12、對于一個具有n個元素的雙向鏈表，若要在第i個位置（1<=i<=n）之前插入一個新節(jié)點，平均需要修改多少個指針？（）A.1B.2C.3D.413、對于一個具有n個節(jié)點的線索二叉樹，若n個節(jié)點中有m個空指針域，則線索的數(shù)量為？A.mB.m/2C.n+1D.n-114、在數(shù)據(jù)結構中，哈希表的負載因子對性能有很大影響。以下關于負載因子的描述，不正確的是（）A.負載因子越大，哈希沖突的可能性越大B.負載因子越小，存儲空間利用率越高C.負載因子通常在0.5到1之間D.可以通過調整負載因子來優(yōu)化哈希表性能15、一棵哈夫曼樹中，葉子節(jié)點的編碼長度一定（）非葉子節(jié)點的編碼長度。A.大于B.等于C.小于D.不小于16、對于一個采用鏈表存儲的隊列，若要實現(xiàn)隊列的逆置操作，以下關于時間復雜度的描述，哪一個是準確的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)17、對于一個用鏈表實現(xiàn)的棧，若要在棧頂插入一個元素，時間復雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)18、以下哪種排序算法在元素數(shù)量較少時性能較好？A.歸并排序B.快速排序C.插入排序D.堆排序19、在字符串處理中，后綴數(shù)組是一種有效的數(shù)據(jù)結構，以下關于后綴數(shù)組的描述，錯誤的是（）A.可以用于字符串的匹配和查找B.構建后綴數(shù)組的時間復雜度較高C.空間復雜度相對較低D.不適合處理大規(guī)模字符串20、在一個具有n個節(jié)點的有向圖中，若存在多個入度為0的節(jié)點，進行拓撲排序時，應該選擇哪個節(jié)點作為起始節(jié)點？A.任意一個入度為0的節(jié)點B.編號最小的入度為0的節(jié)點C.編號最大的入度為0的節(jié)點D.以上都不對二、簡答題（本大題共4個小題，共40分)1、（本題10分）深入探討在一個具有n個元素的循環(huán)隊列中，如何有效地判斷隊列是否已滿。2、（本題10分）什么是二叉搜索樹的旋轉操作？在什么情況下需要進行旋轉操作？請詳細說明。3、（本題10分）論述哈夫曼樹的構建過程及其在數(shù)據(jù)壓縮中的應用原理，說明為什么哈夫曼編碼能夠實現(xiàn)高效壓縮。4、（本題10分）解釋什么是塊狀鏈表及其