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

1、一、單擇題1. 棧和隊(duì)列的共同特點(diǎn)是 ()。A.只允許在端點(diǎn)處插入和刪除元素B .都是先進(jìn)后出C. 都是先進(jìn)先出D. 沒有共同點(diǎn)2. 二叉樹的第 k 層的結(jié)點(diǎn)數(shù)最多為 ()。A.2k-1B.2K+1C.2K-1 D. 2k-13. 數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成 ( )。A. 動(dòng)態(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è)元

2、素需要移動(dòng) ()個(gè)元素。A. n-i B. n+l -i C.n-1-i D. i6. 判定一個(gè)棧ST （最多元素為mO）為空的條件是（）A.ST TOP!=0C.ST TOP!= mOB.ST TOP=0D.ST TOP=m07.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由P所指向）滿足（A.p-> next=NULLB.p=NULLC.p-> next=head D.p=head2. 按昭二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有（）種。A. 3 Bt4 C.5D.63個(gè)棧的入棧序列是則棧的不可能的輸出序列是 （ KA.edcba B.decba C. dceab D abode4假設(shè)以數(shù)組

3、吐m存放猶環(huán)隊(duì)列的元素，其頭尾指針分別為front 和rear,則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為（ 人A. （rearfrontm）B* rear-f ront+1C. （f ron七一廠匕迅廠+m）湎D. （rearf ront） %mH從一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在 查找成功的情況下，需平均比較（）個(gè)結(jié)點(diǎn)占A,n B. n/2 C. (n-1)/2 D. (n+1)/26.在一個(gè)帶頭結(jié)點(diǎn)的單鏈表HL中，若要在第一個(gè)元素之前插入一 個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行(幾A. HL = p; p->next = HL:B. p->next = HL;HL = p ;G p

4、->next = HI ;p = HL;0. p->next = HL->next;= p ;7. 在一棵三叉樹中度為3的結(jié)點(diǎn)數(shù)為2個(gè)，度為2的結(jié)點(diǎn)數(shù)為1 個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，則度為0的結(jié)點(diǎn)數(shù)是( 九A.4 B. 5 C. 6 D. 78在線性結(jié)構(gòu)中，所有結(jié)點(diǎn)都有()個(gè)直接后繼。A.0B.0或1C.1 D.不確定9.設(shè)數(shù)組Am作為循環(huán)隊(duì)列sq的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾 指針，則執(zhí)行入隊(duì)操作時(shí)修改指針的語句是 0A sq.front=(sq.front+1)%mB、sq.front=(sq.front+1)%(m+1)C、sq.rear=(sq.re

5、ar+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(int n)if (n <=1)return 1;elsereturn( n*fact( n-1);4在線索化二叉樹中，t所指結(jié)點(diǎn)沒有左子樹的充要條件是t->Ltag=( )。5現(xiàn)有按中序遍歷二叉樹的結(jié)果為 abc，問有()種不同形態(tài)的 二叉樹可以得到這一遍歷結(jié)果。6如圖所示，刪除元素b的語

6、句為()二、應(yīng)用題1. 給出下面森林對應(yīng)的二叉樹及二叉樹的后序序列2. 已知二叉樹的先序、中序和后序序列如下:前序序列： *BC*G*中序序列： CB*EAGH*后序序列： *EDB*FA ，其中有一些看不清的字母用 * 表示。(1) 請先補(bǔ)充 * 處的字母 .(2) 再構(gòu)造一棵符合條件的二叉樹(3) 最后畫出帶頭結(jié)點(diǎn)的中序線索鏈表。3. 有一個(gè)含頭結(jié)點(diǎn)的單鏈表，頭指針為A, 另有一個(gè)不含頭結(jié)點(diǎn)的單鏈表，頭指針為 B。(1)分別寫出判斷A為空和B為空的條件。假設(shè)S指向一個(gè)新結(jié)點(diǎn)，分別寫出在 A的表頭插入S,和在B的 表頭插入S的語句。4. 設(shè)AH 8個(gè)字符出現(xiàn)的概率為：W=0.10,0.16,

7、 0.01, 0.02,0.29,0.10,0.07,0.25。設(shè)計(jì)最優(yōu)二進(jìn)制編碼(用0,1編碼)( 1 )畫出最優(yōu)二叉樹(2 )計(jì)算平均碼長 (二叉樹的帶權(quán)路徑長度 )。5. 線性表有兩種存儲(chǔ)結(jié)構(gòu)一是順序表，二是鏈表。試問(1)如果有n個(gè)線性表同時(shí)并存，并且在處理過程中各表的長 度會(huì)動(dòng)態(tài)變化，線性表的總數(shù)也會(huì)自動(dòng)地改變。在此情況下，應(yīng)選用哪種存儲(chǔ)結(jié)構(gòu)？ 為什么？ （2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要 求以最快的速度存取線性表中的元素， 那么應(yīng)采用哪種存儲(chǔ)結(jié)構(gòu)？ 為什么？6. 循環(huán)隊(duì)列的優(yōu)點(diǎn)是什么？如何判別它的空和滿？四、編程題1、已知順序表結(jié)構(gòu)體定義如下：#define

8、MAXLEN 100typedef structint dataMAXLEN;int last;SeqList;在順序表 L 的第 i 個(gè)位置上插入值為 x 的元素的函數(shù)定義如下： int InsList（SeqList *L,int i,int x）, / （1）函數(shù)代碼空缺部分 要求：將“（1）函數(shù)代碼空缺部分”的內(nèi)容，在下面空白處填寫完整，其中順序 表滿，返回 -1 ；插入位置錯(cuò)誤，返回 0；正常完成數(shù)據(jù)插入返回 1。2、已知鏈隊(duì)列元素的結(jié)構(gòu)體定義如下： typedef struct Nodeint data; struct Node *next;QNode;鏈隊(duì)列頭結(jié)點(diǎn)定義為：type

9、def structQNode *front,*rear;LQueue; 在隊(duì)列中，完成入隊(duì)操作的函數(shù)定義如下： void In_LQueue（LQueue *q,int x）, / （ 2）函數(shù)代碼空缺部分依據(jù)題目條件，將“（2）函數(shù)代碼空缺部分”的內(nèi)容，在下面空白處填寫完整。3、已知線性單鏈表結(jié)構(gòu)體定義如下：typedef struct Nodeint data;struct Node *next;LNode,*LinkList;在單鏈表 L 的第 i 個(gè)位置上插入值為 x 的元素的函數(shù)定義如下：int Insert_LinkList（LinkList L,int i,int x） , / （1）函數(shù)代碼空缺部分假設(shè) LNode *Get_LinkList（LinkList L,int i） 函數(shù)已經(jīng)定義完成，該函數(shù) 的功能為“在單鏈表L中查找第i個(gè)元素結(jié)點(diǎn)，找到后返回其指針；否則返回空 指針”。要求：將“（1）函數(shù)代碼空缺部分”的內(nèi)容，在下面空白處填寫完整，其中插入 位置錯(cuò)誤，返回值為 0；正常完成數(shù)據(jù)插入返回值為 1。4、已知棧的結(jié)構(gòu)體定義如下：#define MAXLEN 100typedef structchar dataMAX