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

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

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