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

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

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