數(shù)據(jù)結(jié)構(gòu)答疑2014

1、 數(shù)據(jù)結(jié)構(gòu)答疑數(shù)據(jù)結(jié)構(gòu)答疑鄭州大學(xué)信息管理學(xué)院鄭州大學(xué)信息管理學(xué)院徐愛琴徐愛琴一、考試方式 閉卷筆試二、考試的基本要求 本課程要求了解各種常用的數(shù)據(jù)結(jié)構(gòu)、各種數(shù)據(jù)結(jié)構(gòu)內(nèi)涵的邏輯關(guān)系及其在計(jì)算機(jī)中的存儲(chǔ)表示以及這些數(shù)據(jù)結(jié)構(gòu)上的運(yùn)算和實(shí)際的執(zhí)行算法。掌握線性表、棧、隊(duì)列的數(shù)據(jù)結(jié)構(gòu)及各種操作和算法實(shí)現(xiàn)，樹、圖的邏輯結(jié)構(gòu)及物理存儲(chǔ)，常用的排序和查找算法。三、考試題型及試卷結(jié)構(gòu) 試卷有選擇題占20%、是非題占20%、數(shù)據(jù)處理題占30%、編寫算法題占30%。四、例題解析 按照以上四種題型，選取部分例題，介紹解題思路及解答方法。（一）選擇題1采用線性鏈表表示一個(gè)向量時(shí)，要求占用的存儲(chǔ)空間地址( D )。 A

2、必須是連續(xù)的 B部分地址必須是連續(xù)的 C一定是不連續(xù)的 D可連續(xù)可不連續(xù)2在一個(gè)單鏈表中，若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入結(jié)點(diǎn)s，則執(zhí)行( D )。 As-link=p-link; p-link=s; Bp-link=s; s-link=q; Cp-link=s-link; s-link=p; Dq-link=s; s-link=p; 3設(shè)有兩個(gè)串t和p，求p在t中首次出現(xiàn)的位置的運(yùn)算叫做( B )。 A求子串 B模式匹配 C串替換 D串連接 4將一個(gè)遞歸算法改為對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用( A )。 A棧 B隊(duì)列 C循環(huán)隊(duì)列 D優(yōu)先隊(duì)列 5在循環(huán)隊(duì)列中用數(shù)組A0.m-1存

3、放隊(duì)列元素，其隊(duì)頭和隊(duì)尾指針?lè)謩e為front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是( D )。 A(front-rear+1)%m B(rear-front+1)%m C(front-rear+m)%m D(rear-front+m)%m 6在一個(gè)單鏈表HL中，若要在指針q所指結(jié)點(diǎn)的后面插入一個(gè)由指針p所指向的結(jié)點(diǎn)，則執(zhí)行（ D ）。 Aq一next=p一next；p一next=q； Bp一next=q一next；q=p； Cq一next=p；p一next=q； Dp一next=q一next；q一next=p； 7向二叉排序樹中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（ B ）。 AO（1） BO（1

4、og2n） CO（n） D O（nlog2n） 8在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通所有頂點(diǎn)則至少需要（ D ）條邊。 An Bn*(n+1)/2 Cn*n Dn-19假定一棵完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)為50，則它的深度為（ D ）。 A3 B4 C5 D610隊(duì)列的另外一個(gè)別稱是（ A ） A先進(jìn)先出表 B后進(jìn)先出表 C鏈隊(duì)列 D順序隊(duì)列11一個(gè)算法的實(shí)現(xiàn)依賴于采用的（B ）A邏輯結(jié)構(gòu) B存儲(chǔ)結(jié)構(gòu) C時(shí)間復(fù)雜度 D空間復(fù)雜度 12一個(gè)數(shù)組第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第五個(gè)元素的地址是（ B ）A110 B108 C100 D12013一個(gè)棧的入棧序列是a,b,c,d,e，

5、則棧的不可能的輸出序列是（ C ）Aedcba Bdecba Cdceab Dabcde14判斷一個(gè)循環(huán)隊(duì)列QU（最多元素為maxsize）為空的條件是（ A ）AQUfrontQUrearBQUfront！QUrearCQUfront（QUrear1）maxsizeDQUfront?。≦Urear1）maxsize15如果一棵二叉樹任意一層的結(jié)點(diǎn)數(shù)都達(dá)到該層的最多數(shù),該二叉樹稱為（ C ）A平衡二叉樹 B二叉排序樹 C滿二叉樹 D完全二叉樹16在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表中，刪除第i個(gè)元素（1in）時(shí)，需要從前向后依次前移（ A ）個(gè)元素。A n-i B n-i+1 C n-i-1 D

6、i17一個(gè)深度為k的滿二叉樹有（ B ）個(gè)結(jié)點(diǎn)A2k B2k1 C2k-1 D2k118樹最適合用來(lái)表示（ C ）A有序數(shù)據(jù)元素B無(wú)序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無(wú)聯(lián)系的數(shù)據(jù)19對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是（ D ）An B(n1)2 Cn1 Dn220排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為（ D ）A希爾排序 B氣泡排序 C插入排序 D選擇排序（二）是非題1. 直接插入排序方法是穩(wěn)定的。（ ）2. 若已知一個(gè)數(shù)組的起始存儲(chǔ)地址和維數(shù)以及每維的上、下界，且已知每個(gè)數(shù)組元素所占有的單

