西安電子科技大學(xué)《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫(kù)技術(shù)》2021-2022學(xué)年期末試卷

自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密自覺(jué)遵守考場(chǎng)紀(jì)律如考試作弊此答卷無(wú)效密封線(xiàn)第1頁(yè)，共3頁(yè)西安電子科技大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與數(shù)據(jù)庫(kù)技術(shù)》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，若底層從左到右填充，則第i個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)的編號(hào)為？A.2iB.2i+1C.i*2D.i*2+12、二叉樹(shù)是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有多種遍歷方式。對(duì)于先序遍歷、中序遍歷和后序遍歷，以下描述錯(cuò)誤的是（）A.先序遍歷先訪(fǎng)問(wèn)根節(jié)點(diǎn)，然后遞歸遍歷左子樹(shù)和右子樹(shù)B.中序遍歷先遞歸遍歷左子樹(shù)，然后訪(fǎng)問(wèn)根節(jié)點(diǎn)，最后遞歸遍歷右子樹(shù)C.后序遍歷先遞歸遍歷左子樹(shù)和右子樹(shù)，最后訪(fǎng)問(wèn)根節(jié)點(diǎn)D.這三種遍歷方式的結(jié)果總是相同的3、在一棵二叉搜索樹(shù)中，刪除一個(gè)有兩個(gè)子節(jié)點(diǎn)的節(jié)點(diǎn)時(shí)，通常采用的方法是：A.用左子樹(shù)的最大值替代該節(jié)點(diǎn)B.用右子樹(shù)的最小值替代該節(jié)點(diǎn)C.隨機(jī)選擇左子樹(shù)或右子樹(shù)的節(jié)點(diǎn)替代D.不進(jìn)行替代，直接刪除4、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的線(xiàn)性表中，刪除第i個(gè)元素（1<=i<=n），平均需要移動(dòng)多少個(gè)元素？（）A.n-iB.iC.(n-i)/2D.n/25、在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若采用鄰接矩陣存儲(chǔ)，則存儲(chǔ)空間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)6、在一個(gè)帶權(quán)有向圖中，若以頂點(diǎn)v為源點(diǎn)，利用迪杰斯特拉算法求從v到其他頂點(diǎn)的最短路徑，在算法執(zhí)行過(guò)程中，每個(gè)頂點(diǎn)的最短路徑值是如何確定的？（）A.初始時(shí)都設(shè)為無(wú)窮大，逐步更新B.初始時(shí)都設(shè)為0，逐步更新C.隨機(jī)設(shè)定，逐步更新D.根據(jù)頂點(diǎn)的權(quán)值設(shè)定，逐步更新7、在一個(gè)長(zhǎng)度為n的有序線(xiàn)性表中進(jìn)行二分查找，在最壞情況下，需要比較的次數(shù)為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)8、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同9、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和與出度之和的關(guān)系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.沒(méi)有確定的關(guān)系10、對(duì)于一個(gè)用鏈表實(shí)現(xiàn)的棧，若要獲取棧中元素的個(gè)數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護(hù)一個(gè)計(jì)數(shù)器C.以上效率相同D.以上都不對(duì)11、若對(duì)線(xiàn)性表的操作只有兩種，即插入和刪除，且以鏈表作為存儲(chǔ)結(jié)構(gòu)，則插入和刪除操作的時(shí)間復(fù)雜度分別為：A.O(n)和O(n)B.O(1)和O(1)C.O(n)和O(1)D.O(1)和O(n)12、一棵完全二叉樹(shù)的第6層（根為第1層）有8個(gè)葉子節(jié)點(diǎn)，則該完全二叉樹(shù)的節(jié)點(diǎn)總數(shù)最多為（）。A.39B.56C.111D.11913、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)無(wú)向圖中，使用普里姆算法構(gòu)造最小生成樹(shù)，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結(jié)構(gòu)14、一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接表存儲(chǔ)，其空間復(fù)雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)15、在二叉樹(shù)中，判斷兩棵二叉樹(shù)是否完全相同，以下方法不正確的是（）A.同時(shí)進(jìn)行先序遍歷，比較節(jié)點(diǎn)值B.同時(shí)進(jìn)行中序遍歷，比較節(jié)點(diǎn)值C.同時(shí)進(jìn)行后序遍歷，比較節(jié)點(diǎn)值D.比較兩棵樹(shù)的節(jié)點(diǎn)數(shù)量16、在數(shù)據(jù)結(jié)構(gòu)中，字典樹(shù)（Trie樹(shù)）常用于字符串的存儲(chǔ)和查找，以下關(guān)于字典樹(shù)的特點(diǎn)，不正確的是（）A.對(duì)于前綴相同的字符串可以節(jié)省存儲(chǔ)空間B.查找操作的時(shí)間復(fù)雜度與字符串長(zhǎng)度有關(guān)C.適合用于詞頻統(tǒng)計(jì)D.插入和刪除操作比較復(fù)雜17、若一棵二叉樹(shù)的層次遍歷序列為ABCDEFGHI，則其可能的中序遍歷序列有多少種？（）A.1B.n!C.2^nD.不確定18、對(duì)于一個(gè)具有n個(gè)元素的無(wú)序數(shù)組，若要對(duì)其進(jìn)行排序，以下哪種算法在最壞情況下時(shí)間復(fù)雜度最高？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序19、在一個(gè)具有n個(gè)元素的堆中，進(jìn)行插入操作的時(shí)間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)20、在數(shù)據(jù)結(jié)構(gòu)中，桶排序是一種外部排序算法，以下關(guān)于桶排序的描述，錯(cuò)誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時(shí)間復(fù)雜度為O(n)C.空間復(fù)雜度較高D.適用于大規(guī)模數(shù)據(jù)排序二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）鏈表的反轉(zhuǎn)操作在雙向鏈表中的實(shí)現(xiàn)方法與單向鏈表有何不同？2、（本題10分）解釋如何在一個(gè)具有n個(gè)元素的最小堆中，找出第k小的元素，并分析其時(shí)間復(fù)雜度。3、（本題10分）論述如何使用動(dòng)態(tài)規(guī)劃算法解決最長(zhǎng)公共子串問(wèn)題。4、（本題10分）解釋如何將一個(gè)二叉樹(shù)轉(zhuǎn)換為雙向鏈表，給出算法步驟和實(shí)現(xiàn)代碼，并