站名：站名：年級專業：姓名：學號：凡年級專業、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁吉林師范大學

《數據模型與決策》2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、數組通常具有的兩種基本操作是：A.插入和刪除B.查找和修改C.遍歷和排序D.索引和賦值2、對于一個m行n列的二維數組，按行優先存儲時，元素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+i3、在一個具有n個頂點和m條邊的有向圖中，使用弗洛伊德算法求所有頂點對之間的最短路徑，其時間復雜度為？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)4、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則矩陣中非零元素的個數至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/25、一棵哈夫曼樹中，葉子節點的編碼長度一定（）非葉子節點的編碼長度。A.大于B.等于C.小于D.不小于6、廣義表((a,b),c,(d,(e,f)))的長度和深度分別為：A.3和2B.3和3C.4和2D.4和37、深度為5的滿二叉樹的結點數為：A.16B.31C.32D.158、在一個循環隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，隊列最大容量為MAXSIZE，若當前隊列長度為n，則判斷隊滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE9、二叉樹的性質和遍歷方式可以用于解決很多實際問題，以下關于它們的應用的說法中，錯誤的是？（）A.二叉搜索樹可以用于實現高效的查找、插入和刪除操作。B.平衡二叉樹可以用于解決二叉搜索樹的不平衡問題，提高查找效率。C.二叉樹的遍歷方式可以用于實現二叉樹的復制、遍歷和序列化等操作。D.二叉樹的性質和遍歷方式只適用于理論研究，在實際應用中沒有實際價值。10、在圖的遍歷算法中，深度優先搜索（DFS）和廣度優先搜索（BFS）是兩種常見的方法。以下關于它們的描述，錯誤的是（）A.DFS使用棧來保存未訪問的節點B.BFS使用隊列來保存未訪問的節點C.DFS可能會陷入死循環D.BFS一定能找到最短路徑11、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則存儲空間復雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)12、對于一個具有n個元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調整B.直接使用快速排序C.先構建大頂堆再調整D.以上方法效率相同13、在一個具有n個元素的順序表中，若要將其逆置，以下關于操作的時間復雜度的描述，哪一項是恰當的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、以下哪種數據結構可以方便地實現字符串的模式匹配操作？A.二叉樹B.哈希表C.棧D.后綴樹15、數據結構的應用非常廣泛，以下關于它們的應用場景的說法中，錯誤的是？（）A.數組可以用于存儲和處理大量的相同類型的數據。B.鏈表可以用于實現動態數據結構，如棧、隊列和鏈表等。C.樹可以用于實現文件系統、數據庫索引和表達式求值等。D.數據結構只在計算機科學領域有應用，在其他領域沒有實際價值。16、二叉樹是一種重要的數據結構，具有多種遍歷方式。對于先序遍歷、中序遍歷和后序遍歷，以下描述錯誤的是（）A.先序遍歷先訪問根節點，然后遞歸遍歷左子樹和右子樹B.中序遍歷先遞歸遍歷左子樹，然后訪問根節點，最后遞歸遍歷右子樹C.后序遍歷先遞歸遍歷左子樹和右子樹，最后訪問根節點D.這三種遍歷方式的結果總是相同的17、在一個具有n個節點的帶權有向圖中，若存在負權邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用18、對于一個滿二叉樹，若其高度為h，則其節點總數為多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-119、在一個哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法20、在數據結構中，哈弗曼編碼是一種用于數據壓縮的編碼方式，以下關于哈弗曼編碼的描述，錯誤的是（）A.出現頻率高的字符編碼較短B.編碼是唯一的C.解碼過程簡單D.對所有數據都能達到很好的壓縮效果二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述在具有n個頂點的無向圖中，如何使用廣度優先搜索算法查找與指定頂點距離為k的所有頂點，并給出具體的算法步驟和代碼實現。2、（本題10分）簡述哈希表的哈希沖突解決方法中鏈地址法的優化策略及適用場景。3、（本題10分）在數據結構中，闡述如何使用樹堆進行高效的合并和查找操作，給出算法步驟和實現代碼，并分析其性能特點。4、（本題10分）論述在數據結構中，如何使用分治法解決復雜問題，舉