2025年廣東數(shù)據(jù)結(jié)構(gòu)自考試題及答案一、單項(xiàng)選擇題（本大題共10小題，每小題2分，共20分）1.已知某算法的時(shí)間復(fù)雜度遞推式為T(mén)(n)=2T(n/2)+n（n>1），T(1)=1，則其時(shí)間復(fù)雜度為（）A.O(n)B.O(nlogn)C.O(n2)D.O(n3)2.若某線性表最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素或刪除最后一個(gè)元素，則最節(jié)省時(shí)間的存儲(chǔ)結(jié)構(gòu)是（）A.單鏈表B.雙向鏈表C.順序表D.循環(huán)鏈表3.設(shè)棧S的初始狀態(tài)為空，元素a、b、c、d、e依次入棧，允許在任意時(shí)刻出棧。若出棧序列為b、d、c、e、a，則棧的容量至少為（）A.2B.3C.4D.54.已知循環(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+15.若一棵完全二叉樹(shù)有768個(gè)節(jié)點(diǎn)，則該二叉樹(shù)中葉子節(jié)點(diǎn)的個(gè)數(shù)為（）A.384B.383C.385D.3866.對(duì)于圖的鄰接矩陣和鄰接表存儲(chǔ)方式，以下說(shuō)法正確的是（）A.鄰接矩陣的空間復(fù)雜度與頂點(diǎn)數(shù)無(wú)關(guān)B.鄰接表更適合存儲(chǔ)稀疏圖C.鄰接矩陣無(wú)法表示有向圖D.鄰接表的空間復(fù)雜度一定高于鄰接矩陣7.對(duì)長(zhǎng)度為n的有序表進(jìn)行二分查找，最壞情況下的時(shí)間復(fù)雜度為（）A.O(n)B.O(nlogn)C.O(logn)D.O(n2)8.下列排序算法中，不穩(wěn)定的是（）A.冒泡排序B.歸并排序C.插入排序D.快速排序9.設(shè)哈希表長(zhǎng)度為13，哈希函數(shù)為H(key)=key%13。采用線性探測(cè)再散列處理沖突，將關(guān)鍵字序列{25,14,38,46,55,20}依次插入哈希表后，關(guān)鍵字20的存儲(chǔ)地址是（）A.7B.8C.9D.1010.若一棵平衡二叉樹(shù)的高度為4（根節(jié)點(diǎn)高度為1），則其最少節(jié)點(diǎn)數(shù)為（）A.7B.10C.12D.15二、填空題（本大題共10小題，每小題2分，共20分）11.數(shù)據(jù)結(jié)構(gòu)的三要素是邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和__________。12.若單鏈表的每個(gè)節(jié)點(diǎn)包含一個(gè)指針域，則該鏈表的長(zhǎng)度為n時(shí)，共有__________個(gè)指針域（不考慮頭指針）。13.一個(gè)棧的輸入序列是1,2,3,4,5，若輸出序列的第一個(gè)元素是3，則最后一個(gè)輸出元素可能是__________（寫(xiě)出一個(gè)即可）。14.已知中綴表達(dá)式為A+BC-D/E，其對(duì)應(yīng)的后綴表達(dá)式為_(kāi)_________。15.若一棵二叉樹(shù)的前序遍歷序列為ABDCE，中序遍歷序列為DBAEC，則后序遍歷序列為_(kāi)_________。16.無(wú)向圖G有16條邊，度為4的頂點(diǎn)有3個(gè)，其余頂點(diǎn)度均小于4，則G中頂點(diǎn)數(shù)至少為_(kāi)_________。17.對(duì)序列{50,38,46,20,10,70}進(jìn)行堆排序，初始建堆（大根堆）后，堆頂元素為_(kāi)_________，堆的最后一個(gè)葉子節(jié)點(diǎn)為_(kāi)_________（按數(shù)組存儲(chǔ)順序）。18.已知有序表為{12,18,24,35,47,50,62,83,90,115,134}，用二分查找法查找關(guān)鍵字90時(shí)，需要比較__________次。19.對(duì)于具有n個(gè)頂點(diǎn)的無(wú)向連通圖，其提供樹(shù)的邊數(shù)為_(kāi)_________。20.若用十字鏈表存儲(chǔ)有向圖，則每個(gè)邊節(jié)點(diǎn)需要存儲(chǔ)__________個(gè)指針域（不考慮權(quán)值）。三、判斷題（本大題共5小題，每小題2分，共10分）21.順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是可以隨機(jī)訪問(wèn)，缺點(diǎn)是需要連續(xù)的存儲(chǔ)空間。（）22.隊(duì)列的“假溢出”現(xiàn)象可以通過(guò)循環(huán)隊(duì)列解決。（）23.完全二叉樹(shù)的葉子節(jié)點(diǎn)只能在最后兩層出現(xiàn)。（）24.圖的深度優(yōu)先搜索（DFS）遍歷適用于尋找最短路徑。（）25.希爾排序的時(shí)間復(fù)雜度與初始序列的有序性無(wú)關(guān)。（）四、應(yīng)用題（本大題共4小題，共30分）26.（8分）已知單鏈表L（帶頭節(jié)點(diǎn)）存儲(chǔ)整數(shù)序列，設(shè)計(jì)一個(gè)算法刪除L中所有值為奇數(shù)的節(jié)點(diǎn)。要求：（1）用文字描述算法思路；（2）用C語(yǔ)言偽代碼實(shí)現(xiàn)（需包含節(jié)點(diǎn)結(jié)構(gòu)體定義）。27.（8分）已知二叉樹(shù)的層序遍歷序列為ABCDEFG，中序遍歷序列為DBEAFCG。（1）畫(huà)出該二叉樹(shù)的結(jié)構(gòu)；（2）寫(xiě)出其前序遍歷序列和后序遍歷序列。28.（7分）圖G的鄰接表存儲(chǔ)如圖1所示（頂點(diǎn)編號(hào)為0-4，邊權(quán)為正整數(shù)），要求：（1）寫(xiě)出圖G的頂點(diǎn)數(shù)和邊數(shù)；（2）用Dijkstra算法求從頂點(diǎn)0到其他各頂點(diǎn)的最短路徑（需列出每一步的距離數(shù)組）。（注：圖1描述為：頂點(diǎn)0的鄰接表鏈為1(3)→2(5)；頂點(diǎn)1的鄰接表鏈為0(3)→3(6)→4(2)；頂點(diǎn)2的鄰接表鏈為0(5)→3(1)；頂點(diǎn)3的鄰接表鏈為1(6)→2(1)→4(4)；頂點(diǎn)4的鄰接表鏈為1(2)→3(4)）29.（7分）用快速排序算法對(duì)序列{49,38,65,97,76,13,27,49}進(jìn)行升序排序，要求：（1）寫(xiě)出第一趟排序（以第一個(gè)元素為基準(zhǔn)）后的序列；（2）說(shuō)明快速排序的穩(wěn)定性，并解釋原因。五、算法設(shè)計(jì)題（本大題共2小題，共20分）30.（10分）設(shè)計(jì)一個(gè)算法，判斷一個(gè)二叉樹(shù)是否為完全二叉樹(shù)。要求：（1）用文字描述算法思路；（2）用C語(yǔ)言偽代碼實(shí)現(xiàn)（需包含二叉樹(shù)節(jié)點(diǎn)結(jié)構(gòu)體定義）。31.（10分）設(shè)計(jì)一個(gè)算法，將兩個(gè)遞增有序的單鏈表（帶頭節(jié)點(diǎn)）合并為一個(gè)遞增有序的單鏈表。要求：（1）用文字描述算法思路；（2）用C語(yǔ)言偽代碼實(shí)現(xiàn)（需包含節(jié)點(diǎn)結(jié)構(gòu)體定義）。答案一、單項(xiàng)選擇題1.B2.C3.B4.A5.A6.B7.C8.D9.B10.A二、填空題11.數(shù)據(jù)的運(yùn)算（或操作）12.n13.1（或2、4、5）14.ABC+DE/15.DBECA16.817.70；1018.319.n-120.2三、判斷題21.√22.√23.√24.×25.×四、應(yīng)用題26.（1）算法思路：初始化兩個(gè)指針，pre指向頭節(jié)點(diǎn)，p指向頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)（首元節(jié)點(diǎn)）。遍歷鏈表，當(dāng)p不為空時(shí)：若p的值為奇數(shù)，則將pre的next指向p的next，釋放p節(jié)點(diǎn)，p移動(dòng)到pre的next；否則，pre和p同時(shí)后移一個(gè)節(jié)點(diǎn)。直到p為空，結(jié)束遍歷。（2）偽代碼：```ctypedefstructLNode{intdata;structLNodenext;}LNode,LinkList;voidDeleteOdd(LinkListL){LNodepre=L;LNodep=L->next;while(p!=NULL){if(p->data%2==1){//奇數(shù)pre->next=p->next;free(p);p=pre->next;}else{pre=p;p=p->next;}}}```27.（1）二叉樹(shù)結(jié)構(gòu)：```A/\BC/\/\DEFG```（2）前序遍歷序列：ABDECFG；后序遍歷序列：DEBFGCA28.（1）頂點(diǎn)數(shù)5，邊數(shù)8（無(wú)向圖每條邊存兩次，實(shí)際邊數(shù)為8/2=4？不，鄰接表中頂點(diǎn)0→1和1→0是兩條邊，題目未說(shuō)明是無(wú)向圖，根據(jù)描述應(yīng)為有向圖，邊數(shù)為：頂點(diǎn)0有2條，1有3條，2有2條，3有3條，4有2條，共2+3+2+3+2=12條？但根據(jù)鄰接表描述，可能是無(wú)向圖，每條邊存兩次，實(shí)際邊數(shù)為6條（0-1,0-2,1-3,1-4,2-3,3-4）。需根據(jù)題目判斷，原題鄰接表鏈中頂點(diǎn)0的鄰接是1(3)→2(5)，頂點(diǎn)1的鄰接是0(3)→3(6)→4(2)，說(shuō)明是無(wú)向圖，邊數(shù)為：0-1（3）、0-2（5）、1-3（6）、1-4（2）、2-3（1）、3-4（4），共6條邊。頂點(diǎn)數(shù)5，邊數(shù)6。（2）Dijkstra算法步驟（初始距離數(shù)組dist[0]=0，其他為∞）：第1步：選0，更新鄰接點(diǎn)1（3）、2（5），dist=[0,3,5,∞,∞]第2步：選1（最小3），更新鄰接點(diǎn)3（3+6=9）、4（3+2=5），dist=[0,3,5,9,5]第3步：選4（最小5），更新鄰接點(diǎn)3（5+4=9，不小于當(dāng)前9，不更新），dist不變第4步：選2（最小5），更新鄰接點(diǎn)3（5+1=6<9），dist=[0,3,5,6,5]第5步：選3（最小6），無(wú)未訪問(wèn)鄰接點(diǎn)。最終最短路徑：0→1（3），0→2（5），0→2→3（6），0→1→4（5）29.（1）第一趟排序（基準(zhǔn)49）：初始化low=0（49），high=7（49）。從high向左找比49小的數(shù)，找到27（下標(biāo)6）；將27移到low位置，low=1。從low向右找比49大的數(shù)，找到65（下標(biāo)2），移到high位置，high=6。從high向左找比49小的數(shù)，找到13（下標(biāo)5），移到low位置，low=2。從low向右找比49大的數(shù)，找到97（下標(biāo)3），移到high位置，high=5。從high向左找比49小的數(shù)，找到76（下標(biāo)4）比49大，繼續(xù)到low=high=4，基準(zhǔn)49放到下標(biāo)4。最終序列：[27,38,13,49,76,97,65,49]（2）快速排序不穩(wěn)定。原因：在劃分過(guò)程中，相同關(guān)鍵字的相對(duì)順序可能改變（如原序列中兩個(gè)49，排序后第二個(gè)49可能出現(xiàn)在第一個(gè)49前面）。五、算法設(shè)計(jì)題30.（1）算法思路：采用層次遍歷（隊(duì)列實(shí)現(xiàn)），標(biāo)記遇到的第一個(gè)空節(jié)點(diǎn)。若后續(xù)所有節(jié)點(diǎn)均為空，則是完全二叉樹(shù)；否則不是。（2）偽代碼：```ctypedefstructBiTNode{intdata;structBiTNodelchild,rchild;}BiTNode,BiTree;boolIsCompleteBiTree(BiTreeT){if(T==NULL)returntrue;BiTreequeue[100];//假設(shè)隊(duì)列足夠大intfront=0,rear=0;BiTreep;queue[rear++]=T;boolflag=false;//標(biāo)記是否遇到空節(jié)點(diǎn)while(front<rear){p=queue[front++];if(p==NULL){flag=true;}else{if(flag)returnfalse;//遇到非空節(jié)點(diǎn)在空節(jié)點(diǎn)之后queue[rear++]=p->lchild;queue[rear++]=p->rchild;}}returntrue;}```31.（1）算法思路：初始化三個(gè)指針：pa指向L1的首元節(jié)點(diǎn)，pb指向L2的首元節(jié)點(diǎn)，pc指向合并鏈表的頭節(jié)點(diǎn)。比較pa和pb的data值，將較小的節(jié)點(diǎn)鏈接到pc的next，移動(dòng)對(duì)應(yīng)指針。當(dāng)其中一個(gè)鏈表遍歷完后，將另一個(gè)鏈表剩余部分鏈接到pc之后。（2）偽代碼：```ctypedefstructLNode{intdata;structLNodenext;}LNode,LinkList;LinkListMergeTwoLists(LinkListL1,LinkListL2){LinkListL=(LinkList)malloc(sizeof(LNode));//合并后的頭節(jié)點(diǎn)LNodepc=L;LNodepa=L1->next;LNodepb=L2->next;while(pa&&pb){if(pa->d