常州大學《數(shù)據(jù)可視化》2022-2023學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁常州大學《數(shù)據(jù)可視化》

2022-2023學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一棵平衡二叉樹中，插入一個新節(jié)點后可能導致失衡，需要進行調整。以下哪種調整操作可能涉及到旋轉次數(shù)最多？（）A.LL型調整B.RR型調整C.LR型調整D.RL型調整2、對于一個具有n個元素的快速排序，每次劃分選取的基準元素不同，對排序的時間復雜度有何影響？（）A.沒有影響B(tài).可能會提高C.可能會降低D.以上都不對3、以下關于哈希沖突解決方法中二次探測法的描述，哪一項是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)4、對于一個循環(huán)隊列，若隊頭指針為front，隊尾指針為rear，隊列最大容量為MAX_SIZE，那么判斷隊空的條件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-15、在一個具有n個頂點的帶權有向圖中，使用迪杰斯特拉（Dijkstra）算法求單源最短路徑。以下關于該算法的時間復雜度的描述，哪一項是準確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)6、在一個具有n個頂點的有向強連通圖中，至少需要多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)7、若一個圖的廣度優(yōu)先遍歷序列為ABCDEFG，則其深度優(yōu)先遍歷序列可能為？（）A.ABDCEFGB.ACBDEFGC.ADBCEFGD.AECBDFG8、對于一個具有n個頂點的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同9、在一個有序表（12,24,36,48,60,72,84）中，使用二分查找法查找48，需要比較的次數(shù)是：A.1B.2C.3D.410、棧和隊列的操作可以用棧和隊列的基本操作來實現(xiàn)，以下關于它們的操作實現(xiàn)的說法中，錯誤的是？（）A.可以用兩個棧實現(xiàn)一個隊列，也可以用兩個隊列實現(xiàn)一個棧。B.用棧實現(xiàn)隊列時，需要考慮隊列的先進先出特性，可能需要使用輔助棧。C.用隊列實現(xiàn)棧時，需要考慮棧的后進先出特性，可能需要使用輔助隊列。D.棧和隊列的操作只能用棧和隊列的基本操作來實現(xiàn)，不能用其他數(shù)據(jù)結構來輔助實現(xiàn)。11、設有一個帶權無向圖，采用Prim算法生成最小生成樹。在算法執(zhí)行過程中，每次選擇的邊都是權值最小的邊。以下關于Prim算法的時間復雜度的描述，哪一項是準確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(elogv)（其中n為頂點數(shù)，e為邊數(shù)）12、對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素。以下關于二分查找的時間復雜度的描述，哪一個是恰當?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)13、在一個具有n個節(jié)點的無向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以14、在一個堆排序中，最大堆用于升序排序，最小堆用于降序排序。那么對于一個初始無序的數(shù)組，構建最大堆的時間復雜度是多少？（）A.O(n)B.O(log?n)C.O(nlog?n)D.O(n2)15、設有一個帶頭結點的單鏈表，頭指針為head，若要在第一個元素之前插入一個新元素，則需要執(zhí)行的操作是（）。A.s->next=head;head=s;B.s->next=head->next;head->next=s;C.head->next=s;s->next=head;D.s->next=head;s=head;16、在一個具有n個頂點的強連通圖中，至少有多少條邊？（）A.n-1B.nC.n(n-1)/2D.n(n-1)17、在一棵AVL樹中，進行插入操作后，可能導致樹失去平衡，此時需要進行的旋轉操作最多為（）A.1次B.2次C.logn次D.n次18、對于一個具有n個節(jié)點的二叉排序樹，刪除一個節(jié)點后，重新調整為二叉排序樹，其時間復雜度最壞情況下為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在一個有向圖中，所有頂點的入度之和與出度之和的關系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.沒有確定的關系20、對于一個具有n個元素的無序鏈表，若要對其進行排序，以下哪種排序算法較為合適？（）A.冒泡排序B.快速排序C.插入排序D.選擇排序二、簡答題（本大題共4個小題，共40分)1、（本題10分）對于一個用鏈表實現(xiàn)的有序表，解釋如何合并兩個有序鏈表為一個新的有序鏈表，給出算法步驟和時間復雜度分析。2、（本題10分）論述在有向圖中，如何判斷是否存在回路，以及如何找出所有的強連通分量。3、（本題10分）闡述如何在一個具有n個元素的無序數(shù)組中，使用冒泡排序算法進行排序，并分析其時間復雜度和空間復雜度。4、（本題10分）闡述二叉樹的定義和基本性質，說明二叉樹的遍歷方式有哪些，并