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

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁北京工業(yè)大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法課設(shè)》

2021-2022學(xué)年期末試卷題號一二三總分得分一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在一個具有n個元素的二叉排序樹中，查找一個不存在的元素，其時間復(fù)雜度最壞情況下為？（）A.O(1)B.O(log?n)C.O(n)D.O(n2)2、對于一個具有n個頂點的無向圖，若其所有頂點的度之和為20，則該圖的邊數(shù)為（）。A.5B.10C.15D.203、在一個容量為10的順序存儲的循環(huán)隊列中，若front=4，rear=8，則此時隊列中元素的個數(shù)為：A.4B.5C.6D.74、對于一個具有n個頂點和e條邊的有向完全圖，其弧的條數(shù)為（）。A.n(n-1)B.n(n-1)/2C.n(n+1)D.n(n+1)/25、在圖的最小生成樹算法中，Kruskal算法和Prim算法都能得到最小生成樹，以下關(guān)于這兩個算法的比較，錯誤的是（）A.Kruskal算法基于邊，Prim算法基于節(jié)點B.Kruskal算法需要使用并查集C.Prim算法的時間復(fù)雜度通常比Kruskal算法低D.對于稀疏圖，Kruskal算法更優(yōu)6、對于一個用鏈表實現(xiàn)的二叉樹，進行先序遍歷。以下關(guān)于先序遍歷的時間復(fù)雜度的描述，哪一項是正確的？A.O(1)B.O(n)C.O(logn)D.O(nlogn)7、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。在有向圖中，頂點的入度是指指向該頂點的邊的數(shù)量。若要計算一個有向圖中所有頂點的入度，哪種算法較為合適？A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.拓撲排序D.以上都可以8、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)LRU（最近最少使用）頁面置換算法？A.隊列B.棧C.哈希表D.雙鏈表9、深度為5的滿二叉樹的結(jié)點數(shù)為：A.16B.31C.32D.1510、廣義表((a,b),c,(d,(e,f)))的長度和深度分別為：A.3和2B.3和3C.4和2D.4和311、在一棵二叉樹中，若每個節(jié)點的左子樹和右子樹的高度最多相差1，則該二叉樹被稱為平衡二叉樹。對于一個平衡二叉樹，進行插入操作后，為了保持平衡，可能需要進行多少次旋轉(zhuǎn)調(diào)整？A.0次B.1次C.最多2次D.不確定12、若要在一個具有n個元素的有序鏈表中插入一個新元素，使其仍然有序，平均時間復(fù)雜度為？（）A.O(1)B.O(log?n)C.O(n)D.O(nlog?n)13、在一個具有n個元素的順序表中，若要在第i個元素（1<=i<=n）之前插入一個新元素，需要移動的元素個數(shù)為？（）A.n-iB.iC.n-i+1D.n-i-114、數(shù)組是一種常見的數(shù)據(jù)結(jié)構(gòu)，它具有固定的大小和連續(xù)的存儲位置。以下關(guān)于數(shù)組的說法中，錯誤的是？（）A.數(shù)組可以通過下標(biāo)快速訪問其中的元素。B.數(shù)組的插入和刪除操作比較耗時，因為需要移動大量的元素。C.數(shù)組可以存儲不同類型的數(shù)據(jù)元素。D.數(shù)組的長度在創(chuàng)建后不能改變。15、對于一個滿二叉樹，若其高度為h，則其節(jié)點總數(shù)為多少？（）A.2^h-1B.2^(h-1)C.2^hD.2^(h+1)-116、以下關(guān)于線索二叉樹的描述，錯誤的是：A.線索二叉樹便于在中序遍歷中查找前驅(qū)和后繼節(jié)點B.線索二叉樹中的線索是指向空指針的指針C.線索二叉樹的存儲空間利用率比普通二叉樹高D.線索二叉樹的構(gòu)建過程非常簡單，不需要復(fù)雜的算法17、對于一個具有n個節(jié)點的紅黑樹，插入一個新節(jié)點后，調(diào)整樹的結(jié)構(gòu)以保持紅黑樹性質(zhì)，其時間復(fù)雜度為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)18、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實現(xiàn)表達式求值？A.二叉樹B.棧C.隊列D.哈希表19、對于一個具有n個節(jié)點的二叉樹，其高度的最小值和最大值分別是多少？（）A.log?n,n-1B.1,nC.log?n,nD.1,n-120、在一個帶權(quán)的有向圖中，使用迪杰斯特拉算法求從源點到其他頂點的最短路徑，每次選擇的頂點是？（）A.距離源點最近的頂點B.距離源點最遠的頂點C.未確定最短路徑的頂點中權(quán)值最小的頂點D.未確定最短路徑的頂點中權(quán)值最大的頂點二、簡答題（本大題共4個小題，共40分)1、（本題10分）詳細闡述如何將一個有序鏈表轉(zhuǎn)換為平衡二叉搜索樹，給出具體的算法步驟。2、（本題10分）詳細闡述基數(shù)排序和桶排序在處理不同類型數(shù)據(jù)時的特點和適用范圍。3、（本題10分）在一個具有n個頂點和e條邊的無向圖中，如何使用鄰接矩陣和鄰接表兩種方式存儲圖的結(jié)構(gòu)，比較它們在存儲空間和操作效率上的優(yōu)缺點。4、（本題10分）闡述如何在一個具有n個元素的數(shù)組中，找出所有不重復(fù)的元素，分析所使用的算法和時間復(fù)雜度。三、設(shè)計題（本大題共2個