裝訂線裝訂線PAGE2第1頁，共3頁常州大學《數據結構》

2021-2022學年期末試卷院(系)_______班級_______學號_______姓名_______題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、對于一個有向圖，使用鄰接矩陣存儲，判斷是否存在從頂點i到頂點j的邊的時間復雜度為（）A.O(1)B.O(n)C.O(logn)D.O(n^2)2、對于單鏈表，若要訪問鏈表中的第i個元素，必須從鏈表的頭指針開始依次遍歷，平均時間復雜度為O(n)。那么如果要在鏈表的末尾添加一個新元素，時間復雜度是多少？（）A.O(1)B.O(n)C.O(logn)D.O(nlogn)3、在一棵平衡二叉樹中，插入一個新節點后可能導致失衡，需要進行調整。以下哪種調整操作可能涉及到旋轉次數最多？（）A.LL型調整B.RR型調整C.LR型調整D.RL型調整4、在一個具有n個節點的帶權有向圖中，若存在負權邊，以下哪種最短路徑算法可能不適用？A.迪杰斯特拉算法B.貝爾曼-福特算法C.弗洛伊德算法D.以上都適用5、對于一個采用鏈表存儲的棧，若要獲取棧的大小（元素數量），以下關于操作的時間復雜度的描述，哪一個是準確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、樹是一種非線性數據結構，它由節點和邊組成。以下關于樹的說法中，錯誤的是？（）A.樹中的每個節點都有一個父節點（除了根節點）和零個或多個子節點。B.二叉樹是一種特殊的樹，每個節點最多有兩個子節點。C.樹可以用于實現文件系統、數據庫索引等。D.樹的遍歷方式只有前序遍歷、中序遍歷和后序遍歷三種。7、在一個哈希表中，若采用線性探測法解決哈希沖突，當發生沖突時，新元素會存儲在什么位置？A.沖突位置的下一個位置B.沖突位置C.隨機位置D.以上都不對8、設有一個廣義表L=(a,(b,c),d)，其長度和深度分別為？（）A.3和2B.3和3C.4和2D.4和39、棧和隊列在計算機科學中有很多應用，以下關于它們的應用場景的說法中，錯誤的是？（）A.棧可以用于實現表達式求值、括號匹配等。B.隊列可以用于實現任務調度、消息隊列等。C.棧和隊列可以用于實現圖的深度優先搜索和廣度優先搜索。D.棧和隊列只能在編程語言的底層實現中使用，不能在實際應用中直接使用。10、在一個鏈式存儲的隊列中，進行入隊和出隊操作時，指針的移動方向分別是（）A.入隊向前，出隊向后B.入隊向后，出隊向前C.均向前D.均向后11、在一棵平衡二叉樹中，插入一個新結點后，可能需要進行的調整操作是：A.左旋B.右旋C.左旋和右旋D.不需要調整12、設有一個具有n個頂點的有向圖，采用鄰接表存儲。若要計算每個頂點的出度，以下關于操作的時間復雜度的描述，哪一項是恰當的？A.O(n)B.O(n+e)C.O(n^2)D.O(e)13、對于一個用鏈表實現的棧，若要獲取棧中元素的個數，以下哪種方法效率較高？A.遍歷鏈表B.維護一個計數器C.以上效率相同D.以上都不對14、在一個具有n個節點的無向圖中，若邊的數量遠遠小于n(n-1)/2，則適合使用哪種存儲方式？A.鄰接矩陣B.鄰接表C.十字鏈表D.以上都可以15、在一個具有n個節點的二叉樹中，若采用后序遍歷得到的節點序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定16、在一個具有n個節點的無向圖中，若要判斷兩個節點之間是否存在路徑，可以使用哪種算法？A.深度優先搜索B.廣度優先搜索C.普里姆算法D.克魯斯卡爾算法17、對于一個具有n個頂點和e條邊的無向圖，采用鄰接表存儲，若要刪除一條邊，平均需要修改多少個指針？（）A.1B.2C.eD.2e18、以下哪種排序算法在平均情況下的時間復雜度最優？A.冒泡排序B.快速排序C.插入排序D.選擇排序19、在一個鏈式存儲的隊列中，若隊頭指針為front，隊尾指針為rear，要刪除隊頭元素，需要進行的操作是？（）A.front=front->next;B.rear=front;C.rear=rear->next;D.front=NULL;20、對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表存儲，則其空間復雜度為：A.O(n)B.O(n+e)C.O(n^2)D.O(e^2)二、簡答題（本大題共4個小題，共40分)1、（本題10分）深入解釋在鏈表中，如何實現頭插法和尾插法創建鏈表，并比較它們在不同場景下的優缺點。2、（本題10分）解釋如何在一個帶權無向圖中計算任意兩個頂點之間路徑的最大權值和最小值之差。3、（本題10分）詳細論述在利用二叉樹進行后序線索化的過程中，如何建立線索和遍歷線索二叉樹，并給出相應的算法步驟和代碼示例。4、（本題10分）解釋在鏈表中刪除一個節點時，如何正確更新指針以保持鏈表的完整性，并舉例說明。三、設計題（本大