南京信息工程大學《數(shù)據(jù)結(jié)構(gòu)Ⅲ》2021-2022學年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁南京信息工程大學

《數(shù)據(jù)結(jié)構(gòu)Ⅲ》2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、設(shè)有一個鏈棧，棧頂指針為top，若要在棧頂插入一個新元素，則需要執(zhí)行的操作是（）。A.s->next=top;top=s;B.top->next=s;top=s;C.s->next=top->next;top->next=s;D.top=s;s->next=NULL;2、在一個具有n個頂點和m條邊的無向圖中，若采用鄰接表存儲，則存儲空間復(fù)雜度主要取決于？A.nB.mC.n+mD.n^23、在一個具有n個元素的最小堆中，刪除堆頂元素后，為了恢復(fù)堆的性質(zhì)，需要進行的調(diào)整操作的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)4、二叉樹的性質(zhì)和遍歷方式可以用于解決很多實際問題，以下關(guān)于它們的應(yīng)用的說法中，錯誤的是？（）A.二叉搜索樹可以用于實現(xiàn)高效的查找、插入和刪除操作。B.平衡二叉樹可以用于解決二叉搜索樹的不平衡問題，提高查找效率。C.二叉樹的遍歷方式可以用于實現(xiàn)二叉樹的復(fù)制、遍歷和序列化等操作。D.二叉樹的性質(zhì)和遍歷方式只適用于理論研究，在實際應(yīng)用中沒有實際價值。5、若要從一個具有n個元素的有序單鏈表中刪除所有值重復(fù)的元素，使得鏈表中每個元素的值都不同，最優(yōu)的算法時間復(fù)雜度是？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)6、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復(fù)雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復(fù)雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)7、在一個具有n個元素的有序數(shù)組中，使用二分查找查找一個不存在的元素，其時間復(fù)雜度為：A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)8、在一個具有n個頂點的有向完全圖中，邊的數(shù)量為：A.n(n-1)/2B.n(n-1)C.n^2D.2n(n-1)9、以下哪種排序算法的空間復(fù)雜度最低？A.歸并排序B.快速排序C.冒泡排序D.插入排序10、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠在O(1)的時間復(fù)雜度內(nèi)實現(xiàn)元素的隨機訪問？（）A.鏈表B.隊列C.棧D.數(shù)組11、在一個用鄰接矩陣存儲的無向圖中，若要刪除一條邊，需要修改矩陣中的幾個元素？A.1個B.2個C.3個D.4個12、哈希表的沖突解決方法有多種，以下關(guān)于它們的說法中，錯誤的是？（）A.開放定址法是一種常用的沖突解決方法，它通過在哈希表中尋找下一個空閑位置來解決沖突。B.鏈地址法是另一種常用的沖突解決方法，它將沖突的元素存儲在鏈表中。C.再哈希法是通過使用不同的哈希函數(shù)來解決沖突。D.哈希表的沖突解決方法只有開放定址法和鏈地址法兩種。13、若要對一個具有n個元素的數(shù)組進行歸并排序，需要額外的輔助空間大小為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)14、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在有向圖中，頂點的入度是指指向該頂點的邊的數(shù)量。若要計算一個有向圖中所有頂點的入度，哪種算法較為合適？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓撲排序D.以上都可以15、對于一個棧，進行入棧和出棧操作時，以下哪種情況會導(dǎo)致棧溢出？A.入棧元素過多B.出棧元素過多C.連續(xù)進行入棧操作且存儲空間已滿D.連續(xù)進行出棧操作且棧為空16、在一個鏈式存儲的線性表中，若要刪除第i個元素（1<=i<=n），需要找到其前驅(qū)節(jié)點的時間復(fù)雜度為？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)17、已知一個有序表為{11,22,33,44,55,66,77,88,99}，使用折半查找法查找值為77的元素，需要比較的次數(shù)是（）。A.1B.2C.3D.418、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)優(yōu)先級隊列？A.鏈表B.隊列C.棧D.堆19、對于一個滿二叉樹，若其高度為h，則其節(jié)點總數(shù)為多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-120、在一個具有n個頂點和e條邊的無向圖中，使用克魯斯卡爾（Kruskal）算法生成最小生成樹。以下關(guān)于該算法的時間復(fù)雜度的描述，哪一項是正確的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）對于一個用鄰接表存儲的有向圖，詳細闡述如何進行深度優(yōu)先遍歷和廣度優(yōu)先遍歷，給出兩種遍歷算法的步驟和實現(xiàn)代碼框架。2、（本題10分）詳細說明如何在一個有序鏈表中刪除重復(fù)元素，只保留一個，給出算法步驟和實現(xiàn)代碼，并分析其時間復(fù)雜度。3、（本題10分）詳細說明在插入排序中，對于近乎有序的數(shù)組，其性能表現(xiàn)為何較好。4、（本題10分）解釋如何在一個鏈表中實現(xiàn)插入排序的優(yōu)化，給出算法步驟和實現(xiàn)代碼，并分析其性能改進。三、設(shè)計題