鄭州航空工業(yè)管理學(xué)院《數(shù)據(jù)管理原理與技術(shù)》2021-2022學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁鄭州航空工業(yè)管理學(xué)院《數(shù)據(jù)管理原理與技術(shù)》

2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、若要對一個具有n個元素的數(shù)組進行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、在數(shù)據(jù)結(jié)構(gòu)中，使用隊列來實現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點開始入隊B.隊列為空時結(jié)束遍歷C.訪問節(jié)點時將其未訪問的鄰接節(jié)點入隊D.節(jié)點不會被重復(fù)訪問3、以下哪種排序算法是穩(wěn)定的排序算法？A.快速排序B.選擇排序C.冒泡排序D.希爾排序4、若對線性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲結(jié)構(gòu)，則插入和刪除操作的時間復(fù)雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)5、在一個循環(huán)隊列中，front指向隊頭元素的前一個位置，rear指向隊尾元素的位置，隊列最大容量為MAXSIZE，若當前隊列長度為n，則判斷隊滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE6、在一個用鏈表實現(xiàn)的隊列中，若要刪除隊頭元素并返回其值，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、對于一個具有n個元素的有序數(shù)組，若要查找某個元素是否存在，以下哪種查找算法效率最高？（）A.順序查找B.二分查找C.分塊查找D.以上算法效率相同8、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)表達式樹？A.二叉樹B.鏈表C.棧D.隊列9、已知一個圖的鄰接矩陣如下所示，則從頂點V1出發(fā)進行深度優(yōu)先遍歷，可能得到的頂點訪問序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V510、以下關(guān)于快速排序的描述，錯誤的是：A.快速排序在平均情況下的時間復(fù)雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時間復(fù)雜度為O(n^2)D.快速排序不需要額外的存儲空間11、在一個有向無環(huán)圖中，進行拓撲排序的結(jié)果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對12、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，使用克魯斯卡爾算法構(gòu)造最小生成樹時，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對13、在字符串處理中，后綴數(shù)組是一種有效的數(shù)據(jù)結(jié)構(gòu)，以下關(guān)于后綴數(shù)組的描述，錯誤的是（）A.可以用于字符串的匹配和查找B.構(gòu)建后綴數(shù)組的時間復(fù)雜度較高C.空間復(fù)雜度相對較低D.不適合處理大規(guī)模字符串14、一棵完全二叉樹的第6層（根為第1層）有8個葉子節(jié)點，則該完全二叉樹的節(jié)點總數(shù)最多為（）。A.39B.56C.111D.11915、在一個循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，若rear>front，則隊列中的元素個數(shù)為？A.rear-frontB.rear-front+MAXSIZEC.rear-front-1D.(rear-front+MAXSIZE)%MAXSIZE16、設(shè)有一個棧S和一個隊列Q，初始時棧為空，隊列為{1,2,3,4,5}。經(jīng)過一系列入棧和出棧、入隊和出隊操作后，棧頂元素為3，此時隊列的頭元素為？（）A.1B.2C.4D.517、對于一個具有n個節(jié)點的紅黑樹，插入一個新節(jié)點后，調(diào)整樹的結(jié)構(gòu)以保持紅黑樹性質(zhì)，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、棧和隊列的應(yīng)用場景非常廣泛，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.棧可以用于實現(xiàn)函數(shù)調(diào)用、表達式求值和括號匹配等。B.隊列可以用于實現(xiàn)任務(wù)調(diào)度、消息隊列和廣度優(yōu)先搜索等。C.棧和隊列可以用于實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊列只適用于計算機科學(xué)領(lǐng)域，在其他領(lǐng)域沒有實際價值。19、以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實現(xiàn)一個可以快速查找最大值和最小值的數(shù)據(jù)集合？A.鏈表B.棧C.隊列D.堆20、對于一個具有n個頂點的無向連通圖，若要判斷其是否存在環(huán)，以下哪種算法的時間復(fù)雜度最低？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓撲排序D.以上算法時間復(fù)雜度相同二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述如何使用分治法解決尋找數(shù)組中的眾數(shù)問題。2、（本題10分）論述在貪心算法的錯誤應(yīng)用案例中，分析導(dǎo)致結(jié)果不理想的原因和改進方法。3、（本題10分）解釋如何在一個具有n個頂點的有向圖中計算每個頂點的可達頂點集合。4、（本題10分）詳細說明冒泡排序算法的優(yōu)化思路和具體實現(xiàn)方法，并舉例說明優(yōu)化后的效果。三、設(shè)計題（本大題共2個小題，