菏澤學(xué)院《數(shù)據(jù)結(jié)構(gòu)算法及應(yīng)用》2022-2023學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁菏澤學(xué)院《數(shù)據(jù)結(jié)構(gòu)算法及應(yīng)用》

2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，其葉子節(jié)點(diǎn)的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-12、在一個(gè)用數(shù)組實(shí)現(xiàn)的最大堆中，若要增加一個(gè)元素并調(diào)整堆，以下操作正確的是？（）A.將元素放在堆尾，然后從堆尾向上調(diào)整B.將元素放在堆頂，然后從堆頂向下調(diào)整C.將元素插入任意位置，然后重新構(gòu)建堆D.以上都不對(duì)3、在一個(gè)具有n個(gè)元素的順序表中，刪除第i個(gè)元素（1<=i<=n），需要移動(dòng)的元素個(gè)數(shù)最多為（）。A.i-1B.n-iC.n-i+1D.n-14、若一棵二叉樹的先序遍歷序列和后序遍歷序列分別為ABC和CBA，則其中序遍歷序列為：A.BCAB.CABC.ABCD.無法確定5、在數(shù)據(jù)結(jié)構(gòu)中，線段樹的區(qū)間更新操作可以通過懶標(biāo)記實(shí)現(xiàn)，以下關(guān)于懶標(biāo)記的描述，不正確的是（）A.減少不必要的節(jié)點(diǎn)更新B.提高更新操作的效率C.可能會(huì)導(dǎo)致查詢結(jié)果不準(zhǔn)確D.標(biāo)記需要在適當(dāng)?shù)臅r(shí)候向下傳遞6、以下關(guān)于快速排序的描述，錯(cuò)誤的是：A.快速排序在平均情況下的時(shí)間復(fù)雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時(shí)間復(fù)雜度為O(n^2)D.快速排序不需要額外的存儲(chǔ)空間7、棧和隊(duì)列在計(jì)算機(jī)科學(xué)中有很多應(yīng)用，以下關(guān)于它們的應(yīng)用場景的說法中，錯(cuò)誤的是？（）A.棧可以用于實(shí)現(xiàn)表達(dá)式求值、括號(hào)匹配等。B.隊(duì)列可以用于實(shí)現(xiàn)任務(wù)調(diào)度、消息隊(duì)列等。C.棧和隊(duì)列可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊(duì)列只能在編程語言的底層實(shí)現(xiàn)中使用，不能在實(shí)際應(yīng)用中直接使用。8、在一個(gè)具有n個(gè)元素的鏈表中，要?jiǎng)h除所有值為x的節(jié)點(diǎn)，最好的方法是？A.逐個(gè)刪除B.先查找再刪除C.建立新鏈表D.以上方法效率相同9、對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，若要查找某個(gè)元素是否存在，以下哪種查找算法效率最高？（）A.順序查找B.二分查找C.分塊查找D.以上算法效率相同10、對(duì)于一個(gè)具有n個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列，隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置，隊(duì)頭指針front指向隊(duì)頭元素，若隊(duì)列非空，則隊(duì)列中元素的個(gè)數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+111、對(duì)于一個(gè)采用鏈表存儲(chǔ)的隊(duì)列，若要實(shí)現(xiàn)隊(duì)列的逆置操作，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)12、在二叉搜索樹中，每個(gè)節(jié)點(diǎn)的值都大于其左子樹中所有節(jié)點(diǎn)的值，小于其右子樹中所有節(jié)點(diǎn)的值。以下關(guān)于二叉搜索樹的操作，不正確的是（）A.插入操作需要按照節(jié)點(diǎn)值的大小找到合適的位置B.查找操作的時(shí)間復(fù)雜度在最壞情況下為O(n)C.刪除節(jié)點(diǎn)時(shí)，如果該節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)，可以選擇其左子樹中的最大節(jié)點(diǎn)或右子樹中的最小節(jié)點(diǎn)進(jìn)行替換D.二叉搜索樹總是平衡的，即左右子樹的高度差不超過113、在一個(gè)哈希表中，解決沖突的方法不包括：A.開放定址法B.再哈希法C.建立索引表D.鏈地址法14、堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，分為大頂堆和小頂堆。對(duì)于大頂堆，以下描述不正確的是（）A.根節(jié)點(diǎn)的值大于其左右子節(jié)點(diǎn)的值B.可以用于實(shí)現(xiàn)優(yōu)先隊(duì)列C.構(gòu)建大頂堆的時(shí)間復(fù)雜度為O(nlogn)D.每次刪除堆頂元素后，需要重新調(diào)整堆以保持大頂堆的性質(zhì)15、對(duì)于一個(gè)具有n個(gè)元素的選擇排序，在最壞情況下，需要進(jìn)行多少次交換操作？（）A.n-1B.nC.n(n-1)/2D.016、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向連通圖，利用Prim算法構(gòu)造最小生成樹時(shí)，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)17、對(duì)于一個(gè)具有n個(gè)元素的雙向鏈表，若要在第i個(gè)位置（1<=i<=n）之前插入一個(gè)新節(jié)點(diǎn)，平均需要修改多少個(gè)指針？（）A.1B.2C.3D.418、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表，若要在其中查找一個(gè)特定元素，平均需要比較的次數(shù)為？（）A.n/2B.nC.lognD.nlogn19、在一個(gè)有序的單鏈表中，若要?jiǎng)h除一個(gè)重復(fù)出現(xiàn)的元素，使得鏈表中不再有重復(fù)元素，應(yīng)如何操作？（）A.從頭遍歷，遇到重復(fù)元素就刪除B.從尾遍歷，遇到重復(fù)元素就刪除C.先排序，再刪除重復(fù)元素D.建立一個(gè)新鏈表，將不重復(fù)元素插入20、以下關(guān)于串的描述，錯(cuò)誤的是：A.串是一種特殊的線性表B.串的長度是指串中字符的個(gè)數(shù)C.空串和空格串是相同的概念D.串的存儲(chǔ)方式有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）在一個(gè)二叉搜索樹中，如何查找值在給定范圍內(nèi)的所有元素？2、（本題10分）解釋插入排序算法在基本有序和完全無序情況下的性能差異，說明其適用場景和優(yōu)化方法。3、（本題10分）論述如何使用動(dòng)態(tài)規(guī)劃算法解決最長公共子串問題。4、（本題10分）論述哈夫曼樹的構(gòu)建過程及其在數(shù)據(jù)壓縮中的應(yīng)用原理，說明為什么哈夫曼編碼能夠?qū)崿F(xiàn)高效壓縮。三、設(shè)計(jì)題（本大題共2個(gè)小題，共20分)1、（本題