北華大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁北華大學(xué)《數(shù)據(jù)結(jié)構(gòu)》

2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對于一個具有n個頂點(diǎn)和e條邊的有向圖，其鄰接矩陣中非零元素的個數(shù)最多為？（）A.eB.2eC.n^2D.n(n-1)2、在一個帶權(quán)有向圖中，若以頂點(diǎn)v為源點(diǎn)，利用迪杰斯特拉算法求從v到其他頂點(diǎn)的最短路徑，在算法執(zhí)行過程中，每個頂點(diǎn)的最短路徑值是如何確定的？（）A.初始時都設(shè)為無窮大，逐步更新B.初始時都設(shè)為0，逐步更新C.隨機(jī)設(shè)定，逐步更新D.根據(jù)頂點(diǎn)的權(quán)值設(shè)定，逐步更新3、一棵完全二叉樹的第5層（根為第1層）有16個葉子節(jié)點(diǎn)，則該完全二叉樹的節(jié)點(diǎn)總數(shù)最少為（）。A.47B.55C.63D.644、對于一個具有n個頂點(diǎn)和e條邊的無向圖，采用鄰接表存儲，若要刪除一條邊，平均需要修改多少個指針？（）A.1B.2C.eD.2e5、在一個循環(huán)鏈表中，若要刪除鏈表中的最后一個節(jié)點(diǎn)，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、在一個具有n個元素的有序單鏈表中，進(jìn)行插入操作時，平均需要移動的元素個數(shù)約為？A.n/2B.nC.lognD.17、在一個具有n個頂點(diǎn)和e條邊的無向圖中，使用鄰接矩陣存儲，進(jìn)行深度優(yōu)先遍歷，其時間復(fù)雜度為？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)8、對于一個具有n個頂點(diǎn)和e條邊的帶權(quán)有向圖，使用弗洛伊德（Floyd）算法求所有頂點(diǎn)對之間的最短路徑。以下關(guān)于該算法的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)模緼.O(n)B.O(n^2)C.O(n^3)D.O(e^3)9、排序算法的穩(wěn)定性是指在排序過程中，如果兩個元素的值相等，它們在排序后的相對位置是否保持不變。以下關(guān)于排序算法穩(wěn)定性的說法中，錯誤的是？（）A.冒泡排序、插入排序和歸并排序是穩(wěn)定的排序算法。B.選擇排序、快速排序和希爾排序是不穩(wěn)定的排序算法。C.穩(wěn)定性對于某些應(yīng)用場景非常重要，例如在對具有多個關(guān)鍵字的記錄進(jìn)行排序時。D.所有的排序算法都可以通過修改代碼來實(shí)現(xiàn)穩(wěn)定性。10、在一棵二叉搜索樹中，刪除一個只有左子樹的節(jié)點(diǎn)，其右子樹的節(jié)點(diǎn)需要（）A.替換被刪除節(jié)點(diǎn)B.保持不動C.全部刪除D.移動到左子樹11、圖的存儲方式和遍歷方式可以用于解決很多實(shí)際問題，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，適用于社交網(wǎng)絡(luò)分析和交通網(wǎng)絡(luò)規(guī)劃等。B.圖的鄰接表可以用于表示稀疏圖，適用于地圖繪制和電路圖設(shè)計(jì)等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問題和最小生成樹問題等，適用于物流配送和通信網(wǎng)絡(luò)優(yōu)化等。D.圖的存儲方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價值。12、在一個具有n個節(jié)點(diǎn)的二叉樹中，若每個節(jié)點(diǎn)都有左右孩子，則葉子節(jié)點(diǎn)的數(shù)量與度為2的節(jié)點(diǎn)數(shù)量有什么關(guān)系？A.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量+1B.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量-1C.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量D.以上都不對13、以下關(guān)于并查集的描述，錯誤的是：A.并查集可以用于判斷兩個元素是否在同一個集合中B.并查集的查找操作時間復(fù)雜度較低C.并查集的合并操作時間復(fù)雜度較高D.并查集通常采用樹形結(jié)構(gòu)存儲14、在一個B樹中，每個節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-115、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時需要進(jìn)行幾次比較？（）A.1B.2C.3D.416、設(shè)有一個20階的下三角矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯ζ浞橇阍?，第一個非零元素A[1,1]存儲在數(shù)組B[0]中，若A[10,5]在數(shù)組B中的存儲位置為k，則A[8,5]在數(shù)組B中的存儲位置為（）。A.k-18B.k-17C.k-16D.k-1517、對于一個采用順序存儲的棧，若棧頂指針top等于-1時，表示：A.棧滿B.?？誄.棧中只有一個元素D.棧中至少有一個元素18、哈希表的性能取決于哈希函數(shù)的設(shè)計(jì)和沖突解決方法的選擇，以下關(guān)于它們的說法中，錯誤的是？（）A.好的哈希函數(shù)應(yīng)該具有均勻分布性、隨機(jī)性和高效性等特點(diǎn)。B.沖突解決方法的選擇應(yīng)該根據(jù)哈希表的大小、數(shù)據(jù)的特點(diǎn)和操作的頻率等因素來決定。C.哈希表的性能可以通過調(diào)整哈希函數(shù)和沖突解決方法來優(yōu)化。D.哈希表的性能只取決于哈希函數(shù)的設(shè)計(jì)，與沖突解決方法無關(guān)。19、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA20、在一個m行n列的二維數(shù)組中，元素存儲的地址計(jì)算公式為LOC(aij)=LOC(a11)+[(i-1)*n+(j-1)]*d，其中d為每個元素所占的存儲單元數(shù)。若按行優(yōu)先存儲，則a23的地址為？（）A.LOC(a11)+5dB.LOC(a11)+6dC.LOC(a11)+7dD.LOC(a11)+8d二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述在深度優(yōu)先搜索和廣度優(yōu)先搜索的應(yīng)用中，如何解決迷宮問題或?qū)ふ覉D中的所有路徑。2、（本題10分）詳細(xì)論述在一個具有n個頂點(diǎn)的有向圖中，如何進(jìn)行圖的縮點(diǎn)操作。3、（本題10分）詳細(xì)說明堆的性質(zhì)（大根堆、小根堆），以及如何進(jìn)行堆的構(gòu)建、插入和刪除操作。4、（本題10分）詳細(xì)說明如何在一個圖中判斷兩個