湖南財政經(jīng)濟(jì)學(xué)院《數(shù)據(jù)可視化與分析》2022-2023學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁湖南財政經(jīng)濟(jì)學(xué)院

《數(shù)據(jù)可視化與分析》2022-2023學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、圖的存儲方式和遍歷方式可以用于解決很多實際問題，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.圖的鄰接矩陣可以用于表示網(wǎng)絡(luò)中的連接關(guān)系，適用于社交網(wǎng)絡(luò)分析和交通網(wǎng)絡(luò)規(guī)劃等。B.圖的鄰接表可以用于表示稀疏圖，適用于地圖繪制和電路圖設(shè)計等。C.圖的遍歷方式可以用于解決路徑規(guī)劃、網(wǎng)絡(luò)流問題和最小生成樹問題等，適用于物流配送和通信網(wǎng)絡(luò)優(yōu)化等。D.圖的存儲方式和遍歷方式只適用于理論研究，在實際應(yīng)用中沒有實際價值。2、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)圖的存儲？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊列D.數(shù)組和哈希表3、以下關(guān)于圖的存儲結(jié)構(gòu)的描述，哪一項是正確的？（）A.鄰接矩陣適合存儲稀疏圖B.鄰接表在存儲稠密圖時空間效率較高C.十字鏈表適合存儲有向圖D.以上都不正確4、已知一個圖的鄰接矩陣如下所示：ABCDA0110B1011C1100D0100則該圖中頂點A的度為：A.1B.2C.3D.45、對于一個具有n個頂點和e條邊的無向圖，使用深度優(yōu)先搜索算法進(jìn)行遍歷。以下關(guān)于算法中使用的標(biāo)記數(shù)組的空間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)6、在一個不帶頭結(jié)點的單鏈表中，若要刪除表頭結(jié)點，需要修改幾個指針？（）A.0B.1C.2D.37、以下哪種數(shù)據(jù)結(jié)構(gòu)可以方便地實現(xiàn)字符串的模式匹配操作？A.二叉樹B.哈希表C.棧D.后綴樹8、在一個順序存儲的數(shù)組中實現(xiàn)一個簡單的棧結(jié)構(gòu)，若棧頂指針top初始值為-1，當(dāng)進(jìn)行一次入棧操作后，top的值應(yīng)該如何變化？A.top不變B.top=top+1C.top=top-1D.top=09、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），平均需要移動的元素個數(shù)約為？A.n/2B.n-iC.iD.n-i+110、在一個具有n個頂點和m條邊的有向圖中，使用弗洛伊德算法求所有頂點對之間的最短路徑，其時間復(fù)雜度為？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)11、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)字符串的最長公共子序列問題？A.二維數(shù)組B.棧C.隊列D.樹12、在一棵二叉搜索樹中，刪除一個節(jié)點后，為了保持二叉搜索樹的性質(zhì)，需要進(jìn)行的調(diào)整操作可能包括（）A.左旋B.右旋C.左右旋結(jié)合D.以上都有可能13、對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則矩陣中非零元素的個數(shù)至少為：A.n-1B.nC.2(n-1)D.2n14、以下關(guān)于字符串壓縮算法的描述，哪一項是不正確的？（）A.哈夫曼編碼可以根據(jù)字符出現(xiàn)頻率進(jìn)行壓縮B.LZW壓縮算法基于字典進(jìn)行壓縮C.壓縮算法一定能減小字符串的存儲空間D.不同的壓縮算法適用于不同類型的字符串15、在數(shù)據(jù)結(jié)構(gòu)中，雙向循環(huán)鏈表相較于單向鏈表，以下優(yōu)勢描述錯誤的是（）A.可以方便地反向遍歷B.插入和刪除節(jié)點的操作更簡單C.查找前一個節(jié)點的時間復(fù)雜度更低D.空間復(fù)雜度更低16、對于一個具有n個頂點和e條邊的有向圖，采用鄰接表存儲，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時間復(fù)雜度的描述，哪一個是恰當(dāng)?shù)模緼.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)17、二叉樹的性質(zhì)和遍歷方式可以用于解決很多實際問題，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.二叉搜索樹可以用于實現(xiàn)高效的查找、插入和刪除操作，適用于數(shù)據(jù)庫索引和文件系統(tǒng)等。B.平衡二叉樹可以用于解決二叉搜索樹的不平衡問題，提高查找效率，適用于大規(guī)模數(shù)據(jù)的存儲和管理。C.二叉樹的遍歷方式可以用于實現(xiàn)二叉樹的復(fù)制、遍歷和序列化等操作，適用于數(shù)據(jù)備份和傳輸?shù)取.二叉樹的性質(zhì)和遍歷方式只適用于理論研究，在實際應(yīng)用中沒有實際價值。18、若要對一個已經(jīng)排好序的數(shù)組進(jìn)行二分查找，查找不成功時，最多需要比較多少次？（）A.lognB.logn-1C.logn+1D.n-119、以下關(guān)于樹的存儲結(jié)構(gòu)的描述，哪一項是不正確的？（）A.孩子兄弟表示法可以方便地實現(xiàn)樹的遍歷B.雙親表示法便于查找一個節(jié)點的雙親節(jié)點C.孩子鏈表表示法在處理多叉樹時空間利用率較高D.以上存儲結(jié)構(gòu)在時間復(fù)雜度上沒有明顯差異20、在一個具有n個元素的循環(huán)隊列中，若隊尾指針rear指向隊尾元素的下一個位置，隊頭指針front指向隊頭元素，則隊列中元素的個數(shù)為？A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+1二、簡答題（本大題共4個小題，共40分)1、（本題10分）闡述隊列的入隊和出隊操作的具體過程，以及在實際問題中的作用。2、（本題10分）分析在數(shù)據(jù)結(jié)構(gòu)中，如何利用優(yōu)先隊列實現(xiàn)Dijkstra算法求解最短路徑問題。3、（本題10分）詳細(xì)說明拓?fù)渑判虻母拍詈退惴ú襟E，分析其在工程領(lǐng)域中的應(yīng)用場景和意義。4、（本題10分）深入分析在具有n個頂點和e條邊的有向圖中，如何計算圖的強連