湖南財政經(jīng)濟(jì)學(xué)院《數(shù)據(jù)可視化》2023-2024學(xué)年期末試卷

自覺遵守考場紀(jì)律如考試作弊此答卷無效密自覺遵守考場紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁湖南財政經(jīng)濟(jì)學(xué)院

《數(shù)據(jù)可視化》2023-2024學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個節(jié)點(diǎn)的完全二叉樹中，其葉子節(jié)點(diǎn)的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-12、對于一個具有n個節(jié)點(diǎn)的二叉樹，其先序遍歷、中序遍歷和后序遍歷的結(jié)果都是唯一確定的，這個二叉樹一定是（）A.滿二叉樹B.完全二叉樹C.單支樹D.以上都不是3、在一個具有n個元素的鏈?zhǔn)疥犃兄?，若隊頭指針為front，隊尾指針為rear，要入隊一個元素，應(yīng)執(zhí)行的操作是？（）A.rear->next=newNode;rear=newNode;B.newNode->next=front;front=newNode;C.rear->next=newNode;front=newNode;D.newNode->next=rear;rear=newNode;4、在一棵二叉搜索樹中，刪除一個只有左子樹的節(jié)點(diǎn)，其右子樹的節(jié)點(diǎn)需要（）A.替換被刪除節(jié)點(diǎn)B.保持不動C.全部刪除D.移動到左子樹5、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則該二叉樹的后序遍歷序列為（）。A.CBEFDGAB.CEBFDGAC.CBEFGDAD.CEBFGDA6、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復(fù)雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復(fù)雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)7、若一個圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖8、對于一個具有n個節(jié)點(diǎn)的二叉樹，進(jìn)行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹的形狀為？A.只有一個根節(jié)點(diǎn)B.所有節(jié)點(diǎn)只有左子樹C.所有節(jié)點(diǎn)只有右子樹D.是一棵滿二叉樹9、在一個具有n個元素的有序雙向鏈表中，刪除一個節(jié)點(diǎn)并保持鏈表有序，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一個具有n個節(jié)點(diǎn)的帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，其時間復(fù)雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結(jié)構(gòu)11、在一個具有n個頂點(diǎn)的圖中，若存在回路，則深度優(yōu)先遍歷可能會出現(xiàn)什么情況？（）A.訪問某些頂點(diǎn)多次B.無法完成遍歷C.結(jié)果不正確D.以上都有可能12、隊列是一種先進(jìn)先出的線性表，若用一個數(shù)組實(shí)現(xiàn)循環(huán)隊列，隊頭指針front指向隊頭元素的前一個位置，隊尾指針rear指向隊尾元素，隊列最大容量為MAX_SIZE，那么判斷隊滿的條件是什么？（）A.(rear+1)%MAX_SIZE==frontB.rear==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-113、在一個具有n個頂點(diǎn)的連通圖中，生成樹的邊數(shù)一定為？（）A.n-1B.nC.n+1D.2n14、在一個具有n個元素的順序表中，在第i個元素（1<=i<=n）之前插入一個新元素時，需要向后移動的元素個數(shù)為：A.n-iB.iC.n-i+1D.n-i-115、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的最長公共子序列問題？A.二維數(shù)組B.棧C.隊列D.樹16、若要從一個具有n個元素的有序單鏈表中刪除所有值重復(fù)的元素，使得鏈表中每個元素的值都不同，最優(yōu)的算法時間復(fù)雜度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)17、在一個具有n個頂點(diǎn)和e條邊的無向圖中，使用鄰接矩陣存儲，進(jìn)行深度優(yōu)先遍歷，其時間復(fù)雜度為？A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)18、在數(shù)據(jù)結(jié)構(gòu)的應(yīng)用中，優(yōu)先隊列常用于實(shí)現(xiàn)任務(wù)調(diào)度，以下關(guān)于優(yōu)先隊列的描述，錯誤的是（）A.可以使用堆來實(shí)現(xiàn)B.元素的出隊順序按照優(yōu)先級確定C.插入元素的時間復(fù)雜度為O(logn)D.不支持修改元素的優(yōu)先級19、在一個二叉搜索樹中，進(jìn)行中序遍歷得到的序列是一個有序序列。若要刪除一個節(jié)點(diǎn)，并且保持二叉搜索樹的性質(zhì)不變，以下哪種情況處理起來最復(fù)雜？（）A.刪除葉子節(jié)點(diǎn)B.刪除只有一個子節(jié)點(diǎn)的節(jié)點(diǎn)C.刪除有兩個子節(jié)點(diǎn)的節(jié)點(diǎn)D.以上情況復(fù)雜度相同20、在一個具有n個元素的有序數(shù)組中，若要刪除一個特定元素，并且保持?jǐn)?shù)組的有序性，以下關(guān)于刪除操作的平均時間復(fù)雜度的描述，哪一項是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）闡述如何使用計數(shù)排序?qū)μ囟l件下的數(shù)據(jù)進(jìn)行排序，分析其優(yōu)缺點(diǎn)和適用場景。2、（本題10分）闡述如何在一個具有n個元素的順序表中，進(jìn)行查找操作，并分析其時間復(fù)雜度和空間復(fù)雜度。3、（本題10分）論述跳表在數(shù)據(jù)更新操作頻繁且數(shù)據(jù)量大的情況下的性能瓶頸及解決方案。4、（本題10分）解釋有向無環(huán)圖的概念，說明如何使用拓?fù)渑判驅(qū)τ邢驘o環(huán)圖進(jìn)行頂點(diǎn)的排序，并分析其時間復(fù)雜度。三、