西華師范大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁西華師范大學(xué)《數(shù)據(jù)結(jié)構(gòu)》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(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+12、以下哪種排序算法是穩(wěn)定的排序算法？A.快速排序B.選擇排序C.冒泡排序D.希爾排序3、在一個(gè)m行n列的二維數(shù)組中，元素存儲(chǔ)的地址計(jì)算公式為L(zhǎng)OC(aij)=LOC(a11)+[(i-1)*n+(j-1)]*d，其中d為每個(gè)元素所占的存儲(chǔ)單元數(shù)。若按行優(yōu)先存儲(chǔ)，則a23的地址為？（）A.LOC(a11)+5dB.LOC(a11)+6dC.LOC(a11)+7dD.LOC(a11)+8d4、在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用選擇排序進(jìn)行排序，其空間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)5、在一個(gè)平衡二叉搜索樹中，插入一個(gè)新節(jié)點(diǎn)后，可能需要進(jìn)行的調(diào)整操作次數(shù)最多為（）A.1B.lognC.nD.nlogn6、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，進(jìn)行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹的形狀為？A.只有一個(gè)根節(jié)點(diǎn)B.所有節(jié)點(diǎn)只有左子樹C.所有節(jié)點(diǎn)只有右子樹D.是一棵滿二叉樹7、設(shè)有一個(gè)具有n個(gè)元素的最大堆，若要獲取堆中的最大元素，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE9、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行堆排序。以下關(guān)于堆排序的平均時(shí)間復(fù)雜度和空間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.平均時(shí)間復(fù)雜度為O(nlogn)，空間復(fù)雜度為O(1)B.平均時(shí)間復(fù)雜度為O(n^2)，空間復(fù)雜度為O(n)C.平均時(shí)間復(fù)雜度為O(logn)，空間復(fù)雜度為O(logn)D.平均時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)10、深度為5的滿二叉樹的結(jié)點(diǎn)數(shù)為：A.16B.31C.32D.1511、對(duì)于一個(gè)具有n個(gè)元素的棧，若要實(shí)現(xiàn)將棧中元素逆置，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)為？（）A.隊(duì)列B.棧C.鏈表D.數(shù)組12、在數(shù)據(jù)結(jié)構(gòu)中，桶排序是一種外部排序算法，以下關(guān)于桶排序的描述，錯(cuò)誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時(shí)間復(fù)雜度為O(n)C.空間復(fù)雜度較高D.適用于大規(guī)模數(shù)據(jù)排序13、在一個(gè)具有n個(gè)元素的大頂堆中，若要將堆頂元素與最后一個(gè)元素交換，然后調(diào)整堆，其時(shí)間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若存在頂點(diǎn)的入度為0，則該圖可能是：A.強(qiáng)連通圖B.弱連通圖C.非連通圖D.以上都不對(duì)15、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)。對(duì)于一個(gè)滿二叉樹，若其高度為h，則節(jié)點(diǎn)總數(shù)為多少？A.2^h-1B.2^hC.2^(h-1)D.2^(h+1)-116、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖中，使用鄰接矩陣存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷，其時(shí)間復(fù)雜度為？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)17、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹，若按照層次遍歷的順序?qū)⒐?jié)點(diǎn)編號(hào)為1到n，已知編號(hào)為i的節(jié)點(diǎn)有左孩子，則其左孩子的編號(hào)為？A.2iB.2i+1C.i*2D.i/218、在一個(gè)具有n個(gè)元素的順序表中，刪除第i個(gè)元素（1<=i<=n），平均需要移動(dòng)的元素個(gè)數(shù)約為？A.n/2B.n-iC.iD.n-i+119、在一個(gè)具有n個(gè)元素的有序數(shù)組中進(jìn)行二分查找，其時(shí)間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(logn)D.O(n^2)20、若要在一個(gè)具有n個(gè)元素的有序數(shù)組中插入一個(gè)新元素，同時(shí)保持?jǐn)?shù)組有序，平均需要移動(dòng)多少個(gè)元素？（）A.n/2B.nC.lognD.1二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋什么是拓?fù)渑判?，并說明其在項(xiàng)目管理等領(lǐng)域的應(yīng)用。2、（本題10分）解釋并舉例說明在一個(gè)具有n個(gè)元素的順序表中，如何使用排序算法解決區(qū)間最值問題。3、（本題10分）詳細(xì)說明如何在一個(gè)圖中判斷兩個(gè)頂點(diǎn)是否在同一個(gè)連通分量中。4、（本題10分）鏈表的遍歷和數(shù)組的遍歷有哪些不同之處？各自的優(yōu)缺點(diǎn)是什么？三、設(shè)計(jì)題（本大題共