c語(yǔ)言數(shù)據(jù)結(jié)構(gòu)試題模擬試卷

1、模擬試卷一、 一、單項(xiàng)選擇題每題 2分,共20分1. 1.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？ 2 A.有向圖B.隊(duì)列C.線索二叉樹(shù)D. B樹(shù)2. 2.在一個(gè)單鏈表 HL中,假設(shè)要在當(dāng)前由指針p指向的結(jié)點(diǎn)后面插入一個(gè)由q指向的結(jié)點(diǎn),那么執(zhí)行如下4 語(yǔ)句序列.A. p=q; p->next=q; B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q;3. 3.以下哪一個(gè)不是隊(duì)列的根本運(yùn)算？ 1 A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素B.從隊(duì)頭刪除一個(gè)元素

2、C.判斷一個(gè)隊(duì)列是否為空D.讀取隊(duì)頭元素的值4.4. 字符A、B、C依次進(jìn)入一個(gè)棧,按出棧的先后順序組成不同的字符串,至多可以 組成b 個(gè)不同的字符串？5.8.9.AA.145.8.A9.B.5由權(quán)值分別為C.6D.83,8,6,2的葉子生成一棵哈夫曼樹(shù),它的帶權(quán)路徑長(zhǎng)度為 B.35 C. 19 D. 53B、A、A、E.以下6-8題基于圖1.該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為A.A.E、GF、A、GDBB.B.E、AGC、F、BDC.C.E、ACB、DGFD.D.E、GA、C、DF、B該二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為GFCBE.E、F、B、GA、F、b ).(3 ).(1 ).該二叉樹(shù)的按層遍歷的

3、序列為.E、G F、A、C、D B(3 ).C. E、A、G C、F、B DB. E 、A、D. E、GCA、B、CGF、卜面關(guān)于圖的存儲(chǔ)的表達(dá)中正確的選項(xiàng)是.用鄰接表法存儲(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. 10.設(shè)有關(guān)鍵碼序列(q, g, m, z, a, n, p, x, h),下面哪一個(gè)序列是從上述序列出 發(fā)建堆的結(jié)果?( 2 )A. a , g, h

4、, m n, p, q, x, zB. a , g, m h, q, n, p, x, zC. g , m q, a, n, p, x, h, z D. h , g, m p, a, n, q, x, z二、二、填空題(每空1分,共26分)1. 1.數(shù)據(jù)的物理結(jié)構(gòu)被分為順序、鏈表、索引 和 散列四種.2. 2.對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表,在表頭插入元素的時(shí)間復(fù)雜度為_(kāi)o(n),在表尾插入元素的時(shí)間復(fù)雜度為_(kāi)O(1).3. 3. 向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí),需要執(zhí)行的操作是p->next=HS,HS =p;刪除一個(gè)結(jié)點(diǎn)時(shí),需要執(zhí)行的操作是HS=HS->next

5、 (假設(shè)棧不空而且無(wú)需回收被刪除結(jié)點(diǎn)).4. 4.對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),一個(gè)結(jié)點(diǎn)的編號(hào)為i(iwiwn),假設(shè)它有左孩子那么左孩子結(jié)點(diǎn)的編號(hào)為 _2i,假設(shè)它有右孩子,那么右孩子結(jié)點(diǎn)的編號(hào)為 _2i+1, 假設(shè)它有雙親,那么雙親結(jié)點(diǎn)的編號(hào)為2/i.5. 5.當(dāng)向一個(gè)大根堆插入一個(gè)具有最大值的元素時(shí),需要逐層_向上 調(diào)整,直到被調(diào)整到根位置為止.6. 6.以二分查找方法從長(zhǎng)度為10的有序表中查找一個(gè)元素時(shí),平均查找長(zhǎng)度為6.9。7. 7.表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為鄰接矩陣、鄰接表_和_邊集數(shù)組8. 8. 對(duì)于線T表(70, 34, 55, 23, 65, 41, 20)進(jìn)行散列存儲(chǔ)時(shí),

6、假設(shè)選用 H (K) =K %7作為散列函數(shù),那么散列地址為0的元素有 個(gè),散列地址為6的有個(gè).9. 9.在歸并排序中,進(jìn)行每趟D3并的時(shí)間復(fù)雜度為 ,整個(gè)排序過(guò)程的時(shí)間復(fù)雜度為,空間復(fù)雜度為 .10. 10.在一棵m階B_樹(shù)上,每個(gè)非樹(shù)根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為 個(gè),最多為 個(gè),其子樹(shù)數(shù)目最少為 ,最多為 .三、三、運(yùn)算題(每題 6分,共24分)1重1.1.寫(xiě)出以下中綴表達(dá)式的后綴形式：/ - _(1)(1)3X/(Y-2)+1)/、(2)(2)2+X*(Y+3)('2.2. 試對(duì)圖2中的二叉樹(shù)畫(huà)出其：(1) (1)順序存儲(chǔ)表示的示意圖；聲逸)(2) (2)二叉鏈表存儲(chǔ)表示的示意圖.曠

7、"3.3.判斷以下序列是否是小根堆？如果不是,將它一圖2調(diào)整為小根堆.(1) 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 (2) 05, 23, 20, 28, 40, 38, 29, 61,35, 76, 47, 100 4. 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;根據(jù)普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹(shù),試寫(xiě)出在最小生成樹(shù)中依次得到

8、的各條邊.4、 四、閱讀算法(每題 7分,共14分)1. 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,12,15);for(i=0;i<5;i+) Push(S,2*ai);while(!StackEmpty(S) cout<<Pop(S)<<' ')該算法被調(diào)用后得到的輸出結(jié)果為：2. 2. void ABC (BTNode *BT,int &c1,int &c2)

