大連大學(xué)2025年學(xué)年《數(shù)據(jù)結(jié)構(gòu)》期末考試試卷(A卷)附參考答案一、單項(xiàng)選擇題（每小題2分，共20分）1.已知某算法的時(shí)間復(fù)雜度函數(shù)滿足T(n)=2T(n/2)+n（n≥2），T(1)=1，則其時(shí)間復(fù)雜度為（）。A.O(n)B.O(nlogn)C.O(n2)D.O(2?)2.對(duì)于長度為n的順序表，在第i個(gè)位置（1≤i≤n+1）插入一個(gè)元素的時(shí)間復(fù)雜度為（）。A.O(1)B.O(n)C.O(logn)D.O(n2)3.一個(gè)棧的輸入序列為1,2,3,4,5，則不可能的輸出序列是（）。A.5,4,3,2,1B.3,4,5,2,1C.2,3,5,4,1D.1,5,3,2,44.若用帶頭結(jié)點(diǎn)的單鏈表表示隊(duì)列，且只設(shè)尾指針而不設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為（）。A.O(1)B.O(n)C.O(logn)D.O(n2)5.已知一棵完全二叉樹有768個(gè)結(jié)點(diǎn)，則該樹的葉子結(jié)點(diǎn)數(shù)為（）。A.383B.384C.385D.3866.對(duì)圖G進(jìn)行深度優(yōu)先搜索（DFS）時(shí)，若訪問順序?yàn)関1→v2→v3→v4，且v4無未訪問鄰接點(diǎn)，則回溯到v3時(shí)，v3的下一個(gè)未訪問鄰接點(diǎn)可能是（）。A.v1B.v2C.v5（未被訪問過）D.v47.對(duì)于哈希表，若采用鏈地址法處理沖突，哈希表的平均查找長度主要取決于（）。A.哈希函數(shù)B.裝填因子C.處理沖突的方法D.表長8.對(duì)序列{23,17,45,32,5,19,28}進(jìn)行冒泡排序（升序），第一趟排序后得到的序列是（）。A.17,23,32,5,19,28,45B.17,23,5,19,28,32,45C.17,5,23,19,28,32,45D.5,17,19,23,28,32,459.若要在n個(gè)元素中快速找到第k小的元素（k遠(yuǎn)小于n），最適宜的算法是（）。A.堆排序B.快速排序C.歸并排序D.直接插入排序10.下列關(guān)于B樹的描述中，錯(cuò)誤的是（）。A.根結(jié)點(diǎn)至少有1個(gè)關(guān)鍵字B.每個(gè)非根結(jié)點(diǎn)的關(guān)鍵字個(gè)數(shù)至少為?m/2?1（m為階數(shù)）C.所有葉子結(jié)點(diǎn)位于同一層D.插入操作可能引起結(jié)點(diǎn)分裂二、填空題（每空2分，共20分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)和__________。2.對(duì)于雙向鏈表，刪除一個(gè)結(jié)點(diǎn)需要修改__________個(gè)指針域。3.若循環(huán)隊(duì)列的容量為m，隊(duì)頭指針為front，隊(duì)尾指針為rear（均指向?qū)嶋H元素位置），則隊(duì)列中元素個(gè)數(shù)為__________（用front、rear、m表示）。4.已知某二叉樹的先序遍歷序列為ABDECFG，中序遍歷序列為DBEAFCG，則后序遍歷序列為__________。5.一個(gè)有向圖的鄰接表中有n個(gè)頂點(diǎn)，e條邊，則鄰接表的空間復(fù)雜度為__________。6.對(duì)于有序表{2,5,8,12,15,18,22,25}，采用二分查找法查找元素15時(shí)，需要比較__________次。7.希爾排序的時(shí)間復(fù)雜度主要取決于__________。8.若用堆結(jié)構(gòu)實(shí)現(xiàn)優(yōu)先隊(duì)列，插入操作的時(shí)間復(fù)雜度為__________。9.一個(gè)哈希表的表長為13，哈希函數(shù)為H(key)=keymod13，采用線性探測(cè)法處理沖突。若依次插入關(guān)鍵字{25,38,16,47,5}，則關(guān)鍵字5的存儲(chǔ)地址為__________。10.若一個(gè)無向圖有n個(gè)頂點(diǎn)和e條邊，則其提供樹的邊數(shù)為__________。三、判斷題（每小題1分，共10分。正確填“√”，錯(cuò)誤填“×”）1.順序存儲(chǔ)結(jié)構(gòu)的存儲(chǔ)空間可以是不連續(xù)的。（）2.棧和隊(duì)列都是操作受限的線性表。（）3.二叉樹的前序遍歷和后序遍歷可以唯一確定一棵二叉樹。（）4.強(qiáng)連通圖的任意兩個(gè)頂點(diǎn)之間都存在兩條方向相反的邊。（）5.哈希表的查找效率與數(shù)據(jù)的輸入順序無關(guān)。（）6.快速排序是一種穩(wěn)定的排序算法。（）7.平衡二叉樹的左右子樹的高度差的絕對(duì)值不超過1。（）8.拓?fù)渑判蚩梢杂糜谂袛嘤邢驁D中是否存在環(huán)。（）9.堆的結(jié)構(gòu)一定是完全二叉樹。（）10.廣義表的長度是指表中元素的個(gè)數(shù)，深度是指表中括號(hào)的嵌套層數(shù)。（）四、應(yīng)用題（共30分）1.（8分）已知一個(gè)帶權(quán)無向圖的頂點(diǎn)集為{A,B,C,D,E}，邊權(quán)如下：AB(3)、AC(5)、BC(1)、BD(6)、CD(2)、CE(4)、DE(7)。（1）畫出該圖的鄰接矩陣表示（頂點(diǎn)順序?yàn)锳,B,C,D,E）；（2）使用Kruskal算法求該圖的最小提供樹，寫出邊的選擇順序及總權(quán)值。2.（8分）對(duì)序列{49,38,65,97,76,13,27,49}進(jìn)行快速排序（升序），以第一個(gè)元素為樞軸，寫出第一趟排序后的結(jié)果及樞軸的最終位置。3.（7分）已知某二叉樹的中序線索鏈表如下（部分結(jié)點(diǎn)未畫出），其中LTag和RTag為0表示指針指向孩子，1表示指向前驅(qū)或后繼。（1）寫出該二叉樹的中序遍歷序列；（2）指出結(jié)點(diǎn)B的前驅(qū)和后繼。（注：線索鏈表結(jié)構(gòu)：根結(jié)點(diǎn)為A，A的左指針指向B，LTag=0；B的右指針指向C，RTag=1；C的左指針指向B，LTag=1；C的右指針指向D，RTag=0；D的左指針指向C，LTag=1；D的右指針指向E，RTag=1；E的左指針指向D，LTag=1）4.（7分）設(shè)哈希表長為11，哈希函數(shù)為H(key)=keymod11，采用鏈地址法處理沖突。依次插入關(guān)鍵字{22,41,53,46,30,13,1,67}，畫出最終的哈希表結(jié)構(gòu)，并計(jì)算查找成功時(shí)的平均查找長度（ASL）。五、算法設(shè)計(jì)題（共20分）1.（10分）設(shè)計(jì)一個(gè)算法，將一個(gè)帶頭結(jié)點(diǎn)的單鏈表L（元素為整數(shù)）分解為兩個(gè)單鏈表L1和L2，其中L1包含L中所有奇數(shù)結(jié)點(diǎn)（按原順序），L2包含L中所有偶數(shù)結(jié)點(diǎn)（按原順序）。要求不使用額外的輔助空間（即結(jié)點(diǎn)只能從原鏈表中拆分），并給出算法的時(shí)間復(fù)雜度分析。2.（10分）設(shè)計(jì)一個(gè)遞歸算法，計(jì)算二叉樹中所有結(jié)點(diǎn)的值之和（假設(shè)結(jié)點(diǎn)值為整數(shù)類型）。要求給出二叉樹的存儲(chǔ)結(jié)構(gòu)定義，并寫出遞歸函數(shù)的偽代碼。參考答案一、單項(xiàng)選擇題1.B2.B3.D4.A5.B6.C7.B8.A9.A10.A二、填空題1.圖狀結(jié)構(gòu)（或網(wǎng)狀結(jié)構(gòu)）2.23.(rearfront+m)%m4.DEBFGCA5.O(n+e)6.37.增量序列的選擇8.O(logn)9.5（解析：25mod13=12，38mod13=12（沖突，探測(cè)13→0），16mod13=3，47mod13=8，5mod13=5（無沖突））10.n1三、判斷題1.×2.√3.×4.×5.×6.×7.√8.√9.√10.√四、應(yīng)用題1.（1）鄰接矩陣（行/列順序A,B,C,D,E）：\[\begin{bmatrix}0&3&5&∞&∞\\3&0&1&6&∞\\5&1&0&2&4\\∞&6&2&0&7\\∞&∞&4&7&0\\\end{bmatrix}\]（2）Kruskal算法選邊順序（按權(quán)值從小到大）：BC(1)、CD(2)、AB(3)、CE(4)?？倷?quán)值=1+2+3+4=10。2.第一趟排序過程：樞軸為49，左指針i=0（值49），右指針j=7（值49）。j左移找到27（<49），i右移找到38（<49），i繼續(xù)右移找到65（>49），交換65和27→{49,38,27,97,76,13,65,49}；j左移找到13（<49），i右移找到97（>49），交換97和13→{49,38,27,13,76,97,65,49}；j左移找到76（>49），i右移找到76（=i=j=4），交換樞軸與76→{27,38,13,49,76,97,65,49}。最終樞軸位置為3（下標(biāo)從0開始），第一趟結(jié)果：{27,38,13,49,76,97,65,49}。3.（1）中序遍歷序列：B→C→D→E（根據(jù)線索鏈表，B的右線索指向C，C的左線索指向B，右孩子指向D；D的左線索指向C，右線索指向E；E的左線索指向D）。（2）結(jié)點(diǎn)B的前驅(qū)：無（B是中序第一個(gè)結(jié)點(diǎn)）；后繼：C。4.哈希表結(jié)構(gòu)（鏈地址法）：地址0：22→41（22mod11=0，41mod11=8？錯(cuò)誤，重新計(jì)算：22mod11=0，41mod11=8，53mod11=9（5344=9），46mod11=2（4644=2），30mod11=8（3022=8），13mod11=2（1311=2），1mod11=1，67mod11=1（6766=1）。正確鏈結(jié)構(gòu)：0:221:1→672:46→138:41→309:53其他地址為空。ASL=(1+2+2+2+1+1+2)/8=(1+2+2+2+1+1+2)=11？不，總共有8個(gè)元素：22（1次）、1（1次）、67（2次）、46（1次）、13（2次）、41（1次）、30（2次）、53（1次）。ASL=(1+1+2+1+2+1+2+1)/8=11/8=1.375。五、算法設(shè)計(jì)題1.算法思路：遍歷原鏈表，將奇數(shù)結(jié)點(diǎn)插入L1，偶數(shù)結(jié)點(diǎn)插入L2。用兩個(gè)尾指針跟蹤L1和L2的尾部。偽代碼：voidSplitList(LinkListL,LinkList&L1,LinkList&L2){LNodep=L>next;//原鏈表當(dāng)前結(jié)點(diǎn)LNodetail1=L1;//L1尾指針LNodetail2=L2;//L2尾指針while(p!=NULL){LNodenext=p>next;//保存下一個(gè)結(jié)點(diǎn)if(p>data%2==1){//奇數(shù)tail1>next=p;tail1=p;}else{//偶數(shù)tail2>next=p;tail2=p;}p=next;}tail1>next=NULL;//斷開原鏈表尾部tail2>next=NULL;}時(shí)間復(fù)雜度：O(n)，n為原鏈表長度。2.二叉樹存儲(chǔ)結(jié)構(gòu)（二叉鏈表）：typedefstructBiTNode{