湖北工程學(xué)院《數(shù)據(jù)結(jié)構(gòu)》2022-2023學(xué)年期末試卷

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

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