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

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績(jī)按零分記?！堋狻€…………第1頁(yè)，共1頁(yè)湖南財(cái)政經(jīng)濟(jì)學(xué)院

《數(shù)據(jù)可視化》2022-2023學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)不帶頭結(jié)點(diǎn)的單鏈表中，若要?jiǎng)h除表頭結(jié)點(diǎn)，需要修改幾個(gè)指針？（）A.0B.1C.2D.32、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的線性表中，若要在第i個(gè)位置插入一個(gè)新元素，需要修改多少個(gè)指針？（）A.1B.2C.iD.i+13、在一棵度為4的樹中，若有20個(gè)度為4的節(jié)點(diǎn)，10個(gè)度為3的節(jié)點(diǎn)，1個(gè)度為2的節(jié)點(diǎn)，10個(gè)葉子節(jié)點(diǎn)，那么這棵樹的總節(jié)點(diǎn)數(shù)是多少？A.82B.81C.79D.784、在一個(gè)具有n個(gè)節(jié)點(diǎn)的帶權(quán)無(wú)向圖中，使用普里姆算法構(gòu)造最小生成樹，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結(jié)構(gòu)5、已知一個(gè)有序表為{5,10,15,20,25,30,35,40,45,50}，使用折半查找法查找值為35的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.46、在一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉（Dijkstra）算法求單源最短路徑。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)7、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖中，使用克魯斯卡爾（Kruskal）算法生成最小生成樹。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)8、對(duì)于一棵二叉樹，先序遍歷序列為ABC，中序遍歷序列為BAC，則其后序遍歷序列為？A.BCAB.CBAC.ACBD.ABC9、在一個(gè)具有n個(gè)元素的鏈?zhǔn)疥?duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，要入隊(duì)一個(gè)元素，應(yīng)執(zhí)行的操作是？（）A.rear->next=newNode;rear=newNode;B.newNode->next=front;front=newNode;C.rear->next=newNode;front=newNode;D.newNode->next=rear;rear=newNode;10、圖的存儲(chǔ)方式和遍歷方式對(duì)圖的操作效率有很大影響，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.鄰接矩陣適合存儲(chǔ)稠密圖，查找邊的時(shí)間復(fù)雜度為O(1)，但空間復(fù)雜度較高。B.鄰接表適合存儲(chǔ)稀疏圖，插入邊和刪除邊的時(shí)間復(fù)雜度為O(1)，但查找邊的時(shí)間復(fù)雜度較高。C.深度優(yōu)先搜索和廣度優(yōu)先搜索是圖的兩種基本遍歷方式，它們的時(shí)間復(fù)雜度都為O(n+m)，其中n是頂點(diǎn)數(shù)，m是邊數(shù)。D.圖的存儲(chǔ)方式和遍歷方式一旦確定，就不能再改變，否則會(huì)影響圖的操作效率。11、以下關(guān)于平衡二叉樹旋轉(zhuǎn)調(diào)整的描述，正確的是：A.旋轉(zhuǎn)調(diào)整一定會(huì)改變樹的中序遍歷結(jié)果B.左旋操作是將右子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)樽笞庸?jié)點(diǎn)C.右旋操作是將左子樹變?yōu)楦?jié)點(diǎn)，原根節(jié)點(diǎn)變?yōu)橛易庸?jié)點(diǎn)D.平衡二叉樹不需要進(jìn)行旋轉(zhuǎn)調(diào)整12、在一個(gè)順序存儲(chǔ)的棧中，若棧頂指針top為-1，則表示棧（）A.已滿B.為空C.已損壞D.無(wú)法確定13、在一個(gè)具有n個(gè)元素的無(wú)序數(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)14、以下關(guān)于樹的存儲(chǔ)結(jié)構(gòu)的描述，哪一項(xiàng)是不正確的？（）A.孩子兄弟表示法可以方便地實(shí)現(xiàn)樹的遍歷B.雙親表示法便于查找一個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)C.孩子鏈表表示法在處理多叉樹時(shí)空間利用率較高D.以上存儲(chǔ)結(jié)構(gòu)在時(shí)間復(fù)雜度上沒(méi)有明顯差異15、在數(shù)據(jù)結(jié)構(gòu)中，對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，使用二分查找算法查找一個(gè)特定元素，其平均時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)16、在數(shù)據(jù)結(jié)構(gòu)中，基數(shù)排序是一種非比較排序算法，以下關(guān)于基數(shù)排序的描述，不正確的是（）A.按照位數(shù)依次進(jìn)行排序B.可以用于整數(shù)和字符串的排序C.時(shí)間復(fù)雜度為O(d(n+r))，其中d是位數(shù)，r是基數(shù)D.對(duì)數(shù)據(jù)的分布敏感17、若要對(duì)n個(gè)元素進(jìn)行快速排序，在最壞情況下，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(nlog?n)D.O(n2)18、在一個(gè)m行n列的二維數(shù)組中，元素存儲(chǔ)的地址計(jì)算公式為L(zhǎng)OC(aij)=LOC(a11)+[(i-1)*n+(j-1)]*d，其中d為每個(gè)元素所占的存儲(chǔ)單元數(shù)。若按行優(yōu)先存儲(chǔ)，則a23的地址為？（）A.LOC(a11)+5dB.LOC(a11)+6dC.LOC(a11)+7dD.LOC(a11)+8d19、哈希表的沖突解決方法有多種，以下關(guān)于它們的說(shuō)法中，錯(cuò)誤的是？（）A.開放定址法是一種常用的沖突解決方法，它通過(guò)在哈希表中尋找下一個(gè)空閑位置來(lái)解決沖突。B.鏈地址法是另一種常用的沖突解決方法，它將沖突的元素存儲(chǔ)在鏈表中。C.再哈希法是通過(guò)使用不同的哈希函數(shù)來(lái)解決沖突。D.哈希表的沖突解決方法只有開放定址法和鏈地址法兩種。20、在一個(gè)鏈隊(duì)列中，假設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，刪除隊(duì)頭元素的操作是：A.front=front->nextB.rear=rear->nextC.front->next=NULLD.rear->next=NULL二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）深入解釋在具有n個(gè)元素的數(shù)組中，如何實(shí)現(xiàn)冒泡排序和選擇排序算法，并比較它們的性能。2、（本題10分）解釋如何在一個(gè)二叉樹中進(jìn)行中序遍歷的非遞歸多線程實(shí)現(xiàn)，給出算法步驟和實(shí)現(xiàn)代碼，并分析其性能優(yōu)勢(shì)和潛在問(wèn)題。3、（本題10分）詳細(xì)闡述在具有n個(gè)頂點(diǎn)的有向圖中，如何判斷圖是否為有向無(wú)環(huán)圖，并給出兩種不同的檢測(cè)算法和代碼示例。4、（本題10分）詳細(xì)闡述