成都錦城學院《數(shù)據(jù)結(jié)構與算法》2021-2022學年期末試卷

自覺遵守考場紀律如考試作弊此答卷無效密自覺遵守考場紀律如考試作弊此答卷無效密封線第1頁，共3頁成都錦城學院《數(shù)據(jù)結(jié)構與算法》

2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的有序數(shù)組中，若要刪除一個特定元素，并且保持數(shù)組的有序性，以下關于刪除操作的平均時間復雜度的描述，哪一項是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、在一個具有n個節(jié)點的帶權有向圖中，使用迪杰斯特拉算法求最短路徑，其時間復雜度是多少？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)3、對于一個具有n個元素的有序鏈表，進行折半查找，其時間復雜度為？A.O(logn)B.O(nlogn)C.O(n)D.不能進行折半查找4、在一個具有n個節(jié)點的二叉樹中，若每個節(jié)點都有左右孩子，則葉子節(jié)點的數(shù)量與度為2的節(jié)點數(shù)量有什么關系？A.葉子節(jié)點數(shù)量=度為2的節(jié)點數(shù)量+1B.葉子節(jié)點數(shù)量=度為2的節(jié)點數(shù)量-1C.葉子節(jié)點數(shù)量=度為2的節(jié)點數(shù)量D.以上都不對5、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA6、在一個有序的單鏈表中，若要刪除一個重復出現(xiàn)的元素，使得鏈表中不再有重復元素，應如何操作？（）A.從頭遍歷，遇到重復元素就刪除B.從尾遍歷，遇到重復元素就刪除C.先排序，再刪除重復元素D.建立一個新鏈表，將不重復元素插入7、對于一個m行n列的二維數(shù)組，按行優(yōu)先存儲時，元素a[i][j]（0<=i<m,0<=j<n）的地址計算公式為：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i8、在一個具有n個元素的有序數(shù)組中，采用插入排序進行排序，在最好情況下，需要比較的次數(shù)為（）。A.n-1B.nC.0D.n(n-1)/29、在一個具有n個節(jié)點的帶權無向圖中，使用普里姆算法構造最小生成樹，其時間復雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結(jié)構10、在一個具有n個節(jié)點的無向圖中，若邊的數(shù)量遠遠小于n(n-1)/2，則適合使用哪種存儲方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以11、對于一個具有n個頂點和e條邊的有向圖，采用鄰接表存儲，進行深度優(yōu)先遍歷。以下關于遍歷的時間復雜度的描述，哪一個是恰當?shù)?？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)12、在一個字符串匹配算法中，BM算法相對于樸素的字符串匹配算法，其優(yōu)勢在于？（）A.平均性能更好B.代碼更簡潔C.空間復雜度更低D.適用于短字符串匹配13、在一個有n個頂點和e條邊的無向圖中，采用鄰接矩陣存儲，其空間復雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)14、在一棵二叉搜索樹中，刪除一個只有左子樹的節(jié)點，其右子樹的節(jié)點需要（）A.替換被刪除節(jié)點B.保持不動C.全部刪除D.移動到左子樹15、在一個具有n個元素的有序單鏈表中，若要查找一個特定元素，以下關于查找操作的時間復雜度的描述，哪一項是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、二叉樹是一種重要的數(shù)據(jù)結(jié)構，若一個二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，那么它的后序遍歷序列是什么？（）A.BCAB.CBAC.CABD.ACB17、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲時，其空間復雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)18、在一個具有n個頂點和e條邊的帶權無向圖中，使用Prim算法生成最小生成樹。若采用鄰接矩陣存儲圖，以下關于算法的空間復雜度的描述，哪一項是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)19、以下關于樹的存儲結(jié)構的描述，哪一項是不正確的？（）A.孩子兄弟表示法可以方便地實現(xiàn)樹的遍歷B.雙親表示法便于查找一個節(jié)點的雙親節(jié)點C.孩子鏈表表示法在處理多叉樹時空間利用率較高D.以上存儲結(jié)構在時間復雜度上沒有明顯差異20、在一個具有n個頂點和m條邊的無向圖中，若采用鄰接表存儲，則存儲空間復雜度主要取決于？A.nB.mC.n+mD.n^2二、簡答題（本大題共4個小題，共40分)1、（本題10分）闡述在一個循環(huán)隊列中，如何判斷隊空和隊滿的條件，并解釋為什么需要這樣判斷，以及可能會出現(xiàn)的誤判情況和解決方法。2、（本題10分）數(shù)組的索引是如何確定的？在不同編程語言中索引的使用有哪些注意事項？3、（本題10分）詳細闡述B+樹的范圍查詢操作的實現(xiàn)過程和優(yōu)勢。4、（本題10分）對于一個用哈希表存儲的數(shù)據(jù)結(jié)構，解釋哈希函數(shù)的作用和選擇原則，以及如何處理哈希沖突，并分析其查找效率