嶺南師范學院《數(shù)據(jù)結構》2021-2022學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁嶺南師范學院

《數(shù)據(jù)結構》2021-2022學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的雙向鏈表中，刪除一個指定節(jié)點，其時間復雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、哈希表是一種用于快速查找的數(shù)據(jù)結構，通過哈希函數(shù)將關鍵字映射到存儲位置。關于哈希沖突的解決方法，錯誤的是（）A.開放定址法通過尋找空閑位置來解決沖突B.鏈地址法將沖突的元素存儲在鏈表中C.再哈希法通過更換哈希函數(shù)來解決沖突D.哈希沖突無法避免，且對查找效率沒有影響3、圖的最短路徑算法有多種，以下關于它們的說法中，錯誤的是？（）A.迪杰斯特拉算法用于求解單源最短路徑問題，即從一個源點到其他所有頂點的最短路徑。B.弗洛伊德算法用于求解任意兩點之間的最短路徑問題。C.貝爾曼-福特算法也可以用于求解單源最短路徑問題，但它的時間復雜度比迪杰斯特拉算法高。D.圖的最短路徑算法只有迪杰斯特拉算法和弗洛伊德算法兩種。4、在數(shù)據(jù)結構中，斐波那契堆是一種可合并堆，以下關于斐波那契堆的特點，描述不正確的是（）A.插入操作的時間復雜度為O(1)B.查找最小元素的時間復雜度為O(1)C.刪除最小元素的時間復雜度為O(logn)D.合并操作的時間復雜度為O(n)5、對于一個具有n個節(jié)點的二叉樹，若度為0的節(jié)點有n0個，度為1的節(jié)點有n1個，度為2的節(jié)點有n2個，則n0與n1、n2之間的關系為？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+16、對于一個具有n個元素的循環(huán)隊列，隊頭指針為front，隊尾指針為rear，隊列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front7、在一個鏈式存儲的隊列中，若隊頭指針為front，隊尾指針為rear，當進行一次出隊操作后，front指針應該如何移動？A.front=front->nextB.front=rearC.front不變D.front=NULL8、在一個具有n個頂點的無向完全圖中，每個頂點的度為多少？（）A.n-1B.nC.2(n-1)D.2n9、對于一個具有n個頂點的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同10、廣義表((a,b),c,(d,(e,f)))的長度和深度分別為：A.3和2B.3和3C.4和2D.4和311、對于一個具有n個元素的有序鏈表，進行折半查找，其時間復雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進行折半查找12、對于一個具有n個元素的希爾排序，其時間復雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是13、圖的存儲方式有鄰接矩陣和鄰接表兩種，以下關于它們的特點的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，空間復雜度為O(n^2)。B.鄰接表適合存儲稀疏圖，空間復雜度為O(n+m)，其中n是頂點數(shù)，m是邊數(shù)。C.鄰接矩陣的查找邊的時間復雜度為O(1)。D.鄰接表的插入邊和刪除邊的時間復雜度為O(n)。14、在一個有向無環(huán)圖中，進行拓撲排序的結果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對15、對于一個有向無環(huán)圖，進行拓撲排序可以得到一個線性的序列。以下關于拓撲排序的說法，錯誤的是？（）A.可以使用深度優(yōu)先搜索來實現(xiàn)B.結果可能不唯一C.若存在回路則無法進行拓撲排序D.其時間復雜度為O(n2)16、在一個用數(shù)組實現(xiàn)的棧中，若要將棧的容量擴大一倍，以下哪種操作的時間復雜度最低？（）A.重新創(chuàng)建一個更大的數(shù)組并復制元素B.逐步將元素移動到新的更大的數(shù)組中C.直接在原數(shù)組后面追加空間D.以上操作時間復雜度相同17、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n/218、對于一個具有n個頂點和e條邊的無向連通圖，其生成樹中邊的條數(shù)為（）。A.nB.n-1C.eD.e-119、對于一個具有n個元素的有序單鏈表，若要在其中查找一個特定元素，平均需要比較的次數(shù)為？（）A.n/2B.nC.lognD.nlogn20、在一個平衡二叉搜索樹中，插入一個新節(jié)點后，可能需要進行的調整操作次數(shù)最多為（）A.1B.lognC.nD.nlogn二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述哈希表的基本原理，包括哈希函數(shù)的設計和沖突解決方法（如線性探測、鏈地址法等），分析哈希表的性能。2、（本題10分）論述如何使用回溯法解決數(shù)獨問題，給出算法的核心思想和步驟。3、（本題10分）詳細闡述在具有n個頂點的無向圖中，如何使用廣度優(yōu)先搜索算法查找與指定頂點距離為k的所有頂點，并給出具體的算法步驟和代碼實現(xiàn)。4、（本題10分）在一個具有n個元素的雙向鏈表中，說明如何實現(xiàn)