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

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

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