學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁惠州學院

《數(shù)據(jù)結構實驗》2022-2023學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、以下關于并查集的描述，錯誤的是：A.并查集可以用于判斷兩個元素是否在同一個集合中B.并查集的查找操作時間復雜度較低C.并查集的合并操作時間復雜度較高D.并查集通常采用樹形結構存儲2、在數(shù)據(jù)結構中，哈希表的負載因子對性能有很大影響。以下關于負載因子的描述，不正確的是（）A.負載因子越大，哈希沖突的可能性越大B.負載因子越小，存儲空間利用率越高C.負載因子通常在0.5到1之間D.可以通過調整負載因子來優(yōu)化哈希表性能3、已知一個帶權無向圖的鄰接矩陣表示，若要計算圖中兩個頂點之間的最短路徑，可以使用的算法是？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.弗洛伊德（Floyd）算法D.普里姆（Prim）算法4、在一個具有n個元素的小頂堆中，若將堆頂元素與最后一個元素交換，然后對堆進行調整，其時間復雜度為（）。A.O(log?n)B.O(n)C.O(nlog?n)D.O(n^2)5、在一個具有n個元素的有序數(shù)組中，使用插入排序進行排序，其最壞情況下的時間復雜度為？（）A.O(n)B.O(log?n)C.O(n2)D.O(nlog?n)6、在一個具有n個元素的順序表中，若要刪除第i個元素（1<=i<=n），并將后面的元素向前移動，平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n-i+17、在一個具有n個元素的順序表中，刪除第i個元素（1<=i<=n），需要移動的元素個數(shù)最多為（）。A.i-1B.n-iC.n-i+1D.n-18、以下關于字符串匹配的BM算法的描述，哪一項是不正確的？（）A.從模式串的尾部開始匹配B.利用了壞字符和好后綴規(guī)則C.在一般情況下比KMP算法效率低D.可以通過預處理提高匹配速度9、設有一個棧，元素進棧的次序為A、B、C、D、E，下列不可能的出棧序列是（）。A.EDCBAB.DECBAC.DCEABD.ABCDE10、在一個平衡二叉搜索樹中，插入一個新節(jié)點后，可能需要進行的調整操作次數(shù)最多為（）A.1B.lognC.nD.nlogn11、對于一棵具有n個節(jié)點的二叉搜索樹，其平均查找長度的上限大約為？A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)12、以下哪種數(shù)據(jù)結構能夠高效地支持動態(tài)集合的操作，如合并、查找等？（）A.鏈表B.二叉樹C.并查集D.哈希表13、在數(shù)據(jù)結構中，鏈表的反轉是一個常見的操作，以下關于鏈表反轉的實現(xiàn)方法，錯誤的是（）A.使用三個指針依次遍歷并調整節(jié)點的鏈接關系B.遞歸方式實現(xiàn)時不需要額外的輔助空間C.迭代方式的時間復雜度為O(n)D.遞歸方式的空間復雜度比迭代方式低14、在一個具有n個元素的大頂堆中，若要將堆頂元素與最后一個元素交換，然后調整堆，其時間復雜度為：A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)15、在一個用鄰接矩陣表示的無向圖中，矩陣中的元素表示什么？A.頂點之間的距離B.頂點之間是否有邊C.邊的權重D.以上都有可能16、以下關于哈希表沖突解決方法的描述，哪一項是不正確的？（）A.鏈地址法會增加存儲空間的開銷B.開放定址法的查找效率一定高于鏈地址法C.再哈希法可以減少沖突的發(fā)生D.建立公共溢出區(qū)可以存儲發(fā)生沖突的元素17、設有一個鏈棧，棧頂指針為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;18、一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲，其空間復雜度為？（）A.O(n+e)B.O(n^2)C.O(e^2)D.O(n^2+e)19、以下關于拓撲排序的描述，正確的是：A.拓撲排序的結果是唯一的B.一個有環(huán)的圖也可以進行拓撲排序C.拓撲排序可以用于判斷一個圖是否有環(huán)D.拓撲排序只能用于有向圖20、對于一個采用鏈表存儲的隊列，若要刪除隊尾元素，以下關于操作的時間復雜度的描述，哪一個是恰當?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)二、簡答題（本大題共4個小題，共40分)1、（本題10分）解釋在一個帶權無向圖中，如何使用弗洛伊德算法求解任意兩點之間的最短路徑，說明算法的空間復雜度和時間復雜度。2、（本題10分）在一個具有n個頂點的無向圖中，如何找出所有的割點，給出一種有效的算法并分析其時間復雜度。3、（本題10分）論述如何檢測圖是否為二部圖，并說明其在實際問題中的應用。4、（本題10分）解釋并舉例說明在一個具有n個