站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績(jī)按零分記?！堋狻€…………第1頁(yè)，共1頁(yè)常州工學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的線索二叉樹，若n個(gè)節(jié)點(diǎn)中有m個(gè)空指針域，則線索的數(shù)量為？A.mB.m/2C.n+1D.n-12、以下哪種排序算法在元素基本有序的情況下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序3、在一個(gè)用鄰接表表示的無(wú)向圖中，若要?jiǎng)h除一條邊，需要進(jìn)行的操作是？（）A.在兩個(gè)頂點(diǎn)的鄰接表中刪除對(duì)應(yīng)的邊節(jié)點(diǎn)B.只在一個(gè)頂點(diǎn)的鄰接表中刪除對(duì)應(yīng)的邊節(jié)點(diǎn)C.重新構(gòu)建鄰接表D.以上都不對(duì)4、在一個(gè)具有n個(gè)元素的有序數(shù)組中，使用二分查找查找一個(gè)不存在的元素，最多比較次數(shù)約為？A.lognB.nC.n/2D.nlogn5、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的廣度優(yōu)先遍歷的輔助隊(duì)列？A.循環(huán)隊(duì)列B.鏈隊(duì)列C.優(yōu)先隊(duì)列D.雙端隊(duì)列6、在一個(gè)平衡二叉樹中，插入一個(gè)新節(jié)點(diǎn)后可能會(huì)導(dǎo)致樹的不平衡，此時(shí)需要進(jìn)行調(diào)整。以下哪種調(diào)整操作可能會(huì)被執(zhí)行？（）A.左旋B.右旋C.先左旋后右旋D.以上都有可能7、在數(shù)據(jù)結(jié)構(gòu)中，桶排序是一種外部排序算法，以下關(guān)于桶排序的描述，錯(cuò)誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時(shí)間復(fù)雜度為O(n)C.空間復(fù)雜度較高D.適用于大規(guī)模數(shù)據(jù)排序8、對(duì)于一個(gè)具有n個(gè)元素的棧，若要實(shí)現(xiàn)將棧中元素逆置，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)為？（）A.隊(duì)列B.棧C.鏈表D.數(shù)組9、在一個(gè)具有n個(gè)元素的循環(huán)雙鏈表中，若要在表頭插入一個(gè)新元素，以下關(guān)于插入操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、一棵完全二叉樹的第5層（根為第1層）有16個(gè)葉子節(jié)點(diǎn)，則該完全二叉樹的節(jié)點(diǎn)總數(shù)最少為（）。A.47B.55C.63D.6411、在一個(gè)具有n個(gè)元素的順序表中，刪除第i個(gè)元素（1<=i<=n），平均需要移動(dòng)的元素個(gè)數(shù)約為？A.n/2B.n-iC.iD.n-i+112、以下哪種數(shù)據(jù)結(jié)構(gòu)可以快速判斷一個(gè)元素是否在集合中？A.鏈表B.二叉搜索樹C.哈希表D.棧13、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)其下三角部分，第一個(gè)元素A[1,1]存儲(chǔ)在數(shù)組B[0]中，若A[8,5]在數(shù)組B中的存儲(chǔ)位置為k，則A[7,5]在數(shù)組B中的存儲(chǔ)位置為（）。A.k-13B.k-12C.k-11D.k-1014、在一個(gè)具有n個(gè)元素的數(shù)組中，進(jìn)行順序查找，若查找成功，平均比較次數(shù)約為？A.n/2B.nC.lognD.115、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，采用鄰接表存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)16、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)無(wú)向圖中，使用普里姆算法構(gòu)造最小生成樹，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結(jié)構(gòu)17、以下關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的描述，錯(cuò)誤的是：A.鄰接矩陣適合存儲(chǔ)稠密圖B.鄰接表適合存儲(chǔ)稀疏圖C.十字鏈表是鄰接表和逆鄰接表的結(jié)合D.鄰接多重表只適合無(wú)向圖18、在一個(gè)字符串匹配算法中，BM算法相對(duì)于樸素的字符串匹配算法，其優(yōu)勢(shì)在于？（）A.平均性能更好B.代碼更簡(jiǎn)潔C.空間復(fù)雜度更低D.適用于短字符串匹配19、以下哪種排序算法的空間復(fù)雜度最低？A.歸并排序B.快速排序C.冒泡排序D.插入排序20、在一個(gè)用數(shù)組實(shí)現(xiàn)的堆中，若要?jiǎng)h除堆底的元素，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）闡述哈希表的工作原理，包括哈希函數(shù)的設(shè)計(jì)和處理沖突的方法，并分析其查找效率。2、（本題10分）說(shuō)明二叉樹的遍歷算法在二叉樹的節(jié)點(diǎn)距離問題、樹的路徑問題擴(kuò)展中的應(yīng)用。3、（本題10分）論述跳表在大規(guī)模數(shù)據(jù)存儲(chǔ)中的可擴(kuò)展性和性能評(píng)估。4、（本題10分）深入解釋在具有n個(gè)頂點(diǎn)的有向圖中，如何判斷圖是否強(qiáng)連通，并給出具體的算法思想和實(shí)現(xiàn)步驟