南京工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁南京工程學(xué)院

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一棵AVL樹中，進行插入操作后，可能導(dǎo)致樹失去平衡，此時需要進行的旋轉(zhuǎn)操作最多為（）A.1次B.2次C.logn次D.n次2、線段樹是一種用于處理區(qū)間查詢和更新的數(shù)據(jù)結(jié)構(gòu)。對于線段樹的應(yīng)用，以下說法錯誤的是（）A.可以快速計算給定區(qū)間內(nèi)元素的和B.可以用于查找區(qū)間內(nèi)的最大值和最小值C.構(gòu)建線段樹的時間復(fù)雜度為O(n)D.線段樹的空間復(fù)雜度與節(jié)點數(shù)量成正比3、在一個具有n個元素的順序表中，若要在第i個位置（1<=i<=n+1）插入一個新元素，需要移動的元素個數(shù)最少為（）。A.0B.i-1C.n-iD.n-i+14、設(shè)有一個20階的下三角矩陣A，采用壓縮存儲方式，以行序為主存儲其非零元素，第一個非零元素A[1,1]存儲在數(shù)組B[0]中，若A[10,5]在數(shù)組B中的存儲位置為k，則A[8,5]在數(shù)組B中的存儲位置為（）。A.k-18B.k-17C.k-16D.k-155、AVL樹是一種高度平衡的二叉搜索樹，以下關(guān)于AVL樹的旋轉(zhuǎn)操作，描述不正確的是（）A.旋轉(zhuǎn)操作用于保持樹的平衡B.包括單旋轉(zhuǎn)和雙旋轉(zhuǎn)兩種類型C.旋轉(zhuǎn)操作不會改變二叉搜索樹的性質(zhì)D.每次插入或刪除節(jié)點都需要進行旋轉(zhuǎn)操作6、在一個具有n個元素的順序存儲的循環(huán)隊列中，隊滿的條件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front7、以下關(guān)于圖的最短路徑算法的描述，哪一項是正確的？（）A.Dijkstra算法不能處理負權(quán)邊B.Floyd算法的時間復(fù)雜度低于Dijkstra算法C.所有最短路徑算法都能在有向圖和無向圖中使用D.最短路徑一定是唯一的8、以下關(guān)于哈希沖突解決方法中二次探測法的描述，哪一項是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)9、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)，通過哈希函數(shù)將關(guān)鍵字映射到存儲位置。關(guān)于哈希沖突的解決方法，錯誤的是（）A.開放定址法通過尋找空閑位置來解決沖突B.鏈地址法將沖突的元素存儲在鏈表中C.再哈希法通過更換哈希函數(shù)來解決沖突D.哈希沖突無法避免，且對查找效率沒有影響10、對于一個具有n個元素的哈希表，負載因子（loadfactor）為0.7，當(dāng)表中元素數(shù)量超過一定閾值時需要進行擴容。以下關(guān)于擴容操作的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.O(1)B.O(n)C.O(logn)D.O(nlogn)11、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)LRU（最近最少使用）緩存淘汰策略？（）A.隊列B.棧C.哈希表D.雙向鏈表12、設(shè)有一個循環(huán)隊列，存儲空間為Q[0..m-1]，初始時front=rear=m。現(xiàn)經(jīng)過一系列入隊與退隊操作后，front=20，rear=15，則此時隊列中的元素個數(shù)為（）。A.5B.6C.m-5D.m+513、在一個循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，隊列最大容量為MAXSIZE，若當(dāng)前隊列長度為n，則判斷隊滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE14、以下關(guān)于樹的存儲結(jié)構(gòu)的描述，哪一項是不正確的？（）A.孩子兄弟表示法可以方便地實現(xiàn)樹的遍歷B.雙親表示法便于查找一個節(jié)點的雙親節(jié)點C.孩子鏈表表示法在處理多叉樹時空間利用率較高D.以上存儲結(jié)構(gòu)在時間復(fù)雜度上沒有明顯差異15、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持區(qū)間查詢操作？（）A.線段樹B.二叉搜索樹C.堆D.鏈表16、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲時，其空間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)17、對于一個具有n個頂點和e條邊的有向完全圖，其弧的條數(shù)為（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/218、在數(shù)據(jù)結(jié)構(gòu)中，雙向循環(huán)鏈表相較于單向鏈表，以下優(yōu)勢描述錯誤的是（）A.可以方便地反向遍歷B.插入和刪除節(jié)點的操作更簡單C.查找前一個節(jié)點的時間復(fù)雜度更低D.空間復(fù)雜度更低19、在一個具有n個頂點的有向圖中，若存在環(huán)，則使用拓撲排序算法會？A.正常排序B.無法排序C.部分排序D.排序結(jié)果不確定20、在一個有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比較的次數(shù)是：A.1B.2C.3D.4二、簡答題（本大題共4個小題，共40分)1、（本題10分）深入分析在一個具有n個元素的順序表中，如何進行桶排序。2、（本題10分）解釋什么是字典樹，并說明其在單詞查找和統(tǒng)計中的應(yīng)用。3、（本題10分）闡述如何在一個具有n個元素的無序數(shù)組中，使用冒泡排序算法進行排序，并分析其時間復(fù)雜度和空間復(fù)雜度。4、（本題10分）解釋什么是后綴數(shù)組數(shù)據(jù)結(jié)構(gòu)，說明其構(gòu)建過程和應(yīng)用場景，并闡述如何進行