9、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í)行的功能是什么？統(tǒng)計(jì)結(jié)點(diǎn)總數(shù)和葉子總數(shù)；5、 五、算法填空(共8分)向單鏈表的末尾添加一個(gè)元素的算法.Void InsertRear(LNode*& HL,const ElemType& item) LNode* newptr; newptr=new LNode;If (newptr=NULL_) cerr<<&q

10、uot;Memory allocation failare!"<<endl;exit(1);newptr->data=item;newptr->next=NULL;if (HL=NULL)HL=_newptr;elseLNode* P=HL;While (P->next!=NULL)p=p->next; p->next=newptr; newptr=NULL newptr->=data newptrp=p->next6、 六、編寫(xiě)算法(共8分)編寫(xiě)從類型為L(zhǎng)ist的線性表L中將第i個(gè)元素刪除的算法,(假定不需要對(duì)i的值進(jìn)行 有效性

11、檢查,也不用判別L是否為空表.)void Delete(List& L, int i)for(j=i-1;j<L.size-1;j+)L.listj=L.listj+1;L.size-;)模擬試卷一參考答案8.C 9.B 10.B單項(xiàng)選擇題(每題2分,共20分)1.B 2,D 3.A 4.B 5.B 6.C 7.A填空題(每空1分,共26分)1. 1.順序鏈表索引散列2. 2. O(n) O(1)3. 3. p->next=HS;HS=p HS=HS->nexti/2 )5. 5.向上 根6. 6.2.97. 7.鄰接矩陣 鄰接表邊集數(shù)組8. 8.1 49. 9.O(

12、n)O(nlog2n).10. 10. m/2 -1m-1m/2 m24分)三、 三、 運(yùn)算題(每題6分,共1. 1.(1) 3 X * Y 2 - / 1(2)(2)2 X Y 3 +1234567892. 2.(1)012345678910111213141516(2)見(jiàn)圖3所示：3. 3.(1)不是小根堆.調(diào)整為： 12,65,33,70,24,56,48,92,86,33(2)是小根堆.4. 4.普里姆算法從頂點(diǎn)1出發(fā)得到最小生成樹(shù)為：(1,2)3, (1,3)5, (1,4)8, (4,6)4, (2,5)10, (4,7)204、 四、閱讀算法(每題 7分,共14分)1.1.30

13、24 16 10 2 102. 2.該函數(shù)的功能是：統(tǒng)計(jì)出 BT所指向的二叉樹(shù)的結(jié)點(diǎn)總數(shù)和葉子總數(shù)5、 五、算法填空(共 8分,每一空2分)newptr=NULL newptr->=data newptrp=p->next6、 六、編寫(xiě)算法(8分)void Delete(List& L, int i) for(int j=i-1;j<L.size-1; j+)L.listj=L.listj+1; /第 i 個(gè)元素的下標(biāo)為 i-1L.size-;)模擬試卷二1、 一、單項(xiàng)選擇題每題 2分,共20分1. 1.在一個(gè)帶有附加表頭結(jié)點(diǎn)的單鏈表HL中,假設(shè)要向表頭插入一個(gè)由指針

14、p指向的結(jié)點(diǎn),那么執(zhí)行.A. HL=p; p->next=HL;B. p->next=HL->next; HL->next=p;C. p->next=HL; p=HL;D. p->next=HL; HL=p;2. 2.假設(shè)順序存儲(chǔ)的循環(huán)隊(duì)列的QueueMaxSize=n,那么該隊(duì)列最多可存儲(chǔ)個(gè)元素.A. nB.n-1C. n+1 D.不確定3. 3.下述哪一條是順序存儲(chǔ)方式的優(yōu)點(diǎn)？A .存儲(chǔ)密度大B.插入和刪除運(yùn)算方便C.獲取符合某種條件的元素方便D.查找運(yùn)算速度快4. 4.設(shè)有一個(gè)二維數(shù)組 Amn,假設(shè)A0存放位置在600io, A33存放位置在 6781

15、0,每個(gè)元素占一個(gè)空間,問(wèn) A23 10存放在什么位置？腳注10表示用10進(jìn) 制表示,m>3A. 658B. 648C. 633D. 6535. 5.以下關(guān)于二叉樹(shù)遍歷的表達(dá)中,正確的選項(xiàng)是.A.假設(shè)一個(gè)樹(shù)葉是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn),那么它必是該二叉樹(shù)的前序遍歷 最后一個(gè)結(jié)點(diǎn)B.假設(shè)一個(gè)點(diǎn)是某二叉樹(shù)的前序遍歷最后一個(gè)結(jié)點(diǎn),那么它必是該二叉樹(shù)的中序遍歷的最 后一個(gè)結(jié)點(diǎn)C.假設(shè)一個(gè)結(jié)點(diǎn)是某二叉樹(shù)的中序遍歷的最后一個(gè)結(jié)點(diǎn),那么它必是該二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn)D.假設(shè)一個(gè)樹(shù)葉是某二叉樹(shù)的前序最后一個(gè)結(jié)點(diǎn),那么它必是該二叉樹(shù)的中序遍歷最后一個(gè)結(jié)點(diǎn)6. 6. k層二叉樹(shù)的結(jié)點(diǎn)總數(shù)最多為.A

