長春大學(xué)《數(shù)據(jù)可視化》2023-2024學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁長春大學(xué)《數(shù)據(jù)可視化》

2023-2024學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個用數(shù)組實現(xiàn)的循環(huán)隊列，若隊列已滿，此時front=10，rear=20，隊列的最大容量為50，那么下一個入隊元素應(yīng)該存儲在哪個位置？A.21B.0C.30D.無法確定2、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為？（）A.CBEFDAGB.CBEFDGAC.CBFEDGAD.CBFEGDA3、對于一個具有n個元素的希爾排序，其時間復(fù)雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是4、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，使用克魯斯卡爾（Kruskal）算法構(gòu)造最小生成樹，其時間復(fù)雜度主要取決于：A.邊數(shù)eB.頂點數(shù)nC.n和e的和D.n和e的乘積5、在一個具有n個頂點和e條邊的帶權(quán)無向圖中，使用Prim算法生成最小生成樹。若采用鄰接矩陣存儲圖，以下關(guān)于算法的空間復(fù)雜度的描述，哪一項是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)6、已知一個哈希表的裝填因子為0.8，哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突。若依次插入關(guān)鍵字31、25、19、49、37、21、13、17，則在查找關(guān)鍵字19時需要進(jìn)行幾次比較？（）A.1B.2C.3D.47、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則存儲空間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)8、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的每個節(jié)點通常包含數(shù)據(jù)域和指針域。若要在一個單向鏈表中刪除一個指定節(jié)點，以下哪種操作是關(guān)鍵步驟？A.修改被刪除節(jié)點的前一個節(jié)點的指針B.修改被刪除節(jié)點的后一個節(jié)點的指針C.釋放被刪除節(jié)點的內(nèi)存D.以上都是9、對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素。以下關(guān)于二分查找的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為：A.連接B.模式匹配C.求子串D.求串長11、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)，通過哈希函數(shù)將關(guān)鍵字映射到存儲位置。關(guān)于哈希沖突的解決方法，錯誤的是（）A.開放定址法通過尋找空閑位置來解決沖突B.鏈地址法將沖突的元素存儲在鏈表中C.再哈希法通過更換哈希函數(shù)來解決沖突D.哈希沖突無法避免，且對查找效率沒有影響12、設(shè)有一個具有n個頂點的帶權(quán)無向圖，使用普里姆（Prim）算法求最小生成樹。在算法執(zhí)行過程中，需要選擇一個頂點作為起始點。以下關(guān)于起始點選擇對算法時間復(fù)雜度的影響，哪一個是恰當(dāng)?shù)?？A.起始點的選擇對時間復(fù)雜度沒有影響B(tài).選擇不同的起始點可能導(dǎo)致時間復(fù)雜度不同C.選擇頂點度最小的作為起始點可以降低時間復(fù)雜度D.選擇頂點度最大的作為起始點可以降低時間復(fù)雜度13、在一個具有n個元素的大根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進(jìn)行調(diào)整，其時間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)14、對于一個具有n個頂點的有向圖，若采用鄰接表表示，則所有鄰接表中的邊節(jié)點總數(shù)為（）。A.nB.n+1C.eD.2e15、以下哪種排序算法在元素數(shù)量較少時性能較好？A.歸并排序B.快速排序C.插入排序D.堆排序16、以下關(guān)于字符串壓縮算法的描述，哪一項是不正確的？（）A.哈夫曼編碼可以根據(jù)字符出現(xiàn)頻率進(jìn)行壓縮B.LZW壓縮算法基于字典進(jìn)行壓縮C.壓縮算法一定能減小字符串的存儲空間D.不同的壓縮算法適用于不同類型的字符串17、對于一個具有n個頂點的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時間復(fù)雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)18、哈希表是一種常用的數(shù)據(jù)結(jié)構(gòu)，它通過哈希函數(shù)將鍵映射到存儲位置。以下關(guān)于哈希表的說法中，錯誤的是？（）A.哈希表的查找速度非?？欤骄鶗r間復(fù)雜度為O(1)。B.哈希函數(shù)的設(shè)計直接影響哈希表的性能。C.哈希表可能會出現(xiàn)沖突，即不同的鍵被映射到同一個存儲位置。D.哈希表只能存儲整數(shù)類型的鍵值對。19、已知一棵二叉排序樹的中序遍歷序列為{10,12,15,18,20,25,30}，則其可能的前序遍歷序列為？（）A.20,18,15,12,10,25,30B.10,12,15,18,20,25,30C.30,25,20,18,15,12,10D.10,12,18,15,20,30,2520、以下關(guān)于字符串匹配的BM算法的描述，哪一項是不正確的？（）A.從模式串的尾部開始匹配B.利用了壞字符和好后綴規(guī)則C.在一般情況下比KMP算法效率低D.可以通過預(yù)處理提高匹配速度二、簡答題（本大題共4個小題，共40分)1、（本題10分）描述二叉樹的遍歷算法在二叉樹的路徑問題變種（如路徑之和為給定值的路徑數(shù)量）中的應(yīng)用。2、（本題10分）闡述隊列在圖像處理中的應(yīng)用，如像素處理隊列、圖像過濾隊列等，并解釋其作用。3、（本題10分）解釋在一個具有n個頂點的無向圖中，如何通過深度優(yōu)先搜索判斷是否存在哈密頓回路。4、（本題10分）描述二叉樹的遍