北京郵電大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)》2022-2023學(xué)年期末試卷

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

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