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

學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場(chǎng)____________準(zhǔn)考證號(hào)…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁南京信息工程大學(xué)

《數(shù)據(jù)結(jié)構(gòu)（Ⅰ）》2023-2024學(xué)年期末試卷題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.154322、以下關(guān)于圖的遍歷的描述，正確的是：A.深度優(yōu)先遍歷和廣度優(yōu)先遍歷都可以用于有向圖和無向圖B.深度優(yōu)先遍歷總是先訪問離起始頂點(diǎn)近的頂點(diǎn)C.廣度優(yōu)先遍歷總是先訪問深度大的頂點(diǎn)D.圖的遍歷結(jié)果是唯一的3、在一個(gè)采用哈希表存儲(chǔ)的數(shù)據(jù)結(jié)構(gòu)中，哈希函數(shù)將關(guān)鍵字映射到存儲(chǔ)位置。若發(fā)生哈希沖突，通常采用開放定址法解決。以下關(guān)于開放定址法的時(shí)間復(fù)雜度的描述，哪一個(gè)是恰當(dāng)?shù)?？A.查找操作的時(shí)間復(fù)雜度在平均情況下為O(1)，最壞情況為O(n)B.查找操作的時(shí)間復(fù)雜度始終為O(1)C.查找操作的時(shí)間復(fù)雜度在平均情況下為O(logn)，最壞情況為O(nlogn)D.查找操作的時(shí)間復(fù)雜度始終為O(n)4、在一個(gè)用鄰接矩陣表示的無向圖中，矩陣中的元素表示什么？A.頂點(diǎn)之間的距離B.頂點(diǎn)之間是否有邊C.邊的權(quán)重D.以上都有可能5、在一個(gè)哈希表中，若采用線性探測(cè)法解決哈希沖突，當(dāng)發(fā)生沖突時(shí)，新元素會(huì)存儲(chǔ)在什么位置？A.沖突位置的下一個(gè)位置B.沖突位置C.隨機(jī)位置D.以上都不對(duì)6、已知一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBAEDFG，則其后序遍歷序列為：A.CBEFDGAB.CEBFDGAC.CBEFAGDD.CEBFAGD7、在一棵度為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.788、在一個(gè)用鄰接表存儲(chǔ)的有向圖中，若要計(jì)算某個(gè)節(jié)點(diǎn)的出度，以下哪種方法較為高效？A.遍歷該節(jié)點(diǎn)的鄰接表B.遍歷整個(gè)圖的鄰接表C.無法高效計(jì)算D.以上都不對(duì)9、對(duì)于一個(gè)具有n個(gè)元素的堆，進(jìn)行刪除操作并調(diào)整堆的時(shí)間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列？A.鏈表B.隊(duì)列C.棧D.堆11、若要對(duì)一組無序的整數(shù)進(jìn)行排序，使其最終變?yōu)橐粋€(gè)遞增的有序序列，以下哪種排序算法在平均情況下性能最優(yōu)？A.冒泡排序B.插入排序C.選擇排序D.希爾排序12、以下關(guān)于紅黑樹的性質(zhì)，錯(cuò)誤的是：A.每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色B.根節(jié)點(diǎn)是黑色的C.每個(gè)葉子節(jié)點(diǎn)（NIL節(jié)點(diǎn)）是黑色的D.紅色節(jié)點(diǎn)的子節(jié)點(diǎn)一定是紅色的13、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，使用弗洛伊德算法求所有節(jié)點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)14、在一個(gè)具有n個(gè)頂點(diǎn)和m條邊的有向圖中，使用弗洛伊德算法求所有頂點(diǎn)對(duì)之間的最短路徑，其時(shí)間復(fù)雜度為？A.O(n^2)B.O(n^3)C.O(mn)D.O(m^2)15、以下關(guān)于字符串匹配的BM算法的描述，哪一項(xiàng)是不正確的？（）A.從模式串的尾部開始匹配B.利用了壞字符和好后綴規(guī)則C.在一般情況下比KMP算法效率低D.可以通過預(yù)處理提高匹配速度16、對(duì)于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，其先序遍歷、中序遍歷和后序遍歷的結(jié)果都是唯一確定的，這個(gè)二叉樹一定是（）A.滿二叉樹B.完全二叉樹C.單支樹D.以上都不是17、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若其邊的集合為{(1,2),(1,3),(2,3),(2,4),(3,4)}，則該圖的鄰接表存儲(chǔ)中，頂點(diǎn)2的鏈表中包含的頂點(diǎn)有：A.1,3,4B.1,3C.3,4D.1,418、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，使用深度優(yōu)先搜索算法遍歷所有節(jié)點(diǎn)，其時(shí)間復(fù)雜度主要取決于什么？A.邊的數(shù)量B.節(jié)點(diǎn)的數(shù)量C.圖的存儲(chǔ)方式D.以上都是19、在一個(gè)具有n個(gè)頂點(diǎn)的有向無環(huán)圖中，使用拓?fù)渑判蛩惴?，其結(jié)果的唯一性如何？A.一定唯一B.可能不唯一C.取決于頂點(diǎn)的編號(hào)D.以上都不對(duì)20、在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，若要判斷兩個(gè)頂點(diǎn)之間是否存在路徑，使用哪種算法較為合適？A.迪杰斯特拉算法B.弗洛伊德算法C.深度優(yōu)先遍歷或廣度優(yōu)先遍歷D.拓?fù)渑判蚨?、?jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）詳細(xì)說明如何在一個(gè)無向圖中進(jìn)行連通分量的計(jì)算，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。2、（本題10分）解釋在一個(gè)有序數(shù)組中進(jìn)行二分查找的基本思路和步驟，分析其時(shí)間復(fù)雜度和空間復(fù)雜度。3、（本題10分）解釋最小生成樹的概念，比較普里姆算法和克魯斯卡爾算法在構(gòu)建最小生成樹時(shí)的不同策略和效率。4、（本題10分）詳細(xì)論述在利用哈希表存儲(chǔ)結(jié)構(gòu)體數(shù)據(jù)時(shí)，如何設(shè)計(jì)哈