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

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

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、已知一個(gè)完全二叉樹的節(jié)點(diǎn)總數(shù)為100，其葉子節(jié)點(diǎn)的個(gè)數(shù)為（）。A.49B.50C.51D.不確定2、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，使用廣度優(yōu)先遍歷算法。以下關(guān)于遍歷過程中使用的輔助隊(duì)列的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(n^2)3、若一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為？（）A.CEDBAB.CEABDC.ABCDED.EDCAB4、以下關(guān)于二叉排序樹的描述，錯(cuò)誤的是：A.左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值B.右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值C.中序遍歷二叉排序樹可得到一個(gè)有序序列D.二叉排序樹的查找效率總是最高的5、在一個(gè)具有n個(gè)元素的隊(duì)列中，若要獲取隊(duì)頭元素的前一個(gè)元素但不刪除，以下操作不可行的是？（）A.遍歷整個(gè)隊(duì)列B.使用輔助數(shù)據(jù)結(jié)構(gòu)C.直接獲取D.以上都不可行6、在數(shù)據(jù)結(jié)構(gòu)中，樹的遍歷可以采用遞歸和非遞歸方式。以下關(guān)于非遞歸中序遍歷二叉樹的說法，錯(cuò)誤的是（）A.可以使用棧來輔助實(shí)現(xiàn)B.比遞歸方式更復(fù)雜C.時(shí)間復(fù)雜度與遞歸方式相同D.空間復(fù)雜度一定比遞歸方式低7、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時(shí)間復(fù)雜度內(nèi)實(shí)現(xiàn)元素的隨機(jī)訪問？（）A.鏈表B.隊(duì)列C.棧D.數(shù)組8、設(shè)有一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉平衡樹，若要插入一個(gè)新節(jié)點(diǎn)并保持平衡，以下關(guān)于插入操作的平均時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)9、對于一個(gè)具有n個(gè)頂點(diǎn)和m條邊的有向圖，使用鄰接表存儲，其入度和出度的計(jì)算時(shí)間復(fù)雜度分別為（）A.O(n)和O(m)B.O(m)和O(n)C.O(n+m)和O(n+m)D.O(n^2)和O(n^2)10、對于一個(gè)有向無環(huán)圖（DAG），進(jìn)行拓?fù)渑判虻姆椒ú恢挂环N。以下關(guān)于拓?fù)渑判虻拿枋觯e(cuò)誤的是（）A.可以使用深度優(yōu)先搜索實(shí)現(xiàn)B.結(jié)果不唯一C.可以用于判斷圖中是否存在環(huán)D.所有節(jié)點(diǎn)的入度在排序過程中不會改變11、在一個(gè)平衡二叉樹中，插入一個(gè)新節(jié)點(diǎn)后可能會導(dǎo)致樹的不平衡，此時(shí)需要進(jìn)行調(diào)整。以下哪種調(diào)整操作可能會被執(zhí)行？（）A.左旋B.右旋C.先左旋后右旋D.以上都有可能12、對于一個(gè)具有n個(gè)元素的順序存儲的棧，若要判斷棧是否已滿，應(yīng)判斷？（）A.top==n-1B.top==nC.top>=n-1D.top>=n13、在一棵二叉樹中，若度為2的節(jié)點(diǎn)有10個(gè)，度為1的節(jié)點(diǎn)有20個(gè)，那么葉子節(jié)點(diǎn)的數(shù)量是多少？A.11B.21C.30D.無法確定14、在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用選擇排序進(jìn)行排序。以下關(guān)于選擇排序的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.最好情況為O(n)，最壞情況為O(n^2)B.最好情況和最壞情況均為O(n)C.最好情況為O(nlogn)，最壞情況為O(n^2)D.最好情況和最壞情況均為O(n^2)15、在一個(gè)具有n個(gè)元素的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)，需要向后移動的元素個(gè)數(shù)為：A.n-iB.iC.n-i+1D.n-i-116、在一個(gè)具有n個(gè)元素的循環(huán)雙鏈表中，若要在表頭插入一個(gè)新元素，以下關(guān)于插入操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)17、圖的存儲方式和遍歷方式可以用于解決很多實(shí)際問題，以下關(guān)于它們的應(yīng)用的說法中，錯(cuò)誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，適用于社交網(wǎng)絡(luò)分析和交通網(wǎng)絡(luò)規(guī)劃等。B.圖的鄰接表可以用于表示稀疏圖，適用于地圖繪制和電路圖設(shè)計(jì)等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問題和最小生成樹問題等，適用于物流配送和通信網(wǎng)絡(luò)優(yōu)化等。D.圖的存儲方式和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。18、在一個(gè)帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹時(shí)，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個(gè)連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對19、在一個(gè)用鏈表實(shí)現(xiàn)的棧中，若要獲取棧底元素的值，需要的時(shí)間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)20、對于一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(nlogn)C.O(elogn)D.O(e^2)二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述在圖的表示中，如何將一個(gè)有權(quán)無向圖轉(zhuǎn)換為有權(quán)有向圖，并分析其影響。2、（本題10分）在一個(gè)鏈表中，如何刪除所有值為指定值的結(jié)點(diǎn)？3、（本題10分）比較冒泡排序和堆排序在時(shí)間復(fù)雜度上的優(yōu)劣。4、（本題10分）論述在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，如何計(jì)算強(qiáng)連通分