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

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

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