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

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

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