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

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

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