16、 . 2k-1B.2K+1C.2K-1D. 2 k-17. 7.對(duì)線性表進(jìn)行二分法查找,其前提條件是 .A.A.線性表以鏈接方式存儲(chǔ),并且按關(guān)鍵碼值排好序7.8. 線性表以順序方式存儲(chǔ),并且按關(guān)鍵碼值的檢索頻率排好序C.C.線性表以順序方式存儲(chǔ),并且按關(guān)鍵碼值排好序D.D.線性表以鏈接方式存儲(chǔ),并且按關(guān)鍵碼值的檢索頻率排好序8. 8.對(duì)n個(gè)記錄進(jìn)行堆排序,所需要的輔助存儲(chǔ)空間為A. O 1og2nB. O nC. O 1D. O n29. 9.對(duì)于線T表7, 34, 77, 25, 64, 49, 20, 14進(jìn)行散列存儲(chǔ)時(shí),假設(shè)選用H K=K %7作為散列函數(shù),那么散列地址為0的元素有個(gè),A

17、 . 1 B . 2 C . 3 D . 410. 10.以下關(guān)于數(shù)據(jù)結(jié)構(gòu)的表達(dá)中,正確的選項(xiàng)是 .A. A.數(shù)組是不同類型值的集合B. B.遞歸算法的程序結(jié)構(gòu)比迭代算法的程序結(jié)構(gòu)更為精煉C. C.樹(shù)是一種線性結(jié)構(gòu)D. D.用一維數(shù)組存儲(chǔ)一棵完全二叉樹(shù)是有效的存儲(chǔ)方法2、 二、填空題(每空1分,共26分)1. 1.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為 、和 四種.2. 2.一個(gè)算法的時(shí)間復(fù)雜度為(3n3+2000nlog2n+90)/n2,其數(shù)量級(jí)表示為 .3. 3.對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的隊(duì)列,在表頭插入元素的時(shí)間復(fù)雜度為,在表尾插入元素的時(shí)間復(fù)雜度為 .4. 4.假定一棵樹(shù)的廣義表表示為A (D (E

18、, G), H (I, J),那么樹(shù)中所含的結(jié)點(diǎn)數(shù)為個(gè),樹(shù)的深度為,樹(shù)的度為.5. 5.后綴算式79 2 30 + - 4 2 / *的值為.中綴算式(3+X*Y )-2Y/3對(duì)應(yīng)的后綴算式為.6. 6.在一棵高度為5的理想平衡樹(shù)中,最少含有 個(gè)結(jié)點(diǎn),最多含有 個(gè)結(jié)點(diǎn).7. 7.在樹(shù)中,一個(gè)結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)稱為該結(jié)點(diǎn)的 .一個(gè)結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)稱為該結(jié)點(diǎn)的.8. 8.在一個(gè)具有10個(gè)頂點(diǎn)的無(wú)向完全圖中, 包含有 條邊,在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中,包含有 條邊.9. 9.假定一個(gè)線性表為(12,17,74,5,63,49,82,36),假設(shè)按Key % 4條件進(jìn)行劃分,使得同一余數(shù)的元素

19、成為一個(gè)子表,那么得到的四個(gè)子表分別為和.10. 10.對(duì)一棵B_樹(shù)進(jìn)行刪除元素的過(guò)程中,假設(shè)最終引起樹(shù)根結(jié)點(diǎn)的合并時(shí),會(huì)使新樹(shù)的 高度比原樹(shù)的高度.11. 11.在堆排序的過(guò)程中,對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為 ,整個(gè) 堆排序過(guò)程的時(shí)間復(fù)雜度為 .12. 12.在線性表的散列存儲(chǔ)中,裝填因子a又稱為裝填系數(shù),假設(shè)用m表示散列表的長(zhǎng)度,n表示待散列存儲(chǔ)的元素的個(gè)數(shù),那么 以等于運(yùn)算題(每題 6分,共24分)1.1. 在如下數(shù)組性表.A中鏈接存儲(chǔ)了一個(gè)線性表,表頭指針存放在 A 0.next ,試寫(xiě)出該線60507890344040527131 23 45 67data next2. 2

20、.一棵二叉樹(shù)的前序遍歷的結(jié)果是ABKCDFGHIJ,中序遍歷的結(jié)果是KBCDAFHIGJ, 試畫(huà)出這棵二叉樹(shù).3. 3.一個(gè)圖的頂點(diǎn)集V為： V=1,2,3,4,5,6,7;其共有10條邊.該圖用如下邊集數(shù)組存儲(chǔ)：122552261364547677751122233457試用克魯斯卡爾算法依次求出該圖的最小生成樹(shù)中所得到的各條邊及權(quán)值.起點(diǎn) 終點(diǎn) 權(quán)4. 4.畫(huà)出向小根堆中參加數(shù)據(jù)4, 2, 5, 8, 3, 6, 10, 1時(shí),每參加一個(gè)數(shù)據(jù)后堆的變化.四、四、閱讀算法(每題 7分,共14分)1. 1.在下面的每個(gè)程序段中,假定線性表La的類型為L(zhǎng)ist,元素類型ElemType為int

