浙江工業(yè)大學(xué)之江學(xué)院《數(shù)據(jù)可視化》2023-2024學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁浙江工業(yè)大學(xué)之江學(xué)院《數(shù)據(jù)可視化》

2023-2024學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為（）。A.CEABDB.CEDBAC.CABDED.CEDAB2、以下關(guān)于樹的存儲結(jié)構(gòu)的描述，哪一項是不正確的？（）A.孩子兄弟表示法可以方便地實現(xiàn)樹的遍歷B.雙親表示法便于查找一個節(jié)點的雙親節(jié)點C.孩子鏈表表示法在處理多叉樹時空間利用率較高D.以上存儲結(jié)構(gòu)在時間復(fù)雜度上沒有明顯差異3、隊列也是一種線性表，遵循先進(jìn)先出原則。在一個循環(huán)隊列中，隊頭指針為front，隊尾指針為rear，隊列最大容量為MAXSIZE，那么判斷隊列為空的條件是什么？A.front==rearB.(rear+1)%MAXSIZE==frontC.front==(rear+1)%MAXSIZED.以上都不對4、若要對一個已經(jīng)排好序的數(shù)組進(jìn)行二分查找，查找不成功時，最多需要比較多少次？（）A.lognB.logn-1C.logn+1D.n-15、隊列是一種先進(jìn)先出的線性表，若用一個數(shù)組實現(xiàn)循環(huán)隊列，隊頭指針front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素，隊列最大容量為MAX_SIZE，那么判斷隊滿的條件是什么？（）A.(rear+1)%MAX_SIZE==frontB.rear==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-16、二叉樹是一種重要的數(shù)據(jù)結(jié)構(gòu)，具有多種遍歷方式。對于先序遍歷、中序遍歷和后序遍歷，以下描述錯誤的是（）A.先序遍歷先訪問根節(jié)點，然后遞歸遍歷左子樹和右子樹B.中序遍歷先遞歸遍歷左子樹，然后訪問根節(jié)點，最后遞歸遍歷右子樹C.后序遍歷先遞歸遍歷左子樹和右子樹，最后訪問根節(jié)點D.這三種遍歷方式的結(jié)果總是相同的7、在數(shù)據(jù)結(jié)構(gòu)中，棧是一種特殊的線性表，遵循先進(jìn)后出的原則。以下關(guān)于棧的操作，錯誤的是（）A.入棧操作將元素添加到棧頂B.出棧操作取出并刪除棧頂元素C.可以在棧的任意位置進(jìn)行插入和刪除操作D.棧頂指針始終指向棧頂元素8、對于一個用鏈表實現(xiàn)的棧，若要獲取棧中元素的個數(shù)，以下哪種方法效率較高？A.遍歷鏈表B.維護(hù)一個計數(shù)器C.以上效率相同D.以上都不對9、以下關(guān)于哈希沖突解決方法中二次探測法的描述，哪一項是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)10、在一個具有n個頂點的強連通圖中，至少有多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)11、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），需要移動的元素個數(shù)最多為（）。A.i-1B.n-iC.n-i+1D.n-112、設(shè)有一個棧，元素進(jìn)棧的次序為A、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE13、在數(shù)據(jù)結(jié)構(gòu)中，伸展樹（SplayTree）通過自調(diào)整保持較好的性能，以下關(guān)于伸展樹的操作，不正確的是（）A.查找操作會將被查找的節(jié)點旋轉(zhuǎn)到根節(jié)點B.插入操作可能會引起多次旋轉(zhuǎn)C.伸展樹的平均性能較好D.伸展樹的空間復(fù)雜度較高14、AVL樹是一種高度平衡的二叉搜索樹，以下關(guān)于AVL樹的旋轉(zhuǎn)操作，描述不正確的是（）A.旋轉(zhuǎn)操作用于保持樹的平衡B.包括單旋轉(zhuǎn)和雙旋轉(zhuǎn)兩種類型C.旋轉(zhuǎn)操作不會改變二叉搜索樹的性質(zhì)D.每次插入或刪除節(jié)點都需要進(jìn)行旋轉(zhuǎn)操作15、在一個大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個元素交換，然后從堆頂向下調(diào)整D.無需調(diào)整16、對于一個具有n個節(jié)點的完全二叉樹，若按照層次遍歷的順序?qū)⒐?jié)點編號為1到n，已知編號為i的節(jié)點有左孩子，則其左孩子的編號為？A.2iB.2i+1C.i*2D.i/217、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，若采用Prim算法生成最小生成樹，其時間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)18、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD19、設(shè)有一個用鏈表實現(xiàn)的雙向循環(huán)鏈表，若要在其中一個節(jié)點之后插入一個新節(jié)點，以下關(guān)于插入操作的時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)20、以下關(guān)于快速排序的描述，錯誤的是：A.快速排序在平均情況下的時間復(fù)雜度為O(nlogn)B.快速排序是一種不穩(wěn)定的排序算法C.快速排序在最壞情況下的時間復(fù)雜度為O(n^2)D.快速排序不需要額外的存儲空間二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述哈夫曼編碼的原理和構(gòu)建過程，舉例說明哈夫曼編碼在數(shù)據(jù)壓縮中的應(yīng)用優(yōu)勢和效果。2、（本題10分）論述在并查集的應(yīng)用中，如何解決集合合并和查詢的動態(tài)問題。3、（本題10分）在數(shù)據(jù)結(jié)構(gòu)中，解釋如何使用棧實現(xiàn)括號匹配的檢驗，給出算法步驟和實現(xiàn)代碼，并分析其時間復(fù)雜度。4、（本題10分）解釋如何在一個二叉搜索樹中進(jìn)行刪除操作的多線程實現(xiàn)