成都錦城學(xué)院《數(shù)據(jù)可視化技術(shù)與應(yīng)用》2022-2023學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁成都錦城學(xué)院

《數(shù)據(jù)可視化技術(shù)與應(yīng)用》2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個具有n個頂點和e條邊的無向圖，使用深度優(yōu)先搜索算法進(jìn)行遍歷。以下關(guān)于算法中使用的標(biāo)記數(shù)組的空間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)2、在數(shù)據(jù)結(jié)構(gòu)中，使用隊列來實現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點開始入隊B.隊列為空時結(jié)束遍歷C.訪問節(jié)點時將其未訪問的鄰接節(jié)點入隊D.節(jié)點不會被重復(fù)訪問3、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA4、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進(jìn)行先序遍歷，比較節(jié)點值B.同時進(jìn)行中序遍歷，比較節(jié)點值C.同時進(jìn)行后序遍歷，比較節(jié)點值D.比較兩棵樹的節(jié)點數(shù)量5、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)并查集？（）A.數(shù)組B.鏈表C.樹D.哈希表6、在一個用鏈表實現(xiàn)的隊列中，若要實現(xiàn)隊列的遍歷操作，以下哪種方式較為合適？A.從隊頭開始，依次訪問每個節(jié)點B.從隊尾開始，依次向前訪問每個節(jié)點C.隨機(jī)訪問鏈表中的節(jié)點D.以上都不對7、在一個有n個頂點和e條邊的無向圖中，采用鄰接矩陣存儲，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)8、對于一個具有n個頂點的連通圖，其生成樹中邊的數(shù)量為：A.n-1B.nC.n+1D.不確定9、在一個堆排序中，最大堆用于升序排序，最小堆用于降序排序。那么對于一個初始無序的數(shù)組，構(gòu)建最大堆的時間復(fù)雜度是多少？（）A.O(n)B.O(log?n)C.O(nlog?n)D.O(n2)10、對于一個具有n個頂點的無向圖，若采用鄰接矩陣存儲，則存儲空間的復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)11、在一個小根堆中，最小的元素總是位于堆頂。若要將一個元素插入到堆中并保持堆的性質(zhì)，以下哪種操作是必須的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先刪除堆頂元素再插入D.以上都不對12、在一個帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接已選頂點和未選頂點的權(quán)值最小的邊C.任意一條邊D.以上都不對13、在一個字符串匹配算法中，BM算法相對于樸素的字符串匹配算法，其優(yōu)勢在于？（）A.平均性能更好B.代碼更簡潔C.空間復(fù)雜度更低D.適用于短字符串匹配14、字符串匹配是數(shù)據(jù)結(jié)構(gòu)中的一個重要問題，KMP算法是一種高效的字符串匹配算法。關(guān)于KMP算法，以下描述錯誤的是（）A.通過利用已經(jīng)匹配的部分信息來提高匹配效率B.計算next數(shù)組是KMP算法的關(guān)鍵步驟C.KMP算法的時間復(fù)雜度為O(m+n)，其中m和n分別是主串和模式串的長度D.KMP算法在任何情況下都比暴力匹配算法快15、對于一個具有n個頂點的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時間復(fù)雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)16、在一個m行n列的二維數(shù)組中，按列優(yōu)先存儲時，元素aij的存儲地址為？（）A.LOC(a11)+[(j-1)*m+(i-1)]*dB.LOC(a11)+[(i-1)*m+(j-1)]*dC.LOC(a11)+[(j-1)*n+(i-1)]*dD.LOC(a11)+[(i-1)*n+(j-1)]*d17、在一個用數(shù)組實現(xiàn)的小根堆中，若要插入一個元素，應(yīng)該將其插入到數(shù)組的哪個位置？A.數(shù)組末尾B.堆頂C.任意位置D.以上都不對18、對于一個具有n個元素的順序存儲的棧，若要判斷棧是否已滿，應(yīng)判斷？（）A.top==n-1B.top==nC.top>=n-1D.top>=n19、對于一個具有n個元素的冒泡排序，若要交換相鄰兩個元素，平均需要移動多少次？（）A.0B.1C.2D.320、在一個具有n個頂點的有向完全圖中，邊的數(shù)量為：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述在Trie樹中，如何節(jié)省存儲空間，例如采用壓縮存儲或節(jié)點合并等方法。2、（本題10分）論述哈希表的沖突解決方法，如線性探測法、二次探測法和鏈地址法，并分析它們的優(yōu)缺點。3、（本題10分）對于一個用鄰接表存儲的圖，說明如何判斷圖是否為哈密頓圖，給出一種有效的算法并分析其時間復(fù)雜度。4、（本題10分）在一個具有n個頂點的無向圖中，如何使用深度優(yōu)先搜索算法找出所有的連通分量，給出算法步驟