21、,并假定每個(gè)程序段是連續(xù)執(zhí)行的.試寫(xiě)出每個(gè)程序段執(zhí)行后所得到的線性表La.(1) (1) InitList(La);Int a=100,26,57,34,79);For (i=0;i<5;i+)Insert(La,ai);TraverseList(La);(2) (2) DeleteFront(La);InsertRear(La, DeleteFront(La);TraverseList(La);(3) (3) ClearList(La);For (i=0;i<5;i+)InsertFront(La,ai);TraverseList(La);2. 2.現(xiàn)面算法的功能是什么？void

22、 ABC(BTNode * BT)if BT cout<<BT->data<<''ABC(BT->left); ABC(BT->right); ) ) 五、五、算法填空(共8分)查找成功,返回元素的下標(biāo)在左子表上繼續(xù)查找;/在右子表上繼續(xù)查找查找失敗,返回-1二分查找的遞歸算法. Int Binsch(ElemType A,int low,int high,KeyType K) if int mid=(low+high)/2; if () return mid; / else if (K<Amid.key) return Bins

23、ch(A,low,mid-1,K); / else return) else ;/) 六、六、編寫(xiě)算法(共8分)HL為單鏈表的表頭指針,試寫(xiě)出在該單鏈表中查找具有給定的元素item的算法.bool FindLNode* HL, ElemType &item模擬試卷二參考答案1、 一、單項(xiàng)選擇題每題2分,共20分1.B 2.B 3.A 4.C 5.D 6.A 7.C8.C9.D10.D2、 二、填空題每空1分,共26分1.1.集合結(jié)構(gòu)線性結(jié)構(gòu)樹(shù)結(jié)構(gòu)圖結(jié)構(gòu)..0(1)7 294O(1)23 X 丫 * + 2 丫 * 3 / -..1

24、0.10.16 31孩子或子結(jié)點(diǎn)45nn-112, 36減少1 或減少雙親(17,5,49 )或父結(jié)點(diǎn)(74, 82)(63)2.O(log 2n) n/mO(nlog 2n)運(yùn)算題每題6分,共24分.線性表為:(90, 40, 78, 50,當(dāng)前序序列為 ABKCDFGHIJ ,34, 60中序序列為KBCDAFHIGJ時(shí),逐步形成二叉樹(shù)的過(guò)程如以下圖4所示:ABCFHIGJBHIGJCD3.圖3.用克魯斯卡爾算法得到的最小生成樹(shù)為:AACKDHI4(3,5)74.(1,6)1, (2,4)1, (2,5)2,4. 見(jiàn)圖5.(5,7)2,(2,6)3,433

25、521010四、四、閱讀算法每題圖57分,共14分)1.1.(1) La=(26,34,57,79,100)2.五、(2)La=(57,79,100,34)(3)La=(79,34,57,26,100)2.前序遍歷鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù).五、算法填空每空2分,共8分)(low<=high)六、六、K=Amid.key Binsch(A,mid+1,hight,K)編寫(xiě)算法(8分)return -1bool Find(LNode* HL, ElemType &item)(LNode* p=HL;while pif (p->data=item) return true;else p=

26、p->next; return false;模擬試卷三1、 一、單項(xiàng)選擇題(每題 2分,共20分)1. 1.對(duì)一個(gè)算法的評(píng)價(jià),不包括如下()方面的內(nèi)容.A.健壯性和可讀性B.并行性 C.正確性 D.時(shí)空復(fù)雜度2. 2.在帶有頭結(jié)點(diǎn)的單鏈表HL中,要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn),那么執(zhí)行().A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p;C. p->next=HL; p=HL;D. HL=p; p->next=HL;3. 3.對(duì)線性表,在以下哪種情況下應(yīng)當(dāng)采用鏈表表示？()A.經(jīng)常需要隨機(jī)地

27、存取元素B.經(jīng)常需要進(jìn)行插入和刪除操作C.表中元素需要占據(jù)一片連續(xù)的存儲(chǔ)空間D.表中元素的個(gè)數(shù)不變4. 4. 一個(gè)棧的輸入序列為1 2 3,那么以下序列中不可能是棧的輸出序列的是()A. 2 3 1B. 3 2 1C. 3 1 2D. 1 2 35. 5. AOV 網(wǎng)是一種().A.有向圖B.無(wú)向圖C.無(wú)向無(wú)環(huán)圖 D.有向無(wú)環(huán)圖6. 6.采用開(kāi)放定址法處理散列表的沖突時(shí),其平均查找長(zhǎng)度().A .低于鏈接法處理沖突B.高于鏈接法處理沖突C.與鏈接法處理沖突相同D.高于二分查找7. 7.假設(shè)需要利用形參直接訪問(wèn)實(shí)參時(shí),應(yīng)將形參變量說(shuō)明為()參數(shù).A.值 B.函數(shù)C.指針D.引用8. 8.在稀疏矩

28、陣的帶行指針向量的鏈接存儲(chǔ)中,每個(gè)單鏈表中的結(jié)點(diǎn)都具有相同的 ().A.行號(hào) B.列號(hào) C.元素值 D.非零元素個(gè)數(shù)9. 9.快速排序在最壞情況下的時(shí)間復(fù)雜度為().A . O(log 2n) B . O(nlog 2n)C. 0(n)D . 0(n2)9.10. .從二叉搜索樹(shù)中查找一個(gè)元素時(shí),其時(shí)間復(fù)雜度大致為().A. O(n) B. O(1) C. O(log2n) D. O(n2)2、 二、運(yùn)算題(每題 6分,共24分)1. 1.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的 .當(dāng)結(jié)點(diǎn)之間存在 M對(duì)N (M:N)的聯(lián)系時(shí),稱這種結(jié)構(gòu)為 .2. 2.隊(duì)列的插入操作是在隊(duì)列的 進(jìn)行,刪除操作是在隊(duì)列的

