成都大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2022-2023學(xué)年期末試卷

裝訂線裝訂線PAGE2第1頁，共3頁成都大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》

2022-2023學(xué)年期末試卷院(系)_______班級_______學(xué)號_______姓名_______題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、哈希表的沖突解決方法有多種，以下關(guān)于它們的說法中，錯誤的是？（）A.開放定址法是一種常用的沖突解決方法，它通過在哈希表中尋找下一個空閑位置來解決沖突。B.鏈地址法是另一種常用的沖突解決方法，它將沖突的元素存儲在鏈表中。C.再哈希法是通過使用不同的哈希函數(shù)來解決沖突。D.哈希表的沖突解決方法只有開放定址法和鏈地址法兩種。2、鏈表是另一種常見的數(shù)據(jù)結(jié)構(gòu)，它由一系列節(jié)點組成，每個節(jié)點包含數(shù)據(jù)和指向下一個節(jié)點的指針。以下關(guān)于鏈表的說法中，錯誤的是？（）A.鏈表的插入和刪除操作比較方便，只需要修改指針即可。B.鏈表可以動態(tài)地增長和縮小，不像數(shù)組那樣受固定長度的限制。C.鏈表的訪問速度比數(shù)組慢，因為需要遍歷鏈表才能找到特定的元素。D.鏈表只能存儲整數(shù)類型的數(shù)據(jù)元素。3、在一個具有n個元素的順序表中，若要刪除第i個元素（1<=i<=n），并將后面的元素向前移動，平均需要移動多少個元素？（）A.n-iB.iC.(n-i)/2D.n-i+14、若一棵二叉樹的中序遍歷序列為ABCDE，后序遍歷序列為BDCAE，則其先序遍歷序列為？（）A.EACDBB.EABCDC.EADCBD.EDACB5、在一個具有n個元素的堆中，查找最大元素的時間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)6、在一個平衡二叉搜索樹中，插入一個新節(jié)點后，可能需要進(jìn)行的調(diào)整操作次數(shù)最多為（）A.1B.lognC.nD.nlogn7、在一個具有n個節(jié)點的二叉樹中，若采用后序遍歷得到的節(jié)點序列是ABC，中序遍歷序列是BAC，則先序遍歷序列是什么？A.CABB.ABCC.ACBD.無法確定8、在一個具有n個節(jié)點的完全二叉樹中，若節(jié)點編號從1開始，對于編號為i的節(jié)點，其雙親節(jié)點的編號是多少？A.i/2B.(i-1)/2C.(i+1)/2D.以上都不對9、若要對100個元素進(jìn)行排序，以下哪種排序算法在最壞情況下的時間復(fù)雜度最低？A.冒泡排序B.選擇排序C.插入排序D.歸并排序10、以下關(guān)于紅黑樹的性質(zhì)，錯誤的是：A.每個節(jié)點要么是紅色，要么是黑色B.根節(jié)點是黑色的C.每個葉子節(jié)點（NIL節(jié)點）是黑色的D.紅色節(jié)點的子節(jié)點一定是紅色的11、在一個有向圖中，所有頂點的入度之和與出度之和的關(guān)系是：A.入度之和大于出度之和B.入度之和小于出度之和C.入度之和等于出度之和D.沒有確定的關(guān)系12、以下哪種排序算法在平均情況下的時間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序13、在一個具有n個元素的順序表中，要在中間位置插入一個新元素，平均移動元素的個數(shù)約為？A.n/2B.nC.lognD.114、對于一個具有n個元素的無序數(shù)組，使用選擇排序進(jìn)行排序，其交換次數(shù)最多為？A.n-1B.nC.n(n-1)/2D.n^215、對于一個具有n個元素的堆，進(jìn)行插入操作的時間復(fù)雜度為？（）A.O(1)B.O(logn)C.O(n)D.O(nlogn)16、在一個具有n個元素的二叉排序樹中，查找一個不存在的元素，其時間復(fù)雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)17、在一棵平衡二叉樹中，插入一個新節(jié)點后可能導(dǎo)致失衡，需要進(jìn)行調(diào)整。以下哪種調(diào)整操作可能涉及到旋轉(zhuǎn)次數(shù)最多？（）A.LL型調(diào)整B.RR型調(diào)整C.LR型調(diào)整D.RL型調(diào)整18、一個有序序列為{12,18,24,35,47,50,62,83,90,115,134}，當(dāng)用二分法查找值為90的元素時，需要比較的次數(shù)是（）。A.1B.2C.3D.419、以下哪種數(shù)據(jù)結(jié)構(gòu)能夠高效地支持區(qū)間查詢操作？（）A.線段樹B.二叉搜索樹C.堆D.鏈表20、并查集是一種用于處理不相交集合的數(shù)據(jù)結(jié)構(gòu)。在并查集中，以下操作不正確的是（）A.查找操作用于確定元素所屬的集合B.合并操作將兩個集合合并為一個C.并查集可以高效地判斷兩個元素是否在同一個集合中D.并查集的時間復(fù)雜度與集合的數(shù)量成正比二、簡答題（本大題共4個小題，共40分)1、（本題10分）論述伸展樹在頻繁隨機(jī)訪問場景下的性能優(yōu)勢和潛在問題。2、（本題10分）詳細(xì)闡述在一個具有n個頂點的無向圖中，如何求解最小度生成樹問題。3、（本題10分）比較計數(shù)排序和快速排序在對不同特征數(shù)據(jù)的處理能力。4、（本題10分）數(shù)組的排序算法中，堆排序的實現(xiàn)過程是怎樣的？時間復(fù)雜度和空間復(fù)雜度分別是多少？三、設(shè)計題（本大題共2個小