(2025年)版專升本《數(shù)據(jù)結構》試題答案一、單項選擇題（本大題共10小題，每小題2分，共20分）1.已知某算法的時間復雜度遞推式為T(n)=2T(n/2)+n（n>1），T(1)=1，則該算法的時間復雜度為（）A.O(n)B.O(nlogn)C.O(n2)D.O(logn)答案：B解析：根據(jù)主定理，遞推式T(n)=aT(n/b)+f(n)中，a=2，b=2，f(n)=n。此時n^(log_ba)=n^1=n，與f(n)同階，故時間復雜度為O(nlogn)。2.若一個線性表最常用的操作是在末尾插入元素和刪除末尾元素，則最節(jié)省時間的存儲結構是（）A.單向鏈表B.雙向鏈表C.順序表D.循環(huán)鏈表答案：C解析：順序表通過下標直接訪問末尾元素，插入和刪除末尾元素的時間復雜度為O(1)；鏈表需遍歷到末尾，時間復雜度為O(n)，因此順序表更高效。3.設棧S的初始狀態(tài)為空，元素a、b、c、d、e依次入棧，允許在任意時刻出棧。若出棧序列為b、d、c、e、a，則棧的容量至少為（）A.2B.3C.4D.5答案：B解析：入棧順序a→b（此時棧內(nèi)[a,b]，容量2）→b出?！鷆入棧（棧內(nèi)[a,c]）→d入棧（棧內(nèi)[a,c,d]，容量3）→d出?！鷆出?！鷈入棧（棧內(nèi)[a,e]）→e出?！鷄出棧。過程中棧的最大容量為3。4.循環(huán)隊列的隊空條件是（）A.front==rearB.(rear+1)%maxsize==frontC.front==0D.rear==maxsize-1答案：A解析：循環(huán)隊列中，隊空的判斷條件是頭指針等于尾指針（front==rear）；隊滿的條件是(rear+1)%maxsize==front（犧牲一個存儲單元避免歧義）。5.一棵二叉樹的中序遍歷序列為D、B、E、A、F、C，后序遍歷序列為D、E、B、F、C、A，則其前序遍歷序列為（）A.A、B、D、E、C、FB.A、B、D、E、F、CC.A、B、E、D、C、FD.A、B、D、C、E、F答案：A解析：后序遍歷最后一個元素A是根節(jié)點。中序遍歷中，A左側D、B、E為左子樹，右側F、C為右子樹。左子樹的后序序列為D、E、B，根為B（后序最后一個）；中序中B左側D為左子樹，右側E為右子樹。右子樹的后序序列為F、C，根為C，中序中C左側F為左子樹。最終前序遍歷為根→左子樹→右子樹：A→B→D→E→C→F。6.具有10個節(jié)點的完全二叉樹，其葉子節(jié)點數(shù)為（）A.3B.4C.5D.6答案：C解析：完全二叉樹中，節(jié)點數(shù)n=10，葉子節(jié)點數(shù)為?n/2?=5（當n為偶數(shù)時，葉子數(shù)為n/2；n=10為偶數(shù)，故5個）。7.對于有向圖的拓撲排序，以下說法正確的是（）A.拓撲排序適用于所有有向圖B.拓撲排序結果唯一C.存在環(huán)的有向圖無法進行拓撲排序D.拓撲排序是按節(jié)點值大小排序答案：C解析：拓撲排序僅適用于有向無環(huán)圖（DAG），存在環(huán)的圖無法找到拓撲序列；拓撲排序結果可能不唯一（如多個入度為0的節(jié)點時）；其本質是節(jié)點的線性排列，與節(jié)點值大小無關。8.對長度為n的有序表進行二分查找，最壞情況下的時間復雜度為（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)答案：C解析：二分查找每次將查找范圍縮小一半，最壞情況下需比較log?n次，時間復雜度為O(logn)。9.以下排序算法中，不穩(wěn)定的是（）A.冒泡排序B.插入排序C.歸并排序D.快速排序答案：D解析：快速排序在劃分過程中可能改變相同元素的相對順序（如[2,2,1]排序時，第一個2可能被交換到第二個2之后），因此不穩(wěn)定；其他選項均穩(wěn)定。10.哈希表中解決沖突的鏈地址法（拉鏈法）的平均查找長度（）A.僅與哈希函數(shù)有關B.僅與裝填因子有關C.與哈希函數(shù)和裝填因子都有關D.與處理沖突的方法無關答案：C解析：鏈地址法的平均查找長度取決于哈希函數(shù)的均勻性（影響沖突概率）和裝填因子α（α=元素數(shù)/表長，α越大，鏈表越長，查找時間越長）。二、填空題（本大題共5小題，每空2分，共10分）1.線性表的順序存儲結構是通過__________表示元素之間的邏輯關系；鏈式存儲結構是通過__________表示元素之間的邏輯關系。答案：物理位置相鄰；指針（或鏈域）2.一個棧的輸入序列是1、2、3、4、5，若輸出序列的第一個元素是3，則最后一個輸出元素可能是__________（寫出所有可能）。答案：1、2、5（或1或2或5）解析：第一個出棧元素是3，說明1、2、3已入棧，3出棧后，棧內(nèi)有1、2。后續(xù)可能的操作：2出棧→1出?！?、5入?！?出棧（輸出序列3、2、1、5）；或4入?！?出?！?入?！?出?！?出?！?出棧（輸出序列3、4、5、2、1）；或4、5入?！?出?！?出棧→2出?！?出棧（輸出序列3、5、4、2、1）。因此最后一個元素可能是1、2或5。3.深度為5的滿二叉樹有__________個葉子節(jié)點；若該樹為完全二叉樹，則最少有__________個節(jié)點。答案：16；16解析：滿二叉樹深度h的葉子數(shù)為2^(h-1)，h=5時為16；完全二叉樹深度h的最少節(jié)點數(shù)為2^(h-1)（即前h-1層滿，第h層僅1個節(jié)點），但h=5時，前4層節(jié)點數(shù)為15，最少節(jié)點數(shù)為15+1=16。4.無向圖G有16條邊，度為4的節(jié)點有3個，度為3的節(jié)點有4個，其余節(jié)點度為2，則G的節(jié)點總數(shù)為__________。答案：11解析：無向圖總度數(shù)=2×邊數(shù)=32。設度為2的節(jié)點數(shù)為x，則4×3+3×4+2x=32→12+12+2x=32→x=4?？偣?jié)點數(shù)=3+4+4=11。5.對序列{50,38,66,90,70,8,23}進行直接插入排序，第三趟（假設初始有序序列為前1個元素）結束后，序列為__________。答案：{38,50,66,90,70,8,23}解析：直接插入排序每趟將下一個元素插入到有序序列中。初始有序序列[50]；第一趟插入38→[38,50]；第二趟插入66→[38,50,66]；第三趟插入90→[38,50,66,90]（原序列前四個元素變?yōu)?8,50,66,90，后續(xù)元素不變）。三、判斷題（本大題共5小題，每小題2分，共10分）1.數(shù)據(jù)的邏輯結構與存儲結構是一一對應的。（）答案：×解析：同一邏輯結構（如線性表）可采用順序存儲或鏈式存儲，存儲結構不唯一。2.隊列是先進后出的線性表。（）答案：×解析：隊列是先進先出（FIFO），棧是先進后出（LIFO）。3.二叉樹的前序遍歷序列和后序遍歷序列可以唯一確定一棵二叉樹。（）答案：×解析：前序和后序無法唯一確定二叉樹（如根節(jié)點的左右子樹可能無法區(qū)分），需前序+中序或中序+后序。4.圖的廣度優(yōu)先遍歷（BFS）使用棧作為輔助數(shù)據(jù)結構。（）答案：×解析：BFS使用隊列，DFS使用棧（或遞歸）。5.希爾排序的時間復雜度一定優(yōu)于直接插入排序。（）答案：×解析：希爾排序的時間復雜度取決于增量序列，最壞情況下可能退化為O(n2)，與直接插入排序相同。四、應用題（本大題共3小題，共30分）1.（10分）已知一棵二叉樹的中序遍歷序列為B、A、D、E、C、F，后序遍歷序列為A、B、E、D、F、C。（1）畫出該二叉樹的邏輯結構；（2）寫出其層次遍歷（按層從左到右）的序列。答案：（1）二叉樹結構：根節(jié)點為C（后序最后一個元素）。中序中C左側B、A、D、E為左子樹，右側F為右子樹。左子樹的后序序列為A、B、E、D，根為D（后序最后一個）；中序中D左側B、A為左子樹，右側E為右子樹。左子樹的后序序列為A、B，根為B（后序最后一個）；中序中B左側無，右側A為右子樹。右子樹E無左右子樹。右子樹F為C的右孩子。結構如下：C/\DF/\BE\A（2）層次遍歷序列：C→D→F→B→E→A2.（10分）給定無向圖G的鄰接矩陣如下（節(jié)點編號1-5）：\[\begin{bmatrix}0&1&1&0&0\\1&0&0&1&0\\1&0&0&1&1\\0&1&1&0&1\\0&0&1&1&0\\\end{bmatrix}\]（1）畫出G的鄰接表表示；（2）從節(jié)點1出發(fā)，分別寫出深度優(yōu)先搜索（DFS，遞歸）和廣度優(yōu)先搜索（BFS）的遍歷序列（假設訪問順序按節(jié)點編號從小到大）。答案：（1）鄰接表（每個節(jié)點的鄰接點按編號排序）：1:2→32:1→43:1→4→54:2→3→55:3→4（2）DFS序列（1→2→4→3→5）；BFS序列（1→2→3→4→5）解析：DFS從1出發(fā)，訪問2（未訪問），從2訪問4（未訪問），從4訪問3（未訪問），從3訪問5（未訪問）；BFS按層訪問，1的鄰接點2、3（按順序），然后訪問2的鄰接點4（未訪問），3的鄰接點5（未訪問），最后4的鄰接點3已訪問，5的鄰接點3、4已訪問，故序列為1→2→3→4→5。3.（10分）用哈希函數(shù)H(key)=keymod7（表長7），采用線性探測法處理沖突，將關鍵字序列{38,19,63,25,7,10,44}插入哈希表。（1）構造哈希表；（2）計算查找成功時的平均查找長度（ASL）。答案：（1）哈希表構造過程（下標0-6）：-38mod7=38-5×7=3→位置3（無沖突）-19mod7=19-2×7=5→位置5（無沖突）-63mod7=0→位置0（無沖突）-25mod7=25-3×7=4→位置4（無沖突）-7mod7=0→位置0沖突，探測0+1=1（無沖突）→位置1-10mod7=3→位置3沖突，探測3+1=4（沖突），3+2=5（沖突），3+3=6（無沖突）→位置6-44mod7=44-6×7=2→位置2（無沖突）最終哈希表：下標：0123456值：6374438251910（2）ASL計算（各關鍵字查找次數(shù)）：-63（位置0）：1次-7（位置1）：2次（沖突后探測1次）-44（位置2）：1次-38（位置3）：1次-25（位置4）：1次-19（位置5）：1次-10（位置6）：4次（沖突3次，探測3次）ASL=(1+2+1+1+1+1+4)/7=11/7≈1.57五、算法設計題（本大題共2小題，共30分）1.（15分）設計一個算法，將一個帶頭節(jié)點的單鏈表L逆置（即第一個節(jié)點變?yōu)樽詈笠粋€，最后一個節(jié)點變?yōu)榈谝粋€）。要求用文字描述算法步驟，并給出偽代碼。答案：算法步驟：（1）初始化三個指針：前驅指針pre（初始為NULL）、當前指針p（初始為頭節(jié)點的下一個節(jié)點）、后繼指針next（保存p的下一個節(jié)點）。（2）遍歷鏈表，每次將p的next指向pre（實現(xiàn)逆置），然后pre移動到p，p移動到next，next移動到p的下一個節(jié)點（若存在）。（3）當p為NULL時，遍歷結束，原鏈表的尾節(jié)點成為新的頭節(jié)點的下一個節(jié)點。偽代碼：voidReverseList(LinkList&L){LNodepre=NULL;LNodep=L->next;//p指向第一個數(shù)據(jù)節(jié)點LNodenext;while(p!=NULL){next=p->next;//保存下一個節(jié)點p->next=pre;//逆置指針pre=p;//pre后移p=next;//p后移}L->next=pre;//頭節(jié)點指向原尾節(jié)點（新頭節(jié)點）}2.（15分）已知一個遞增有序的順序表L（元素互不相同），設計一個高效算法，刪除所有值介于s和t之間的元素（s<t）。要求時間復雜度為O(n)，并給出偽代碼。答案：算法思路：（1）由于順序表遞增，所有需刪除的元素是連續(xù)的一段（從第一個大于s的元素到最后一個小于t的元素）。（2）找到第一個大于等于