成都錦城學(xué)院《數(shù)據(jù)可視化技術(shù)實(shí)訓(xùn)》2021-2022學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁(yè)，共3頁(yè)成都錦城學(xué)院

《數(shù)據(jù)可視化技術(shù)實(shí)訓(xùn)》2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、以下關(guān)于字符串匹配算法的描述，哪一項(xiàng)是不正確的？（）A.BF算法的時(shí)間復(fù)雜度在最壞情況下較高B.KMP算法通過(guò)利用已匹配的部分信息來(lái)提高效率C.BM算法在一般情況下比KMP算法效率更高D.所有字符串匹配算法的時(shí)間復(fù)雜度都與模式串的長(zhǎng)度成正比2、以下關(guān)于哈希沖突解決方法中二次探測(cè)法的描述，哪一項(xiàng)是不正確的？（）A.可以減少聚集現(xiàn)象B.探測(cè)的位置是連續(xù)的C.可能會(huì)出現(xiàn)找不到空閑位置的情況D.相比線性探測(cè)法，性能更優(yōu)3、在一個(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)%MAXSIZE4、以下哪種排序算法在最壞情況下的交換次數(shù)最少？A.冒泡排序B.快速排序C.選擇排序D.插入排序5、隊(duì)列也是一種線性表，遵循先進(jìn)先出原則。在一個(gè)循環(huán)隊(duì)列中，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAXSIZE，那么判斷隊(duì)列為空的條件是什么？A.front==rearB.(rear+1)%MAXSIZE==frontC.front==(rear+1)%MAXSIZED.以上都不對(duì)6、對(duì)于一個(gè)滿二叉樹，若其高度為h，則其節(jié)點(diǎn)總數(shù)為多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-17、在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，邊的數(shù)量為？（）A.n(n-1)/2B.n(n-1)C.n^2D.2n8、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)其下三角部分，第一個(gè)元素A[1,1]存儲(chǔ)在數(shù)組B[0]中，若A[8,5]在數(shù)組B中的存儲(chǔ)位置為k，則A[7,5]在數(shù)組B中的存儲(chǔ)位置為（）。A.k-13B.k-12C.k-11D.k-109、在一棵平衡二叉樹中，插入一個(gè)新節(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)整10、對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，若要查找某個(gè)元素是否存在，以下哪種查找算法效率最高？（）A.順序查找B.二分查找C.分塊查找D.以上算法效率相同11、已知一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖采用鄰接矩陣存儲(chǔ)，若要?jiǎng)h除所有的邊，時(shí)間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(nlogn)D.O(e)12、對(duì)于一個(gè)具有n個(gè)元素的雙向鏈表，若要在第i個(gè)位置（1<=i<=n）之前插入一個(gè)新節(jié)點(diǎn)，平均需要修改多少個(gè)指針？（）A.1B.2C.3D.413、隊(duì)列是一種先進(jìn)先出的線性表，若用一個(gè)數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列，隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置，隊(duì)尾指針rear指向隊(duì)尾元素，隊(duì)列最大容量為MAX_SIZE，那么判斷隊(duì)滿的條件是什么？（）A.(rear+1)%MAX_SIZE==frontB.rear==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-114、在一個(gè)有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，采用鄰接矩陣存儲(chǔ)，其空間復(fù)雜度為多少？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)15、以下哪種排序算法的空間復(fù)雜度最低？A.歸并排序B.快速排序C.冒泡排序D.插入排序16、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的棧中，進(jìn)行入棧和出棧操作時(shí)，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.入棧和出棧的時(shí)間復(fù)雜度均為O(1)B.入棧的時(shí)間復(fù)雜度為O(n)，出棧的時(shí)間復(fù)雜度為O(1)C.入棧的時(shí)間復(fù)雜度為O(1)，出棧的時(shí)間復(fù)雜度為O(n)D.入棧和出棧的時(shí)間復(fù)雜度均為O(n)17、圖的存儲(chǔ)方式和遍歷方式可以用于解決很多實(shí)際問(wèn)題，以下關(guān)于它們的應(yīng)用的說(shuō)法中，錯(cuò)誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，適用于社交網(wǎng)絡(luò)分析和交通網(wǎng)絡(luò)規(guī)劃等。B.圖的鄰接表可以用于表示稀疏圖，適用于地圖繪制和電路圖設(shè)計(jì)等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問(wèn)題和最小生成樹問(wèn)題等，適用于物流配送和通信網(wǎng)絡(luò)優(yōu)化等。D.圖的存儲(chǔ)方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒(méi)有實(shí)際價(jià)值。18、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行刪除堆頂元素的操作，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)19、在一個(gè)大根堆中，刪除堆頂元素后，為了重新調(diào)整為大根堆，需要進(jìn)行的操作是？（）A.將最后一個(gè)元素移到堆頂，然后從堆頂向下調(diào)整B.將堆中所有元素重新排序C.將堆頂元素與最后一個(gè)元素交換，然后從堆頂向下調(diào)整D.無(wú)需調(diào)整20、隊(duì)列是另一種特殊的線性數(shù)據(jù)結(jié)構(gòu)，它遵循先進(jìn)先出（FIFO）的原則。以下關(guān)于隊(duì)列的說(shuō)法中，錯(cuò)誤的是？（）A.隊(duì)列可以用數(shù)組或鏈表實(shí)現(xiàn)。B.隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)首進(jìn)行。C.隊(duì)列可以用于實(shí)現(xiàn)任務(wù)調(diào)度、消息傳遞等。D.隊(duì)列的容量是無(wú)限的，可以存儲(chǔ)任意數(shù)量的元素。二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述伸展樹在刪除元素后的調(diào)整機(jī)制和性能影響。2、（本題10分）解釋如何在一個(gè)鏈表中實(shí)現(xiàn)插入排序，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題10分）對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的有向圖，如何使用拓?fù)渑判蛩惴ń鉀Q課程安排問(wèn)題？4、（本題10分）詳細(xì)說(shuō)明在最短路徑問(wèn)題的變種中，如多源最短路徑問(wèn)題，如何求解。三、設(shè)計(jì)題（本大題共2個(gè)小題，共2