常州工學院《數(shù)據(jù)可視化》2022-2023學年期末試卷

站名：站名：年級專業(yè)：姓名：學號：凡年級專業(yè)、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁常州工學院《數(shù)據(jù)可視化》

2022-2023學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、若一棵二叉樹的先序遍歷序列和后序遍歷序列分別為ABC和CBA，則其中序遍歷序列為：A.BCAB.CABC.ABCD.無法確定2、在一個具有n個頂點的無向圖中，若采用鄰接矩陣存儲，則矩陣中非零元素的個數(shù)至少為？（）A.nB.n-1C.2(n-1)D.n(n-1)/23、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時進行先序遍歷，比較節(jié)點值B.同時進行中序遍歷，比較節(jié)點值C.同時進行后序遍歷，比較節(jié)點值D.比較兩棵樹的節(jié)點數(shù)量4、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持區(qū)間查詢操作？（）A.線段樹B.二叉搜索樹C.堆D.鏈表5、隊列也是一種常見的數(shù)據(jù)結(jié)構(gòu)，遵循先進先出的原則。對于一個循環(huán)隊列，以下說法不正確的是（）A.隊頭指針和隊尾指針的移動需要考慮循環(huán)的情況B.當隊頭指針等于隊尾指針時，隊列為空C.可以通過犧牲一個存儲單元來區(qū)分隊列空和隊列滿的情況D.循環(huán)隊列可以避免假溢出的問題6、在一個循環(huán)隊列中，若隊頭指針front=5，隊尾指針rear=2，則隊列中的元素個數(shù)為：A.7B.3C.2D.不確定7、在一個具有n個元素的最小堆中，若要將堆頂元素與堆底元素交換，然后調(diào)整堆的結(jié)構(gòu)，需要的時間復雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、在一個具有n個元素的順序表中，若要在第i個位置（1<=i<=n+1）插入一個新元素，需要移動的元素個數(shù)最少為（）。A.0B.i-1C.n-iD.n-i+19、在數(shù)據(jù)結(jié)構(gòu)中，對于線性表的順序存儲和鏈式存儲，以下說法正確的是：順序存儲結(jié)構(gòu)可以隨機訪問元素，但插入和刪除操作效率較低；鏈式存儲結(jié)構(gòu)插入和刪除操作方便，但不能隨機訪問。那么在頻繁進行插入和刪除操作的情況下，應優(yōu)先選擇哪種存儲結(jié)構(gòu)？（）A.順序存儲B.鏈式存儲C.兩者均可D.無法確定10、對于一個具有n個節(jié)點的無向連通圖，其生成樹的邊數(shù)為（）A.n-1B.nC.n+1D.2n11、以下關于平衡二叉樹旋轉(zhuǎn)調(diào)整的描述，正確的是：A.旋轉(zhuǎn)調(diào)整一定會改變樹的中序遍歷結(jié)果B.左旋操作是將右子樹變?yōu)楦?jié)點，原根節(jié)點變?yōu)樽笞庸?jié)點C.右旋操作是將左子樹變?yōu)楦?jié)點，原根節(jié)點變?yōu)橛易庸?jié)點D.平衡二叉樹不需要進行旋轉(zhuǎn)調(diào)整12、若要對一個具有n個元素的數(shù)組進行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、圖是一種復雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個有向圖，通?？梢允褂媚姆N存儲結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可14、若一個隊列的入隊序列是1、2、3、4、5，在進行出隊操作時，第一個出隊的元素是：A.1B.2C.3D.415、在一個鏈式存儲的線性表中，若要刪除第i個元素（1<=i<=n），需要找到其前驅(qū)節(jié)點的時間復雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)16、對于一個具有n個元素的順序存儲的循環(huán)隊列，隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，若隊列非空，則隊列中元素的個數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+117、以下關于圖的深度優(yōu)先搜索和廣度優(yōu)先搜索的描述，哪一項是正確的？（）A.深度優(yōu)先搜索使用隊列實現(xiàn)B.廣度優(yōu)先搜索使用棧實現(xiàn)C.兩種搜索算法都可以用于判斷圖是否連通D.深度優(yōu)先搜索一定能找到最短路徑18、在一個采用哈希表存儲的數(shù)據(jù)結(jié)構(gòu)中，哈希函數(shù)將關鍵字映射到存儲位置。若發(fā)生哈希沖突，通常采用開放定址法解決。以下關于開放定址法的時間復雜度的描述，哪一個是恰當?shù)模緼.查找操作的時間復雜度在平均情況下為O(1)，最壞情況為O(n)B.查找操作的時間復雜度始終為O(1)C.查找操作的時間復雜度在平均情況下為O(logn)，最壞情況為O(nlogn)D.查找操作的時間復雜度始終為O(n)19、堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，分為大頂堆和小頂堆。對于大頂堆，以下描述不正確的是（）A.根節(jié)點的值大于其左右子節(jié)點的值B.可以用于實現(xiàn)優(yōu)先隊列C.構(gòu)建大頂堆的時間復雜度為O(nlogn)D.每次刪除堆頂元素后，需要重新調(diào)整堆以保持大頂堆的性質(zhì)20、在數(shù)據(jù)結(jié)構(gòu)中，桶排序是一種外部排序算法，以下關于桶排序的描述，錯誤的是（）A.要求輸入數(shù)據(jù)具有特定的分布B.時間復雜度為O(n)C.空間復雜度較高D.適用于大規(guī)模數(shù)據(jù)排序二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述哈希表的基本原理，包括哈希函數(shù)的設計和沖突解決方法（開放定址法、鏈地址法等）。2、（本題10分）解釋數(shù)據(jù)結(jié)構(gòu)中棧的應用場景，如函數(shù)調(diào)用棧的模擬、深度優(yōu)先搜索的非遞歸實現(xiàn)等，并說明其原理。3、（本題10分）對于一個用哈希表存儲的字符串集合，解釋如何進行字符串的插入、查找和刪除操作，并分析其平均時間復雜度。4、（本題10分）論述哈夫曼編碼的原理和構(gòu)建過程，舉例說明哈夫曼編碼在數(shù)據(jù)壓縮中的應用優(yōu)勢和效果。三