青島黃海學(xué)院《數(shù)據(jù)可視化分析》2021-2022學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁(yè)，共3頁(yè)青島黃海學(xué)院《數(shù)據(jù)可視化分析》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在二叉樹中，判斷兩棵二叉樹是否完全相同，以下方法不正確的是（）A.同時(shí)進(jìn)行先序遍歷，比較節(jié)點(diǎn)值B.同時(shí)進(jìn)行中序遍歷，比較節(jié)點(diǎn)值C.同時(shí)進(jìn)行后序遍歷，比較節(jié)點(diǎn)值D.比較兩棵樹的節(jié)點(diǎn)數(shù)量2、在一個(gè)棧中，若入棧序列為1,2,3,4，且在入棧過(guò)程中可以出棧，則可能得到的出棧序列有多少種？（）A.14B.15C.16D.173、以下關(guān)于樹的遍歷算法的描述，哪一項(xiàng)是不正確的？（）A.先序遍歷先訪問根節(jié)點(diǎn)B.中序遍歷先訪問左子樹C.后序遍歷先訪問右子樹D.三種遍歷算法都可以用遞歸或非遞歸方式實(shí)現(xiàn)4、在一個(gè)具有n個(gè)節(jié)點(diǎn)的無(wú)向圖中，若要判斷圖是否連通，可以使用哪種算法？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.克魯斯卡爾算法D.以上都可以5、在一棵二叉搜索樹中，刪除一個(gè)節(jié)點(diǎn)后，為了保持二叉搜索樹的性質(zhì)，需要進(jìn)行的調(diào)整操作可能包括（）A.左旋B.右旋C.左右旋結(jié)合D.以上都有可能6、在一個(gè)具有n個(gè)元素的數(shù)組中，進(jìn)行冒泡排序，在最壞情況下，需要比較的次數(shù)為？（）A.n-1B.n(n-1)/2C.n2D.nlog?n7、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，進(jìn)行先序遍歷和中序遍歷，得到的序列相同，則該二叉樹的形狀為？A.只有一個(gè)根節(jié)點(diǎn)B.所有節(jié)點(diǎn)只有左子樹C.所有節(jié)點(diǎn)只有右子樹D.是一棵滿二叉樹8、對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，若采用折半插入排序算法進(jìn)行排序，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)9、在一個(gè)哈希表中，負(fù)載因子越大，說(shuō)明什么？A.哈希沖突越少B.存儲(chǔ)空間利用率越高C.查找效率越高D.以上都不對(duì)10、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小為（）。A.nB.n^2C.n(n-1)D.n(n+1)11、鏈表是另一種常見的數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含數(shù)據(jù)和指向下一個(gè)節(jié)點(diǎn)的指針。以下關(guān)于鏈表的說(shuō)法中，錯(cuò)誤的是？（）A.鏈表的插入和刪除操作比較方便，只需要修改指針即可。B.鏈表可以動(dòng)態(tài)地增長(zhǎng)和縮小，不像數(shù)組那樣受固定長(zhǎng)度的限制。C.鏈表的訪問速度比數(shù)組慢，因?yàn)樾枰闅v鏈表才能找到特定的元素。D.鏈表只能存儲(chǔ)整數(shù)類型的數(shù)據(jù)元素。12、在數(shù)據(jù)結(jié)構(gòu)中，字典樹（Trie樹）常用于字符串的存儲(chǔ)和查找，以下關(guān)于字典樹的特點(diǎn)，不正確的是（）A.對(duì)于前綴相同的字符串可以節(jié)省存儲(chǔ)空間B.查找操作的時(shí)間復(fù)雜度與字符串長(zhǎng)度有關(guān)C.適合用于詞頻統(tǒng)計(jì)D.插入和刪除操作比較復(fù)雜13、棧和隊(duì)列的應(yīng)用場(chǎng)景非常廣泛，以下關(guān)于它們的應(yīng)用的說(shuō)法中，錯(cuò)誤的是？（）A.棧可以用于實(shí)現(xiàn)函數(shù)調(diào)用、表達(dá)式求值和括號(hào)匹配等。B.隊(duì)列可以用于實(shí)現(xiàn)任務(wù)調(diào)度、消息隊(duì)列和廣度優(yōu)先搜索等。C.棧和隊(duì)列可以用于實(shí)現(xiàn)圖的深度優(yōu)先搜索和廣度優(yōu)先搜索。D.棧和隊(duì)列只適用于計(jì)算機(jī)科學(xué)領(lǐng)域，在其他領(lǐng)域沒有實(shí)際價(jià)值。14、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖中，使用Prim算法生成最小生成樹。若采用鄰接矩陣存儲(chǔ)圖，以下關(guān)于算法的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(n)B.O(n^2)C.O(e)D.O(e^2)15、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖，采用鄰接表存儲(chǔ)，進(jìn)行深度優(yōu)先遍歷。以下關(guān)于遍歷的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)模緼.O(n+e)B.O(n^2)C.O(e^2)D.O(n^3)16、以下關(guān)于哈希表沖突解決方法的描述，哪一項(xiàng)是不正確的？（）A.鏈地址法會(huì)增加存儲(chǔ)空間的開銷B.開放定址法的查找效率一定高于鏈地址法C.再哈希法可以減少?zèng)_突的發(fā)生D.建立公共溢出區(qū)可以存儲(chǔ)發(fā)生沖突的元素17、已知一個(gè)帶權(quán)有向圖G=(V,E)，頂點(diǎn)集合V={1,2,3,4,5}，邊集合E={(1,2,5),(1,3,3),(2,4,2),(3,4,6),(3,5,4),(4,5,1)}，采用迪杰斯特拉（Dijkstra）算法求從頂點(diǎn)1到頂點(diǎn)5的最短路徑，經(jīng)過(guò)的中間頂點(diǎn)依次為？（）A.2,4B.3,4C.2,3D.3,518、在數(shù)據(jù)結(jié)構(gòu)中，使用隊(duì)列來(lái)實(shí)現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過(guò)程的描述，錯(cuò)誤的是（）A.從起始節(jié)點(diǎn)開始入隊(duì)B.隊(duì)列為空時(shí)結(jié)束遍歷C.訪問節(jié)點(diǎn)時(shí)將其未訪問的鄰接節(jié)點(diǎn)入隊(duì)D.節(jié)點(diǎn)不會(huì)被重復(fù)訪問19、已知一個(gè)圖的鄰接表存儲(chǔ)結(jié)構(gòu)，若要判斷任意兩個(gè)頂點(diǎn)之間是否存在邊，哪種方法最有效？（）A.遍歷鄰接表B.建立逆鄰接表C.建立鄰接矩陣D.深度優(yōu)先搜索20、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉算法求最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)闡述如何使用A*算法在圖中進(jìn)行尋路，解釋其啟發(fā)函數(shù)的作用和設(shè)計(jì)原則，并分析其性能優(yōu)勢(shì)。2、（本題10分）詳細(xì)論述在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，如何使用Prim算法從不同的起始頂點(diǎn)構(gòu)建最小生成樹，并比較結(jié)果。3、（本題10分）闡述如何在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，進(jìn)行查找操作，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。4、（本題