北京交通大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》2021-2022學(xué)年期末試卷

自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密自覺遵守考場(chǎng)紀(jì)律如考試作弊此答卷無效密封線第1頁，共3頁北京交通大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》

2021-2022學(xué)年期末試卷院(系)_______班級(jí)_______學(xué)號(hào)_______姓名_______題號(hào)一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、二叉樹的性質(zhì)和遍歷方式可以用于解決很多實(shí)際問題，以下關(guān)于它們的應(yīng)用的說法中，錯(cuò)誤的是？（）A.二叉搜索樹可以用于實(shí)現(xiàn)高效的查找、插入和刪除操作。B.平衡二叉樹可以用于解決二叉搜索樹的不平衡問題，提高查找效率。C.二叉樹的遍歷方式可以用于實(shí)現(xiàn)二叉樹的復(fù)制、遍歷和序列化等操作。D.二叉樹的性質(zhì)和遍歷方式只適用于理論研究，在實(shí)際應(yīng)用中沒有實(shí)際價(jià)值。2、在一個(gè)具有n個(gè)頂點(diǎn)的有向無環(huán)圖中，使用拓?fù)渑判蛩惴?，其結(jié)果的唯一性如何？A.一定唯一B.可能不唯一C.取決于頂點(diǎn)的編號(hào)D.以上都不對(duì)3、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同4、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，若采用迪杰斯特拉（Dijkstra）算法求單源最短路徑，其時(shí)間復(fù)雜度為（）。A.O(n^2)B.O(elog?e)C.O(nlog?n)D.O(n^3)5、在一個(gè)順序存儲(chǔ)的隊(duì)列中，若要在隊(duì)尾插入一個(gè)元素，需要移動(dòng)元素的平均次數(shù)為（）A.0B.n/2C.nD.n-16、對(duì)于一個(gè)具有n個(gè)元素的堆，若要?jiǎng)h除堆頂元素并調(diào)整堆，時(shí)間復(fù)雜度為？（）A.O(logn)B.O(n)C.O(nlogn)D.O(n^2)7、設(shè)棧的初始狀態(tài)為空，元素1、2、3、4、5依次入棧，出棧序列不可能是？（）A.54321B.21543C.21345D.154328、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向完全圖，其弧的條數(shù)為（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/29、若要在一棵二叉搜索樹中查找一個(gè)特定的值，平均時(shí)間復(fù)雜度為？（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)10、線段樹是一種用于處理區(qū)間查詢和更新的數(shù)據(jù)結(jié)構(gòu)。對(duì)于線段樹的應(yīng)用，以下說法錯(cuò)誤的是（）A.可以快速計(jì)算給定區(qū)間內(nèi)元素的和B.可以用于查找區(qū)間內(nèi)的最大值和最小值C.構(gòu)建線段樹的時(shí)間復(fù)雜度為O(n)D.線段樹的空間復(fù)雜度與節(jié)點(diǎn)數(shù)量成正比11、哈希表是一種用于快速查找的數(shù)據(jù)結(jié)構(gòu)。在處理哈希沖突時(shí)，常用的方法有開放地址法和鏈地址法。以下關(guān)于這兩種方法的描述，哪一項(xiàng)是不準(zhǔn)確的？A.開放地址法會(huì)增加查找時(shí)間B.鏈地址法需要額外的指針空間C.開放地址法容易產(chǎn)生聚集現(xiàn)象D.鏈地址法的沖突解決更復(fù)雜12、以下哪種排序算法在平均情況下的時(shí)間復(fù)雜度最優(yōu)？A.冒泡排序B.快速排序C.插入排序D.選擇排序13、在數(shù)據(jù)結(jié)構(gòu)中，使用棧來實(shí)現(xiàn)表達(dá)式求值，以下關(guān)于表達(dá)式求值的過程，描述錯(cuò)誤的是（）A.遇到操作數(shù)入棧B.遇到運(yùn)算符時(shí)，彈出棧頂?shù)膬蓚€(gè)操作數(shù)進(jìn)行計(jì)算C.括號(hào)不影響求值的順序D.最終棧頂元素即為表達(dá)式的結(jié)果14、在一個(gè)具有n個(gè)元素的有序數(shù)組中，使用插入排序進(jìn)行排序，其最壞情況下的時(shí)間復(fù)雜度為？（）A.O(n)B.O(log?n)C.O(n2)D.O(nlog?n)15、對(duì)于一個(gè)具有n個(gè)元素的希爾排序，其時(shí)間復(fù)雜度取決于？（）A.初始序列B.增量序列C.元素值D.以上都是16、設(shè)有一個(gè)廣義表L=((a,b),c,(d,e))，其表頭和表尾分別為？（）A.(a,b)和(c,(d,e))B.(a,b)和(c,d,e)C.((a,b))和(c,(d,e))D.((a,b))和(c,d,e)17、在一個(gè)長(zhǎng)度為n的有序線性表中進(jìn)行二分查找，在最壞情況下，需要比較的次數(shù)為（）。A.O(n)B.O(n^2)C.O(log?n)D.O(nlog?n)18、在一個(gè)具有n個(gè)元素的順序存儲(chǔ)的線性表中，要在第i個(gè)位置插入一個(gè)新元素（1<=i<=n+1），需要移動(dòng)的元素個(gè)數(shù)約為？A.n-iB.iC.n-i+1D.n-i-119、跳表是一種基于鏈表的數(shù)據(jù)結(jié)構(gòu)，用于實(shí)現(xiàn)有序集合的快速查找。關(guān)于跳表的特點(diǎn)，以下描述錯(cuò)誤的是（）A.跳表的查找、插入和刪除操作的平均時(shí)間復(fù)雜度為O(logn)B.跳表通過增加索引層次來提高查找效率C.跳表的空間復(fù)雜度比普通鏈表高D.跳表的性能不如二叉搜索樹20、對(duì)于一個(gè)具有n個(gè)元素的有序單鏈表，要查找一個(gè)值為x的元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.1二、簡(jiǎn)答題（本大題共4個(gè)小題，共40分)1、（本題10分）比較希爾排序和插入排序在元素移動(dòng)方式上的不同。2、（本題10分）鏈表的歸并排序有哪些步驟？請(qǐng)?jiān)敿?xì)描述其實(shí)現(xiàn)過程。3、（本題10分）詳細(xì)解釋在一個(gè)具有n個(gè)元素的二叉樹中，如何通過中序遍歷判斷二叉樹是否為搜索二叉樹。4、（本題10分）在哈希表中，闡述常見的哈希函數(shù)構(gòu)造方法和處理沖突的策略，分析它們的優(yōu)缺點(diǎn)，并舉例說明在實(shí)際應(yīng)用中的選擇依