學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁湖北工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)》

2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、若要對一個具有n個元素的數(shù)組進(jìn)行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)2、在一個具有n個頂點(diǎn)的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n3、在一個長度為n的有序數(shù)組中進(jìn)行二分查找，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)4、在一個具有n個元素的小根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進(jìn)行調(diào)整，其時間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)5、在一棵紅黑樹中，插入一個新節(jié)點(diǎn)后，調(diào)整樹的結(jié)構(gòu)以保持紅黑性質(zhì)的操作次數(shù)最多為（）A.1B.2C.lognD.n6、在一個具有n個元素的有序數(shù)組中，若要刪除一個特定元素，并且保持?jǐn)?shù)組的有序性，以下關(guān)于刪除操作的平均時間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、對于一個具有n個節(jié)點(diǎn)的二叉樹，若度為0的節(jié)點(diǎn)有n0個，度為1的節(jié)點(diǎn)有n1個，度為2的節(jié)點(diǎn)有n2個，則n0與n1、n2之間的關(guān)系為？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+18、在圖的最短路徑算法中，Dijkstra算法適用于帶權(quán)有向圖，以下關(guān)于Dijkstra算法的描述，錯誤的是（）A.以起始節(jié)點(diǎn)為中心向外層層擴(kuò)展B.每次選擇距離起始節(jié)點(diǎn)最近的未訪問節(jié)點(diǎn)C.可以處理負(fù)權(quán)邊D.時間復(fù)雜度為O(n^2)9、在數(shù)據(jù)結(jié)構(gòu)的應(yīng)用中，優(yōu)先隊列常用于實(shí)現(xiàn)任務(wù)調(diào)度，以下關(guān)于優(yōu)先隊列的描述，錯誤的是（）A.可以使用堆來實(shí)現(xiàn)B.元素的出隊順序按照優(yōu)先級確定C.插入元素的時間復(fù)雜度為O(logn)D.不支持修改元素的優(yōu)先級10、在一個具有n個元素的鏈表中，要刪除所有值為x的節(jié)點(diǎn)，最好的方法是？A.逐個刪除B.先查找再刪除C.建立新鏈表D.以上方法效率相同11、在一個具有n個元素的雙向鏈表中，若要刪除尾結(jié)點(diǎn)，需要修改幾個指針？（）A.1B.2C.3D.412、以下哪種排序算法是穩(wěn)定的排序算法？A.快速排序B.選擇排序C.冒泡排序D.希爾排序13、對于一個采用鏈表存儲的棧，若要獲取棧的大?。ㄔ財?shù)量），以下關(guān)于操作的時間復(fù)雜度的描述，哪一個是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、在一個具有n個頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度之和為m，入度之和為k，則m和k之間的關(guān)系是？（）A.m=kB.m>kC.m<kD.m+k=n15、在數(shù)據(jù)結(jié)構(gòu)中，對于線性表的順序存儲和鏈?zhǔn)酱鎯Γ韵抡f法正確的是：順序存儲結(jié)構(gòu)可以隨機(jī)訪問元素，但插入和刪除操作效率較低；鏈?zhǔn)酱鎯Y(jié)構(gòu)插入和刪除操作方便，但不能隨機(jī)訪問。那么在頻繁進(jìn)行插入和刪除操作的情況下，應(yīng)優(yōu)先選擇哪種存儲結(jié)構(gòu)？（）A.順序存儲B.鏈?zhǔn)酱鎯.兩者均可D.無法確定16、在一個具有n個節(jié)點(diǎn)的無向圖中，若邊的數(shù)量遠(yuǎn)遠(yuǎn)小于n(n-1)/2，則適合使用哪種存儲方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以17、在一個長度為n的有序線性表中進(jìn)行二分查找，在最壞情況下，需要比較的次數(shù)為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)18、以下關(guān)于哈夫曼樹的描述，正確的是：A.哈夫曼樹一定是完全二叉樹B.哈夫曼樹中不存在度為1的節(jié)點(diǎn)C.哈夫曼樹的帶權(quán)路徑長度是唯一的D.哈夫曼樹的構(gòu)建過程不需要進(jìn)行節(jié)點(diǎn)的比較和交換19、在一個具有n個節(jié)點(diǎn)的帶權(quán)有向圖中，若存在負(fù)權(quán)邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用20、對于一個采用鏈?zhǔn)酱鎯Φ年犃校絷狀^指針和隊尾指針相同，則隊列的狀態(tài)為：A.隊空B.隊滿C.不確定D.隊列中只有一個元素二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋插入排序算法在基本有序和完全無序情況下的性能差異，說明其適用場景和優(yōu)化方法。2、（本題10分）詳細(xì)闡述在一個具有n個元素的堆中，如何查找最大的k個元素。3、（本題10分）闡述隊列在操作系統(tǒng)中的應(yīng)用，如進(jìn)程調(diào)度、消息隊列等，并解釋其作用。4、（本題10分）解釋線段樹在進(jìn)行區(qū)間更新時，如何通過lazy標(biāo)記提高效率。三、設(shè)計