浙江工業(yè)大學之江學院《數據可視化》2022-2023學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁浙江工業(yè)大學之江學院

《數據可視化》2022-2023學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下哪種數據結構可以方便地實現(xiàn)集合的交集運算，并具有較低的時間復雜度？A.鏈表B.二叉搜索樹C.哈希表D.并查集2、若一棵二叉樹的先序遍歷序列和后序遍歷序列分別為ABC和CBA，則其中序遍歷序列為：A.BCAB.CABC.ABCD.無法確定3、在一個具有n個頂點的有向圖中，若所有頂點的出度之和為m，入度之和為k，則m和k之間的關系是？（）A.m=kB.m>kC.m<kD.m+k=n4、在一個順序存儲的數組中實現(xiàn)一個簡單的棧結構，若棧頂指針top初始值為-1，當進行一次入棧操作后，top的值應該如何變化？A.top不變B.top=top+1C.top=top-1D.top=05、在數據結構中，伸展樹（SplayTree）通過自調整保持較好的性能，以下關于伸展樹的操作，不正確的是（）A.查找操作會將被查找的節(jié)點旋轉到根節(jié)點B.插入操作可能會引起多次旋轉C.伸展樹的平均性能較好D.伸展樹的空間復雜度較高6、以下關于哈希表沖突解決方法的描述，哪一項是不正確的？（）A.鏈地址法會增加存儲空間的開銷B.開放定址法的查找效率一定高于鏈地址法C.再哈希法可以減少沖突的發(fā)生D.建立公共溢出區(qū)可以存儲發(fā)生沖突的元素7、在一棵度為4的樹中，度為4的節(jié)點個數為1，度為3的節(jié)點個數為2，度為2的節(jié)點個數為3，度為1的節(jié)點個數為4，葉子節(jié)點個數為（）。A.15B.16C.17D.188、在一個鏈式存儲的隊列中，若隊頭指針為front，隊尾指針為rear，要刪除隊頭元素，需要進行的操作是？（）A.front=front->next;B.rear=front;C.rear=rear->next;D.front=NULL;9、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則該二叉樹的后序遍歷序列為（）。A.CBEFDGAB.CEBFDGAC.CBEFGDAD.CEBFGDA10、在一個長度為n的順序表中，刪除第i個元素（1<=i<=n）時，需要移動的元素個數為：A.n-iB.i-1C.n-i+1D.i11、已知一個圖的鄰接矩陣如下所示，則從頂點V1出發(fā)進行深度優(yōu)先遍歷，可能得到的頂點訪問序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V512、對于一個大根堆，若要刪除堆頂元素并保持堆的性質，以下哪種操作是正確的？A.將堆底元素移到堆頂，然后從堆頂向下調整B.將堆頂元素直接刪除，不進行其他操作C.將堆頂元素與任意子節(jié)點交換，然后調整D.以上都不對13、若一棵二叉樹的中序遍歷序列是ABCDEFG，后序遍歷序列是BDCAFGE，則其先序遍歷序列是（）。A.EACBDGFB.EACFBDGC.EAGCFBDD.EAGFCDB14、在一個具有n個節(jié)點的二叉樹中，若先序遍歷序列為ABC，中序遍歷序列為BAC，則后序遍歷序列是什么？A.BCAB.CBAC.ACBD.無法確定15、在一個具有n個頂點的無向圖中，若每個頂點的度都為k，則邊的數量為多少？（）A.nk/2B.nkC.n(k-1)/2D.n(k-1)16、以下關于哈希沖突解決方法中二次探測法的描述，哪一項是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)17、對于一個有向無環(huán)圖（DAG），進行拓撲排序的方法不止一種。以下關于拓撲排序的描述，錯誤的是（）A.可以使用深度優(yōu)先搜索實現(xiàn)B.結果不唯一C.可以用于判斷圖中是否存在環(huán)D.所有節(jié)點的入度在排序過程中不會改變18、在一個具有n個元素的棧中，若要將棧中元素依次出棧并打印，以下關于操作的時間復雜度的描述，哪一項是準確的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)19、在一個順序存儲的隊列中，若要在隊尾插入一個元素，需要移動元素的平均次數為（）A.0B.n/2C.nD.n-120、以下哪種數據結構適合頻繁進行插入和刪除操作，并且能夠快速查找最大元素？（）A.數組B.鏈表C.棧D.最大堆二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細說明棧的基本操作（入棧、出棧）的實現(xiàn)原理，以及在實際應用中的場景。2、（本題10分）解釋在一個具有n個頂點的圖中，如何使用廣度優(yōu)先搜索計算兩點之間的最短路徑長度。3、（本題10分）論述在一個具有n個頂點的無向圖中，如何使用廣度優(yōu)先搜索算法來生成連通分量。4、（本題10分）解釋并舉例說明在一個具有n個元素的順序表中，如何進行選擇排