29、進(jìn)行.3. 3.當(dāng)用長(zhǎng)度為N的數(shù)組順序存儲(chǔ)一個(gè)棧時(shí),假定用 top=N表示棧空,那么表示棧滿的條件是.4. 4.對(duì)于一個(gè)長(zhǎng)度為n的單鏈存儲(chǔ)的線性表,在表頭插入元素的時(shí)間復(fù)雜度為,在表尾插入元素的時(shí)間復(fù)雜度為 .5. 5. 設(shè)W為一個(gè)二維數(shù)組,其每個(gè)數(shù)據(jù)元素占用4個(gè)字節(jié),行下標(biāo)i從0到7 ,列下標(biāo)j從0到3 ,那么二維數(shù)組 W的數(shù)據(jù)元素共占用_ 個(gè)字節(jié).W中第6行的元 素和第4列的元素共占用_ 一個(gè)字節(jié).假設(shè)按行順序存放二維數(shù)組W,其起始地址為100,那么二維數(shù)組元素 W6 , 3的起始地址為_(kāi) .6. 6. 廣義表 A= (a,(a,b),(a,b),c),那么它的深度為,它的長(zhǎng)度為7. 7.

30、二叉樹(shù)是指度為 2的 樹(shù).一棵結(jié)點(diǎn)數(shù)為 N的二叉樹(shù),其所有結(jié)點(diǎn)的度的總和是 .8. 8.對(duì)一棵二叉搜索樹(shù)進(jìn)行中序遍歷時(shí),得到的結(jié)點(diǎn)序列是一個(gè) .對(duì)一棵由算術(shù)表達(dá)式組成的二叉語(yǔ)法樹(shù)進(jìn)行后序遍歷得到的結(jié)點(diǎn)序列是該算術(shù)表達(dá)式的9. 9. 對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù),用二叉鏈表存儲(chǔ)時(shí),其指針總數(shù)為個(gè),其中 個(gè)用于指向孩子, 個(gè)指針 是空閑的.10. 10.假設(shè)對(duì)一棵完全二叉樹(shù)從0開(kāi)始進(jìn)行結(jié)點(diǎn)的編號(hào),并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組A中,即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到 A0中.其余類推,那么 A i 元素的左孩子元素為,右孩子元素為,雙親元素為.11. 11.在線性表的散列存儲(chǔ)中,處理沖突的常用方法有 和兩種

31、.12. 12.當(dāng)待排序的記錄數(shù)較大,排序碼較隨機(jī)且對(duì)穩(wěn)定性不作要求時(shí),宜采用排序；當(dāng)待排序的記錄數(shù)較大,存儲(chǔ)空間允許且要求排序是穩(wěn)定時(shí),宜采用 排序.00001000000-10000000-25000000700-3、 三、運(yùn)算題(每題6分,共24分)1. 1.一個(gè)6父5稀疏矩陣如右所示,試：(1) (1)寫(xiě)出它的三元組線性表；(2) (2)給出三元組線性表的順序存儲(chǔ)表示.2. 2.設(shè)有一個(gè)輸入數(shù)據(jù)的序列是 46, 25, 78, 62, 12,80 ),試畫(huà)出從空樹(shù)起,逐個(gè)輸入各個(gè)數(shù)據(jù)而生成的二 叉搜索樹(shù).3. 3. 對(duì)于圖6所示的有向圖假設(shè)存儲(chǔ)它采用鄰接表,并且每個(gè)頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)

32、都是根據(jù)終點(diǎn)序號(hào)從小到大的次序鏈接的,試寫(xiě)出:(1)從頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索所得到的深度優(yōu)先生成樹(shù);(2)從頂點(diǎn)出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的廣度優(yōu)先生成樹(shù);4. 4. 一個(gè)圖的頂點(diǎn)集 V和邊集E分別為：V=1,2,3,4,5,6,7;E=<2,1>,<3,2>,<3,6>,<4,3>,<4,5>, <4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>假設(shè)存儲(chǔ)它采用鄰接表,并且每個(gè)頂點(diǎn)鄰 接表中的邊結(jié)點(diǎn)都是根據(jù)終點(diǎn)序號(hào)從小到試給出得到的拓樸排序的

