成都錦城學(xué)院《數(shù)據(jù)可視化技術(shù)與應(yīng)用》2023-2024學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁成都錦城學(xué)院

《數(shù)據(jù)可視化技術(shù)與應(yīng)用》2023-2024學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個具有n個節(jié)點(diǎn)的二叉樹中，若采用后序遍歷得到的節(jié)點(diǎn)序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定2、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），需要移動的元素個數(shù)最多為（）。A.i-1B.n-iC.n-i+1D.n-13、以下關(guān)于哈希沖突解決方法中二次探測法的描述，哪一項(xiàng)是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)4、以下關(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)先搜索一定能找到最短路徑5、設(shè)有一個m階的B樹，每個非葉子節(jié)點(diǎn)至少有┌m/2┐個孩子，則一棵3階B樹中，根節(jié)點(diǎn)最少有幾個孩子？（）A.1B.2C.3D.46、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)并查集？（）A.數(shù)組B.鏈表C.樹D.哈希表7、在一個具有n個元素的大根堆中，刪除堆頂元素后，將最后一個元素放到堆頂，然后進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)8、在一個具有n個元素的順序表中，若要將其逆置，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是恰當(dāng)?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)9、對于一個具有n個元素的雙向循環(huán)鏈表，若要刪除第i個節(jié)點(diǎn)（1<=i<=n），平均需要修改多少個指針？（）A.2B.3C.4D.510、對于一個滿二叉樹，若其高度為h，則其節(jié)點(diǎn)總數(shù)為多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-111、若要在一個已排序的數(shù)組中使用二分查找算法查找一個特定元素，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)12、對于一個具有n個元素的選擇排序，在最壞情況下，需要進(jìn)行多少次交換操作？（）A.n-1B.nC.n(n-1)/2D.013、在一個具有n個頂點(diǎn)的無向圖中，使用廣度優(yōu)先遍歷算法。以下關(guān)于遍歷過程中使用的輔助隊(duì)列的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(n^2)14、在一個具有n個元素的順序表中，若要查找一個元素，平均需要比較多少次？（）A.n/2B.nC.lognD.不確定15、在一棵二叉樹中，若度為2的節(jié)點(diǎn)有10個，度為1的節(jié)點(diǎn)有20個，那么葉子節(jié)點(diǎn)的數(shù)量是多少？A.11B.21C.30D.無法確定16、在一個具有n個元素的單鏈表中，若要在第i個位置（1<=i<=n）插入一個新元素，平均需要遍歷多少個節(jié)點(diǎn)？（）A.i-1B.iC.(i-1)/2D.i/217、圖的存儲方式和遍歷方式對圖的操作效率有很大影響，以下關(guān)于它們的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，查找邊的時(shí)間復(fù)雜度為O(1)，但空間復(fù)雜度較高。B.鄰接表適合存儲稀疏圖，插入邊和刪除邊的時(shí)間復(fù)雜度為O(1)，但查找邊的時(shí)間復(fù)雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時(shí)間復(fù)雜度都為O(n+m)，其中n是頂點(diǎn)數(shù)，m是邊數(shù)。D.圖的存儲方式和遍歷方式一旦確定，就不能再改變，否則會影響圖的操作效率。18、在一個有向無環(huán)圖中，進(jìn)行拓?fù)渑判虻慕Y(jié)果是唯一的嗎？A.一定唯一B.一定不唯一C.可能唯一，也可能不唯一D.以上都不對19、在一個具有n個元素的小根堆中，最小元素的值位于（）。A.根節(jié)點(diǎn)B.任意節(jié)點(diǎn)C.葉子節(jié)點(diǎn)D.無法確定20、跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，用于實(shí)現(xiàn)有序集合的快速查找。關(guān)于跳表的特點(diǎn)，以下描述錯誤的是（）A.跳表的查找、插入和刪除操作的平均時(shí)間復(fù)雜度為O(logn)B.跳表通過增加索引層次來提高查找效率C.跳表的空間復(fù)雜度比普通鏈表高D.跳表的性能不如二叉搜索樹二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述在一個具有n個頂點(diǎn)的無向圖中，如何使用廣度優(yōu)先搜索算法來生成連通分量。2、（本題10分）比較插入排序和歸并排序在數(shù)據(jù)量較大時(shí)的性能差異。3、（本題10分）詳細(xì)說明如何在一個圖中進(jìn)行最短路徑的更新操作（如增加新的邊或修改邊的權(quán)值），給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。4、（本題10分）詳細(xì)闡述如何在一個具有n個元素的雙向鏈表中，進(jìn)行高效的刪除操作，