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

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

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