成都錦城學(xué)院《數(shù)據(jù)可視化項目實踐》2022-2023學(xué)年期末試卷

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

《數(shù)據(jù)可視化項目實踐》2022-2023學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種排序算法在平均情況下的時間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序2、在一個用數(shù)組實現(xiàn)的棧中，若要將棧的容量擴大一倍，以下哪種操作的時間復(fù)雜度最低？（）A.重新創(chuàng)建一個更大的數(shù)組并復(fù)制元素B.逐步將元素移動到新的更大的數(shù)組中C.直接在原數(shù)組后面追加空間D.以上操作時間復(fù)雜度相同3、對于一個具有n個元素的棧，若要實現(xiàn)將棧中元素逆置，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)為？（）A.隊列B.棧C.鏈表D.數(shù)組4、在一個用鄰接表存儲的有向圖中，若要計算某個節(jié)點的出度，以下哪種方法較為高效？A.遍歷該節(jié)點的鄰接表B.遍歷整個圖的鄰接表C.無法高效計算D.以上都不對5、以下哪種排序算法在元素基本有序的情況下性能最佳？A.快速排序B.冒泡排序C.插入排序D.堆排序6、在二叉搜索樹的刪除操作中，如果刪除的節(jié)點是其父節(jié)點的唯一子節(jié)點，以下處理方式錯誤的是（）A.直接將該節(jié)點刪除，不做其他調(diào)整B.將該節(jié)點的值替換為其父節(jié)點的值，并刪除父節(jié)點C.將該節(jié)點的左子樹或右子樹替代該節(jié)點D.以上處理方式都不對7、若要從一個具有n個元素的有序單鏈表中刪除所有值重復(fù)的元素，使得鏈表中每個元素的值都不同，最優(yōu)的算法時間復(fù)雜度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)8、對于一個具有n個節(jié)點的帶權(quán)連通圖，其最小生成樹一定包含圖中的所有節(jié)點嗎？A.一定包含B.不一定包含C.視情況而定D.以上都不對9、若要對n個元素進行快速排序，在最壞情況下，其時間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(nlog?n)D.O(n2)10、對于一個采用順序存儲的棧，若棧頂指針top等于-1時，表示：A.棧滿B.棧空C.棧中只有一個元素D.棧中至少有一個元素11、在一個具有n個元素的順序表中，若要將其逆置，以下關(guān)于操作的時間復(fù)雜度的描述，哪一項是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)12、在一棵紅黑樹中，插入一個新節(jié)點后，調(diào)整樹的結(jié)構(gòu)以保持紅黑性質(zhì)的操作次數(shù)最多為（）A.1B.2C.lognD.n13、在一個具有n個頂點的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n14、對于一個具有n個元素的有序單鏈表，要查找一個值為x的元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.115、在一個具有n個頂點的無向圖中，若每個頂點的度都為k，則邊的數(shù)量為多少？（）A.nk/2B.nkC.n(k-1)/2D.n(k-1)16、設(shè)有一個具有n個節(jié)點的二叉搜索樹，若要查找一個值大于給定值的最小節(jié)點，以下關(guān)于查找操作的時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），需要移動的元素個數(shù)最多為（）。A.i-1B.n-iC.n-i+1D.n-118、一個有序序列為{12,18,24,35,47,50,62,83,90,115,134}，當(dāng)用二分法查找值為90的元素時，需要比較的次數(shù)是（）。A.1B.2C.3D.419、對于一個具有n個元素的大頂堆，若要獲取堆中的第k大元素（1<=k<=n），以下哪種方法效率較高？A.先排序再獲取B.每次刪除堆頂元素k-1次C.構(gòu)建一個大小為k的小頂堆，然后逐步替換D.以上方法效率相同20、對于一個具有n個元素的有序鏈表，進行二分查找的時間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.不能進行二分查找二、簡答題（本大題共4個小題，共40分)1、（本題10分）深入分析在具有n個元素的循環(huán)鏈表中，如何查找指定元素，并給出時間復(fù)雜度和空間復(fù)雜度的分析。2、（本題10分）深入分析在一個具有n個元素的鏈表中，如何刪除指定區(qū)間內(nèi)的節(jié)點。3、（本題10分）解釋什么是字典樹，并說明其在單詞查找和統(tǒng)計中的應(yīng)用。4、（本題10分）在一個具有n個頂點的無向圖中，如何找出所有的頂點割集，給出一種有效的算法并分析其時間復(fù)雜度。三、設(shè)計題（本大題共2個小題，共