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

站名：站名：年級(jí)專業(yè)：姓名：學(xué)號(hào)：凡年級(jí)專業(yè)、姓名、學(xué)號(hào)錯(cuò)寫、漏寫或字跡不清者，成績按零分記。…………密………………封………………線…………第1頁，共1頁北京郵電大學(xué)《數(shù)據(jù)結(jié)構(gòu)與算法》

2021-2022學(xué)年期末試卷題號(hào)一二三總分得分一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在哈夫曼編碼中，對于出現(xiàn)頻率較高的字符，其編碼長度通常怎樣？（）A.較長B.較短C.固定不變D.隨機(jī)確定2、在一個(gè)具有n個(gè)頂點(diǎn)的連通圖中，生成樹的邊數(shù)一定為？（）A.n-1B.nC.n+1D.2n3、數(shù)據(jù)結(jié)構(gòu)的應(yīng)用非常廣泛，以下關(guān)于它們的應(yīng)用場景的說法中，錯(cuò)誤的是？（）A.數(shù)組可以用于存儲(chǔ)和處理大量的相同類型的數(shù)據(jù)。B.鏈表可以用于實(shí)現(xiàn)動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，如棧、隊(duì)列和鏈表等。C.樹可以用于實(shí)現(xiàn)文件系統(tǒng)、數(shù)據(jù)庫索引和表達(dá)式求值等。D.數(shù)據(jù)結(jié)構(gòu)只在計(jì)算機(jī)科學(xué)領(lǐng)域有應(yīng)用，在其他領(lǐng)域沒有實(shí)際價(jià)值。4、對于一個(gè)有向圖進(jìn)行深度優(yōu)先遍歷，若從頂點(diǎn)v開始，訪問完v的鄰接點(diǎn)后，接著應(yīng)該訪問哪個(gè)頂點(diǎn)？（）A.按照頂點(diǎn)編號(hào)順序的下一個(gè)未訪問頂點(diǎn)B.v的第一個(gè)鄰接點(diǎn)C.任意一個(gè)未訪問的鄰接點(diǎn)D.以上都不對5、在一個(gè)具有n個(gè)元素的鏈表中，若要在表頭插入一個(gè)新元素，平均需要修改幾個(gè)指針？（）A.1B.2C.nD.n+16、對于一個(gè)具有n個(gè)元素的歸并排序，其時(shí)間復(fù)雜度為？（）A.O(n)B.O(nlogn)C.O(n^2)D.O(logn)7、在一個(gè)具有n個(gè)元素的棧中，若要獲取棧底元素但不刪除，需要進(jìn)行多少次操作？（）A.1B.n-1C.nD.n+18、在一個(gè)用數(shù)組實(shí)現(xiàn)的循環(huán)隊(duì)列中，若front=rear，則隊(duì)列的狀態(tài)可能為（）A.隊(duì)空B.隊(duì)滿C.既不空也不滿D.以上都有可能9、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的無向連通圖，其生成樹的邊數(shù)為（）A.n-1B.nC.n+1D.2n10、對于一個(gè)具有n個(gè)元素的順序存儲(chǔ)的循環(huán)隊(duì)列，隊(duì)尾指針rear指向隊(duì)尾元素的下一個(gè)位置，隊(duì)頭指針front指向隊(duì)頭元素，若隊(duì)列非空，則隊(duì)列中元素的個(gè)數(shù)為？（）A.(rear-front+n)%nB.(rear-front)%nC.rear-frontD.rear-front+111、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表主要用于存儲(chǔ)有向圖，以下關(guān)于十字鏈表的特點(diǎn)，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲(chǔ)空間比鄰接表節(jié)省C.對于刪除邊的操作比較復(fù)雜D.不適合用于稀疏有向圖12、圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，若要表示一個(gè)有向圖，通?？梢允褂媚姆N存儲(chǔ)結(jié)構(gòu)？（）A.鄰接矩陣B.鄰接表C.十字鏈表D.以上均可13、對于一個(gè)具有n個(gè)元素的無序數(shù)組，使用插入排序進(jìn)行排序，其最好情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(logn)C.O(nlogn)D.O(n^2)14、在一個(gè)具有n個(gè)元素的雙向鏈表中，要在指定節(jié)點(diǎn)之后插入一個(gè)新節(jié)點(diǎn)，需要修改幾個(gè)指針？A.2B.3C.4D.515、設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)存儲(chǔ)單元，則a85的地址為？（）A.33B.32C.18D.4016、在一棵完全二叉樹中，若節(jié)點(diǎn)個(gè)數(shù)為n，那么其葉子節(jié)點(diǎn)的個(gè)數(shù)大約為多少？（）A.n/2B.n/4C.(n+1)/2D.n/317、在圖的最短路徑算法中，Dijkstra算法適用于帶權(quán)有向圖，以下關(guān)于Dijkstra算法的描述，錯(cuò)誤的是（）A.以起始節(jié)點(diǎn)為中心向外層層擴(kuò)展B.每次選擇距離起始節(jié)點(diǎn)最近的未訪問節(jié)點(diǎn)C.可以處理負(fù)權(quán)邊D.時(shí)間復(fù)雜度為O(n^2)18、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)字符串的反轉(zhuǎn)操作？A.棧B.隊(duì)列C.鏈表D.樹19、對于一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹，其高度的最小值和最大值分別是多少？（）A.log?n,n-1B.1,nC.log?n,nD.1,n-120、設(shè)有一個(gè)帶權(quán)有向圖G=(V,E)，采用拓?fù)渑判蛩惴▽ζ溥M(jìn)行排序，若得到的拓?fù)湫蛄形ㄒ?，則圖G一定是？（）A.有環(huán)圖B.無環(huán)圖C.強(qiáng)連通圖D.弱連通圖二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋如何在一個(gè)有序數(shù)組中進(jìn)行快速插入操作，保持?jǐn)?shù)組的有序性，給出算法步驟和實(shí)現(xiàn)代碼，并分析其時(shí)間復(fù)雜度。2、（本題10分）詳細(xì)闡述B樹和B+樹的結(jié)構(gòu)特點(diǎn)和區(qū)別，以及它們在數(shù)據(jù)庫中的應(yīng)用。3、（本題10分）解釋圖的最短路徑問題的變體，如帶權(quán)有向圖的單源最短路徑問題、所有點(diǎn)對最短路徑問題等。4、（本題10分）詳細(xì)論述在一個(gè)具有n個(gè)元素的循環(huán)鏈表中，如何實(shí)現(xiàn)插入、刪除和查找操作，并分析其時(shí)間復(fù)雜