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

裝訂線裝訂線PAGE2第1頁，共3頁北方民族大學(xué)《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，若一個二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，那么它的后序遍歷序列是什么？（）A.BCAB.CBAC.CABD.ACB2、在一個具有n個節(jié)點的完全二叉樹中，其葉子節(jié)點的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-13、在一個具有n個元素的雙向鏈表中，若要刪除尾結(jié)點，需要修改幾個指針？（）A.1B.2C.3D.44、在一個具有n個節(jié)點的圖中，使用弗洛伊德算法求所有節(jié)點對之間的最短路徑，其時間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)5、在一個哈希表中，負(fù)載因子越大，說明什么？A.哈希沖突越少B.存儲空間利用率越高C.查找效率越高D.以上都不對6、對于一個具有n個頂點的無向完全圖，其邊的數(shù)量為多少？（）A.n(n-1)/2B.n(n-1)C.n2D.2n7、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無數(shù)種8、在一棵二叉搜索樹中，刪除一個只有左子樹的節(jié)點，其右子樹的節(jié)點需要（）A.替換被刪除節(jié)點B.保持不動C.全部刪除D.移動到左子樹9、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)，通過哈希函數(shù)將關(guān)鍵字映射到存儲位置。關(guān)于哈希沖突的解決方法，錯誤的是（）A.開放定址法通過尋找空閑位置來解決沖突B.鏈地址法將沖突的元素存儲在鏈表中C.再哈希法通過更換哈希函數(shù)來解決沖突D.哈希沖突無法避免，且對查找效率沒有影響10、棧和隊列的應(yīng)用場景非常廣泛，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.棧可以用于實現(xiàn)函數(shù)調(diào)用、表達(dá)式求值和括號匹配等。B.隊列可以用于實現(xiàn)任務(wù)調(diào)度、消息隊列和廣度優(yōu)先搜索等。C.棧和隊列可以用于實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊列只適用于計算機(jī)科學(xué)領(lǐng)域，在其他領(lǐng)域沒有實際價值。11、對于一個具有n個節(jié)點的二叉樹，若每個節(jié)點都有左子樹和右子樹，則其葉子節(jié)點的個數(shù)至少為？A.n/2B.(n+1)/2C.n-1D.logn12、對于一個具有n個元素的希爾排序，其時間復(fù)雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是13、在一個具有n個節(jié)點的二叉樹中，若每個節(jié)點的值都不相同，并且中序遍歷和后序遍歷的結(jié)果分別為[4,2,5,1,3]和[4,5,2,3,1]，則先序遍歷的結(jié)果為（）A.[1,2,4,3,5]B.[1,2,3,4,5]C.[1,2,4,5,3]D.[1,3,2,5,4]14、棧是一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它遵循后進(jìn)先出（LIFO）的原則。以下關(guān)于棧的說法中，錯誤的是？（）A.?？梢杂脭?shù)組或鏈表實現(xiàn)。B.棧的插入和刪除操作只能在棧頂進(jìn)行。C.?？梢杂糜趯崿F(xiàn)函數(shù)調(diào)用、表達(dá)式求值等。D.棧的容量是無限的，可以存儲任意數(shù)量的元素。15、在數(shù)據(jù)結(jié)構(gòu)中，字典樹（Trie樹）常用于字符串的存儲和查找，以下關(guān)于字典樹的特點，不正確的是（）A.對于前綴相同的字符串可以節(jié)省存儲空間B.查找操作的時間復(fù)雜度與字符串長度有關(guān)C.適合用于詞頻統(tǒng)計D.插入和刪除操作比較復(fù)雜16、對于一個循環(huán)隊列，若隊列的最大容量為m，當(dāng)前front指針為5，rear指針為2，則隊列中的元素個數(shù)為（）A.7B.3C.m-3D.m-717、在一個用十字鏈表存儲的有向圖中，查找一個頂點的所有出邊和入邊的時間復(fù)雜度是？（）A.O(1)B.O(n)C.O(e)D.O(n+e)18、以下關(guān)于圖的遍歷算法的描述，哪一項是正確的？（）A.深度優(yōu)先遍歷和廣度優(yōu)先遍歷都能訪問到圖中的所有節(jié)點B.深度優(yōu)先遍歷適合用于求解最短路徑問題C.廣度優(yōu)先遍歷的空間復(fù)雜度低于深度優(yōu)先遍歷D.兩種遍歷算法的時間復(fù)雜度都與圖的邊數(shù)成正比19、在一個用鄰接矩陣表示的無向圖中，矩陣中的元素表示什么？A.頂點之間的距離B.頂點之間是否有邊C.邊的權(quán)重D.以上都有可能20、若一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBDAEGF，則其后序遍歷序列為？（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEAGF二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述如何使用分治法解決最大子數(shù)組和問題。2、（本題10分）分析在字符串匹配中，如何結(jié)合多種算法提高匹配效率。3、（本題10分）闡述隊列在操作系統(tǒng)中的應(yīng)用，如進(jìn)程調(diào)度、消息隊列等，并解釋其作用。4、（本題10分）詳細(xì)闡述在圖的遍歷中，如何處理圖的連通性判斷和連通分量