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

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

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