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