成都錦城學(xué)院《數(shù)據(jù)可視化》2023-2024學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)成都錦城學(xué)院《數(shù)據(jù)可視化》

2023-2024學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下哪種排序算法在數(shù)據(jù)基本有序時(shí)的時(shí)間復(fù)雜度接近O(n)？A.冒泡排序B.快速排序C.插入排序D.選擇排序2、棧和隊(duì)列的操作可以用棧和隊(duì)列的基本操作來實(shí)現(xiàn)，以下關(guān)于它們的操作實(shí)現(xiàn)的說法中，錯(cuò)誤的是？（）A.可以用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列，也可以用兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧。B.用棧實(shí)現(xiàn)隊(duì)列時(shí)，需要考慮隊(duì)列的先進(jìn)先出特性，可能需要使用輔助棧。C.用隊(duì)列實(shí)現(xiàn)棧時(shí)，需要考慮棧的后進(jìn)先出特性，可能需要使用輔助隊(duì)列。D.棧和隊(duì)列的操作只能用棧和隊(duì)列的基本操作來實(shí)現(xiàn)，不能用其他數(shù)據(jù)結(jié)構(gòu)來輔助實(shí)現(xiàn)。3、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（1<=i<=n），需要移動(dòng)多少個(gè)元素？（）A.n-iB.iC.n-i+1D.n-i-14、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖中，采用鄰接表存儲(chǔ)，其時(shí)間復(fù)雜度為？（）A.O(n+e)B.O(n2)C.O(e2)D.O(ne)5、對(duì)于一個(gè)用鏈表實(shí)現(xiàn)的棧，若要在棧頂插入一個(gè)元素，時(shí)間復(fù)雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)6、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的存儲(chǔ)？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊(duì)列D.數(shù)組和哈希表7、在一個(gè)用鄰接表存儲(chǔ)的有向圖中，若要計(jì)算某個(gè)節(jié)點(diǎn)的出度，以下哪種方法較為高效？A.遍歷該節(jié)點(diǎn)的鄰接表B.遍歷整個(gè)圖的鄰接表C.無法高效計(jì)算D.以上都不對(duì)8、對(duì)于一個(gè)具有n個(gè)元素的哈希表，若采用鏈地址法處理沖突，以下關(guān)于查找操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接表存儲(chǔ)時(shí)，其空間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)10、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的無向圖中，若采用鄰接表存儲(chǔ)，則存儲(chǔ)空間復(fù)雜度主要取決于？A.nB.mC.n+mD.n^211、在數(shù)據(jù)結(jié)構(gòu)中，使用并查集解決集合合并問題時(shí)，以下關(guān)于路徑壓縮的描述，錯(cuò)誤的是（）A.可以提高查找效率B.不改變集合的關(guān)系C.增加了合并操作的復(fù)雜度D.使樹的高度降低12、已知一個(gè)棧的進(jìn)棧序列為1,2,3,4，出棧序列為3,2,4,1，則棧的容量至少為（）。A.2B.3C.4D.513、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)14、對(duì)于一個(gè)采用鏈表存儲(chǔ)的棧，若要獲取棧的大?。ㄔ?cái)?shù)量），以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、在一個(gè)循環(huán)隊(duì)列中，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，若rear>front，則隊(duì)列中的元素個(gè)數(shù)為？A.rear-frontB.rear-front+MAXSIZEC.rear-front-1D.(rear-front+MAXSIZE)%MAXSIZE16、已知一個(gè)圖的鄰接表如下所示，則從頂點(diǎn)V1出發(fā)進(jìn)行廣度優(yōu)先遍歷，可能得到的頂點(diǎn)訪問序列是（）。V1:->V2->V3V2:->V4V3:->V4->V5V4:->V5V5:A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V4,V3,V5D.V1,V4,V2,V3,V517、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉排序樹，刪除一個(gè)節(jié)點(diǎn)后，重新調(diào)整為二叉排序樹，其時(shí)間復(fù)雜度最壞情況下為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、在一個(gè)用鏈表實(shí)現(xiàn)的隊(duì)列中，若要實(shí)現(xiàn)隊(duì)列的遍歷操作，以下哪種方式較為合適？A.從隊(duì)頭開始，依次訪問每個(gè)節(jié)點(diǎn)B.從隊(duì)尾開始，依次向前訪問每個(gè)節(jié)點(diǎn)C.隨機(jī)訪問鏈表中的節(jié)點(diǎn)D.以上都不對(duì)19、以下關(guān)于圖的存儲(chǔ)結(jié)構(gòu)的描述，錯(cuò)誤的是：A.鄰接矩陣適合存儲(chǔ)稠密圖B.鄰接表適合存儲(chǔ)稀疏圖C.十字鏈表是鄰接表和逆鄰接表的結(jié)合D.鄰接多重表只適合無向圖20、對(duì)于一個(gè)采用順序存儲(chǔ)的棧，若棧頂指針top等于-1時(shí)，表示：A.棧滿B.棧空C.棧中只有一個(gè)元素D.棧中至少有一個(gè)元素二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)說明冒泡排序算法的優(yōu)化思路和具體實(shí)現(xiàn)方法，并舉例說明優(yōu)化后的效果。2、（本題10分）解釋什么是斐波那契堆的合并操作及其時(shí)間復(fù)雜度。3、（本題10分）解釋如何使用循環(huán)鏈表解決約瑟夫環(huán)問題，說明問題的背景和解決方案，并分析其時(shí)間復(fù)雜度。4、（本題10分）詳細(xì)闡述在哈夫曼編碼的擴(kuò)展應(yīng)用中，如何處理不同長(zhǎng)度的編碼以及解碼的復(fù)雜性。三、設(shè)計(jì)題（本大題共2個(gè)小題，共