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

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

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