吉林師范大學(xué)《數(shù)據(jù)模型與決策》2021-2022學(xué)年期末試卷

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

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