數(shù)據(jù)結(jié)構(gòu)試題06(有答案)

1、數(shù)據(jù)結(jié)構(gòu)試題06（有答案）一、 單選題（每題2分，共20分）1 .以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？（）A. 有向圖B.隊(duì)列 C.線索二叉樹D. B樹2 .在一個(gè)單鏈表HL中，若要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指 向的結(jié)點(diǎn)，則執(zhí)行如下（）語(yǔ)句序列。A. p=q; p->next=q;C. p->next=q->next;p->next=q;B. p->next=q; q->next=p;p=q；D. q->next=p->next;3.以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？（）A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.C.判斷一個(gè)隊(duì)列是否為空D.從

2、隊(duì)頭刪除一個(gè)元素 讀取隊(duì)頭元素的值4.字符A、B、C依次進(jìn)入一個(gè)棧，按出棧的先后順序組成不同的字符串，至多可以組成（）個(gè)不同的字符串？A.14B.5C.6D.85.A.A.B.116.A.B.C.D.7.A、由權(quán)值分別為 3,8,6,2的葉子生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為（）。B.35 C. 19 D. 53以下6-8題基于圖1。該二叉樹結(jié)點(diǎn)的前序遍歷的序列為（）E、E、E、E、GA、A、GF、GC、A、A、C、B、C、C、F、DDDB、GF、BDFB該二叉樹結(jié)點(diǎn)的中序遍歷的序列為（）B、GE、A、GC. EE.D E、G FC、F、B、D、A、C B D G FB、D G A、F、G

3、E8.該二叉樹的按層遍歷的序列為（）E、G F、A、C、D BB. E、A、G B、D G9.F、C.BE、A、G G F、B、DD. E、G A、C、卜面關(guān)于圖的存儲(chǔ)的敘述中正確的是（）第2頁(yè)（共4頁(yè)）A .用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)B .用鄰接表法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中邊數(shù)和結(jié)點(diǎn)個(gè)數(shù)都有關(guān) C.用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小與圖中結(jié)點(diǎn)個(gè)數(shù)和邊數(shù)都有 關(guān)D .用鄰接矩陣法存儲(chǔ)圖，占用的存儲(chǔ)空間大小只與圖中邊數(shù)有關(guān)，而與結(jié) 點(diǎn)個(gè)數(shù)無(wú)關(guān)10.設(shè)有關(guān)鍵碼序列（q , g, m, z, a, n, p, x, h）,下面哪一個(gè)序列是從上述

4、 序列出發(fā)建堆的結(jié)果？（）A. a , g, h,旦 n, p, q, x, zB. a , g, m, h,q, n, p, x, zC. g ，由 q, a, n, p, x, h, z D. h , g, m p, a, n, q, x, z2、 填空題（每空1分，共26分）1 . 數(shù)據(jù)的物理結(jié)構(gòu)被分為 、> ?口 四種。2 .對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為,在表尾插入元素的時(shí)間復(fù)雜度為 03 .向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí)，需要執(zhí)行的操作是;刪除一個(gè)結(jié)點(diǎn)時(shí)，需要執(zhí)行的操作是（假設(shè)棧不空而且無(wú)需回收被刪除 結(jié)點(diǎn)）。4 .對(duì)于一棵具有n

5、個(gè)結(jié)點(diǎn)的二叉樹，一個(gè)結(jié)點(diǎn)的編號(hào)為i（1 <i <n）,若它有左孩子則左孩子結(jié)點(diǎn)的編號(hào)為 ,若它有右孩子，則右孩子結(jié) 點(diǎn)的編號(hào)為，若它有雙親，則雙親結(jié)點(diǎn)的編號(hào)為 。5 .當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí)，需要逐層 調(diào)整，直到被調(diào)整到位置為止。6 .以二分查找方法從長(zhǎng)度為10的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為7 .表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為、和8 .對(duì)于線性表（70, 34, 55, 23, 65, 41, 20）進(jìn)行散列存儲(chǔ)時(shí)，若選用H （K） =K %7作為散列函數(shù)，則散列地址為 0的元素有個(gè)，散列地址為6的有個(gè)。9 .在歸并排序中，進(jìn)行每趟歸并的時(shí)間復(fù)雜度為 ，整

