北京林業(yè)大學(xué)《數(shù)據(jù)可視化》2022-2023學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)北京林業(yè)大學(xué)《數(shù)據(jù)可視化》

2022-2023學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)用數(shù)組實(shí)現(xiàn)的棧中，若要將棧的容量擴(kuò)大一倍，以下哪種操作的時(shí)間復(fù)雜度最低？（）A.重新創(chuàng)建一個(gè)更大的數(shù)組并復(fù)制元素B.逐步將元素移動(dòng)到新的更大的數(shù)組中C.直接在原數(shù)組后面追加空間D.以上操作時(shí)間復(fù)雜度相同2、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，使用深度優(yōu)先搜索算法遍歷所有節(jié)點(diǎn)，其時(shí)間復(fù)雜度主要取決于什么？A.邊的數(shù)量B.節(jié)點(diǎn)的數(shù)量C.圖的存儲(chǔ)方式D.以上都是3、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖中，使用弗洛伊德算法求所有頂點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(n2)C.O(n3)D.O(e3)4、在數(shù)據(jù)結(jié)構(gòu)中，鏈表的每個(gè)節(jié)點(diǎn)通常包含數(shù)據(jù)域和指針域。若要在一個(gè)單向鏈表中刪除一個(gè)指定節(jié)點(diǎn)，以下哪種操作是關(guān)鍵步驟？A.修改被刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)的指針B.修改被刪除節(jié)點(diǎn)的后一個(gè)節(jié)點(diǎn)的指針C.釋放被刪除節(jié)點(diǎn)的內(nèi)存D.以上都是5、對(duì)于一個(gè)用數(shù)組實(shí)現(xiàn)的小根堆，若要將堆頂元素與最后一個(gè)元素交換，然后重新調(diào)整堆，以下關(guān)于調(diào)整的方向，哪一項(xiàng)是正確的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先從堆頂向下調(diào)整，再?gòu)亩训紫蛏险{(diào)整D.以上都不對(duì)6、在一個(gè)具有n個(gè)元素的順序表中，若要將其逆置，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、在一個(gè)帶權(quán)無(wú)向圖中，使用普里姆算法構(gòu)造最小生成樹(shù)時(shí)，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個(gè)連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對(duì)8、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，采用中序遍歷將其轉(zhuǎn)換為一個(gè)有序的單鏈表。以下關(guān)于轉(zhuǎn)換過(guò)程的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(nlogn)C.O(n^2)D.O(n^3)9、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)中，其葉子節(jié)點(diǎn)的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-110、在一個(gè)具有n個(gè)元素的有序數(shù)組中，若要?jiǎng)h除一個(gè)特定元素，并且保持?jǐn)?shù)組的有序性，以下關(guān)于刪除操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)11、在一個(gè)循環(huán)隊(duì)列中，front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素的位置，隊(duì)列最大容量為MAXSIZE，若當(dāng)前隊(duì)列長(zhǎng)度為n，則判斷隊(duì)滿的條件是？（）A.(rear+1)%MAXSIZE==frontB.rear==frontC.rear+1==frontD.(rear-front+MAXSIZE)%MAXSIZE==MAXSIZE12、對(duì)于一個(gè)具有n個(gè)元素的無(wú)序數(shù)組，使用插入排序進(jìn)行排序，其最好情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)13、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實(shí)現(xiàn)字符串的模式匹配操作？A.二叉樹(shù)B.哈希表C.棧D.后綴樹(shù)14、在一個(gè)具有n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖中，使用拓?fù)渑判蛩惴?，其結(jié)果的唯一性如何？A.一定唯一B.可能不唯一C.取決于頂點(diǎn)的編號(hào)D.以上都不對(duì)15、在數(shù)據(jù)結(jié)構(gòu)中，優(yōu)先隊(duì)列可以用堆來(lái)實(shí)現(xiàn)，以下關(guān)于堆調(diào)整的描述，錯(cuò)誤的是（）A.插入元素時(shí)，從下往上調(diào)整堆B.刪除堆頂元素時(shí)，從上往下調(diào)整堆C.調(diào)整堆的過(guò)程中，節(jié)點(diǎn)的值可能會(huì)交換D.調(diào)整堆的時(shí)間復(fù)雜度與堆的大小無(wú)關(guān)16、在數(shù)據(jù)結(jié)構(gòu)中，線段樹(shù)的區(qū)間更新操作可以通過(guò)懶標(biāo)記實(shí)現(xiàn)，以下關(guān)于懶標(biāo)記的描述，不正確的是（）A.減少不必要的節(jié)點(diǎn)更新B.提高更新操作的效率C.可能會(huì)導(dǎo)致查詢結(jié)果不準(zhǔn)確D.標(biāo)記需要在適當(dāng)?shù)臅r(shí)候向下傳遞17、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以18、已知一個(gè)完全二叉樹(shù)的節(jié)點(diǎn)總數(shù)為100，其葉子節(jié)點(diǎn)的個(gè)數(shù)為（）。A.49B.50C.51D.不確定19、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣存儲(chǔ)，則存儲(chǔ)空間的復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)20、在一個(gè)哈希表中，若采用線性探測(cè)法解決哈希沖突，當(dāng)發(fā)生沖突時(shí)，新元素會(huì)存儲(chǔ)在什么位置？A.沖突位置的下一個(gè)位置B.沖突位置C.隨機(jī)位置D.以上都不對(duì)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述跳表在數(shù)據(jù)更新操作頻繁且數(shù)據(jù)量大的情況下的性能瓶頸及解決方案。2、（本題10分）詳細(xì)闡述在哈希表的擴(kuò)容過(guò)程中，如何重新計(jì)算哈希值并遷移數(shù)據(jù)，以保證性能。3、（本題10分）比較插入排序和歸并排序在數(shù)據(jù)量較大時(shí)的性能差異。4、（本題10分）描述二叉樹(shù)的遍歷算法在二叉樹(shù)的最大路