東北大學(xué)2025年學(xué)年《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷(A卷)附參考答案一、單項選擇題（每題2分，共20分）1.若某線性表最常用的操作是在最后一個元素之后插入一個元素或刪除最后一個元素，則采用（）存儲結(jié)構(gòu)最節(jié)省時間。A.單鏈表B.雙鏈表C.順序表D.循環(huán)鏈表2.設(shè)一個棧的輸入序列為1,2,3,4,5，則不可能的輸出序列是（）。A.5,4,3,2,1B.4,5,3,2,1C.3,4,1,5,2D.2,3,1,5,43.已知循環(huán)隊列的存儲空間為數(shù)組data[0..m1]，隊頭指針為front，隊尾指針為rear（指向隊尾元素的下一個位置），則隊列中元素個數(shù)為（）。A.(rearfront+m)%mB.rearfront+1C.rearfrontD.(rearfront)%m4.一棵完全二叉樹有100個結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個數(shù)是（）。A.49B.50C.51D.525.對于圖的存儲結(jié)構(gòu)，鄰接矩陣與鄰接表相比，（）的描述是錯誤的。A.鄰接矩陣的空間復(fù)雜度為O(n2)，適用于稠密圖B.鄰接表的空間復(fù)雜度為O(n+e)，適用于稀疏圖C.鄰接矩陣可以快速判斷兩頂點(diǎn)是否相鄰D.鄰接表更便于進(jìn)行圖的廣度優(yōu)先遍歷6.對關(guān)鍵字序列{28,15,37,42,12,56,23}進(jìn)行快速排序，以第一個元素為樞軸，一次劃分后的結(jié)果是（）。A.{12,15,23,28,37,42,56}B.{15,12,23,28,42,56,37}C.{12,15,23,28,56,42,37}D.{12,15,23,28,42,56,37}7.哈希表中解決沖突的鏈地址法（拉鏈法）本質(zhì)上是將哈希表的每個單元擴(kuò)展為一個（）。A.順序表B.鏈表C.棧D.隊列8.若對n個元素進(jìn)行歸并排序，則其時間復(fù)雜度為（）。A.O(n)B.O(n2)C.O(nlogn)D.O(n2logn)9.設(shè)有向圖G的鄰接表中，每個頂點(diǎn)的出邊表長度為d?,d?,…,d?，則圖中邊的總數(shù)為（）。A.d?+d?+…+d?B.(d?+d?+…+d?)/2C.max(d?,d?,…,d?)D.min(d?,d?,…,d?)10.已知二叉樹的先序序列為ABDCE，中序序列為BDAEC，則后序序列為（）。A.DBEACB.DEBCAC.DBECAD.DBEAC（注：原題可能存在排版問題，正確后序為DBECA）二、填空題（每空2分，共20分）1.線性表的順序存儲結(jié)構(gòu)是一種（）存儲結(jié)構(gòu)，鏈表是一種（）存儲結(jié)構(gòu)。2.一個棧的輸入序列為1,2,3，則可能的輸出序列有（）種。3.深度為5的完全二叉樹至少有（）個結(jié)點(diǎn)（根結(jié)點(diǎn)深度為1）。4.無向圖的鄰接矩陣是（）對稱矩陣（填“一定”或“不一定”）。5.對長度為n的有序表進(jìn)行二分查找，其最大比較次數(shù)為（）（用對數(shù)形式表示）。6.堆排序的時間復(fù)雜度為（），且是（）排序（填“穩(wěn)定”或“不穩(wěn)定”）。7.哈夫曼樹中權(quán)值最小的兩個結(jié)點(diǎn)一定是（）（填“兄弟結(jié)點(diǎn)”或“父子結(jié)點(diǎn)”）。8.若哈希函數(shù)為H(key)=key%11，采用線性探測法處理沖突，關(guān)鍵字序列{14,23,35,47,52}的哈希表中，關(guān)鍵字52的存儲地址是（）。三、判斷題（每題1分，共10分）1.循環(huán)隊列的隊滿條件是(rear+1)%maxsize==front。（）2.二叉樹的中序遍歷序列中，任意一個結(jié)點(diǎn)的左子樹結(jié)點(diǎn)都在其左側(cè)，右子樹結(jié)點(diǎn)都在其右側(cè)。（）3.圖的廣度優(yōu)先遍歷需要使用棧作為輔助數(shù)據(jù)結(jié)構(gòu)。（）4.快速排序在最壞情況下的時間復(fù)雜度為O(n2)。（）5.順序查找適用于有序表和無序表。（）6.完全二叉樹一定是滿二叉樹。（）7.拓?fù)渑判蛑荒苡糜谟邢驘o環(huán)圖（DAG）。（）8.歸并排序的空間復(fù)雜度為O(n)。（）9.哈希表的查找效率主要取決于哈希函數(shù)的設(shè)計，與處理沖突的方法無關(guān)。（）10.鏈表的刪除操作不需要移動元素，因此時間復(fù)雜度一定為O(1)。（）四、應(yīng)用題（共30分）1.（8分）已知單鏈表L的頭結(jié)點(diǎn)指針為head（帶頭結(jié)點(diǎn)），試編寫算法將L逆置（要求不額外申請結(jié)點(diǎn)空間）。2.（8分）給定二叉樹的中序序列為BDAEC，后序序列為DBECA，畫出該二叉樹的邏輯結(jié)構(gòu)，并寫出其先序序列。3.（7分）圖G的鄰接矩陣如下，畫出其鄰接表表示（頂點(diǎn)編號為04），并寫出從頂點(diǎn)0出發(fā)的深度優(yōu)先遍歷序列（假設(shè)鄰接表中頂點(diǎn)按編號升序排列）。\[\begin{bmatrix}0&1&0&1&0\\1&0&1&0&1\\0&1&0&1&0\\1&0&1&0&1\\0&1&0&1&0\\\end{bmatrix}\]4.（7分）對關(guān)鍵字序列{45,38,66,90,88,10,25,45}進(jìn)行基數(shù)排序（最低位優(yōu)先，十進(jìn)制），寫出每一趟分配和收集后的結(jié)果。五、綜合題（共20分）1.（12分）設(shè)計一個算法，判斷一個二叉樹是否為平衡二叉樹（平衡二叉樹的定義：任意結(jié)點(diǎn)的左右子樹高度差的絕對值不超過1，且左右子樹均為平衡二叉樹）。要求給出算法的基本思路、關(guān)鍵步驟描述，并寫出偽代碼（或C語言函數(shù)）。2.（8分）某系統(tǒng)需要頻繁在有序數(shù)組中插入新元素，同時要求插入操作的時間復(fù)雜度盡可能低?，F(xiàn)有兩種方案：方案一：使用順序表存儲，每次插入時用二分查找找到插入位置，然后移動元素完成插入；方案二：使用二叉排序樹存儲，每次插入時按二叉排序樹規(guī)則插入新結(jié)點(diǎn)。分析兩種方案的優(yōu)缺點(diǎn)，并結(jié)合實際應(yīng)用場景說明哪種方案更優(yōu)。參考答案一、單項選擇題1.C2.C3.A4.B5.D6.D7.B8.C9.A10.D（正確后序為DBECA）二、填空題1.隨機(jī)；鏈?zhǔn)?.53.164.一定5.?log?(n+1)?6.O(nlogn)；不穩(wěn)定7.兄弟結(jié)點(diǎn)8.5（計算：52%11=8，地址8未沖突？原序列14%11=3，23%11=1，35%11=2，47%11=3（沖突，線性探測到4），52%11=8，無沖突，故地址8？需重新計算：假設(shè)哈希表初始為空，依次插入14（地址3）、23（地址1）、35（地址2）、47（地址3沖突，探測4）、52（地址8無沖突），故52地址為8。可能原題計算有誤，正確應(yīng)為8）三、判斷題1.√2.√3.×（使用隊列）4.√5.√6.×7.√8.√9.×（與處理沖突有關(guān)）10.×（需找到結(jié)點(diǎn)，時間復(fù)雜度O(n)）四、應(yīng)用題1.逆置算法思路：從頭結(jié)點(diǎn)后第一個結(jié)點(diǎn)開始，依次將當(dāng)前結(jié)點(diǎn)插入到頭結(jié)點(diǎn)之后。偽代碼：```cvoidReverseList(LinkListhead){LNodep=head>next;//p指向第一個數(shù)據(jù)結(jié)點(diǎn)head>next=NULL;//原鏈表置空while(p!=NULL){LNodeq=p>next;//保存下一個結(jié)點(diǎn)p>next=head>next;//插入到頭結(jié)點(diǎn)后head>next=p;p=q;//移動p到下一個結(jié)點(diǎn)}}```2.二叉樹結(jié)構(gòu)：根為A，左子樹中序BD，后序DB→左子樹根為B，右子樹為D；右子樹中序EC，后序EC→右子樹根為C，左子樹為E。先序序列：ABDCE。3.鄰接表：頂點(diǎn)0的鄰接點(diǎn)1、3；頂點(diǎn)1的鄰接點(diǎn)0、2、4；頂點(diǎn)2的鄰接點(diǎn)1、3；頂點(diǎn)3的鄰接點(diǎn)0、2、4；頂點(diǎn)4的鄰接點(diǎn)1、3。深度優(yōu)先遍歷序列（從0出發(fā)）：0→1→2→3→4（或0→3→2→1→4，取決于鄰接表順序，按升序則為01234）。4.基數(shù)排序過程：第一趟（個位）：分配：桶0:10；桶5:無；桶8:38；桶5:無；桶6:66；桶0:無；桶0:無；桶5:25；桶8:88；桶5:45（個位為5的有25、45，個位8的有38、88，個位6的66，個位0的10，個位0的90？原序列{45,38,66,90,88,10,25,45}個位分別為5,8,6,0,8,0,5,5。分配后桶0:90,10；桶5:45,25,45；桶6:66；桶8:38,88。收集后：90,10,45,25,45,66,38,88。第二趟（十位）：十位分別為9,1,4,2,4,6,3,8。分配后桶1:10；桶2:25；桶3:38；桶4:45,45；桶6:66；桶8:88；桶9:90。收集后：10,25,38,45,45,66,88,90。五、綜合題1.算法思路：遞歸計算每個結(jié)點(diǎn)的左右子樹高度，若高度差超過1則標(biāo)記為不平衡。關(guān)鍵步驟：遞歸函數(shù)返回結(jié)點(diǎn)高度，若子樹不平衡則返回1；對當(dāng)前結(jié)點(diǎn)，計算左子樹高度h_left和右子樹高度h_right；若h_left或h_right為1，或|h_lefth_right|>1，返回1（不平衡）；否則返回max(h_left,h_right)+1（當(dāng)前結(jié)點(diǎn)高度）。偽代碼：```cintIsBalanced(BiTreeT){if(T==NULL)return0;//空樹高度為0intleft_h=IsBalanced(T>lchild);if(left_h==1)return1;//左子樹不平衡intright_h=IsBalanced(T>rchild);if(right_h==1)return1;//右子樹不平衡if(abs(left_hright_h)>1)return1;//當(dāng)前結(jié)點(diǎn)不平衡returnmax(left_h,right_h)+1;//返回當(dāng)前結(jié)點(diǎn)高度}//主函數(shù)調(diào)用：若返回值≠1則平衡```2.方案分析：方案一（順序表）：優(yōu)點(diǎn)：二分查找定位O(log