湖北第二師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)湖北第二師范學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

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