寶雞文理學(xué)院《數(shù)據(jù)結(jié)構(gòu)實驗》2021-2022學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁寶雞文理學(xué)院《數(shù)據(jù)結(jié)構(gòu)實驗》

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個用數(shù)組實現(xiàn)的棧中，若要將棧的容量擴大一倍，以下哪種操作的時間復(fù)雜度最低？（）A.重新創(chuàng)建一個更大的數(shù)組并復(fù)制元素B.逐步將元素移動到新的更大的數(shù)組中C.直接在原數(shù)組后面追加空間D.以上操作時間復(fù)雜度相同2、在一個具有n個元素的有序數(shù)組中，若要刪除一個特定元素，并且保持數(shù)組的有序性，以下關(guān)于刪除操作的平均時間復(fù)雜度的描述，哪一項是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)3、在一個采用順序存儲結(jié)構(gòu)的線性表中，若要在第i個位置插入一個新元素，需要將第i個位置及之后的元素依次向后移動一位。以下關(guān)于插入操作的時間復(fù)雜度的描述，哪一項是正確的？A.時間復(fù)雜度為O(1)B.時間復(fù)雜度為O(n)C.時間復(fù)雜度為O(logn)D.時間復(fù)雜度為O(nlogn)4、以下哪種圖的遍歷算法可以用于判斷一個圖是否為連通圖？A.深度優(yōu)先遍歷B.廣度優(yōu)先遍歷C.兩者均可D.兩者均不可5、若要從一個具有n個元素的有序單鏈表中刪除所有值重復(fù)的元素，使得鏈表中每個元素的值都不同，最優(yōu)的算法時間復(fù)雜度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)6、在一個鏈式存儲的棧中，進行入棧和出棧操作時，以下關(guān)于時間復(fù)雜度的描述，哪一個是準確的？A.入棧和出棧的時間復(fù)雜度均為O(1)B.入棧的時間復(fù)雜度為O(n)，出棧的時間復(fù)雜度為O(1)C.入棧的時間復(fù)雜度為O(1)，出棧的時間復(fù)雜度為O(n)D.入棧和出棧的時間復(fù)雜度均為O(n)7、對于一個具有n個元素的快速排序，每次劃分選取的基準元素不同，對排序的時間復(fù)雜度有何影響？（）A.沒有影響B(tài).可能會提高C.可能會降低D.以上都不對8、在圖的存儲結(jié)構(gòu)中，十字鏈表主要用于存儲有向圖，以下關(guān)于十字鏈表的特點，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲空間比鄰接表節(jié)省C.對于刪除邊的操作比較復(fù)雜D.不適合用于稀疏有向圖9、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），需要移動多少個元素？（）A.n-iB.iC.n-i+1D.n-i-110、在一個長度為n的順序表中，刪除第i個元素（1<=i<=n）時，需要移動的元素個數(shù)為：A.n-iB.i-1C.n-i+1D.i11、在一個用鏈表實現(xiàn)的隊列中，若要實現(xiàn)隊列的遍歷操作，以下哪種方式較為合適？A.從隊頭開始，依次訪問每個節(jié)點B.從隊尾開始，依次向前訪問每個節(jié)點C.隨機訪問鏈表中的節(jié)點D.以上都不對12、對于一個具有n個節(jié)點的完全二叉樹，若底層從左到右填充，則第i個節(jié)點的左孩子節(jié)點的編號為？A.2iB.2i+1C.i*2D.i*2+113、對于一個棧，進行入棧和出棧操作時，以下哪種情況會導(dǎo)致棧溢出？A.入棧元素過多B.出棧元素過多C.連續(xù)進行入棧操作且存儲空間已滿D.連續(xù)進行出棧操作且棧為空14、排序算法的時間復(fù)雜度和空間復(fù)雜度是衡量算法性能的重要指標，以下關(guān)于它們的說法中，錯誤的是？（）A.時間復(fù)雜度是指算法執(zhí)行所需的時間與問題規(guī)模之間的關(guān)系。B.空間復(fù)雜度是指算法執(zhí)行所需的存儲空間與問題規(guī)模之間的關(guān)系。C.不同的排序算法具有不同的時間復(fù)雜度和空間復(fù)雜度，選擇合適的排序算法可以提高算法的性能。D.排序算法的時間復(fù)雜度和空間復(fù)雜度越低越好，不需要考慮其他因素。15、在一個具有n個元素的順序表中，若要將其逆置，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項是恰當?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、在一個具有n個頂點的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n17、對于一個具有n個元素的有序數(shù)組，若采用折半插入排序算法進行排序，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)18、以下哪種排序算法對大規(guī)模數(shù)據(jù)排序時，通常不被優(yōu)先選擇？A.冒泡排序B.插入排序C.快速排序D.歸并排序19、已知一個具有n個頂點的無向圖采用鄰接矩陣存儲，若要刪除所有的邊，時間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(nlogn)D.O(e)20、在一棵平衡二叉樹中，插入一個新節(jié)點后可能導(dǎo)致失衡，需要進行調(diào)整。以下哪種調(diào)整操作可能涉及到旋轉(zhuǎn)次數(shù)最多？（）A.LL型調(diào)整B.RR型調(diào)整C.LR型調(diào)整D.RL型調(diào)整二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述如何使用遞歸算法實現(xiàn)斐波那契數(shù)列的計算，并分析其時間復(fù)雜度和空間復(fù)雜度。2、（本題10分）在一個具有n個頂點的有向圖中，如何找出所有的強連通分量，給出一種有效的算法并分析其時間復(fù)雜度。3、（本題10分）深入探討在有向圖和無向圖中，如何判斷圖是否連通，以及求連通分量的方法。4、（本題10分）詳細解釋在一個具有n個元素的二叉樹中，如何進行前序遍歷的