33、大的次序鏈接的,按主教材中介紹的拓樸排序算法進(jìn)行排序, 序列.四、四、閱讀算法(每題 7分,共14分)1) 1. int Prime(int n)( int i=1;int x=(int) sqrt(n); while (+i<=x)if (n%i=0) break;if (i>x) return 1; else return 0; (1)(1)指出該算法的功能；2) ) (2)該算法的時(shí)間復(fù)雜度是多少？2.2.寫(xiě)出下述算法的功能：void AJ(adjlist GL, int i, int n) (Queue Q; InitQueue(Q); cout<<i<&

34、lt;' ' visitedi=true; QInsert(Q,i);while(!QueueEmpty(Q) int k=QDelete(Q); edgenode* p=GLk; while(p!=NULL) int j=p->adjvex; if(!visitedj) cout<<j<<' ' visitedj=true; QInsert(Q,j); p=p->next; 5、 五、算法填空(共8分)如下為二分查找的非遞歸算法,試將其填寫(xiě)完整.Int Binsch(ElemType A ,int n,KeyType K)

35、int low=0;int high=n-1;while (low<=high)(int mid= ;if (K=Amid.key) return mid;查找成功,返回元素的下標(biāo)else if (K<mid.key);/在左子表上繼續(xù)查找else;/在右子表上繼續(xù)查找return -1;查找失敗,返回-16、 六、編寫(xiě)算法(共8分)HL是單鏈表的頭指針,試寫(xiě)出刪除頭結(jié)點(diǎn)的算法.ElemType DeleFront(LNode * & HL)模擬試卷三參考答案單項(xiàng)選擇題(每題2分,共20分)1.B2.A3.B 4.C 5.D 6.B 7.D二、填空題(每空8.A9.D10.

36、C1分,共26分)1. 1. 聯(lián)系 圖(或圖結(jié)構(gòu))2. 2.尾 首3. 3.top=04. 4. O (1) O (n)5. 5.128441086.6.33 7.7.6558.8.1519.9.32-110.1045-211.1151512.12637圖7有序 n-1后序序列后綴表達(dá)式(或逆波蘭式)2nn-1n+12i+12i+2(i-1)/2開(kāi)放定址法鏈接法快速歸并運(yùn)算題每題6分,共24分1.1. (1)(1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)(3 分)(2) 三兀組線性表的順序存儲(chǔ)表不如圖7不.bEd圖82. 2.如圖8所示.3. 3.DFS:B

37、FS:4. 4.拓樸排序?yàn)椋? 3 6 5 7 2 1四、四、閱讀算法每題7分,共14分1. 1.1判斷n是否是素?cái)?shù)或質(zhì)數(shù)（2） O ,n 2. 2. 功能為：從初始點(diǎn) vi出發(fā)廣度優(yōu)先搜索由鄰接表GL所表示的圖.5、 五、算法填空8分(low+high)/2high=mid-1low=mid+16、 六、編寫(xiě)算法(8分)ElemType DeleFront(LNode * & HL) (if (HL=NULL)cerr<<"空表"<<endl;exit(1);)LNode* p=HL;HL=HL->next;ElemType temp

38、=p->data;delete p;return temp;)模擬試卷四一、 一、單項(xiàng)選擇題每題 2分,共20分1. 1.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是線性結(jié)構(gòu)？A.有向圖B.棧C.二叉樹(shù)D. B樹(shù)2. 2.假設(shè)某鏈表最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn),那么采用存儲(chǔ)方式最節(jié)省時(shí)間.A.單鏈表B.雙鏈表C.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表D.單循環(huán)鏈表3.3.以下哪一個(gè)不是隊(duì)列的根本運(yùn)算？A.在隊(duì)列第i個(gè)元素之后插入一個(gè)元素C.判斷一個(gè)隊(duì)列是否為空B.從隊(duì)頭刪除一個(gè)元素D.讀取隊(duì)頭元素的值4.4. 字符A、B、C、D依次進(jìn)入一個(gè)棧,按出棧的先后順序組成不同的字符串,至多 可以組成個(gè)

39、不同的字符串？A.15B.14C.16D.215.5.由權(quán)值分別為4,7,6,2的葉子生成一棵哈夫曼樹(shù),它的帶權(quán)路徑長(zhǎng)度為A、B、C、D、E、A. 11B.37 C. 19 D. 53以下6-8題基于下面的表達(dá)：假設(shè)某二叉樹(shù)結(jié)點(diǎn)的中序遍歷的序列為F、6.G,6.后序遍歷的序列為B、D、C、A、F、那么該二叉樹(shù)結(jié)點(diǎn)的前序遍歷的序列為G、E..A. EC.7.A8.、G F、A、A、C B該二叉樹(shù)有.3B.2C D BD G F)個(gè)葉子.(B.D.).EE、A、GGA、C、F、DB、DF、B該二叉樹(shù)的按層遍歷的序列為C.5()D.4、A、CB. ED. E、G A、9.

40、(q,g,BDDDDBC、F、m, z, a),B、GF、.E、G F、A、C. E 、A、G C、10.設(shè)有關(guān)鍵碼序列的結(jié)果?A.C.1.N)2.3.卜面哪一個(gè)序列是從上述序列出發(fā)建的小根堆a(bǔ) , g ,g , m,mq,q, za, z填空題D.每空B. a,g , m g, m, a, 共26分)z,qq, z數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之間的的聯(lián)系時(shí),稱這種結(jié)構(gòu)為 一個(gè)廣義表中的元素分為 元素和.當(dāng)結(jié)點(diǎn)之間存在1對(duì)N 1:元素兩類.對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表,在表頭插入元素的時(shí)間復(fù)雜度為,在表尾插入元素的時(shí)間復(fù)雜度為4.4. 向一個(gè)由HS指向的鏈棧中插入一個(gè)結(jié)點(diǎn)時(shí)p時(shí),需要執(zhí)行的操

