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

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績(jī)按零分記?！堋狻€…………第1頁(yè)，共1頁(yè)吉林師范大學(xué)

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