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

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁湖北理工學(xué)院

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