成都大學(xué)《數(shù)據(jù)可視化》2022-2023學(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ù)可視化》2022-2023學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)哈希表中，負(fù)載因子越大，說(shuō)明什么？A.哈希沖突越少B.存儲(chǔ)空間利用率越高C.查找效率越高D.以上都不對(duì)2、設(shè)有一個(gè)廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)3、對(duì)于一個(gè)具有n個(gè)元素的待排序序列，若采用冒泡排序算法進(jìn)行排序，在最壞情況下需要進(jìn)行的比較次數(shù)為？（）A.n(n-1)/2B.nlognC.n-1D.n4、已知一個(gè)帶權(quán)無(wú)向圖的鄰接矩陣表示，若要計(jì)算圖中兩個(gè)頂點(diǎn)之間的最短路徑，可以使用的算法是？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法5、若一個(gè)圖的鄰接矩陣對(duì)角線以下（不包括對(duì)角線）的元素全為0，則該圖一定是：A.無(wú)向圖B.有向圖C.強(qiáng)連通圖D.弱連通圖6、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向連通圖，其生成樹(shù)中邊的條數(shù)為（）。A.nB.n-1C.eD.e-17、在一個(gè)具有n個(gè)元素的大頂堆中，若要將堆頂元素與最后一個(gè)元素交換，然后調(diào)整堆，其時(shí)間復(fù)雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)8、在一個(gè)具有n個(gè)元素的順序表中，在第i個(gè)元素（1<=i<=n）之前插入一個(gè)新元素時(shí)，需要向后移動(dòng)的元素個(gè)數(shù)為：A.n-iB.iC.n-i+1D.n-i-19、在一個(gè)用鄰接矩陣存儲(chǔ)的無(wú)向圖中，若要?jiǎng)h除一條邊，需要修改矩陣中的幾個(gè)元素？A.1個(gè)B.2個(gè)C.3個(gè)D.4個(gè)10、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，使用克魯斯卡爾（Kruskal）算法生成最小生成樹(shù)。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)11、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，有鄰接矩陣和鄰接表兩種存儲(chǔ)方式。對(duì)于一個(gè)稀疏圖，以下說(shuō)法正確的是（）A.鄰接矩陣比鄰接表更節(jié)省存儲(chǔ)空間B.鄰接表更適合用于存儲(chǔ)和遍歷C.兩種存儲(chǔ)方式的時(shí)間復(fù)雜度相同D.稀疏圖的邊數(shù)很少，節(jié)點(diǎn)數(shù)很多12、在一個(gè)具有n個(gè)頂點(diǎn)的圖中，若存在回路，則深度優(yōu)先遍歷可能會(huì)出現(xiàn)什么情況？（）A.訪問(wèn)某些頂點(diǎn)多次B.無(wú)法完成遍歷C.結(jié)果不正確D.以上都有可能13、在數(shù)據(jù)結(jié)構(gòu)中，使用隊(duì)列來(lái)實(shí)現(xiàn)廣度優(yōu)先遍歷圖，以下關(guān)于遍歷過(guò)程的描述，錯(cuò)誤的是（）A.從起始節(jié)點(diǎn)開(kāi)始入隊(duì)B.隊(duì)列為空時(shí)結(jié)束遍歷C.訪問(wèn)節(jié)點(diǎn)時(shí)將其未訪問(wèn)的鄰接節(jié)點(diǎn)入隊(duì)D.節(jié)點(diǎn)不會(huì)被重復(fù)訪問(wèn)14、對(duì)于一個(gè)具有n個(gè)元素的快速排序，每次劃分選取的基準(zhǔn)元素不同，對(duì)排序的時(shí)間復(fù)雜度有何影響？（）A.沒(méi)有影響B(tài).可能會(huì)提高C.可能會(huì)降低D.以上都不對(duì)15、設(shè)有一個(gè)具有n個(gè)元素的最大堆，若要獲取堆中的最大元素，以下關(guān)于操作的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、對(duì)于一個(gè)采用鏈表存儲(chǔ)的隊(duì)列，若要實(shí)現(xiàn)隊(duì)列的逆置操作，以下關(guān)于時(shí)間復(fù)雜度的描述，哪一個(gè)是準(zhǔn)確的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)17、設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)存儲(chǔ)單元，則a85的地址為？（）A.33B.32C.18D.4018、在一個(gè)具有n個(gè)元素的有序數(shù)組中，使用二分查找算法查找一個(gè)特定元素，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(n2)D.O(nlog?n)19、在一個(gè)具有n個(gè)元素的小根堆中，最小元素的值位于（）。A.根節(jié)點(diǎn)B.任意節(jié)點(diǎn)C.葉子節(jié)點(diǎn)D.無(wú)法確定20、在循環(huán)鏈表中，尾指針rear指向鏈表的尾節(jié)點(diǎn)，若要在鏈表中插入一個(gè)新的節(jié)點(diǎn)，使其成為新的尾節(jié)點(diǎn)，以下操作正確的是？（）A.rear->next=new_node;new_node->next=rear;rear=new_node;B.new_node->next=rear;rear->next=new_node;rear=new_node;C.rear=new_node;new_node->next=rear->next;rear->next=new_node;D.new_node->next=rear->next;rear->next=new_node;二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋如何在一個(gè)帶權(quán)無(wú)向圖中計(jì)算所有頂點(diǎn)對(duì)之間的最大權(quán)值路徑。2、（本題10分）詳細(xì)闡述如何在一個(gè)帶權(quán)有向圖中計(jì)算兩個(gè)頂點(diǎn)之間路徑經(jīng)過(guò)的頂點(diǎn)數(shù)量。3、（本題10分）比較希爾排序和快速排序在穩(wěn)定性方面的表現(xiàn)。4、（本題10分）論述在深度優(yōu)先搜索和廣度優(yōu)先搜索的應(yīng)用中，如何解決迷宮問(wèn)題或?qū)ふ覉D中的所有路徑。三、設(shè)