北京城市學(xué)院《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》2022-2023學(xué)年期末試卷

學(xué)校________________班級(jí)____________姓名____________考場____________準(zhǔn)考證號(hào)學(xué)校________________班級(jí)____________姓名____________考場____________準(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、若對一棵二叉排序樹進(jìn)行中序遍歷，得到的節(jié)點(diǎn)序列是一個(gè)遞增序列，則該二叉排序樹（）。A.沒有左子樹B.沒有右子樹C.左子樹均為空D.右子樹均為空2、對于一個(gè)具有n個(gè)元素的循環(huán)隊(duì)列，隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列滿的條件是？（）A.(rear+1)%MaxSize==frontB.rear==frontC.rear+1==frontD.(rear-1)%MaxSize==front3、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)文件系統(tǒng)中的目錄結(jié)構(gòu)？（）A.棧B.隊(duì)列C.樹D.哈希表4、圖的最短路徑算法有多種，以下關(guān)于它們的說法中，錯(cuò)誤的是？（）A.迪杰斯特拉算法用于求解單源最短路徑問題，即從一個(gè)源點(diǎn)到其他所有頂點(diǎn)的最短路徑。B.弗洛伊德算法用于求解任意兩點(diǎn)之間的最短路徑問題。C.貝爾曼-福特算法也可以用于求解單源最短路徑問題，但它的時(shí)間復(fù)雜度比迪杰斯特拉算法高。D.圖的最短路徑算法只有迪杰斯特拉算法和弗洛伊德算法兩種。5、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的隊(duì)列中，若隊(duì)頭指針為front，隊(duì)尾指針為rear，當(dāng)進(jìn)行一次出隊(duì)操作后，front指針應(yīng)該如何移動(dòng)？A.front=front->nextB.front=rearC.front不變D.front=NULL6、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向連通圖，利用Prim算法構(gòu)造最小生成樹時(shí)，其時(shí)間復(fù)雜度為：A.O(n^2)B.O(elogn)C.O(nlogn)D.O(e^2)7、在數(shù)據(jù)結(jié)構(gòu)中，線段樹的區(qū)間更新操作可以通過懶標(biāo)記實(shí)現(xiàn)，以下關(guān)于懶標(biāo)記的描述，不正確的是（）A.減少不必要的節(jié)點(diǎn)更新B.提高更新操作的效率C.可能會(huì)導(dǎo)致查詢結(jié)果不準(zhǔn)確D.標(biāo)記需要在適當(dāng)?shù)臅r(shí)候向下傳遞8、在一個(gè)具有n個(gè)節(jié)點(diǎn)的完全二叉樹中，其葉子節(jié)點(diǎn)的數(shù)量大約為（）A.n/2B.n/4C.n/8D.n/2-19、對于一個(gè)具有n個(gè)元素的無序數(shù)組，使用冒泡排序進(jìn)行排序，最壞情況下的比較次數(shù)為？A.n(n-1)/2B.nlognC.n^2D.2^n10、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)無向圖，使用克魯斯卡爾算法構(gòu)造最小生成樹時(shí)，每次選擇的邊是？（）A.權(quán)值最小的邊B.連接兩個(gè)連通分量的權(quán)值最小的邊C.任意一條邊D.以上都不對11、在一個(gè)具有n個(gè)元素的無序數(shù)組中，采用冒泡排序進(jìn)行排序，在最壞情況下，需要比較的次數(shù)為（）。A.n-1B.n(n-1)/2C.n(n+1)/2D.n^212、設(shè)有一個(gè)10階的對稱矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)存儲(chǔ)單元，則a85的地址為？（）A.33B.32C.18D.4013、在一個(gè)用鄰接表表示的無向圖中，若要?jiǎng)h除一條邊，需要進(jìn)行哪些操作？A.在兩個(gè)相關(guān)頂點(diǎn)的鄰接表中刪除對應(yīng)的邊節(jié)點(diǎn)B.只在一個(gè)頂點(diǎn)的鄰接表中刪除對應(yīng)的邊節(jié)點(diǎn)C.重新構(gòu)建鄰接表D.以上都不對14、在數(shù)據(jù)結(jié)構(gòu)中，伸展樹（SplayTree）通過自調(diào)整保持較好的性能，以下關(guān)于伸展樹的操作，不正確的是（）A.查找操作會(huì)將被查找的節(jié)點(diǎn)旋轉(zhuǎn)到根節(jié)點(diǎn)B.插入操作可能會(huì)引起多次旋轉(zhuǎn)C.伸展樹的平均性能較好D.伸展樹的空間復(fù)雜度較高15、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)圖的存儲(chǔ)？A.鄰接矩陣和鄰接表B.二叉樹和鏈表C.棧和隊(duì)列D.數(shù)組和哈希表16、對于一個(gè)有向無環(huán)圖（DAG），進(jìn)行拓?fù)渑判虻姆椒ú恢挂环N。以下關(guān)于拓?fù)渑判虻拿枋?，錯(cuò)誤的是（）A.可以使用深度優(yōu)先搜索實(shí)現(xiàn)B.結(jié)果不唯一C.可以用于判斷圖中是否存在環(huán)D.所有節(jié)點(diǎn)的入度在排序過程中不會(huì)改變17、在一個(gè)用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的棧中，若棧頂指針top指向棧頂元素的上一個(gè)位置，當(dāng)棧為空時(shí)，top的值為？A.-1B.0C.1D.n-1（其中n為棧的最大容量）18、設(shè)有一個(gè)m階的B+樹，每個(gè)節(jié)點(diǎn)最多有m個(gè)孩子，除根節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)至少有┌m/2┐個(gè)孩子。若要插入一個(gè)新關(guān)鍵字，需要進(jìn)行節(jié)點(diǎn)分裂的條件是？（）A.節(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)等于mB.節(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)大于mC.節(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)等于┌m/2┐D.節(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)小于┌m/2┐19、在一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)無向圖中，若采用普里姆（Prim）算法生成最小生成樹，其時(shí)間復(fù)雜度為？（）A.O(n2)B.O(eloge)C.O(nlogn)D.O(e2)20、在一個(gè)具有n個(gè)元素的線性表中，采用順序查找法查找一個(gè)特定元素，若查找成功，平均查找長度為？（）A.(n+1)/2B.n/2C.lognD.n二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）論述如何利用圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法解決迷宮問題。2、（本題10分）論述如何使用計(jì)數(shù)排序?qū)μ囟l件下的數(shù)組進(jìn)行排序，給出算法步驟和時(shí)間復(fù)雜度分析。3、（本題10分）解釋什么是字典樹（Trie樹）數(shù)據(jù)結(jié)構(gòu)，說明其特點(diǎn)和應(yīng)用場景，并闡述如何進(jìn)行插入和查找操作。4、（本題10分）在一個(gè)鏈