浙江工業(yè)大學(xué)之江學(xué)院《數(shù)據(jù)可視化》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)浙江工業(yè)大學(xué)之江學(xué)院《數(shù)據(jù)可視化》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字典操作，并且能夠快速查找、插入和刪除元素？（）A.棧B.隊(duì)列C.二叉搜索樹D.數(shù)組2、二叉樹的遍歷方式可以遞歸實(shí)現(xiàn)，也可以非遞歸實(shí)現(xiàn)，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.遞歸實(shí)現(xiàn)的二叉樹遍歷方式簡(jiǎn)單直觀，但可能會(huì)導(dǎo)致棧溢出問題。B.非遞歸實(shí)現(xiàn)的二叉樹遍歷方式需要使用?；蜿?duì)列來輔助實(shí)現(xiàn)。C.非遞歸實(shí)現(xiàn)的二叉樹遍歷方式比遞歸實(shí)現(xiàn)的效率更高。D.二叉樹的遍歷方式只能用遞歸或非遞歸方式實(shí)現(xiàn)，不能用其他方式實(shí)現(xiàn)。3、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組4、對(duì)于一個(gè)用數(shù)組實(shí)現(xiàn)的小根堆，進(jìn)行刪除堆頂元素操作后，需要重新調(diào)整堆以保持堆的性質(zhì)。以下關(guān)于刪除操作的時(shí)間復(fù)雜度的描述，哪一個(gè)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、已知一個(gè)圖的鄰接表存儲(chǔ)結(jié)構(gòu)，若要判斷任意兩個(gè)頂點(diǎn)之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索6、在一個(gè)帶權(quán)的有向圖中，使用迪杰斯特拉算法求從源點(diǎn)到其他頂點(diǎn)的最短路徑，每次選擇的頂點(diǎn)是？（）A.距離源點(diǎn)最近的頂點(diǎn)B.距離源點(diǎn)最遠(yuǎn)的頂點(diǎn)C.未確定最短路徑的頂點(diǎn)中權(quán)值最小的頂點(diǎn)D.未確定最短路徑的頂點(diǎn)中權(quán)值最大的頂點(diǎn)7、若對(duì)一棵二叉搜索樹進(jìn)行先序遍歷，得到的節(jié)點(diǎn)序列是一個(gè)遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空8、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表主要用于存儲(chǔ)有向圖，以下關(guān)于十字鏈表的特點(diǎn)，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲(chǔ)空間比鄰接表節(jié)省C.對(duì)于刪除邊的操作比較復(fù)雜D.不適合用于稀疏有向圖9、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若每個(gè)節(jié)點(diǎn)都有左右孩子，則葉子節(jié)點(diǎn)的數(shù)量與度為2的節(jié)點(diǎn)數(shù)量有什么關(guān)系？A.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量+1B.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量-1C.葉子節(jié)點(diǎn)數(shù)量=度為2的節(jié)點(diǎn)數(shù)量D.以上都不對(duì)10、以下關(guān)于拓?fù)渑判虻拿枋?，正確的是：A.拓?fù)渑判虻慕Y(jié)果是唯一的B.一個(gè)有環(huán)的圖也可以進(jìn)行拓?fù)渑判駽.拓?fù)渑判蚩梢杂糜谂袛嘁粋€(gè)圖是否有環(huán)D.拓?fù)渑判蛑荒苡糜谟邢驁D11、在一個(gè)具有n個(gè)元素的有序數(shù)組中，使用插入排序進(jìn)行排序，其最壞情況下的時(shí)間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(n2)D.O(nlog?n)12、在一個(gè)具有n個(gè)元素的最大堆中，插入一個(gè)新元素后，為了恢復(fù)堆的性質(zhì)，需要進(jìn)行的調(diào)整操作的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、在一個(gè)循環(huán)鏈表中，若要?jiǎng)h除鏈表中的最后一個(gè)節(jié)點(diǎn)，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、在一個(gè)有n個(gè)頂點(diǎn)和e條邊的無向圖中，采用鄰接矩陣存儲(chǔ)，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)15、樹是一種非線性數(shù)據(jù)結(jié)構(gòu)，它由節(jié)點(diǎn)和邊組成。以下關(guān)于樹的說法中，錯(cuò)誤的是？（）A.樹中的每個(gè)節(jié)點(diǎn)都有一個(gè)父節(jié)點(diǎn)（除了根節(jié)點(diǎn)）和零個(gè)或多個(gè)子節(jié)點(diǎn)。B.二叉樹是一種特殊的樹，每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。C.樹可以用于實(shí)現(xiàn)文件系統(tǒng)、數(shù)據(jù)庫(kù)索引等。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。16、在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，邊的數(shù)量為：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)17、對(duì)于一棵二叉樹，先序遍歷序列為ABC，中序遍歷序列為BAC，則其后序遍歷序列為？A.BCAB.CBAC.ACBD.ABC18、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行刪除堆頂元素的操作，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的無向完全圖，其邊的數(shù)量為多少？A.n(n-1)/2B.n(n+1)/2C.n^2D.n^2/220、以下哪種排序算法在最壞情況下的交換次數(shù)最少？A.冒泡排序B.快速排序C.選擇排序D.插入排序二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述如何在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用快速選擇算法查找第k小的元素，分析其時(shí)間復(fù)雜度。2、（本題10分）簡(jiǎn)述數(shù)據(jù)結(jié)構(gòu)中棧的定義、特點(diǎn)及基本操作，并舉例說明棧在實(shí)際中的應(yīng)用。3、（本題10分）比較冒泡排序和快速排序在對(duì)小規(guī)模數(shù)據(jù)的處理速度。4、（本題10分）詳細(xì)闡述在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，如何進(jìn)行邊的雙連通分量的求解。三、設(shè)計(jì)題