湖南城市學(xué)院《數(shù)據(jù)結(jié)構(gòu)A》2021-2022學(xué)年期末試卷

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

《數(shù)據(jù)結(jié)構(gòu)A》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)具有n個(gè)元素的單鏈表中，若要在第i個(gè)位置（1<=i<=n）插入一個(gè)新元素，平均需要遍歷多少個(gè)節(jié)點(diǎn)？（）A.i-1B.iC.(i-1)/2D.i/22、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的平衡二叉樹，插入一個(gè)新節(jié)點(diǎn)并調(diào)整平衡，其平均時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、在一個(gè)具有n個(gè)頂點(diǎn)的有向無環(huán)圖中，使用拓?fù)渑判蛩惴?，其結(jié)果的唯一性如何？A.一定唯一B.可能不唯一C.取決于頂點(diǎn)的編號D.以上都不對4、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組5、對于一個(gè)用數(shù)組實(shí)現(xiàn)的最小堆，若要?jiǎng)h除堆頂元素并調(diào)整堆，以下操作正確的是？（）A.將堆尾元素移到堆頂，然后從堆頂向下調(diào)整B.將堆頂元素與堆尾元素交換，然后從堆頂向下調(diào)整C.將堆頂元素刪除，然后重新構(gòu)建堆D.以上都不對6、在一個(gè)m行n列的二維數(shù)組中，按列優(yōu)先存儲時(shí)，元素aij的存儲地址為？（）A.LOC(a11)+[(j-1)*m+(i-1)]*dB.LOC(a11)+[(i-1)*m+(j-1)]*dC.LOC(a11)+[(j-1)*n+(i-1)]*dD.LOC(a11)+[(i-1)*n+(j-1)]*d7、棧和隊(duì)列的應(yīng)用場景非常廣泛，以下關(guān)于它們的應(yīng)用的說法中，錯(cuò)誤的是？（）A.?？梢杂糜趯?shí)現(xiàn)函數(shù)調(diào)用、表達(dá)式求值和括號匹配等。B.隊(duì)列可以用于實(shí)現(xiàn)任務(wù)調(diào)度、消息隊(duì)列和廣度優(yōu)先搜索等。C.棧和隊(duì)列可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊(duì)列只適用于計(jì)算機(jī)科學(xué)領(lǐng)域，在其他領(lǐng)域沒有實(shí)際價(jià)值。8、對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若采用鄰接矩陣存儲，則存儲空間的復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)9、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的紅黑樹，插入一個(gè)新節(jié)點(diǎn)后，調(diào)整樹的結(jié)構(gòu)以保持紅黑樹性質(zhì)，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一個(gè)字符串中，要查找某個(gè)子串首次出現(xiàn)的位置，通?？梢允褂媚姆N算法？（）A.冒泡排序B.快速排序C.順序查找D.二分查找11、對于一個(gè)具有n個(gè)元素的有序鏈表，若要在其中查找一個(gè)特定元素，其平均時(shí)間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)12、對于一個(gè)循環(huán)隊(duì)列，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAX_SIZE，那么判斷隊(duì)空的條件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-113、在圖的最小生成樹算法中，Kruskal算法和Prim算法都能得到最小生成樹，以下關(guān)于這兩個(gè)算法的比較，錯(cuò)誤的是（）A.Kruskal算法基于邊，Prim算法基于節(jié)點(diǎn)B.Kruskal算法需要使用并查集C.Prim算法的時(shí)間復(fù)雜度通常比Kruskal算法低D.對于稀疏圖，Kruskal算法更優(yōu)14、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖中，使用鄰接矩陣存儲，進(jìn)行深度優(yōu)先遍歷，其時(shí)間復(fù)雜度為？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)15、在一棵度為4的樹中，度為4的節(jié)點(diǎn)個(gè)數(shù)為1，度為3的節(jié)點(diǎn)個(gè)數(shù)為2，度為2的節(jié)點(diǎn)個(gè)數(shù)為3，度為1的節(jié)點(diǎn)個(gè)數(shù)為4，葉子節(jié)點(diǎn)個(gè)數(shù)為（）。A.15B.16C.17D.1816、以下哪種數(shù)據(jù)結(jié)構(gòu)適合用于實(shí)現(xiàn)一個(gè)可以快速查找最大值和最小值的數(shù)據(jù)集合？A.鏈表B.棧C.隊(duì)列D.堆17、對于一個(gè)具有n個(gè)元素的大頂堆，若要獲取堆中的第k大元素（1<=k<=n），以下哪種方法效率較高？A.先排序再獲取B.每次刪除堆頂元素k-1次C.構(gòu)建一個(gè)大小為k的小頂堆，然后逐步替換D.以上方法效率相同18、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接表存儲時(shí)，其空間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)19、在一個(gè)具有n個(gè)元素的雙向鏈表中，若要?jiǎng)h除尾結(jié)點(diǎn)，需要修改幾個(gè)指針？（）A.1B.2C.3D.420、已知一個(gè)具有n個(gè)頂點(diǎn)的無向圖采用鄰接矩陣存儲，若要?jiǎng)h除所有的邊，時(shí)間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(nlogn)D.O(e)二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）鏈表的插入和刪除操作與數(shù)組相比有哪些優(yōu)勢？請舉例說明。2、（本題10分）解釋在平衡二叉搜索樹中，如何通過平衡調(diào)整操作減少節(jié)點(diǎn)的移動次數(shù)。3、（本題10分）比較快速排序和冒泡排序在最好情況下的性能表現(xiàn)。4、（本題10分）比較計(jì)數(shù)排序和冒泡排序在處理大量重