湖南工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)試卷-重點(diǎn)

一、單擇題棧和隊(duì)列的共同特點(diǎn)是()。A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒有共同點(diǎn)二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為()。A.2k-1B.2K+1C.2K-1D.2k-1數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成()。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.進(jìn)湊結(jié)構(gòu)和非進(jìn)湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4.設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二樹滿足的條件是()。A.空或只有一個(gè)結(jié)點(diǎn)B.高度等于其結(jié)點(diǎn)數(shù)C.任一結(jié)點(diǎn)無左孩子D.任一結(jié)點(diǎn)無右孩子5.設(shè)順序線性表中有n個(gè)數(shù)據(jù)元素，則刪除表中第i個(gè)元素需要移動()個(gè)元素。A.n-iB.n+l-iC.n-1-iD.i6.判定一個(gè)棧ST（最多元素為m0）為空的條件是()。A.ST→TOP!=0B.ST→TOP==0C.ST→TOP!=m0D.ST→TOP==m07.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由P所指向）滿足()。A.p->next=NULLB.p=NULLC.p->next=headD.p=head8.在線性結(jié)構(gòu)中，所有結(jié)點(diǎn)都有()個(gè)直接后繼。A.0B.0或1C.1D.不確定9.設(shè)數(shù)組A[m]作為循環(huán)隊(duì)列sq的存儲空間，front為隊(duì)頭指針，rear為隊(duì)尾指針，則執(zhí)行入隊(duì)操作時(shí)修改指針的語句是。A、sq.front=(sq.front+1)%mB、sq.front=(sq.front+1)%(m+1)C、sq.rear=(sq.rear+1)%mD、sq.rear=(sq.rear+1)%(m+1)二、填空題1.已知一棵二叉樹的中序序列和后序序列分別為：DBGEACHF和DGEBHFCA，則該二叉樹的前序序列是()。2.在()鏈表中，從任何一結(jié)點(diǎn)出發(fā)都能訪問到表中的所有結(jié)點(diǎn)。3.以下函數(shù)的時(shí)間復(fù)雜度為()。fact(intn){if(n<=1)return1;elsereturn(n*fact(n-1));}4.在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是t->Ltag==()。5.現(xiàn)有按中序遍歷二叉樹的結(jié)果為abc，問有()種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果。6.如圖所示，刪除元素b的語句為()。三、應(yīng)用題1.給出下面森林對應(yīng)的二叉樹及二叉樹的后序序列。2.已知二叉樹的先序、中序和后序序列如下:前序序列：*BC***G*中序序列：CB*EAGH*后序序列：*EDB**FA，其中有一些看不清的字母用*表示。請先補(bǔ)充*處的字母.再構(gòu)造一棵符合條件的二叉樹(3)最后畫出帶頭結(jié)點(diǎn)的中序線索鏈表。3.有一個(gè)含頭結(jié)點(diǎn)的單鏈表，頭指針為A,另有一個(gè)不含頭結(jié)點(diǎn)的單鏈表，頭指針為B。(1)分別寫出判斷A為空和B為空的條件。(2)假設(shè)S指向一個(gè)新結(jié)點(diǎn)，分別寫出在A的表頭插入S，和在B的表頭插入S的語句。設(shè)A～H8個(gè)字符出現(xiàn)的概率為:W={0.10,0.16,0.01,0.02,0.29,0.10,0.07,0.25}。設(shè)計(jì)最優(yōu)二進(jìn)制編碼（用0,1編碼）畫出最優(yōu)二叉樹計(jì)算平均碼長(二叉樹的帶權(quán)路徑長度)。5.線性表有兩種存儲結(jié)構(gòu)一是順序表，二是鏈表。試問（1）如果有n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？為什么？（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)？為什么？6.循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它的空和滿？四、編程題1、已知順序表結(jié)構(gòu)體定義如下：#defineMAXLEN100 typedefstruct{ intdata[MAXLEN]; intlast; }SeqList;在順序表L的第i個(gè)位置上插入值為x的元素的函數(shù)定義如下：intInsList(SeqList*L,inti,intx){ ……//（1）函數(shù)代碼空缺部分}要求：將“（1）函數(shù)代碼空缺部分”的內(nèi)容，在下面空白處填寫完整，其中順序表滿，返回-1；插入位置錯(cuò)誤，返回0；正常完成數(shù)據(jù)插入返回1。2、已知鏈隊(duì)列元素的結(jié)構(gòu)體定義如下：typedefstructNode{ intdata; structNode*next;}QNode;鏈隊(duì)列頭結(jié)點(diǎn)定義為：typedefstruct{ QNode*front,*rear;}LQueue;在隊(duì)列中，完成入隊(duì)操作的函數(shù)定義如下：voidIn_LQueue(LQueue*q,intx){ ……//（2）函數(shù)代碼空缺部分 }依據(jù)題目條件，將“（2）函數(shù)代碼空缺部分”的內(nèi)容，在下面空白處填寫完整。3、已知線性單鏈表結(jié)構(gòu)體定義如下：typedefstructNode{ intdata; structNode*next;}LNode,*LinkList;在單鏈表L的第i個(gè)位置上插入值為x的元素的函數(shù)定義如下：intInsert_LinkList(LinkListL,inti,intx){ …………//（1）函數(shù)代碼空缺部分}假設(shè)LNode*Get_LinkList(LinkListL,inti)函數(shù)已經(jīng)定義完成，該函數(shù)的功能為“在單鏈表L中查找第i個(gè)元素結(jié)點(diǎn)，找到后返回其指針；否則返回空指針”。要求：將“（1）函數(shù)代碼空缺部分”的內(nèi)容，在下面空白處填寫完整，其中插入位置錯(cuò)誤，返回值為0；正常完成數(shù)據(jù)插入返回值為1。4、已知棧的結(jié)構(gòu)體定義如下：#defineMAXLEN100typedefstruct{ chardata[MAXLEN]; inttop;}SeqSta