站名：站名：年級專業：姓名：學號：凡年級專業、姓名、學號錯寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁北京郵電大學《數據結構課程設計》

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