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

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

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