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

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

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