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

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

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