北華大學(xué)《數(shù)據(jù)結(jié)構(gòu)》2023-2024學(xué)年期末試卷

學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號學(xué)校________________班級____________姓名____________考場____________準(zhǔn)考證號…………密…………封…………線…………內(nèi)…………不…………要…………答…………題…………第1頁，共3頁北華大學(xué)《數(shù)據(jù)結(jié)構(gòu)》

2023-2024學(xué)年期末試卷題號一二三總分得分批閱人一、單選題（本大題共20個(gè)小題，每小題2分，共40分．在每小題給出的四個(gè)選項(xiàng)中，只有一項(xiàng)是符合題目要求的．）1、在圖的存儲(chǔ)結(jié)構(gòu)中，十字鏈表主要用于存儲(chǔ)有向圖，以下關(guān)于十字鏈表的特點(diǎn)，描述不正確的是（）A.既能方便地訪問出邊，也能方便地訪問入邊B.存儲(chǔ)空間比鄰接表節(jié)省C.對于刪除邊的操作比較復(fù)雜D.不適合用于稀疏有向圖2、在一個(gè)B樹中，每個(gè)節(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)量最少為多少？（）A.1B.2C.?m/2?-1D.m-13、棧是一種特殊的線性表，遵循先進(jìn)后出的原則。當(dāng)一個(gè)棧已滿，再進(jìn)行入棧操作時(shí)，通常會(huì)發(fā)生什么情況？A.覆蓋棧頂元素B.產(chǎn)生溢出錯(cuò)誤C.新建一個(gè)更大的棧D.自動(dòng)擴(kuò)展棧的容量4、在一個(gè)鏈?zhǔn)酱鎯?chǔ)的線性表中，若要在第i個(gè)位置插入一個(gè)新元素，需要修改多少個(gè)指針？（）A.1B.2C.iD.i+15、對于一個(gè)循環(huán)隊(duì)列，若隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列最大容量為MAX_SIZE，那么判斷隊(duì)空的條件是？（）A.front==rearB.(rear+1)%MAX_SIZE==frontC.rear==MAX_SIZE-1D.front==MAX_SIZE-16、已知一個(gè)圖的鄰接矩陣如下所示，則從頂點(diǎn)V1出發(fā)進(jìn)行深度優(yōu)先遍歷，可能得到的頂點(diǎn)訪問序列是（）。|01100||10010||10001||01000||00100|A.V1,V2,V3,V4,V5B.V1,V3,V2,V5,V4C.V1,V2,V5,V3,V4D.V1,V4,V3,V2,V57、以下哪種數(shù)據(jù)結(jié)構(gòu)常用于實(shí)現(xiàn)操作系統(tǒng)中的進(jìn)程調(diào)度？A.隊(duì)列B.棧C.樹D.圖8、若一棵二叉樹的先序遍歷序列為ABCDEFG，中序遍歷序列為CBDAEGF，則其后序遍歷序列為？（）A.CDBGFEAB.CDBFGEAC.CDBAGFED.CDBEAGF9、對于一個(gè)具有n個(gè)元素的有序單鏈表，要查找一個(gè)值為x的元素，平均比較次數(shù)約為？A.n/2B.nC.lognD.110、已知一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則其先序遍歷序列為（）。A.CEABDB.CEDBAC.CABDED.CEDAB11、對于一個(gè)具有n個(gè)頂點(diǎn)的無向圖，若要判斷其是否為連通圖，以下哪種方法效率較高？（）A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.枚舉所有邊D.以上方法效率相同12、在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖中，使用克魯斯卡爾（Kruskal）算法生成最小生成樹。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(nlogn)B.O(eloge)C.O(elogn)D.O(n^2)13、對于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，使用深度優(yōu)先搜索算法進(jìn)行遍歷。以下關(guān)于算法中使用的標(biāo)記數(shù)組的空間復(fù)雜度的描述，哪一項(xiàng)是正確的？A.O(1)B.O(n)C.O(e)D.O(n^2)14、在一個(gè)具有n個(gè)頂點(diǎn)的帶權(quán)有向圖中，使用迪杰斯特拉（Dijkstra）算法求單源最短路徑。以下關(guān)于該算法的時(shí)間復(fù)雜度的描述，哪一項(xiàng)是準(zhǔn)確的？A.O(n)B.O(n^2)C.O(nlogn)D.O(n^3)15、對于一個(gè)用數(shù)組實(shí)現(xiàn)的小根堆，若要將堆頂元素與最后一個(gè)元素交換，然后重新調(diào)整堆，以下關(guān)于調(diào)整的方向，哪一項(xiàng)是正確的？A.從堆頂向下調(diào)整B.從堆底向上調(diào)整C.先從堆頂向下調(diào)整，再從堆底向上調(diào)整D.以上都不對16、在一個(gè)具有n個(gè)節(jié)點(diǎn)的圖中，使用弗洛伊德算法求所有節(jié)點(diǎn)對之間的最短路徑，其時(shí)間復(fù)雜度是多少？A.O(n^2)B.O(n^3)C.O(nlogn)D.O(n^4)17、在一個(gè)順序存儲(chǔ)的數(shù)組中實(shí)現(xiàn)一個(gè)簡單的棧結(jié)構(gòu)，若棧頂指針top初始值為-1，當(dāng)進(jìn)行一次入棧操作后，top的值應(yīng)該如何變化？A.top不變B.top=top+1C.top=top-1D.top=018、在一個(gè)具有n個(gè)元素的順序表中，若要?jiǎng)h除第i個(gè)元素（1<=i<=n），并將后面的元素向前移動(dòng)，平均需要移動(dòng)多少個(gè)元素？（）A.n-iB.iC.(n-i)/2D.n-i+119、在一個(gè)具有n個(gè)節(jié)點(diǎn)的二叉樹中，若先序遍歷序列為ABC，中序遍歷序列為BAC，則后序遍歷序列是什么？A.BCAB.CBAC.ACBD.無法確定20、在一個(gè)帶頭結(jié)點(diǎn)的雙向鏈表中，若要在p所指結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)q，需要修改幾個(gè)指針？（）A.2B.4C.6D.8二、簡答題（本大題共4個(gè)小題，共40分)1、（本題10分）解釋如何在一個(gè)具有n個(gè)元素的無序數(shù)組中，使用快速排序算法進(jìn)行排序，并分析其時(shí)間復(fù)雜度和空間復(fù)雜度。2、（本題10分）在圖的存儲(chǔ)結(jié)構(gòu)中，比較鄰接矩陣和鄰接表的優(yōu)缺點(diǎn)，舉例說明在不同情況下應(yīng)如何選擇合適的存儲(chǔ)結(jié)構(gòu)。3、（本題10分）解釋二叉樹的概念，包括滿二叉樹、完全二叉樹。闡述二叉樹的先序、中序和后序遍歷的遞歸和非遞歸算法實(shí)現(xiàn)，并分析其時(shí)間復(fù)雜度。4、（本題10分）詳細(xì)解釋在二叉