北京郵電大學《數(shù)據結構與算法課程設計》2022-2023學年期末試卷

學校________________班級____________姓名____________考場____________準考證號學校________________班級____________姓名____________考場____________準考證號…………密…………封…………線…………內…………不…………要…………答…………題…………第1頁，共3頁北京郵電大學《數(shù)據結構與算法課程設計》

2022-2023學年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個小題，每小題2分，共40分．在每小題給出的四個選項中，只有一項是符合題目要求的．）1、在圖的存儲結構中，鄰接多重表主要用于存儲無向圖，以下關于鄰接多重表的特點，描述錯誤的是（）A.可以方便地刪除邊B.存儲空間比鄰接矩陣節(jié)省C.對于判斷兩點之間是否有邊，效率較高D.不適合用于有向圖的存儲2、在數(shù)據結構中，雙向循環(huán)鏈表相較于單向鏈表，以下優(yōu)勢描述錯誤的是（）A.可以方便地反向遍歷B.插入和刪除節(jié)點的操作更簡單C.查找前一個節(jié)點的時間復雜度更低D.空間復雜度更低3、若對一棵二叉搜索樹進行先序遍歷，得到的節(jié)點序列是一個遞減序列，則該二叉搜索樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空4、若一棵二叉樹的先序遍歷序列為ABC，中序遍歷序列為BAC，則該二叉樹的后序遍歷序列為？（）A.BCAB.CBAC.ABCD.ACB5、對于一個具有n個節(jié)點的二叉排序樹，刪除一個節(jié)點后，重新調整為二叉排序樹，其時間復雜度最壞情況下為？A.O(1)B.O(logn)C.O(n)D.O(nlogn)6、設有一個具有n個元素的最大堆，若要獲取堆中的最大元素，以下關于操作的時間復雜度的描述，哪一項是正確的？A.O(1)B.O(logn)C.O(n)D.O(nlogn)7、在數(shù)據結構中，字典樹在處理大量字符串時，可能會出現(xiàn)內存占用過高的問題，以下解決方法錯誤的是（）A.壓縮節(jié)點B.限制字典樹的深度C.使用哈希表替代字典樹D.減少字符串的存儲8、以下哪種數(shù)據結構常用于實現(xiàn)LRU（最近最少使用）緩存淘汰策略？（）A.隊列B.棧C.哈希表D.雙向鏈表9、已知一個圖的鄰接矩陣如下所示：ABCDA0110B1011C1100D0100則該圖中頂點A的度為：A.1B.2C.3D.410、在一個具有n個元素的雙向鏈表中，若要刪除尾結點，需要修改幾個指針？（）A.1B.2C.3D.411、設有一個廣義表L=(a,(b,c),d)，其長度和深度分別為？（）A.3和2B.3和3C.4和2D.4和312、對于一個具有n個頂點的無向圖，若其邊的集合為{(1,2),(1,3),(2,3),(2,4),(3,4)}，則該圖的鄰接表存儲中，頂點2的鏈表中包含的頂點有：A.1,3,4B.1,3C.3,4D.1,413、設有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱為：A.連接B.模式匹配C.求子串D.求串長14、在一個具有n個頂點和e條邊的有向圖中，采用鄰接表存儲，求頂點的入度的時間復雜度為？（）A.O(n)B.O(e)C.O(n+e)D.O(n2)15、在一個具有n個頂點的強連通圖中，至少有（）條邊。A.n-1B.nC.n(n-1)D.n(n-1)/216、在一個具有n個頂點的連通圖中，生成樹的邊數(shù)一定為？（）A.n-1B.nC.n+1D.2n17、以下關于哈希沖突解決方法中二次探測法的描述，哪一項是不正確的？（）A.可以減少聚集現(xiàn)象B.探測的位置是連續(xù)的C.可能會出現(xiàn)找不到空閑位置的情況D.相比線性探測法，性能更優(yōu)18、在數(shù)據結構中，跳表的索引層數(shù)是根據數(shù)據量動態(tài)調整的，以下關于索引層數(shù)調整的描述，錯誤的是（）A.當數(shù)據量增加時，可能增加索引層數(shù)B.索引層數(shù)越多，查找效率越高C.調整索引層數(shù)的過程比較復雜D.索引層數(shù)的調整不會影響數(shù)據的存儲結構19、對于一個具有n個元素的有序數(shù)組，使用二分查找算法查找一個特定元素。以下關于二分查找的時間復雜度的描述，哪一個是恰當?shù)模緼.O(1)B.O(logn)C.O(n)D.O(nlogn)20、在二叉搜索樹中，每個節(jié)點的值都大于其左子樹中所有節(jié)點的值，小于其右子樹中所有節(jié)點的值。以下關于二叉搜索樹的操作，不正確的是（）A.插入操作需要按照節(jié)點值的大小找到合適的位置B.查找操作的時間復雜度在最壞情況下為O(n)C.刪除節(jié)點時，如果該節(jié)點有兩個子節(jié)點，可以選擇其左子樹中的最大節(jié)點或右子樹中的最小節(jié)點進行替換D.二叉搜索樹總是平衡的，即左右子樹的高度差不超過1二、簡答題（本大題共4個小題，共40分)1、（本題10分）闡述后綴樹在自然語言處理中的應用場景和技術挑戰(zhàn)。2、（本題10分）描述二叉樹的遍歷算法在二叉樹的路徑總和問題、節(jié)點間最大距離問題中的應用。3、（本題10分）論述如何利用深度優(yōu)先搜索算法檢測圖中是否存在環(huán)。4、（本題10分）簡述數(shù)據結構中棧的定義、特點及基本操作，并舉例說明棧在實際中的應用。三、設計