6、個(gè)排序過(guò)程的時(shí)間 復(fù)雜度為,空間復(fù)雜度為 010 .在一棵m階B2W上，每個(gè)非樹根結(jié)點(diǎn)白關(guān)鍵字?jǐn)?shù)目最少為 個(gè)，最多為個(gè)，其子樹數(shù)目最少為 ,最多為。3、 運(yùn)算題（每題6分，共24分）第2頁(yè)（共4頁(yè)）1 .寫出下列中綴表達(dá)式的后綴形式：(1) 3X/(Y-2)+1(2) 2+X*(Y+3)2 .試對(duì)圖2中的二叉樹畫出其： (1)順序存儲(chǔ)表示的示意圖； (2)二叉鏈表存儲(chǔ)表示的示意圖。3 .判斷以下序列是否是小根堆？如果不是將它調(diào)整為小根堆。(1) 12,24,33,65,33,56,48,92,86,70 (2) 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 4

7、7, 100 4.已知一個(gè)圖的頂點(diǎn)集V和邊集E分別為：V=1,2,3,4,5,6,7;E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4 , (4,7)20,(5,6)18,(6,7)25;按照普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹，試寫出在最小生成樹中 依次得到的各條邊。4、 閱讀算法(每題7分，共14分)1. void AE(Stack& S) InitStack(S);Push(S,3);Push(S,4);int x=Pop(S)+2*Pop(S);Push(S,x);int i,a5=1,5,8

8、,12,15;for(i=0;i<5;i+) Push(S,2*ai);while(!StackEmpty(S) cout<<Pop(S)<<'' 該算法被調(diào)用后得到的輸出結(jié)果為： 2. void ABC (BTNode *BT,int &c1,int &c2) if (BT !=NULL ) ABC(BT->left,c1,c2);c1+;if (BT->left=NULL&&BT->right=NULL) c2+;ABC(BT->right,c1,c2);/if該函數(shù)執(zhí)行的功能是什么？5、

9、 算法填空(共8分) 向單鏈表的末尾添加一個(gè)元素的算法。Void InsertRear(LNode*& HL,const ElemType& item) LNode* newptr;newptr=new LNode;If () cerr<<"Memory allocation failare!"<<endl; exit； =item;newptr->next=NULL;if (HL=NULL)HL=;elseLNode* P=HL;While (P->next!=NULL);p->next=newptr; 6、 編寫

10、算法(共8分)編寫從類型為L(zhǎng)ist的線性表L中將第i個(gè)元素刪除的算法，(假定不需要對(duì) i的值進(jìn)行有效性檢查，也不用判別L是否為空表。void Delete(List& L, int i)10.B"I：I 雙£ I17守回,八I岡；I八小1、 單選題（每題2分，共20分）1.B 2.D 3.A 4.B 5.B 6.C 7.A 8.C 9.B2、 填空題（每空1分，共26分）1. 順序鏈表索引散列2. O（n） O（1）3. p->next=HS;HS=p HS=HS->next4. 2i 2i+1i/2 （或 i/2 ）5. 向上 根6. 2.9第3頁(yè)（共

11、4頁(yè)）7. 鄰接矩陣鄰接表邊集數(shù)組8. 1 49. O(n) O(nlog 2n) O(n)10. m/2-1m-1m/2 m三、運(yùn)算題(每題6分，共24分)1. (1) 3X* Y 2- / 1+(2) 2 XY3 + * +2. (1) (3 分)012345678910 n 12 13 14 18 31123456789(2)見圖3所示：3. (1)不是小根堆。調(diào)整為：12,65,33,70,24,56,48,92,86,33(2)是小根堆。4. 普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹為：(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)20四、閱讀算法(每題7分，共14分)1 . 30 24 16 10 2 102 .該函數(shù)的功能是：統(tǒng)計(jì)出BT所指向的二叉樹的結(jié)點(diǎn)總數(shù)和葉子總數(shù)五、算法填空(共8分，