北方民族大學(xué)《數(shù)據(jù)可視化實(shí)驗(yàn)》2022-2023學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁北方民族大學(xué)《數(shù)據(jù)可視化實(shí)驗(yàn)》

2022-2023學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD2、對于一個m行n列的二維數(shù)組，按行優(yōu)先存儲時，元素a[i][j]（0<=i<m,0<=j<n）的地址計(jì)算公式為：A.LOC(a[i][j])=LOC(a[0][0])+i*n+jB.LOC(a[i][j])=LOC(a[0][0])+j*m+iC.LOC(a[i][j])=LOC(a[0][0])+i*m+jD.LOC(a[i][j])=LOC(a[0][0])+j*n+i3、在一個具有n個元素的最小堆中，插入一個新元素并調(diào)整為最小堆，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、在圖的最小生成樹算法中，Kruskal算法和Prim算法都能得到最小生成樹，以下關(guān)于這兩個算法的比較，錯誤的是（）A.Kruskal算法基于邊，Prim算法基于節(jié)點(diǎn)B.Kruskal算法需要使用并查集C.Prim算法的時間復(fù)雜度通常比Kruskal算法低D.對于稀疏圖，Kruskal算法更優(yōu)5、對于一個具有n個節(jié)點(diǎn)的二叉樹，進(jìn)行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹的形狀為？A.只有一個根節(jié)點(diǎn)B.所有節(jié)點(diǎn)只有左子樹C.所有節(jié)點(diǎn)只有右子樹D.是一棵滿二叉樹6、對于一個棧，若入棧序列為1、2、3、4、5，在入棧過程中可以出棧，則可能得到的出棧序列有多少種？（）A.5B.14C.21D.無數(shù)種7、在一個具有n個元素的順序表中，若要在第i個元素（1<=i<=n）之前插入一個新元素，需要移動的元素個數(shù)為？（）A.n-iB.iC.n-i+1D.n-i-18、在一個具有n個元素的二叉排序樹中，查找一個不存在的元素，其時間復(fù)雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)9、設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序?yàn)橹鞔鎯ζ湎氯遣糠?，第一個元素A[1,1]存儲在數(shù)組B[0]中，若A[8,5]在數(shù)組B中的存儲位置為k，則A[7,5]在數(shù)組B中的存儲位置為（）。A.k-13B.k-12C.k-11D.k-1010、在數(shù)據(jù)結(jié)構(gòu)中，使用并查集解決集合合并問題時，以下關(guān)于路徑壓縮的描述，錯誤的是（）A.可以提高查找效率B.不改變集合的關(guān)系C.增加了合并操作的復(fù)雜度D.使樹的高度降低11、對于一個具有n個節(jié)點(diǎn)的帶權(quán)有向圖，使用迪杰斯特拉算法求最短路徑，其時間復(fù)雜度為？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)12、對于一個具有n個元素的無序數(shù)組，使用快速排序算法進(jìn)行排序，在平均情況下的空間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)13、隊(duì)列也是一種線性表，遵循先進(jìn)先出原則。在一個循環(huán)隊(duì)列中，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，那么判斷隊(duì)列為空的條件是什么？A.front==rearB.(rear+1)%MAXSIZE==frontC.front==(rear+1)%MAXSIZED.以上都不對14、若一個圖的鄰接矩陣對角線以下（不包括對角線）的元素全為0，則該圖一定是：A.無向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖15、在一個具有n個頂點(diǎn)的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n16、在一個用順序存儲結(jié)構(gòu)實(shí)現(xiàn)的棧中，若棧頂指針top指向棧頂元素的上一個位置，當(dāng)棧為空時，top的值為？A.-1B.0C.1D.n-1（其中n為棧的最大容量）17、圖的存儲方式和遍歷方式對圖的操作效率有很大影響，以下關(guān)于它們的說法中，錯誤的是？（）A.鄰接矩陣適合存儲稠密圖，查找邊的時間復(fù)雜度為O(1)，但空間復(fù)雜度較高。B.鄰接表適合存儲稀疏圖，插入邊和刪除邊的時間復(fù)雜度為O(1)，但查找邊的時間復(fù)雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時間復(fù)雜度都為O(n+m)，其中n是頂點(diǎn)數(shù)，m是邊數(shù)。D.圖的存儲方式和遍歷方式一旦確定，就不能再改變，否則會影響圖的操作效率。18、在一個用數(shù)組實(shí)現(xiàn)的小根堆中，若要插入一個元素，應(yīng)該將其插入到數(shù)組的哪個位置？A.數(shù)組末尾B.堆頂C.任意位置D.以上都不對19、在一個帶權(quán)的有向圖中，使用迪杰斯特拉算法求從源點(diǎn)到其他頂點(diǎn)的最短路徑，每次選擇的頂點(diǎn)是？（）A.距離源點(diǎn)最近的頂點(diǎn)B.距離源點(diǎn)最遠(yuǎn)的頂點(diǎn)C.未確定最短路徑的頂點(diǎn)中權(quán)值最小的頂點(diǎn)D.未確定最短路徑的頂點(diǎn)中權(quán)值最大的頂點(diǎn)20、在一個循環(huán)鏈表中，若要刪除鏈表中的最后一個節(jié)點(diǎn)，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細(xì)說明如何在一個具有n個元素的順序表中，進(jìn)行刪除操作，并分析其時間復(fù)雜度和空間復(fù)雜度。2、（本題10分）解釋什么是哈希表沖突，以及常見的解決哈希表沖突的方法有哪些？3、（本題10分）解釋如何使用跳表實(shí)現(xiàn)有序集合的插入、刪除和查找操作，分析其時間復(fù)雜度和空間復(fù)雜度。4、（本題10分）解釋線段