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