成都錦城學(xué)院《數(shù)據(jù)可視化》2022-2023學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁成都錦城學(xué)院

《數(shù)據(jù)可視化》2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在數(shù)據(jù)結(jié)構(gòu)中，基數(shù)排序是一種非比較排序算法，以下關(guān)于基數(shù)排序的描述，不正確的是（）A.按照位數(shù)依次進(jìn)行排序B.可以用于整數(shù)和字符串的排序C.時(shí)間復(fù)雜度為O(d(n+r))，其中d是位數(shù)，r是基數(shù)D.對數(shù)據(jù)的分布敏感2、圖的存儲方式有鄰接矩陣和鄰接表兩種，以下關(guān)于它們的特點(diǎn)的說法中，錯(cuò)誤的是？（）A.鄰接矩陣適合存儲稠密圖，空間復(fù)雜度為O(n^2)。B.鄰接表適合存儲稀疏圖，空間復(fù)雜度為O(n+m)，其中n是頂點(diǎn)數(shù)，m是邊數(shù)。C.鄰接矩陣的查找邊的時(shí)間復(fù)雜度為O(1)。D.鄰接表的插入邊和刪除邊的時(shí)間復(fù)雜度為O(n)。3、在一個(gè)具有n個(gè)元素的順序存儲的循環(huán)隊(duì)列中，隊(duì)滿的條件是（）。A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front4、對于一個(gè)具有n個(gè)元素的大頂堆，若要獲取堆中的第k大元素（1<=k<=n），以下哪種方法效率較高？A.先排序再獲取B.每次刪除堆頂元素k-1次C.構(gòu)建一個(gè)大小為k的小頂堆，然后逐步替換D.以上方法效率相同5、在一個(gè)順序存儲的數(shù)組中實(shí)現(xiàn)一個(gè)簡單的棧結(jié)構(gòu)，若棧頂指針top初始值為-1，當(dāng)進(jìn)行一次入棧操作后，top的值應(yīng)該如何變化？A.top不變B.top=top+1C.top=top-1D.top=06、若一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB7、對于一個(gè)采用順序存儲結(jié)構(gòu)的完全二叉樹，若已知根節(jié)點(diǎn)在數(shù)組中的位置為1，則其第i個(gè)節(jié)點(diǎn)的左孩子節(jié)點(diǎn)在數(shù)組中的位置為？A.2iB.2i+1C.i*2D.i*2-18、對于一個(gè)具有n個(gè)元素的哈希表，若采用鏈地址法處理沖突，以下關(guān)于查找操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、以下關(guān)于哈希沖突解決方法中二次探測法的描述，哪一項(xiàng)是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)10、設(shè)有一個(gè)廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)11、以下哪種排序算法在數(shù)據(jù)基本有序時(shí)的時(shí)間復(fù)雜度接近O(n)？A.冒泡排序B.快速排序C.插入排序D.選擇排序12、樹的遍歷方式有多種，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.前序遍歷是先訪問根節(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。B.中序遍歷是先遍歷左子樹，然后訪問根節(jié)點(diǎn)，最后遍歷右子樹。C.后序遍歷是先遍歷左子樹，然后遍歷右子樹，最后訪問根節(jié)點(diǎn)。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。13、若哈希函數(shù)H(key)=key%7，要將關(guān)鍵字38插入到長度為7的哈希表中，其存儲位置是：A.3B.5C.6D.014、數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型（ADT）是一種定義數(shù)據(jù)結(jié)構(gòu)的方式，它包括數(shù)據(jù)的存儲結(jié)構(gòu)和操作集合。以下關(guān)于ADT的說法中，錯(cuò)誤的是？（）A.ADT使得數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)與使用分離，提高了代碼的可維護(hù)性和可擴(kuò)展性。B.ADT可以用多種編程語言實(shí)現(xiàn)，不同的實(shí)現(xiàn)方式可能會有不同的性能和特點(diǎn)。C.ADT的操作集合包括插入、刪除、查找、遍歷等基本操作。D.ADT只適用于線性數(shù)據(jù)結(jié)構(gòu)，不適用于非線性數(shù)據(jù)結(jié)構(gòu)。15、以下關(guān)于字符串壓縮算法的描述，哪一項(xiàng)是不正確的？（）A.哈夫曼編碼可以根據(jù)字符出現(xiàn)頻率進(jìn)行壓縮B.LZW壓縮算法基于字典進(jìn)行壓縮C.壓縮算法一定能減小字符串的存儲空間D.不同的壓縮算法適用于不同類型的字符串16、若要對一棵二叉排序樹進(jìn)行中序遍歷，得到的序列是一個(gè)有序序列，這是因?yàn)槎媾判驑涞亩x具有什么特性？（）A.左子樹的值小于根節(jié)點(diǎn)，右子樹的值大于根節(jié)點(diǎn)B.左子樹和右子樹的深度相同C.每個(gè)節(jié)點(diǎn)的值都不同D.以上都不是17、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)18、在一個(gè)用數(shù)組實(shí)現(xiàn)的小根堆中，若要插入一個(gè)元素，應(yīng)該將其插入到數(shù)組的哪個(gè)位置？A.數(shù)組末尾B.堆頂C.任意位置D.以上都不對19、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，使用弗洛伊德算法求所有節(jié)點(diǎn)對之間的最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)20、排序算法的穩(wěn)定性和時(shí)間復(fù)雜度可以用于選擇合適的排序算法，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.穩(wěn)定性對于某些應(yīng)用場景非常重要，如對具有多個(gè)關(guān)鍵字的記錄進(jìn)行排序時(shí)。B.時(shí)間復(fù)雜度是衡量排序算法效率的重要指標(biāo)，不同的排序算法具有不同的時(shí)間復(fù)雜度。C.可以根據(jù)實(shí)際情況選擇穩(wěn)定的或不穩(wěn)定的排序算法，以及時(shí)間復(fù)雜度較低的排序算法。D.排序算法的穩(wěn)定性和時(shí)間復(fù)雜度只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）對于一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列，如何實(shí)現(xiàn)循環(huán)隊(duì)列的擴(kuò)容操作，給出算法思路和代碼實(shí)現(xiàn)。2、（本題10分）深入分析在一個(gè)具有n個(gè)元素的順序表中，如何進(jìn)行插入排序，并分析其時(shí)間復(fù)雜度。3、（本題10分）深入分析在一個(gè)具有n個(gè)元素的鏈表中，如何刪除指定區(qū)間內(nèi)的節(jié)點(diǎn)。4、（本題10分）解釋如何使用遞歸思