41、作是 個(gè)結(jié)點(diǎn)時(shí),需要執(zhí)行的操作是假設(shè)棧不空而且無(wú)需回收被刪除結(jié)點(diǎn).棧又稱為表,隊(duì)列又稱為在稀疏矩陣所對(duì)應(yīng)的三元組線性表中,每個(gè)三元組元素按表.為主序、為輔序的次序排列.7.右子樹(shù)皆非空的結(jié)點(diǎn), 設(shè)葉結(jié)點(diǎn)的個(gè)數(shù)為 K,7. 假設(shè)一棵二叉樹(shù)中只有葉子結(jié)點(diǎn)和左、那么左、右子樹(shù)皆非空的結(jié)點(diǎn)個(gè)數(shù)是8. 8. 以折半或二分查找方法從長(zhǎng)度為8的有序表中查找一個(gè)元素時(shí),平均查找長(zhǎng)度為.9. 9. 表示圖的三種常用的存儲(chǔ)結(jié)構(gòu)為、和10. 10.對(duì)于線T表(78, 4, 56, 30, 65)進(jìn)行散列存儲(chǔ)時(shí),假設(shè)選用 H (K) =K %5作為 散列函數(shù),那么散列地址為0的元素有 個(gè),散列地址為4的

42、有 個(gè).11. 11.在歸并排序中,進(jìn)行每趟D3并的時(shí)間復(fù)雜度為 ,整個(gè)排序過(guò)程的時(shí)間復(fù)雜 度為,空間復(fù)雜度為.12. 12.在n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)造出的所有二叉樹(shù)中,帶權(quán)路徑長(zhǎng)度最小的二叉樹(shù)稱為 . WPL 稱為.13. 13.在索引表中,假設(shè)一個(gè)索引項(xiàng)對(duì)應(yīng)主表的一個(gè)記錄,那么此索引為 索引, 假設(shè)對(duì)應(yīng)主表的假設(shè)干條記錄,那么稱此索引為 索引.3、 三、運(yùn)算題(每題 6分,共24分)1. 1.寫(xiě)出以下中綴表達(dá)式的后綴形式：(1) (1)3X/(Y-2H)+1(2) (2)2+X*(Y+3)2. 2.假定一棵二叉樹(shù)廣義表表示為a(b(c),d(e,f),分別寫(xiě)出對(duì)它進(jìn)行先序、中序、后序、按層遍歷

43、的結(jié)果.先序：中序：后序：按層：3. 3.一個(gè)無(wú)向圖的頂點(diǎn)集為a, b, c, d, e,其鄰接矩陣如下所示a01001b10010c00011d01101e_ 10110(1)畫(huà)出該圖的圖形；a出發(fā)進(jìn)行深度優(yōu)先遍歷和廣度優(yōu)先遍歷,V和邊集E分別為：寫(xiě)出相應(yīng)的遍歷序(2)根據(jù)鄰接矩陣從頂點(diǎn) 列.4. 4. 一個(gè)圖的頂點(diǎn)集V=0,1,2,3,4,5,6,7;E=(0,1)8,(0,2)5,(0,3)2,(1,5)6,(2,3)25,(2,4)13,(3,5)9,(3,6)10,(4,6)4,(5,7)20;根據(jù)普里姆算法從頂點(diǎn)0出發(fā)得到最小生成樹(shù),試寫(xiě)出在最小生成樹(shù)中依次得到的各條邊.4、 四、

44、閱讀算法(每題 7分,共14分)1. 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=2,5,8,22,15);for(i=0;i<5;i+) Push(S,ai);while(!StackEmpty(S) cout<<Pop(S)<<)該算法被調(diào)用后得到的輸出結(jié)果為：2. 2. int akm ( unsigned m, unsigned n ) if ( m = 0 ) return n+1;else if (

45、 n = 0 ) return akm ( m-1, 1 ); else return akm ( m-1, akm ( m, n-1 ) );)該函數(shù)執(zhí)行的功能是什么？5、 五、算法填空(共8分)二叉搜索樹(shù)的查找一俳遞歸算法 bool Find(BTreeNode* BST,ElemType& item) while(BST(!=NULL)if (item=) item=BST->data;查找成功return true;else if(item<BST->data) BST=BST->else BST=BST->/while return ;/查找失敗

46、6、 六、編寫(xiě)算法(共8分)用遞歸的算法編寫(xiě)出對(duì)存入在 an+1數(shù)組中的n個(gè)有序元素進(jìn)行二分(又稱折半)查找(假定a0單元不用)的程序.int halfsearch(SSTable *a, KeyType k,int low,int high)模擬試卷四參考答案1、 一、單項(xiàng)選擇題(每題2分,共20分)1.B 2,C 3.A 4.B 5.B 6.C 7.A 8.C 9.C 10.B2、 二、填空題(每空1分,共26分)1. 1.聯(lián)系樹(shù)(或樹(shù)結(jié)構(gòu))2. 2. 單 (子)表3. 3. O(n) O(1)4. 4. p->next=HS;HS=pHS=HS->next5. 5.先進(jìn)后出先

47、進(jìn)先出6. 6.行歹U7. 7. k-18. 8. 2.6259. 9.鄰接矩陣鄰接表邊集數(shù)組10. 10. 2 111. 11. O(n) O(nlog2n) O(n)12. 12.哈夫曼樹(shù)帶權(quán)路徑長(zhǎng)度13. 13.稠密 稀疏3、 運(yùn)算題每題6分,共24分1. 1.1 3 X * Y 2 H *- / 1+（2） 2 X Y 3 + * +2. 2.先序：a,b,c,d,e,f中序：c,b,a,e,d,f后序：c,b,e,f,d,a按層：a,b,d,c,e,f3. 3.1該圖的圖形如圖 9示：2深度優(yōu)先遍歷序列為：abdce廣度優(yōu)先遍歷序列為：abedc4. 4.普里姆：(0,3)2, (0

48、,2)5, (0,1)8, (1,5)6, (3,6)10, (6,4)4, (5,7)204、 四、閱讀算法每題 7分,共14分3. 3.15 22 8 5 2 10當(dāng)m = 0時(shí)當(dāng)m-: 0,n = 00寸當(dāng)m= 0,n = 0寸4. 4.該函數(shù)的功能是："1akn(inin) =：akn(im-1, 1)求:五、五、BST->data六、六、遞歸算法：akn(im-1, akn(m|n-1)算法填空(共8分,每一空2分)left right false編寫(xiě)算法(8分)int halfsearch(SSTable *a, KeyType k,int low,int high

49、) if (low>high)return 0;else int mid=(low+high)/2if EQ(k,amid.key) return mid;else if LT(k,amid.key) return halfsearch(a,k,low,mid-1); else return halfsearch(a,k,mid+1,high);)模擬試卷五一、單項(xiàng)選擇題每題 2分,共20分1. 1.棧和隊(duì)列的共同特點(diǎn)是.A.只允許在端點(diǎn)處插入和刪除元素B.都是先進(jìn)后出C.都是先進(jìn)先出D.沒(méi)有共同點(diǎn)2. 2.用鏈接方式存儲(chǔ)的隊(duì)列,在進(jìn)行插入運(yùn)算時(shí).A.僅修改頭指針B. 頭、尾指針都要修改

