青島黃海學院《數(shù)據(jù)可視化分析》2021-2022學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁青島黃海學院《數(shù)據(jù)可視化分析》

2021-2022學年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進行先序遍歷，比較節(jié)點值B.同時進行中序遍歷，比較節(jié)點值C.同時進行后序遍歷，比較節(jié)點值D.比較兩棵樹的節(jié)點數(shù)量2、在一個棧中，若入棧序列為1,2,3,4，且在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.173、以下關于樹的遍歷算法的描述，哪一項是不正確的？（）A.先序遍歷先訪問根節(jié)點B.中序遍歷先訪問左子樹C.后序遍歷先訪問右子樹D.三種遍歷算法都可以用遞歸或非遞歸方式實現(xiàn)4、在一個具有n個節(jié)點的無向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以5、在一棵二叉搜索樹中，刪除一個節(jié)點后，為了保持二叉搜索樹的性質(zhì)，需要進行的調(diào)整操作可能包括（）A.左旋B.右旋C.左右旋結合D.以上都有可能6、在一個具有n個元素的數(shù)組中，進行冒泡排序，在最壞情況下，需要比較的次數(shù)為？（）A.n-1B.n(n-1)/2C.n2D.nlog?n7、對于一個具有n個節(jié)點的二叉樹，進行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹的形狀為？A.只有一個根節(jié)點B.所有節(jié)點只有左子樹C.所有節(jié)點只有右子樹D.是一棵滿二叉樹8、對于一個具有n個元素的有序數(shù)組，若采用折半插入排序算法進行排序，其時間復雜度為？（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)9、在一個哈希表中，負載因子越大，說明什么？A.哈希沖突越少B.存儲空間利用率越高C.查找效率越高D.以上都不對10、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)11、鏈表是另一種常見的數(shù)據(jù)結構，它由一系列節(jié)點組成，每個節(jié)點包含數(shù)據(jù)和指向下一個節(jié)點的指針。以下關于鏈表的說法中，錯誤的是？（）A.鏈表的插入和刪除操作比較方便，只需要修改指針即可。B.鏈表可以動態(tài)地增長和縮小，不像數(shù)組那樣受固定長度的限制。C.鏈表的訪問速度比數(shù)組慢，因為需要遍歷鏈表才能找到特定的元素。D.鏈表只能存儲整數(shù)類型的數(shù)據(jù)元素。12、在數(shù)據(jù)結構中，字典樹（Trie樹）常用于字符串的存儲和查找，以下關于字典樹的特點，不正確的是（）A.對于前綴相同的字符串可以節(jié)省存儲空間B.查找操作的時間復雜度與字符串長度有關C.適合用于詞頻統(tǒng)計D.插入和刪除操作比較復雜13、棧和隊列的應用場景非常廣泛，以下關于它們的應用的說法中，錯誤的是？（）A.?？梢杂糜趯崿F(xiàn)函數(shù)調(diào)用、表達式求值和括號匹配等。B.隊列可以用于實現(xiàn)任務調(diào)度、消息隊列和廣度優(yōu)先搜索等。C.棧和隊列可以用于實現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊列只適用于計算機科學領域，在其他領域沒有實際價值。14、在一個具有n個頂點和e條邊的帶權無向圖中，使用Prim算法生成最小生成樹。若采用鄰接矩陣存儲圖，以下關于算法的空間復雜度的描述，哪一項是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)15、對于一個具有n個頂點和e條邊的有向圖，采用鄰接表存儲，進行深度優(yōu)先遍歷。以下關于遍歷的時間復雜度的描述，哪一個是恰當?shù)?？A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)16、以下關于哈希表沖突解決方法的描述，哪一項是不正確的？（）A.鏈地址法會增加存儲空間的開銷B.開放定址法的查找效率一定高于鏈地址法C.再哈希法可以減少沖突的發(fā)生D.建立公共溢出區(qū)可以存儲發(fā)生沖突的元素17、已知一個帶權有向圖G=(V,E)，頂點集合V={1,2,3,4,5}，邊集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求從頂點1到頂點5的最短路徑，經(jīng)過的中間頂點依次為？（）A.2,4B.3,4C.2,3D.3,518、在數(shù)據(jù)結構中，使用隊列來實現(xiàn)廣度優(yōu)先遍歷圖，以下關于遍歷過程的描述，錯誤的是（）A.從起始節(jié)點開始入隊B.隊列為空時結束遍歷C.訪問節(jié)點時將其未訪問的鄰接節(jié)點入隊D.節(jié)點不會被重復訪問19、已知一個圖的鄰接表存儲結構，若要判斷任意兩個頂點之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索20、在一個具有n個節(jié)點的帶權有向圖中，使用迪杰斯特拉算法求最短路徑，其時間復雜度是多少？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述如何使用A*算法在圖中進行尋路，解釋其啟發(fā)函數(shù)的作用和設計原則，并分析其性能優(yōu)勢。2、（本題10分）詳細論述在一個具有n個頂點的無向圖中，如何使用Prim算法從不同的起始頂點構建最小生成樹，并比較結果。3、（本題10分）闡述如何在一個具有n個元素的循環(huán)鏈表中，進行查找操作，并分析其時間復雜度和空間復雜度。4、（本題