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

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

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