長(zhǎng)春工業(yè)大學(xué)《數(shù)據(jù)可視化技術(shù)》2021-2022學(xué)年期末試卷

自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁長(zhǎng)春工業(yè)大學(xué)《數(shù)據(jù)可視化技術(shù)》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)順序存儲(chǔ)的棧中，若要實(shí)現(xiàn)共享?xiàng)?，即兩個(gè)棧共用一個(gè)數(shù)組空間，以下關(guān)于棧頂指針的設(shè)置，哪一種方案較為合理？A.兩個(gè)棧的棧頂指針分別從數(shù)組的兩端向中間移動(dòng)B.兩個(gè)棧的棧頂指針都從數(shù)組的同一端開始移動(dòng)C.一個(gè)棧的棧頂指針從數(shù)組的開頭移動(dòng)，另一個(gè)從結(jié)尾移動(dòng)D.以上都可以2、若哈希函數(shù)H(key)=key%7，要將關(guān)鍵字38插入到長(zhǎng)度為7的哈希表中，其存儲(chǔ)位置是：A.3B.5C.6D.03、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的紅黑樹，插入一個(gè)新節(jié)點(diǎn)后，調(diào)整樹的結(jié)構(gòu)以保持紅黑樹性質(zhì)，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、以下關(guān)于樹的存儲(chǔ)結(jié)構(gòu)的描述，哪一項(xiàng)是不正確的？（）A.孩子兄弟表示法可以方便地實(shí)現(xiàn)樹的遍歷B.雙親表示法便于查找一個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)C.孩子鏈表表示法在處理多叉樹時(shí)空間利用率較高D.以上存儲(chǔ)結(jié)構(gòu)在時(shí)間復(fù)雜度上沒有明顯差異5、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表，要查找一個(gè)值為x的元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.16、對(duì)于一個(gè)具有n個(gè)元素的哈希表，負(fù)載因子越大，發(fā)生沖突的可能性如何變化？（）A.越大B.越小C.不變D.不確定7、一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接表存儲(chǔ)，其空間復(fù)雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)8、對(duì)于一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front9、以下哪種排序算法是穩(wěn)定的排序算法？A.快速排序B.選擇排序C.冒泡排序D.希爾排序10、以下哪種排序算法對(duì)大規(guī)模數(shù)據(jù)排序時(shí)，通常不被優(yōu)先選擇？A.冒泡排序B.插入排序C.快速排序D.歸并排序11、設(shè)有一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無向圖，使用普里姆（Prim）算法求最小生成樹。在算法執(zhí)行過程中，需要選擇一個(gè)頂點(diǎn)作為起始點(diǎn)。以下關(guān)于起始點(diǎn)選擇對(duì)算法時(shí)間復(fù)雜度的影響，哪一個(gè)是恰當(dāng)?shù)?？A.起始點(diǎn)的選擇對(duì)時(shí)間復(fù)雜度沒有影響B(tài).選擇不同的起始點(diǎn)可能導(dǎo)致時(shí)間復(fù)雜度不同C.選擇頂點(diǎn)度最小的作為起始點(diǎn)可以降低時(shí)間復(fù)雜度D.選擇頂點(diǎn)度最大的作為起始點(diǎn)可以降低時(shí)間復(fù)雜度12、以下哪種數(shù)據(jù)結(jié)構(gòu)適合頻繁進(jìn)行插入和刪除操作，并且能夠快速查找最大元素？（）A.數(shù)組B.鏈表C.棧D.最大堆13、在一個(gè)用數(shù)組實(shí)現(xiàn)的棧中，若要將棧的容量擴(kuò)大一倍，以下哪種操作的時(shí)間復(fù)雜度最低？（）A.重新創(chuàng)建一個(gè)更大的數(shù)組并復(fù)制元素B.逐步將元素移動(dòng)到新的更大的數(shù)組中C.直接在原數(shù)組后面追加空間D.以上操作時(shí)間復(fù)雜度相同14、在一個(gè)具有n個(gè)元素的雙向鏈表中，刪除一個(gè)指定節(jié)點(diǎn)，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)15、若一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB16、在一棵平衡二叉樹中，插入一個(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)整17、對(duì)于一個(gè)具有n個(gè)元素的棧，若要實(shí)現(xiàn)將棧中元素逆置，需要借助的輔助數(shù)據(jù)結(jié)構(gòu)為？（）A.隊(duì)列B.棧C.鏈表D.數(shù)組18、對(duì)于一個(gè)大根堆，若將堆中所有元素按照層次遍歷的順序存儲(chǔ)到一個(gè)數(shù)組中，以下關(guān)于數(shù)組元素的排列，哪一項(xiàng)是正確的？A.完全無序B.從左到右依次遞減C.從左到右依次遞增D.以上都不對(duì)19、設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.1543220、在一個(gè)具有n個(gè)元素的雙向循環(huán)鏈表中，刪除一個(gè)節(jié)點(diǎn)后，需要修改幾個(gè)指針？A.2B.3C.4D.5二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)論述在利用二叉樹進(jìn)行按層遍歷的過程中，如何使用隊(duì)列實(shí)現(xiàn)，并處理空層的情況，給出具體的算法步驟和代碼實(shí)現(xiàn)。2、（本題10分）詳細(xì)說明如何在一個(gè)具有n個(gè)元素的隊(duì)列中，實(shí)現(xiàn)元素的循環(huán)移位，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題10分）分析在字符串匹配中，Sunday算法的工作原理和特點(diǎn)。4、（本題10分）數(shù)組和鏈表在存儲(chǔ)數(shù)據(jù)方面有哪些不同之處？各自的優(yōu)缺點(diǎn)是什么？三、設(shè)計(jì)題（本大題