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

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

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