2025年《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷試題及答案一、單項(xiàng)選擇題（每題2分，共20分）1.已知某算法的時(shí)間復(fù)雜度函數(shù)為T(n)=2n3+3n2logn+5n+7，其漸近時(shí)間復(fù)雜度為（）。A.O(n3)B.O(n2logn)C.O(n2)D.O(nlogn)2.若需頻繁在鏈表中間插入或刪除元素，最不適合的存儲(chǔ)結(jié)構(gòu)是（）。A.單鏈表B.雙向鏈表C.循環(huán)鏈表D.順序表3.一個(gè)棧的輸入序列為1,2,3,4,5，不可能的輸出序列是（）。A.5,4,3,2,1B.3,4,1,5,2C.2,3,1,5,4D.1,3,2,5,44.若用數(shù)組Q[0..m-1]實(shí)現(xiàn)循環(huán)隊(duì)列，隊(duì)列頭指針為front，尾指針為rear，則隊(duì)列中元素個(gè)數(shù)為（）。A.(rear-front+1)%mB.(rear-front+m)%mC.(rear-front)%mD.rear-front5.一棵完全二叉樹有100個(gè)節(jié)點(diǎn)，其葉子節(jié)點(diǎn)數(shù)為（）。A.49B.50C.51D.526.對(duì)于圖G=(V,E)，若從頂點(diǎn)v出發(fā)進(jìn)行廣度優(yōu)先搜索（BFS）能訪問所有頂點(diǎn)，則G一定是（）。A.無(wú)向圖B.強(qiáng)連通圖C.連通圖D.有向圖7.哈希表采用開放定址法解決沖突時(shí)，若插入新元素發(fā)生沖突，則需繼續(xù)尋找下一個(gè)空槽。若哈希函數(shù)為H(key)=key%11，沖突處理函數(shù)為H_i=(H(key)+i2)%11（二次探測(cè)），則插入關(guān)鍵字25時(shí)，探測(cè)的第二個(gè)位置是（）。A.3B.4C.5D.68.對(duì)序列{23,14,56,37,8,91,45}進(jìn)行快速排序，以第一個(gè)元素為基準(zhǔn)，一次劃分后的結(jié)果是（）。A.{8,14,23,37,56,91,45}B.{8,14,37,23,56,91,45}C.{8,14,23,56,37,91,45}D.{8,14,23,37,56,45,91}9.若二叉排序樹中插入一個(gè)新節(jié)點(diǎn)后仍保持二叉排序樹的性質(zhì)，則該節(jié)點(diǎn)的位置由（）決定。A.前序遍歷B.中序遍歷C.節(jié)點(diǎn)值的大小D.后序遍歷10.對(duì)n個(gè)元素進(jìn)行歸并排序，其空間復(fù)雜度為（）。A.O(1)B.O(n)C.O(nlogn)D.O(n2)二、填空題（每空2分，共20分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和__________。2.一個(gè)單鏈表中，已知指針p指向某個(gè)節(jié)點(diǎn)，若要?jiǎng)h除p的后繼節(jié)點(diǎn)（假設(shè)存在），需執(zhí)行操作：__________。3.若一個(gè)棧的輸入序列長(zhǎng)度為n，則其可能的輸出序列共有__________種（用卡特蘭數(shù)表示）。4.深度為h的滿二叉樹中，葉子節(jié)點(diǎn)數(shù)為__________。5.無(wú)向圖的鄰接矩陣是__________矩陣（填“對(duì)稱”或“非對(duì)稱”）。6.對(duì)于有序表{5,12,23,35,47,58,69,80}，采用二分查找法查找元素58時(shí)，需比較__________次。7.堆排序的時(shí)間復(fù)雜度為__________。8.線索二叉樹中，每個(gè)節(jié)點(diǎn)的右線索指向其__________（填“前驅(qū)”或“后繼”）。9.拓?fù)渑判蜻m用于__________圖（填“有向無(wú)環(huán)”或“無(wú)向連通”）。10.若哈希表的裝填因子α=0.75，表長(zhǎng)為16，則最多可存儲(chǔ)__________個(gè)元素。三、判斷題（每題2分，共10分。正確填“√”，錯(cuò)誤填“×”）1.順序存儲(chǔ)的線性表可以隨機(jī)訪問，鏈?zhǔn)酱鎯?chǔ)的線性表只能順序訪問。（）2.隊(duì)列的“假溢出”是由于隊(duì)列中元素個(gè)數(shù)超過(guò)數(shù)組長(zhǎng)度導(dǎo)致的。（）3.二叉樹的前序遍歷序列和后序遍歷序列可以唯一確定一棵二叉樹。（）4.強(qiáng)連通圖中任意兩個(gè)頂點(diǎn)之間都存在兩條方向相反的路徑。（）5.直接插入排序在最好情況下（已有序）的時(shí)間復(fù)雜度為O(n)。（）四、應(yīng)用題（共40分）1.（10分）已知二叉樹的中序遍歷序列為DBEAFC，后序遍歷序列為DEBFCA。（1）畫出該二叉樹的結(jié)構(gòu)；（2）寫出其前序遍歷序列。2.（10分）圖G的鄰接表表示如下（頂點(diǎn)編號(hào)為1-5，邊權(quán)為正整數(shù)）：1:(2,3)→(3,5)→null2:(1,3)→(4,2)→null3:(1,5)→(4,4)→(5,1)→null4:(2,2)→(3,4)→(5,6)→null5:(3,1)→(4,6)→null（1）畫出圖G的無(wú)向圖結(jié)構(gòu)（假設(shè)邊是無(wú)向的）；（2）使用Kruskal算法求G的最小提供樹，寫出選邊順序及最終總權(quán)值。3.（10分）對(duì)序列{42,15,36,28,50,12,48}進(jìn)行希爾排序，初始增量d=3，后續(xù)增量依次為d=2、d=1。（1）寫出各趟排序后的序列；（2）比較希爾排序與直接插入排序的優(yōu)缺點(diǎn)。4.（10分）設(shè)哈希表表長(zhǎng)m=13，哈希函數(shù)H(key)=key%13，采用鏈地址法處理沖突。將關(guān)鍵字序列{25,38,16,47,52,63,71}依次插入哈希表。（1）畫出最終的哈希表結(jié)構(gòu)；（2）計(jì)算查找成功時(shí)的平均查找長(zhǎng)度（ASL）。五、算法設(shè)計(jì)題（共10分）設(shè)計(jì)一個(gè)算法，判斷一個(gè)單鏈表是否為回文鏈表（即鏈表正讀和反讀相同）。要求時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(1)。（注：?jiǎn)捂湵砉?jié)點(diǎn)結(jié)構(gòu)為structNode{intdata;Nodenext;};）答案一、單項(xiàng)選擇題1-5:ADBBB6-10:CBACB二、填空題1.圖狀結(jié)構(gòu)（或網(wǎng)狀結(jié)構(gòu)）2.p->next=p->next->next;（需先保存p->next的后繼）3.C(2n,n)/(n+1)（或卡特蘭數(shù)表達(dá)式）4.2^(h-1)5.對(duì)稱6.37.O(nlogn)8.后繼9.有向無(wú)環(huán)10.12三、判斷題1.√2.×3.×4.√5.√四、應(yīng)用題1.（1）二叉樹結(jié)構(gòu)：A/\BC/\/DEF（2）前序遍歷序列：ABDECF2.（1）無(wú)向圖結(jié)構(gòu)（頂點(diǎn)1-5，邊權(quán)對(duì)應(yīng)鄰接表）：1-2(3),1-3(5),2-4(2),3-4(4),3-5(1),4-5(6)（2）Kruskal選邊順序（按權(quán)值從小到大）：3-5(1)→2-4(2)→1-2(3)→3-4(4)→總權(quán)值=1+2+3+4=10（最后一條邊1-3(5)會(huì)形成環(huán)，不選）3.（1）各趟排序：初始序列：42,15,36,28,50,12,48（n=7，d=3）d=3時(shí)，子序列為[42,28,48],[15,50],[36,12]排序后子序列：[28,42,48],[15,50],[12,36]合并后序列：28,15,12,42,50,36,48d=2時(shí)，子序列為[28,12,50,48],[15,42,36]排序后子序列：[12,28,48,50],[15,36,42]合并后序列：12,15,28,36,48,42,50d=1時(shí)，直接插入排序后：12,15,28,36,42,48,50（2）希爾排序優(yōu)點(diǎn)：利用分組插入減少逆序?qū)?，時(shí)間效率高于直接插入；缺點(diǎn)：時(shí)間復(fù)雜度依賴增量選擇，不穩(wěn)定。直接插入排序優(yōu)點(diǎn)：簡(jiǎn)單穩(wěn)定，最好情況O(n)；缺點(diǎn)：最壞情況O(n2)，效率低。4.（1）哈希表結(jié)構(gòu)（鏈地址法，m=13）：索引0:52（52%13=0）索引1:63（63%13=11→63-13×4=11？計(jì)算錯(cuò)誤，正確H(63)=63%13=11（13×4=52,63-52=11），H(25)=25%13=12，H(38)=38%13=12（38-2×13=12），H(16)=16%13=3，H(47)=47%13=8（13×3=39,47-39=8），H(52)=52%13=0，H(63)=63%13=11，H(71)=71%13=6（13×5=65,71-65=6）。修正后各關(guān)鍵字的哈希地址：25→12，38→12（沖突，鏈在25后），16→3，47→8，52→0，63→11，71→6。哈希表結(jié)構(gòu)：0:52→null1:null2:null3:16→null4:null5:null6:71→null7:null8:47→null9:null10:null11:63→null12:25→38→null（2）ASL計(jì)算：各關(guān)鍵字查找次數(shù)為1（52,16,47,71,63）、2（25）、2（38）。總次數(shù)=1×5+2×2=9，ASL=9/7≈1.29。五、算法設(shè)計(jì)題思路：快慢指針找中點(diǎn)→反轉(zhuǎn)后半部分鏈表→比較前后兩部分是否相同。算法步驟：1.初始化快指針fast和慢指針slow，均指向頭節(jié)點(diǎn)；2.快指針每次走兩步，慢指針每次走一步，直到fast或fast->next為null，此時(shí)slow指向中點(diǎn)（奇數(shù)長(zhǎng)度時(shí)為中間節(jié)點(diǎn)，偶數(shù)時(shí)為前半部分末尾）；3.反轉(zhuǎn)slow之后的鏈表（后半部分）；4.同時(shí)遍歷原鏈表前半部分和反轉(zhuǎn)后的后半部分，比較節(jié)點(diǎn)值是否全部相同；5.若全部相同則返回true，否則返回false；最后恢復(fù)原鏈表（可選）。代碼實(shí)現(xiàn)：```cppboolisPalindrome(Nodehead){if(head==nullptr||head->next==nullptr)returntrue;//找中點(diǎn)Nodeslow=head;Nodefast=head;while(fast->next!=nullptr&&fast->next->next!=nullptr){slow=slow->next;fast=fast->next->next;}//反轉(zhuǎn)后半部分Nodeprev=nullptr;Nodecurr=slow->next;while(curr!=nullptr){Nodenext=curr->next;curr->next=prev;prev=curr;curr=next;}slow->nex