(2025年)數(shù)據(jù)結(jié)構(gòu)題集c語(yǔ)言版考試題及答案一、單項(xiàng)選擇題（每題2分，共20分）1.已知某算法的時(shí)間復(fù)雜度遞推式為T(mén)(n)=2T(n/2)+n，T(1)=1，則該算法的時(shí)間復(fù)雜度為（）A.O(n)B.O(nlogn)C.O(n2)D.O(n3)2.對(duì)于長(zhǎng)度為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,2,5,4,1C.2,3,1,5,4D.1,5,4,3,24.循環(huán)隊(duì)列存儲(chǔ)在數(shù)組data[0...maxSize-1]中，隊(duì)頭指針為front，隊(duì)尾指針為rear（指向隊(duì)尾元素的下一個(gè)位置），則隊(duì)列長(zhǎng)度為（）A.(rear-front+maxSize)%maxSizeB.rear-frontC.(front-rear+maxSize)%maxSizeD.rear-front+15.已知二叉樹(shù)的先序遍歷序列為ABCDE，中序遍歷序列為ACBED，則后序遍歷序列為（）A.CABEDB.CBEADC.CBAEDD.CEBDA6.具有10個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，其葉子節(jié)點(diǎn)數(shù)為（）A.3B.4C.5D.67.對(duì)于無(wú)向圖的鄰接矩陣，下列說(shuō)法錯(cuò)誤的是（）A.鄰接矩陣是對(duì)稱的B.第i行非零元素個(gè)數(shù)等于第i列非零元素個(gè)數(shù)C.鄰接矩陣的空間復(fù)雜度為O(n2)，n為頂點(diǎn)數(shù)D.鄰接矩陣中元素全為0表示圖中有n個(gè)孤立頂點(diǎn)8.對(duì)關(guān)鍵字序列{55,31,47,29,68,50}進(jìn)行直接插入排序，第三趟排序后的序列是（）A.{29,31,47,55,68,50}B.{31,47,55,29,68,50}C.{29,31,55,47,68,50}D.{31,55,47,29,68,50}9.哈希表采用鏈地址法處理沖突時(shí)，查找成功的平均查找長(zhǎng)度取決于（）A.哈希表的裝填因子B.哈希函數(shù)C.沖突次數(shù)D.表長(zhǎng)10.若對(duì)n個(gè)元素進(jìn)行歸并排序，其輔助存儲(chǔ)空間的復(fù)雜度為（）A.O(1)B.O(n)C.O(nlogn)D.O(n2)二、填空題（每空2分，共20分）1.數(shù)據(jù)的邏輯結(jié)構(gòu)分為集合、線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和__________。2.單鏈表中設(shè)置頭結(jié)點(diǎn)的主要目的是__________。3.一個(gè)棧的輸入序列是a,b,c,d，輸出序列的第一個(gè)元素是c，則第三個(gè)輸出元素可能是__________（寫(xiě)出一個(gè)即可）。4.若用數(shù)組Q[0...m-1]實(shí)現(xiàn)循環(huán)隊(duì)列，隊(duì)列滿的條件是__________（設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear）。5.深度為5的完全二叉樹(shù)至少有__________個(gè)節(jié)點(diǎn)（根節(jié)點(diǎn)深度為1）。6.具有n個(gè)節(jié)點(diǎn)的二叉樹(shù)，其線索二叉樹(shù)中共有__________個(gè)線索指針。7.無(wú)向圖的邊數(shù)為e，頂點(diǎn)數(shù)為n，則其鄰接表的邊表節(jié)點(diǎn)數(shù)為_(kāi)_________。8.對(duì)序列{25,18,46,2,53,39,32,4,74}進(jìn)行快速排序，以第一個(gè)元素為樞軸，第一趟劃分后的序列是__________。9.在平衡二叉樹(shù)中，每個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差絕對(duì)值不超過(guò)__________。10.順序查找長(zhǎng)度為n的線性表，在等概率情況下的平均查找長(zhǎng)度為_(kāi)_________。三、算法設(shè)計(jì)題（共40分）1.（8分）設(shè)計(jì)一個(gè)C語(yǔ)言函數(shù)，刪除單鏈表中所有值為x的節(jié)點(diǎn)（假設(shè)鏈表帶頭結(jié)點(diǎn)）。鏈表節(jié)點(diǎn)定義：typedefstructLNode{intdata;structLNodenext;}LNode,LinkList;2.（10分）編寫(xiě)一個(gè)非遞歸算法，計(jì)算二叉樹(shù)的高度（深度）。二叉樹(shù)節(jié)點(diǎn)定義：typedefstructBiTNode{intdata;structBiTNodelchild,rchild;}BiTNode,BiTree;3.（12分）已知兩個(gè)遞增有序的單鏈表L1和L2，編寫(xiě)函數(shù)合并它們，得到一個(gè)遞減有序的單鏈表L（要求利用原鏈表節(jié)點(diǎn)，不額外申請(qǐng)空間）。4.（10分）設(shè)計(jì)一個(gè)算法，判斷一個(gè)棧S（順序棧）中的元素是否對(duì)稱（如1,2,3,2,1是對(duì)稱的）。順序棧定義：typedefstruct{intdata[MaxSize];inttop;}SqStack;四、綜合應(yīng)用題（共20分）某高校需要開(kāi)發(fā)一個(gè)學(xué)提供績(jī)管理系統(tǒng)，要求用雙向鏈表存儲(chǔ)學(xué)生信息（包含學(xué)號(hào)、姓名、數(shù)學(xué)成績(jī)、英語(yǔ)成績(jī)）。功能需求如下：（1）插入操作：在鏈表尾部插入新學(xué)生信息；（2）刪除操作：根據(jù)學(xué)號(hào)刪除指定學(xué)生；（3）查詢操作：查詢數(shù)學(xué)成績(jī)≥85分且英語(yǔ)成績(jī)≥85分的學(xué)生，輸出其姓名；（4）統(tǒng)計(jì)操作：統(tǒng)計(jì)數(shù)學(xué)成績(jī)不及格（<60）的學(xué)生人數(shù)。請(qǐng)完成以下任務(wù)：（1）定義雙向鏈表的節(jié)點(diǎn)結(jié)構(gòu)體（5分）；（2）編寫(xiě)插入操作的C語(yǔ)言函數(shù)（5分）；（3）編寫(xiě)查詢操作的C語(yǔ)言函數(shù)（5分）；（4）說(shuō)明刪除操作的實(shí)現(xiàn)步驟（5分）。參考答案一、單項(xiàng)選擇題1.B2.B3.C4.A5.D6.C7.D8.A9.A10.B二、填空題1.圖狀結(jié)構(gòu)（或網(wǎng)狀結(jié)構(gòu)）2.簡(jiǎn)化插入和刪除操作的邊界條件處理3.a（或b、d，合理即可）4.(rear+1)%m==front5.166.n+17.2e8.{4,18,25,2,32,39,53,46,74}9.110.(n+1)/2三、算法設(shè)計(jì)題1.刪除單鏈表中所有值為x的節(jié)點(diǎn)```cvoidDeleteX(LinkListL,intx){LNodepre=L,p=L->next;//pre指向當(dāng)前節(jié)點(diǎn)前驅(qū)，p指向當(dāng)前節(jié)點(diǎn)while(p!=NULL){if(p->data==x){pre->next=p->next;//跳過(guò)p節(jié)點(diǎn)free(p);//釋放被刪節(jié)點(diǎn)空間p=pre->next;//p移動(dòng)到下一個(gè)節(jié)點(diǎn)}else{pre=p;//同步后移p=p->next;}}}```2.非遞歸計(jì)算二叉樹(shù)高度```cintBiTreeDepth(BiTreeT){if(T==NULL)return0;BiTreequeue[MaxSize];//定義隊(duì)列用于層次遍歷intfront=0,rear=0;intdepth=0;queue[rear++]=T;//根節(jié)點(diǎn)入隊(duì)while(front<rear){//隊(duì)列非空時(shí)循環(huán)intlevelSize=rearfront;//當(dāng)前層節(jié)點(diǎn)數(shù)depth++;//層數(shù)加1for(inti=0;i<levelSize;i++){//處理當(dāng)前層所有節(jié)點(diǎn)BiTreep=queue[front++];//出隊(duì)if(p->lchild)queue[rear++]=p->lchild;//左孩子入隊(duì)if(p->rchild)queue[rear++]=p->rchild;//右孩子入隊(duì)}}returndepth;}```3.合并兩個(gè)遞增鏈表為遞減鏈表```cLinkListMergeDesc(LinkListL1,LinkListL2){LNodep=L1->next,q=L2->next;//p、q分別指向兩鏈表當(dāng)前節(jié)點(diǎn)L1->next=NULL;//初始化結(jié)果鏈表L（利用L1頭結(jié)點(diǎn)）while(p!=NULL&&q!=NULL){//比較兩鏈表當(dāng)前節(jié)點(diǎn)值if(p->data<=q->data){//取較小值節(jié)點(diǎn)，頭插法逆序LNodetemp=p;p=p->next;temp->next=L1->next;L1->next=temp;}else{LNodetemp=q;q=q->next;temp->next=L1->next;L1->next=temp;}}//處理剩余節(jié)點(diǎn)（頭插法逆序）while(p!=NULL){LNodetemp=p;p=p->next;temp->next=L1->next;L1->next=temp;}while(q!=NULL){LNodetemp=q;q=q->next;temp->next=L1->next;L1->next=temp;}free(L2);//釋放L2頭結(jié)點(diǎn)returnL1;//L1即為結(jié)果鏈表頭結(jié)點(diǎn)}```4.判斷棧中元素是否對(duì)稱```cboolIsSymmetric(SqStackS){inti=0,j=S.top;//i指向棧底，j指向棧頂while(i<j){//兩端向中間遍歷if(S.data[i]!=S.data[j])returnfalse;i++;j--;}returntrue;}```四、綜合應(yīng)用題（1）雙向鏈表節(jié)點(diǎn)結(jié)構(gòu)體定義```ctypedefstructStudentNode{charid[12];//學(xué)號(hào)（假設(shè)最多11位）charname[20];//姓名intmath;//數(shù)學(xué)成績(jī)intenglish;//英語(yǔ)成績(jī)structStudentNodeprior;//前驅(qū)指針structStudentNodenext;//后繼指針}StudentNode,StudentList;```（2）尾部插入操作函數(shù)```cvoidInsertTail(StudentListL,StudentNodenewNode){if(L==NULL){//鏈表為空時(shí)，新節(jié)點(diǎn)作為頭結(jié)點(diǎn)L=newNode;newNode->prior=NULL;newNode->next=NULL;return;}StudentNodep=L;while(p->next!=NULL){//找到尾節(jié)點(diǎn)p=p->next;}p->next=newNode;//插入到尾部newNode->prior=p;newNode->next=NULL;}```（3）查詢雙科≥85分學(xué)生姓名函數(shù)```cvoidQueryExcellent(StudentListL){StudentNodep=L;while(p!=NULL){if(p->math>=85&&p->english>=85){pri