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

站名：站名：年級(jí)專(zhuān)業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專(zhuān)業(yè)、姓名、學(xué)號(hào)錯(cuò)寫(xiě)、漏寫(xiě)或字跡不清者，成績(jī)按零分記?！堋狻€…………第1頁(yè)，共1頁(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è)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接表存儲(chǔ)時(shí)，其空間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)2、在一個(gè)帶頭結(jié)點(diǎn)的雙向鏈表中，若要在p所指結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)q，需要修改幾個(gè)指針？（）A.2B.4C.6D.83、以下關(guān)于線索二叉樹(shù)的描述，錯(cuò)誤的是：A.線索二叉樹(shù)便于在中序遍歷中查找前驅(qū)和后繼節(jié)點(diǎn)B.線索二叉樹(shù)中的線索是指向空指針的指針C.線索二叉樹(shù)的存儲(chǔ)空間利用率比普通二叉樹(shù)高D.線索二叉樹(shù)的構(gòu)建過(guò)程非常簡(jiǎn)單，不需要復(fù)雜的算法4、若一個(gè)隊(duì)列的入隊(duì)序列是1、2、3、4、5，在進(jìn)行出隊(duì)操作時(shí)，第一個(gè)出隊(duì)的元素是：A.1B.2C.3D.45、一棵哈夫曼樹(shù)中，葉子節(jié)點(diǎn)的編碼長(zhǎng)度一定（）非葉子節(jié)點(diǎn)的編碼長(zhǎng)度。A.大于B.等于C.小于D.不小于6、已知一個(gè)圖的鄰接表如下所示，則從頂點(diǎn)V1出發(fā)進(jìn)行廣度優(yōu)先遍歷，可能得到的頂點(diǎn)訪問(wèn)序列是（）。V1:->V2->V3V2:->V4V3:->V4->V5V4:->V5V5:A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V4,V3,V5D.V1,V4,V2,V3,V57、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉排序樹(shù)，刪除一個(gè)節(jié)點(diǎn)后，重新調(diào)整為二叉排序樹(shù)，其時(shí)間復(fù)雜度最壞情況下為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)存儲(chǔ)單元，則a85的地址為？（）A.33B.32C.18D.409、在一個(gè)有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，采用鄰接矩陣存儲(chǔ)，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)10、在一個(gè)具有n個(gè)元素的小頂堆中，若將堆頂元素與最后一個(gè)元素交換，然后對(duì)堆進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)11、若對(duì)一棵二叉排序樹(shù)進(jìn)行中序遍歷，得到的節(jié)點(diǎn)序列是一個(gè)遞增序列，則該二叉排序樹(shù)（）。A.沒(méi)有左子樹(shù)B.沒(méi)有右子樹(shù)C.左子樹(shù)均為空D.右子樹(shù)均為空12、在數(shù)據(jù)結(jié)構(gòu)中，棧是一種特殊的線性表，遵循先進(jìn)后出的原則。以下關(guān)于棧的操作，錯(cuò)誤的是（）A.入棧操作將元素添加到棧頂B.出棧操作取出并刪除棧頂元素C.可以在棧的任意位置進(jìn)行插入和刪除操作D.棧頂指針始終指向棧頂元素13、以下哪種排序算法在數(shù)據(jù)基本有序時(shí)的時(shí)間復(fù)雜度接近O(n)？A.冒泡排序B.快速排序C.插入排序D.選擇排序14、對(duì)于一個(gè)具有n個(gè)元素的無(wú)序數(shù)組，若要找出第k小的元素，以下哪種算法較為合適？（）A.冒泡排序B.快速排序C.選擇排序D.堆排序15、對(duì)于一個(gè)具有n個(gè)元素的冒泡排序，在最壞情況下，需要進(jìn)行多少次比較操作？（）A.n(n-1)/2B.nC.n+1D.n-116、在一個(gè)用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧中，若棧頂指針top指向棧頂元素的上一個(gè)位置，當(dāng)棧為空時(shí)，top的值為？A.-1B.0C.1D.n-1（其中n為棧的最大容量）17、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表主要用于存儲(chǔ)有向圖，以下關(guān)于十字鏈表的特點(diǎn)，描述不正確的是（）A.既能方便地訪問(wèn)出邊，也能方便地訪問(wèn)入邊B.存儲(chǔ)空間比鄰接表節(jié)省C.對(duì)于刪除邊的操作比較復(fù)雜D.不適合用于稀疏有向圖18、對(duì)于一個(gè)具有n個(gè)元素的堆，若要將其所有元素從小到大排序，最好的方法是？A.每次刪除堆頂元素并調(diào)整B.直接使用快速排序C.先構(gòu)建大頂堆再調(diào)整D.以上方法效率相同19、若一棵二叉樹(shù)的先序遍歷序列和后序遍歷序列分別為ABC和CBA，則其中序遍歷序列為：A.BCAB.CABC.ABCD.無(wú)法確定20、在一個(gè)用數(shù)組實(shí)現(xiàn)的堆中，若要?jiǎng)h除堆底的元素，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述紅黑樹(shù)的插入操作中，顏色調(diào)整的具體步驟和邏輯。2、（本題10分）在圖的遍歷中，如何處理帶負(fù)權(quán)邊的圖？有哪些算法可以解決帶負(fù)權(quán)邊的最短路徑問(wèn)題？3、（本題10分）解釋插入排序算法在基本有序和完全無(wú)序情況下的性能差異，說(shuō)明其適用場(chǎng)景和優(yōu)化方法。4、（本題10分）詳細(xì)說(shuō)明如何在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中計(jì)