7、元數(shù)，則不管按照行優(yōu)先還是列優(yōu)先，元素aij 的存儲(chǔ)地址是一樣的。（ ）3. 順序表只能用順序方式來(lái)查詢。（ ）4. 將一個(gè)森林或者一棵樹轉(zhuǎn)換成一棵二叉樹后，得到的二叉樹不惟一。（ ）5. 將一棵樹轉(zhuǎn)換成一棵二叉樹之后，二叉樹的根結(jié)點(diǎn)的右子樹必定為空。（ ）6.二叉樹的前序遍歷序列中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面。 （ ）7二分查找和二叉排序樹的時(shí)間性能是相同的。（ ）8可以對(duì)鏈表進(jìn)行二分法排序。（ ）9無(wú)向完全圖的頂點(diǎn)數(shù)為n，則邊的數(shù)目為n*n。（ ）10二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。（ ）（三）數(shù)據(jù)處理題1.設(shè)給定權(quán)集w2，3，

8、4，7，8，9，試構(gòu)造關(guān)于w的一棵哈夫曼樹。181599785423332.請(qǐng)給出上圖的先序和后序遍歷結(jié)點(diǎn)序列。ABDEHCFIGJDHEBIFJGCAFBADEGHIJC3. 請(qǐng)給出上圖的二叉樹形態(tài)。ABDEFCGIHJABDEFCGIHJ4.寫出下圖的拓?fù)湫蛄?A C B D E FABCDEF5.使用普里姆算法（或克魯斯卡爾算法）構(gòu)造出下圖的一棵最小生成樹。12435 616355、2664512435 66.設(shè)下圖以鄰接矩陣形式存儲(chǔ)，指出從頂點(diǎn)1出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列。 深度優(yōu)先遍歷和廣度優(yōu)先遍歷序列均是12345124537.已知一關(guān)鍵字序列為70，83，100，65，

9、10，32，7，9，請(qǐng)給出采用直接插入排序法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。初始：（70），83，100，65，10，32，7，91趟：（70，83），100，65，10，32，7，92趟：（70，83，100），65，10，32，7，93趟：（65，70，83，100），10，32，7，94趟：（10，65，70，83，100），32，7，95趟：（10，32，65，70，83，100），7，96趟：（7，10，32，65，70，83，100），97趟：（7，9，10，32，65，70，83，100）8.已知一關(guān)鍵字序列為17，18，60，40，7，32，73，65，85，請(qǐng)給出采用直接

10、氣泡排序法對(duì)該序列作升序排序時(shí)的每一趟的結(jié)果。初始：17，18，60，40，7，32，73，65，851趟：17，18，40，7，32，60，65，73，852趟：17，18，7，32，40，60，65，73，853趟：17，7，18，32，40，60，65，73，854趟：7，17，18，32，40，60，65，73，855趟：7，17，18，32，40，60，65，73，85第5趟無(wú)元素交換，則排序結(jié)束。9.已知有一關(guān)鍵字序列為13，15，6，10，20，8，3, 19，現(xiàn)采用簡(jiǎn)單選擇排序的方法進(jìn)行排序（按照升序排列），請(qǐng)給出每一趟排序的結(jié)果。 (0) 13 15 6 10 20 8 3

11、19 (1) 3 15 6 10 20 8 13 19 (2) 3 6 15 10 20 8 13 19 (3) 3 6 8 10 20 15 13 19 (4) 3 6 8 10 20 15 13 19 (5) 3 6 8 10 13 15 20 19 (6) 3 6 8 10 13 15 20 19 (7) 3 6 8 10 13 15 19 20 （四）編寫算法1.已知一個(gè)順序表A，其中的元素按值非遞減有序排列，編寫一個(gè)函數(shù)插入一個(gè)元素x后保持該順序表仍按非遞減有序排列。void insert(listtp A, int n, x) int i, j; if(x=An-1) An=x e

12、lse i=0; while(x=Ai) i+; for(j=n-1; j=i; j-) Aj+1=Aj; Ai=x; n+;2.編寫一個(gè)函數(shù)將一個(gè)順序表A（有n個(gè)元素，且任何元素均不為0）分拆成兩個(gè)順序表，使A中大于0的元素存放在B中，小于0的元素存放在C中。void ret(listtp A, int n) listtp B, C; int p, q; p=0;q=0; for(int i=0; i0) Bp=Ai; p+; else Cq=Ai; q+; 3.編寫一個(gè)鏈接兩個(gè)單鏈表的算法。設(shè)有鏈表A和B，B鏈表鏈接在A鏈表之后，產(chǎn)生新鏈表C，原鏈表不破壞。linklist *merge(

13、linklist *headA,linklist *headB) linklist *headC; headC=(struct lnode *)malloc(sizeof(struct lnode); headC-next=null; lnode *p,*q; p=headA-next; r=headC; while(p!=null) s=(struct lnode *)malloc(sizeof(struct lnode); s-data=p-data; s-next=null; r-next=s; r=s; p=p-next; p=headB-next; while(p!=null) s=

14、(struct lnode *)malloc(sizeof(struct lnode); s-data=p-data; s-next=null; r-next=s; r=s； p=p-next; return(headC); 4.編寫將一單鏈表逆置的算法。 linklist * invert (linklist *head) list * p , * q, * r; p =head-next ; q =p -next; while (q !=null) r = q - next ; q - next=head-next ; head-next =q ; q = r ;r=r-next; p -

15、next =null ; return head;5.設(shè)計(jì)算法，將順序串r中所有字符按相反的次序逆置。 void invert(SqString &r) int i; char tmp; for (i=0;i(r.len/2);i+) tmp=r.chi; r.chi=r.chr.len-i-1; r.chr.len-i-1=tmp; 6.設(shè)計(jì)算法，從順序串r中刪除其值等于ch的所有字符。 void delall(SqString &r,char ch) int i,j; for (i=0;ir.len;i+) if (r.chi=ch) for (j=i;jlchild); num2=nodes(b-rchild); return(num1+num2+1); 8.設(shè)計(jì)一個(gè)算法，求出給定二叉排序樹中最小和最大的關(guān)鍵字。 KeyType MinKey(BSTNode