南京信息工程大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2023-2024學(xué)年期末試卷

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫(xiě)、漏寫(xiě)或字跡不清者，成績(jī)按零分記?！堋狻€…………第1頁(yè)，共1頁(yè)南京信息工程大學(xué)

《數(shù)據(jù)結(jié)構(gòu)與算法》2023-2024學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在一個(gè)長(zhǎng)度為n的有序數(shù)組中進(jìn)行二分查找，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)2、在一個(gè)帶權(quán)無(wú)向圖中，使用普里姆算法構(gòu)造最小生成樹(shù)，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接已選頂點(diǎn)和未選頂點(diǎn)的權(quán)值最小的邊C.任意一條邊D.以上都不對(duì)3、在一個(gè)順序存儲(chǔ)的數(shù)組中實(shí)現(xiàn)一個(gè)簡(jiǎn)單的棧結(jié)構(gòu)，若棧頂指針top初始值為-1，當(dāng)進(jìn)行一次入棧操作后，top的值應(yīng)該如何變化？A.top不變B.top=top+1C.top=top-1D.top=04、在一個(gè)具有n個(gè)元素的雙向鏈表中，刪除一個(gè)指定節(jié)點(diǎn)，其時(shí)間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)5、在一個(gè)具有n個(gè)元素的有序數(shù)組中，使用二分查找查找一個(gè)不存在的元素，最多比較次數(shù)約為？A.lognB.nC.n/2D.nlogn6、對(duì)于一個(gè)采用鏈?zhǔn)酱鎯?chǔ)的隊(duì)列，若隊(duì)頭指針和隊(duì)尾指針相同，則隊(duì)列的狀態(tài)為：A.隊(duì)空B.隊(duì)滿C.不確定D.隊(duì)列中只有一個(gè)元素7、對(duì)于一個(gè)具有n個(gè)元素的有序數(shù)組，使用二分查找算法查找一個(gè)特定元素。以下關(guān)于二分查找的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.O(1)B.O(logn)C.O(n)D.O(nlogn)8、在一個(gè)具有n個(gè)元素的數(shù)組中，進(jìn)行順序查找，若查找成功，平均比較次數(shù)約為？A.n/2B.nC.lognD.19、在一個(gè)具有n個(gè)元素的大頂堆中，插入一個(gè)新元素后，需要進(jìn)行調(diào)整，其時(shí)間復(fù)雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)10、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)LRU（最近最少使用）緩存淘汰策略？（）A.隊(duì)列B.棧C.哈希表D.雙向鏈表11、在數(shù)據(jù)結(jié)構(gòu)中，使用棧來(lái)實(shí)現(xiàn)表達(dá)式求值，以下關(guān)于表達(dá)式求值的過(guò)程，描述錯(cuò)誤的是（）A.遇到操作數(shù)入棧B.遇到運(yùn)算符時(shí)，彈出棧頂?shù)膬蓚€(gè)操作數(shù)進(jìn)行計(jì)算C.括號(hào)不影響求值的順序D.最終棧頂元素即為表達(dá)式的結(jié)果12、在一個(gè)用鄰接矩陣存儲(chǔ)的圖中，若要判斷兩個(gè)節(jié)點(diǎn)是否相鄰，時(shí)間復(fù)雜度是多少？A.O(1)B.O(n)C.O(logn)D.O(nlogn)13、在數(shù)據(jù)結(jié)構(gòu)中，伸展樹(shù)（SplayTree）通過(guò)自調(diào)整保持較好的性能，以下關(guān)于伸展樹(shù)的操作，不正確的是（）A.查找操作會(huì)將被查找的節(jié)點(diǎn)旋轉(zhuǎn)到根節(jié)點(diǎn)B.插入操作可能會(huì)引起多次旋轉(zhuǎn)C.伸展樹(shù)的平均性能較好D.伸展樹(shù)的空間復(fù)雜度較高14、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)中，若底層從左到右依次編號(hào)，節(jié)點(diǎn)i的左孩子節(jié)點(diǎn)編號(hào)是多少（假設(shè)根節(jié)點(diǎn)編號(hào)為1）？A.2iB.2i+1C.i*2D.以上都不對(duì)15、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無(wú)向圖，若采用克魯斯卡爾（Kruskal）算法生成最小生成樹(shù)，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)16、在一個(gè)循環(huán)隊(duì)列中，若隊(duì)頭指針front=5，隊(duì)尾指針rear=2，則隊(duì)列中的元素個(gè)數(shù)為：A.7B.3C.2D.不確定17、對(duì)于一個(gè)具有n個(gè)元素的無(wú)序數(shù)組，使用選擇排序進(jìn)行排序，其交換次數(shù)最多為？A.n-1B.nC.n(n-1)/2D.n^218、對(duì)于一個(gè)有向無(wú)環(huán)圖（DAG），進(jìn)行拓?fù)渑判虻姆椒ú恢挂环N。以下關(guān)于拓?fù)渑判虻拿枋?，錯(cuò)誤的是（）A.可以使用深度優(yōu)先搜索實(shí)現(xiàn)B.結(jié)果不唯一C.可以用于判斷圖中是否存在環(huán)D.所有節(jié)點(diǎn)的入度在排序過(guò)程中不會(huì)改變19、若要在一個(gè)具有n個(gè)元素的有序鏈表中插入一個(gè)新元素，使其仍然有序，平均時(shí)間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)20、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接表存儲(chǔ)時(shí)，其空間復(fù)雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋并舉例說(shuō)明在一個(gè)具有n個(gè)元素的順序表中，如何使用排序算法進(jìn)行數(shù)據(jù)去重。2、（本題10分）在一個(gè)雙向鏈表中，如何將鏈表逆序？3、（本題10分）論述如何利用廣度優(yōu)先搜索算法計(jì)算圖中兩個(gè)節(jié)點(diǎn)之間的最短路徑。4、（本題10分）對(duì)于一個(gè)用哈希表存儲(chǔ)的浮點(diǎn)數(shù)集合，解釋如何處理哈希沖突以提高查