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

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

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