大學(xué)數(shù)據(jù)結(jié)構(gòu)2025年期末試卷及答案一、單項(xiàng)選擇題（每題2分，共20分）1.對(duì)于長(zhǎng)度為n的順序表，刪除第i個(gè)元素（1≤i≤n）時(shí)，需要移動(dòng)的元素個(gè)數(shù)為（）。A.n-i+1B.n-iC.iD.i-12.若一個(gè)棧的輸入序列是1,2,3,4,5，不可能的輸出序列是（）。A.5,4,3,2,1B.3,2,5,4,1C.2,3,1,4,5D.1,5,4,3,23.已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組data[0...m-1]，隊(duì)頭指針為front，隊(duì)尾指針為rear（指向隊(duì)尾元素的下一個(gè)位置），則隊(duì)列中元素個(gè)數(shù)為（）。A.(rear-front+m)%mB.rear-frontC.(front-rear+m)%mD.rear-front+14.一棵深度為k的完全二叉樹（根節(jié)點(diǎn)深度為1），其最少結(jié)點(diǎn)數(shù)為（）。A.2^(k-1)B.2^k-1C.2^(k-1)+1D.2^(k-1)-15.對(duì)圖G進(jìn)行廣度優(yōu)先搜索（BFS）時(shí)，采用隊(duì)列作為輔助結(jié)構(gòu)，若圖中有n個(gè)頂點(diǎn)和m條邊，則時(shí)間復(fù)雜度為（）。A.O(n+m)B.O(n^2)C.O(m^2)D.O(nm)6.對(duì)于關(guān)鍵字序列{25,30,18,42,35,20}，若采用哈希函數(shù)H(key)=key%7，哈希表長(zhǎng)度為7，用線性探測(cè)法處理沖突，則插入所有元素后，哈希表中地址2的位置存儲(chǔ)的關(guān)鍵字是（）。A.25B.30C.20D.357.下列排序算法中，時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響，恒為O(nlogn)的是（）。A.快速排序B.堆排序C.冒泡排序D.直接插入排序8.若某二叉樹的先序遍歷序列為ABDCE，中序遍歷序列為DBAEC，則后序遍歷序列為（）。A.DBECAB.DEBCAC.DBEACD.DCEBA9.對(duì)于帶權(quán)無向圖G=(V,E)，若所有邊的權(quán)值均為正數(shù)，且存在唯一的最小提供樹，則以下說法正確的是（）。A.G中任意兩個(gè)頂點(diǎn)之間有且僅有一條簡(jiǎn)單路徑B.G的邊權(quán)值各不相同C.G是一棵樹D.G中存在環(huán)，但環(huán)上的最大邊權(quán)唯一10.若一個(gè)串S的長(zhǎng)度為n（n≥1），則其所有真子串（長(zhǎng)度≥1且小于n）的個(gè)數(shù)為（）。A.n(n-1)/2B.n(n+1)/2C.n(n-1)D.2^n-n-1二、填空題（每空2分，共20分）1.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，結(jié)點(diǎn)包含數(shù)據(jù)域和______域。2.一個(gè)棧的入棧序列是a,b,c,d，若出棧序列的第一個(gè)元素是c，則第四個(gè)出棧元素可能是______（寫出一個(gè)即可）。3.若某二叉樹的后序遍歷序列為DEBFC，中序遍歷序列為DBEAC，則其先序遍歷序列為______。4.對(duì)于有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)，計(jì)算某個(gè)頂點(diǎn)的出度需要遍歷其______鏈表。5.對(duì)關(guān)鍵字序列{50,38,66,90,70,17,23}進(jìn)行堆排序（小根堆），初始建堆后堆頂元素是______。6.若哈希表的裝填因子α=0.75，表長(zhǎng)為16，則最多可存儲(chǔ)______個(gè)關(guān)鍵字。7.已知一個(gè)隊(duì)列的入隊(duì)序列是1,3,5,7,9，若采用鏈?zhǔn)酱鎯?chǔ)且僅設(shè)尾指針，則出隊(duì)操作的時(shí)間復(fù)雜度為______。8.一個(gè)m階B樹中，每個(gè)結(jié)點(diǎn)最多有______個(gè)子結(jié)點(diǎn)。9.對(duì)長(zhǎng)度為n的有序表進(jìn)行二分查找，最壞情況下的比較次數(shù)為______（用對(duì)數(shù)形式表示）。10.若用鄰接矩陣存儲(chǔ)一個(gè)有n個(gè)頂點(diǎn)的無向圖，矩陣中0元素的個(gè)數(shù)為n(n-1)-2m（m為邊數(shù)），則1元素的個(gè)數(shù)為______。三、判斷題（每題1分，共10分。正確填“√”，錯(cuò)誤填“×”）1.順序表的插入操作平均需要移動(dòng)約n/2個(gè)元素。（）2.隊(duì)列的“假溢出”現(xiàn)象可以通過循環(huán)隊(duì)列解決。（）3.二叉樹的度可以大于2。（）4.圖的深度優(yōu)先搜索（DFS）遍歷結(jié)果唯一，與訪問順序無關(guān)。（）5.直接選擇排序是穩(wěn)定的排序算法。（）6.平衡二叉樹（AVL樹）的左右子樹高度差的絕對(duì)值不超過1。（）7.串的模式匹配中，KMP算法的時(shí)間復(fù)雜度一定低于暴力匹配算法。（）8.稀疏矩陣的三元組表存儲(chǔ)方式可以節(jié)省存儲(chǔ)空間。（）9.拓?fù)渑判蛑荒苡糜谟邢驘o環(huán)圖（DAG）。（）10.歸并排序的空間復(fù)雜度為O(n)。（）四、簡(jiǎn)答題（每題5分，共20分）1.比較順序表和鏈表在存儲(chǔ)結(jié)構(gòu)、插入/刪除操作、隨機(jī)訪問方面的優(yōu)缺點(diǎn)。2.簡(jiǎn)述二叉排序樹的定義，并說明插入一個(gè)新結(jié)點(diǎn)的基本步驟。3.對(duì)于帶權(quán)有向圖，Dijkstra算法和Floyd算法的適用場(chǎng)景有何不同？4.說明快速排序的分治思想，并分析其在最好、最壞情況下的時(shí)間復(fù)雜度。五、綜合題（共30分）1.（10分）已知表達(dá)式“3(5+7)-2^4/8”，要求：（1）將其轉(zhuǎn)換為后綴表達(dá)式（逆波蘭式）；（2）用棧計(jì)算該后綴表達(dá)式的值，寫出每一步棧的狀態(tài)。2.（10分）已知二叉樹的中序遍歷序列為DGBEACHF，后序遍歷序列為GDEBHFCA。（1）畫出該二叉樹的邏輯結(jié)構(gòu)；（2）寫出其先序遍歷序列。3.（10分）某帶權(quán)無向圖的鄰接矩陣如下（頂點(diǎn)編號(hào)為0-4，權(quán)值為∞表示無直接邊）：\[\begin{bmatrix}0&5&∞&7&∞\\5&0&4&∞&∞\\∞&4&0&2&3\\7&∞&2&0&6\\∞&∞&3&6&0\\\end{bmatrix}\]（1）畫出該圖的鄰接表表示；（2）使用Prim算法從頂點(diǎn)0出發(fā)構(gòu)造最小提供樹，寫出每一步選擇的邊（按權(quán)值從小到大順序）。答案一、單項(xiàng)選擇題1.B2.C3.A4.A5.A6.C7.B8.A9.B10.A二、填空題1.指針（或鏈）2.a（或d，合理即可）3.ABDEC4.出邊5.176.127.O(1)（注：鏈?zhǔn)疥?duì)列僅設(shè)尾指針時(shí)，若需出隊(duì)需找到頭結(jié)點(diǎn)，實(shí)際應(yīng)為O(n)，但通常鏈?zhǔn)疥?duì)列設(shè)頭尾指針，此處可能題目假設(shè)頭尾指針均存在，故答案為O(1)，需根據(jù)題意調(diào)整）8.m9.?log?(n+1)?（或log?n向上取整）10.2m三、判斷題1.√2.√3.×4.×5.×6.√7.×8.√9.√10.√四、簡(jiǎn)答題1.順序表：-存儲(chǔ)結(jié)構(gòu)：連續(xù)內(nèi)存，隨機(jī)訪問O(1)；-插入/刪除：需移動(dòng)元素，平均O(n)；-優(yōu)點(diǎn)：空間利用率高，隨機(jī)訪問快；-缺點(diǎn)：插入/刪除效率低，大小固定。鏈表：-存儲(chǔ)結(jié)構(gòu)：離散內(nèi)存，指針連接；-插入/刪除：只需修改指針，O(1)（已知位置）；-優(yōu)點(diǎn)：動(dòng)態(tài)擴(kuò)展，插入/刪除高效；-缺點(diǎn)：需額外存儲(chǔ)指針，隨機(jī)訪問O(n)。2.二叉排序樹定義：左子樹所有結(jié)點(diǎn)值≤根結(jié)點(diǎn)值≤右子樹所有結(jié)點(diǎn)值（或嚴(yán)格小于/大于，依具體定義）。插入步驟：（1）若樹空，新結(jié)點(diǎn)為根；（2）否則，比較新結(jié)點(diǎn)值與當(dāng)前根結(jié)點(diǎn)值，小于則遞歸插入左子樹，大于則遞歸插入右子樹；（3）重復(fù)直到找到空位置，插入新結(jié)點(diǎn)。3.Dijkstra算法：適用于單源最短路徑（從某一頂點(diǎn)到其他所有頂點(diǎn)），要求邊權(quán)非負(fù)；Floyd算法：適用于所有頂點(diǎn)對(duì)的最短路徑，允許邊權(quán)為負(fù)（但不能有負(fù)權(quán)環(huán)）。4.分治思想：選擇基準(zhǔn)元素，將序列分為小于/大于基準(zhǔn)的兩部分，遞歸排序子序列。最好情況：每次劃分平衡，時(shí)間復(fù)雜度O(nlogn)；最壞情況：序列已有序，每次劃分僅減少1個(gè)元素，時(shí)間復(fù)雜度O(n2)。五、綜合題1.（1）后綴表達(dá)式：357+24^8/-（2）計(jì)算過程：棧初始：[]讀3→[3]讀5→[3,5]讀7→[3,5,7]讀+→彈出5,7→5+7=12→[3,12]讀→彈出3,12→3×12=36→[36]讀2→[36,2]讀4→[36,2,4]讀^→彈出2,4→2^4=16→[36,16]讀8→[36,16,8]讀/→彈出16,8→16/8=2→[36,2]讀-→彈出36,2→36-2=34→[34]最終結(jié)果：342.（1）二叉樹結(jié)構(gòu)：根為A（后序最后一個(gè)元素），中序中A左邊為左子樹{DGBE}，右邊為右子樹{CHF}；左子樹后序?yàn)镚DEB，根為B（后序最后一個(gè)），中序B左邊{DG}，右邊{E}；B左子樹后序GD，根為D，中序D左邊無，右邊G；B右子樹E（單結(jié)點(diǎn)）；右子樹后序HFC，根為C（后序最后一個(gè)），中序C右邊{HF}；C右子樹后序HF，根為F，中序F左邊H；最終結(jié)構(gòu)：A/\BC/\\DEF\/GH（2）先序遍歷序列：ABDGECFH3.（1）鄰接表（頂點(diǎn)0-4）：0:(1,5),(3,7)1:(0,5),(2,4)2:(1,4),(3,2),(4,3)3:(0,7),(2,2),(4,6)4:(2,3),(3,6)（2）Prim算法（從0出發(fā)）：初始集合U={0}，候選邊：0-1(5),0-