佳木斯大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁佳木斯大學(xué)

《數(shù)據(jù)結(jié)構(gòu)》2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個頂點(diǎn)和e條邊的帶權(quán)無向圖，使用克魯斯卡爾（Kruskal）算法構(gòu)造最小生成樹，其時間復(fù)雜度主要取決于：A.邊數(shù)eB.頂點(diǎn)數(shù)nC.n和e的和D.n和e的乘積2、對于一個具有n個節(jié)點(diǎn)的無向完全圖，其邊的數(shù)量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/23、在一個鏈?zhǔn)酱鎯Φ木€性表中，若要在第i個位置插入一個新元素，需要修改多少個指針？（）A.1B.2C.iD.i+14、在二叉搜索樹中，每個節(jié)點(diǎn)的值都大于其左子樹中所有節(jié)點(diǎn)的值，小于其右子樹中所有節(jié)點(diǎn)的值。以下關(guān)于二叉搜索樹的操作，不正確的是（）A.插入操作需要按照節(jié)點(diǎn)值的大小找到合適的位置B.查找操作的時間復(fù)雜度在最壞情況下為O(n)C.刪除節(jié)點(diǎn)時，如果該節(jié)點(diǎn)有兩個子節(jié)點(diǎn)，可以選擇其左子樹中的最大節(jié)點(diǎn)或右子樹中的最小節(jié)點(diǎn)進(jìn)行替換D.二叉搜索樹總是平衡的，即左右子樹的高度差不超過15、在一個順序存儲的棧中，若要實現(xiàn)共享棧，即兩個棧共用一個數(shù)組空間，以下關(guān)于棧頂指針的設(shè)置，哪一種方案較為合理？A.兩個棧的棧頂指針分別從數(shù)組的兩端向中間移動B.兩個棧的棧頂指針都從數(shù)組的同一端開始移動C.一個棧的棧頂指針從數(shù)組的開頭移動，另一個從結(jié)尾移動D.以上都可以6、設(shè)有一個具有n個節(jié)點(diǎn)的二叉樹，若每個節(jié)點(diǎn)都有左右子樹，則該二叉樹的葉子節(jié)點(diǎn)數(shù)量與度為2的節(jié)點(diǎn)數(shù)量之間存在特定關(guān)系。以下關(guān)于這種關(guān)系的描述，哪一項是正確的？A.葉子節(jié)點(diǎn)數(shù)量等于度為2的節(jié)點(diǎn)數(shù)量B.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量多1C.葉子節(jié)點(diǎn)數(shù)量比度為2的節(jié)點(diǎn)數(shù)量少1D.兩者之間沒有固定關(guān)系7、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為（）。A.CEABDB.CEDBAC.CABDED.CEDAB8、以下哪種排序算法對大規(guī)模數(shù)據(jù)排序時，通常不被優(yōu)先選擇？A.冒泡排序B.插入排序C.快速排序D.歸并排序9、對于一個具有n個元素的堆，進(jìn)行刪除操作并調(diào)整堆的時間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、以下關(guān)于并查集的描述，錯誤的是：A.并查集可以用于判斷兩個元素是否在同一個集合中B.并查集的查找操作時間復(fù)雜度較低C.并查集的合并操作時間復(fù)雜度較高D.并查集通常采用樹形結(jié)構(gòu)存儲11、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實現(xiàn)字典操作（添加、刪除、查找），且平均時間復(fù)雜度較低？A.數(shù)組B.鏈表C.二叉搜索樹D.哈希表12、對于一個具有n個節(jié)點(diǎn)的二叉樹，若度為0的節(jié)點(diǎn)有n0個，度為1的節(jié)點(diǎn)有n1個，度為2的節(jié)點(diǎn)有n2個，則n0與n1、n2之間的關(guān)系為？A.n0=n1+n2B.n0=n2-1C.n0=n1-1D.n0=n2+113、在一個具有n個元素的棧中，若要將棧中元素依次出棧并打印，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項是準(zhǔn)確的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)14、在一個具有n個元素的順序存儲的線性表中，刪除第i個元素（1<=i<=n），平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n/215、設(shè)有一個具有n個節(jié)點(diǎn)的二叉樹，采用中序遍歷將其轉(zhuǎn)換為一個有序的單鏈表。以下關(guān)于轉(zhuǎn)換過程的時間復(fù)雜度的描述，哪一項是正確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)16、在一個帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹時，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對17、已知一個圖的鄰接表存儲結(jié)構(gòu)，若要判斷任意兩個頂點(diǎn)之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索18、對于一個具有n個元素的快速排序，在最好情況下，其時間復(fù)雜度為？（）A.O(nlogn)B.O(n^2)C.O(n)D.O(logn)19、若一個圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖20、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無數(shù)種二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋并比較內(nèi)部排序和外部排序的概念和方法，分析在處理大規(guī)模數(shù)據(jù)時外部排序的常用算法和策略。2、（本題10分）詳細(xì)說明如何在一個圖中判斷兩個節(jié)點(diǎn)是否連通，給出算法步驟和實現(xiàn)代碼，并分析其時間復(fù)雜度。3、（本題10分）詳細(xì)說明如何在一個具有n個元素的鏈表中，使用插入排序算法進(jìn)行排序，并分析其時間復(fù)雜度和空間復(fù)雜度。4、（本題10分）論述如何使用堆優(yōu)化迪杰