北京郵電大學(xué)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》2021-2022學(xué)年期末試卷

站名：站名：年級專業(yè)：姓名：學(xué)號：凡年級專業(yè)、姓名、學(xué)號錯寫、漏寫或字跡不清者，成績按零分記?！堋狻€…………第1頁，共1頁北京郵電大學(xué)《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》

2021-2022學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個鏈?zhǔn)酱鎯Φ木€性表中，若要在第i個位置插入一個新元素，需要修改多少個指針？（）A.1B.2C.iD.i+12、在數(shù)據(jù)結(jié)構(gòu)中，棧是一種特殊的線性表，遵循先進后出的原則。以下關(guān)于棧的操作，錯誤的是（）A.入棧操作將元素添加到棧頂B.出棧操作取出并刪除棧頂元素C.可以在棧的任意位置進行插入和刪除操作D.棧頂指針始終指向棧頂元素3、設(shè)有一個長度為n的順序表，要在第i個元素之前插入一個新元素，并且移動元素的平均次數(shù)為n/2，則插入算法的平均時間復(fù)雜度為？A.O(n)B.O(n^2)C.O(logn)D.O(nlogn)4、在數(shù)據(jù)結(jié)構(gòu)中，線段樹的區(qū)間更新操作可以通過懶標(biāo)記實現(xiàn)，以下關(guān)于懶標(biāo)記的描述，不正確的是（）A.減少不必要的節(jié)點更新B.提高更新操作的效率C.可能會導(dǎo)致查詢結(jié)果不準(zhǔn)確D.標(biāo)記需要在適當(dāng)?shù)臅r候向下傳遞5、在一個哈希表中，若采用線性探測法解決哈希沖突，當(dāng)發(fā)生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機位置D.以上都不對6、以下關(guān)于堆的描述，正確的是：A.大頂堆中每個父節(jié)點的值都大于其子節(jié)點的值B.小頂堆中每個父節(jié)點的值都小于其子節(jié)點的值C.堆可以用順序存儲也可以用鏈?zhǔn)酱鎯.堆是完全二叉樹7、對于一個具有n個元素的希爾排序，其時間復(fù)雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是8、對于一個采用鏈?zhǔn)酱鎯Φ年犃?，若隊頭指針和隊尾指針相同，則隊列的狀態(tài)為：A.隊空B.隊滿C.不確定D.隊列中只有一個元素9、在一個循環(huán)鏈表中，若要刪除鏈表中的最后一個節(jié)點，需要的時間復(fù)雜度為（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)10、在一個具有n個元素的棧中，若要獲取棧底元素但不刪除，需要進行多少次操作？（）A.1B.n-1C.nD.n+111、在一個具有n個節(jié)點的帶權(quán)無向圖中，使用普里姆算法構(gòu)造最小生成樹，其時間復(fù)雜度是多少？A.O(n^2)B.O(nlogn)C.O(n^3)D.取決于圖的結(jié)構(gòu)12、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)字符串的反轉(zhuǎn)操作？A.棧B.隊列C.鏈表D.樹13、若要在一個具有n個元素的有序鏈表中插入一個新元素，使其仍然有序，平均時間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)14、對于一個具有n個頂點和e條邊的帶權(quán)無向圖，若采用Prim算法生成最小生成樹，其時間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)15、對于一個具有n個元素的選擇排序，在最壞情況下，需要進行多少次交換操作？（）A.n-1B.nC.n(n-1)/2D.016、若要在一個具有n個元素的有序數(shù)組中插入一個新元素，同時保持?jǐn)?shù)組有序，平均需要移動多少個元素？（）A.n/2B.nC.lognD.117、在一個具有n個元素的有序數(shù)組中，使用二分查找查找一個不存在的元素，最多比較次數(shù)約為？A.lognB.nC.n/2D.nlogn18、廣義表((a,b),c,(d,(e,f)))的長度和深度分別為：A.3和2B.3和3C.4和2D.4和319、對于一個具有n個元素的歸并排序，其時間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)20、對于一棵二叉樹，先序遍歷序列為ABC，中序遍歷序列為BAC，則其后序遍歷序列為？A.BCAB.CBAC.ACBD.ABC二、簡答題（本大題共4個小題，共40分)1、（本題10分）分析在數(shù)據(jù)結(jié)構(gòu)中，如何利用樹狀數(shù)組實現(xiàn)高效的區(qū)間查詢和更新操作。2、（本題10分）詳細(xì)說明如何在一個帶權(quán)無向圖中計算所有頂點對之間的最小權(quán)值路徑的平均值。3、（本題10分）詳細(xì)說明在一個具有n個頂點的有向圖中，如何判斷圖中是否存在環(huán)，給出一種有效的算法并分析其時間復(fù)雜度。4、（本題10分）詳細(xì)論述在一個具有n個頂點的無向圖中，如何判斷兩個子圖是否同構(gòu)。三、設(shè)計題（本大題共2個小題，共