50、C.僅修改尾指針D. 頭、尾指針可能都要修改3. 3.以下數(shù)據(jù)結(jié)構(gòu)中哪一個(gè)是非線性結(jié)構(gòu)？()A.隊(duì)列B.棧C.線性表D.二叉樹(shù)4. 4.設(shè)有一個(gè)二維數(shù)組Amn,假設(shè)A00存放位置在644(i0), A22存放位置在676(10),每個(gè)元素占一個(gè)空間,問(wèn)A33(10)存放在什么位置？腳注(10)表示用10進(jìn)制表不.B. 678C. 692D. 6965. 5.樹(shù)最適合用來(lái)表示().A.有序數(shù)據(jù)元素C.元素之間具有分支層次關(guān)系的數(shù)據(jù)6. 6.二叉樹(shù)的第k層的結(jié)點(diǎn)數(shù)最多為().A . 2k-1B.2K+1C.2K-1B.無(wú)序數(shù)據(jù)元素D.元素之間無(wú)聯(lián)系的數(shù)據(jù)D. 2k-17. 7.假設(shè)有18個(gè)元素的有

51、序表存放在一維數(shù)組A19中,第一個(gè)元素放 A1中,現(xiàn)進(jìn)行二分查找,那么查找 A 3的比擬序列的下標(biāo)依次為()A. 1 , 2, 3B. 9, 5, 2, 3C. 9 , 5, 3D. 9 , 4, 2, 38. 8.對(duì)n個(gè)記錄的文件進(jìn)行快速排序,所需要的輔助存儲(chǔ)空間大致為A. O (1)B. O (n) C. O(1og2n)D. O (n2)9. 9.對(duì)于線T表(7, 34, 55, 25, 64, 46, 20, 10)進(jìn)行散列存儲(chǔ)時(shí),假設(shè)選用H ( K)=K %9作為散列函數(shù),那么散列地址為1的元素有()個(gè),A . 1 B . 2 C . 3 D . 410. 10.設(shè)有6個(gè)結(jié)點(diǎn)的無(wú)向圖

52、,該圖至少應(yīng)有()條邊才能保證是一個(gè)連通圖.A.5B.6C.7D.8二、填空題(每空1分,共26分)1. 1.通常從四個(gè)方面評(píng)價(jià)算法的質(zhì)量： 、和2. 2.一個(gè)算法的時(shí)間復(fù)雜度為(n3+n2log2n+14n)/n2,其數(shù)量級(jí)表示為 .3. 3.假定一棵樹(shù)的廣義表表示為 A(C, D(E, F,G), H(I,J),那么樹(shù)中所含的結(jié)點(diǎn)數(shù)為 個(gè),樹(shù)的深度為 ,樹(shù)的度為 .4. 4. 后綴算式9 2 3 +- 10 2 / -的值為 .中綴算式(3+4X) -2Y/3對(duì)應(yīng)的后綴算式為.5. 5. 假設(shè)用鏈表存儲(chǔ)一棵二叉樹(shù)時(shí),每個(gè)結(jié)點(diǎn)除數(shù)據(jù)域外,還有指向左孩子和右孩子的兩個(gè)指針.在這種存儲(chǔ)結(jié)構(gòu)中,n個(gè)結(jié)點(diǎn)的二叉樹(shù)共有 個(gè)指針域,其中有個(gè)指針域是存放了地址,有 個(gè)指針是空指針.6. 6. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖,在其對(duì)應(yīng)的鄰接表中,所含邊結(jié)點(diǎn)分別有 個(gè)和 個(gè).7. 7. AOV網(wǎng)是一種 的圖.8. 8.在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中,包含有 條邊,在一個(gè)具有 n個(gè)頂