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

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

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