數(shù)據(jù)結(jié)構(gòu)馬睿孫麗云習(xí)題答案（精編版）

1、第1章緒論一、選擇題1、c2 、c3 、c4 、d5 、b6 、c二、判斷題1×2 ×3 ×4×5 6 × 三、簡(jiǎn)答題（略）四、算法分析題：1. 分析下列程序段中帶標(biāo)號(hào)“#”語(yǔ)句的執(zhí)行頻度（n 為正整數(shù)）。（ 1）頻度： n ，時(shí)間復(fù)雜度： o（ n）（ 2）頻度： 1 ，時(shí)間復(fù)雜度： o（ 1）22（ 3）頻度： n，時(shí)間復(fù)雜度： o（n ）（ 4）頻度： n/2-1，時(shí)間復(fù)雜度： o（ n）（ 5）頻度： 11002. 寫出下列各程序段關(guān)于n 的時(shí)間復(fù)雜度。（ 1） o（ log 3n）2（ 2） o（ n ）2（ 3） o（ n ）第 2

2、 章 線性表一、選擇題1、a2.b3.c4. d5.c6.b7. a8.b9.b10.c二、填空題1. 、線性表2、前驅(qū)，后繼3、p->next; s->data; t 4、q->next5、head->next = null 6、p->next, s7、p->next != p 8、 o(1),o(n)第 3 章 棧和隊(duì)列一、選擇題1、c2.c3.d4.c5.c6.d7.c8.b9.b10. d11.a12.b二、填空題1. 、 n-1 2、o(n) 3、135424、2xy+1x-/*5、36、a2, a4, a 1, a2, 27、先進(jìn)后出，加1， 減

3、 18、滿，空， n9、線性結(jié)構(gòu)10、4三、判斷題1. 、錯(cuò)2、錯(cuò) 3、對(duì)4、錯(cuò)5、對(duì)6、錯(cuò)7、錯(cuò)四、解答題4、列車進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，開出車站有14可能的順序：abcd; abdcadcbacdb, acbdbdca,bcda, bcadbacd, badccdba,cbda, cbad,dcba列車進(jìn)入一個(gè)隊(duì)列式結(jié)構(gòu)的車站，開出車站有1可能的順序： abcd5、6, 247、staxy 8、char9、第一個(gè)循環(huán)：隊(duì)列q中的元素依次出隊(duì)，出隊(duì)后即進(jìn)棧s第二個(gè)循環(huán)：棧s中的元素依次出棧，出棧后即進(jìn)入隊(duì)列q第 4 章 串一、選擇題1、a2 、d3 、c4 、c5 、d 二、簡(jiǎn)答題1、含零個(gè)

4、字符的串稱為空串，用表示，串的長(zhǎng)度為0。而空格串是由一個(gè)或多個(gè)空格組成的串，串的長(zhǎng)度為所含空格的個(gè)數(shù)。由串中任意連續(xù)字符組成的子序列稱為該串的子串。包含子串的串相應(yīng)地被稱為主串。假如一個(gè)串s=“a0a1 a2an-1 ” (n 0) ，其中： s 為串名，用雙引號(hào)括起來(lái)的內(nèi)容為串的值，雙引號(hào)本身不是串的值。2、當(dāng)且僅當(dāng)兩個(gè)串的長(zhǎng)度相等并且各個(gè)對(duì)應(yīng)位置上的字符都相同時(shí)，兩個(gè)串才相等。3、19，7， good， e， 0， 3，” i am a goodteacher ”，” a goodyestea”4、j0123456模式串a(chǎn)bcabaanextj-1000121三、算法題1、void ass

5、ign(string *s, string t)/s為串指針類型的參數(shù)/將串變量 t 的值賦給串變量s inti;for(i=0;i<t.curlen;i+)s.stri=t.stri;s.curlen=t.curlen;2、略3、略4、lstring *insert(lstring *s, int pos, lstring *t)/在串 s 的第 pos 字符之前插入串 tintk;lstring *str_temp,*p1=s->next,*p2=t->next,*q,*r;str_temp=(lstring*) malloc (sizeof(lstring);str_t

6、emp->next=null;r=str_temp;if(pos<0 | | pos>s.curlen)/參數(shù)不正確時(shí)返回空串returnstr_temp;for(k=0;k<pos;k+) /將 s 的前 pos-1 個(gè)結(jié)點(diǎn)復(fù)制到str_tempq=(lstring*) malloc (sizeof(lstring);q->str=p1->str;q->next=null;r->next=q;r=q;p1=p1->next;while (p2!=null) q=(lstring*) malloc (sizeof(lstring);q-&g

7、t;str=p2->str;q->next=null;r->next=q;r=q;p2=p2->next;while (p1!=null) /將*p1 及其后的結(jié)點(diǎn)復(fù)制到str_tempq=(lstring*) malloc (sizeof(lstring);q->str=p1->str;q->next=null;r->next=q;r=q;p1=p1->next;returnstr_temp;5、lstring*delete(lstring *s, int pos, int len)/從串 s 中刪去從第 pos 個(gè)字符起長(zhǎng)度為len的子

8、串intk;lstring*str_temp,*p=s->next,*q ,*r;str_temp=(lstring*) malloc (sizeof(lstring);str_temp->next=null;r=str_temp;if (pos<0 | | pos>length(s)-1 | | len<0 | | pos+len-1>length(s)returnstr_temp;/參 數(shù) 不 正 確 時(shí) 返 回 空 串 for(k=0;k<pos;k+） /將 s 的前 pos-1個(gè)字符復(fù)制到str_temp q=(lstring*) mallo

9、c (sizeof(lstring);q->str=p->str;q->next=null;r->next=q;r=q;p=p->next;for(k=0;k<len;k+)/p沿 next跳 len個(gè)結(jié)點(diǎn)p=p->next;while(p!=null) /將*p 及其后的結(jié)點(diǎn)復(fù)制到str_tempq=(lstring*) malloc (sizeof(lstring);q->str=p->str;q->next=null;r->next=q;r=q;p=p->next;returnstr_temp;第 5 章數(shù)組和廣義表

10、一、選擇題1、 c2、 a3、a4 、b5 、b6 、c7 、b8 、c9 、c10 、b二、填空題：1、 線性結(jié)構(gòu)順序結(jié)構(gòu)2、 以行為主序以列為主序3、（ d1-c1+1 ）* （ d2-c2+1 ）4、326【解析】采用列主序時(shí)，loc（a612） =loc（ a00+（ 12*10+6 ） *1=326 5、答: 9136、42【解析】a85前有 8 行，第 0 行 1 個(gè)元素，第1 行 2 個(gè)元素，第7 行 8 個(gè)元素，共（ 1+8） *8/2=36個(gè)元素，第 8 行前有 5 個(gè)元素，所以a85的地址為36+5+1=42。7、答: k=i(i-1)/2+j ,當(dāng) i j時(shí) k=n(n+

11、1)/2+1 ,當(dāng) i<j時(shí)8、22109、（ x,y,z）10、gettail(gettail(gettail(gethead(gettail(ls) 11、5 ?3三、操作題1、設(shè)數(shù)組元素aij存放在起始地址為loc（ i, j） 的存儲(chǔ)單元中。 loc（ 2, 2） = loc（ 0, 0） + 2 * n + 2 = 644 + 2 * n + 2 = 676. n =（ 676 - 2 - 644） / 2 = 15 loc（ 3, 3） = loc（ 0, 0） + 3 * 15 + 3 = 644 + 45 + 3 = 692.2、（ 1） 數(shù)組 b共有 12 + 3 +?

12、 + n=（ n+1） *n / 2個(gè)元素。（ 2） 只存下三角部分時(shí)，若 i ? j ，則數(shù)組元素 aij 前面有 i-1 行（ 1?i-1 ， 第 0 行第 0 列不算），第 1 行有 1 個(gè)元素，第 2 行有 2 個(gè)元素， ?，第 i-1 行有 i-1 個(gè)元素。在第 i 行中，第 j 號(hào)元素排在第 j 個(gè)元素位置，因此，數(shù)組元素aij在數(shù)組 b中的存放位置為：1 + 2 + ? +（ i-1 ） + j =（ i-1）*i / 2 + j若 i < j，數(shù)組元素aij在數(shù)組 b 中沒(méi)有存放，可以找它的對(duì)稱元素aji。在數(shù)組 b 的第（j-1）*j / 2 + i位置中找到。如果第

13、0 行第 0 列也計(jì)入，數(shù)組b從 0 號(hào)位置開始存放，則數(shù)組元素aij在數(shù)組 b 中的存放位置可以改為：當(dāng) i ? j時(shí)， = i*（ i+1 ） / 2 + j當(dāng) i < j時(shí)， = j*（ j+1 ） / 2 + i3、（1） head（2） head（3） head（4） head（ tail（ tail（ head （ tail（ head （ tail（ head （ tail（ l1）（ l2）（ tail（ tail） ） ）（ head （ l3） ） ） ） ）（ l4） ） ） ）（5） head（ tail（ head（ l5） ） ）（6） head（ head

14、（ tail（ head （ tail（ l6） ） ） ） ）4、由于線性表中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)稀疏矩陣的一個(gè)非零元素，其中包括3 個(gè)字段， 分別為該元素的行下標(biāo)、列下標(biāo)和值，結(jié)點(diǎn)間的次序按矩陣的行優(yōu)先順序排列，這個(gè)線性表用順序的方法存儲(chǔ)在連續(xù)的存儲(chǔ)區(qū)，則對(duì)應(yīng)的三元組為其十字鏈表形式為：5、6、l=(a,(b,c),(d,(e)四、算法題1、【算法分析】從前向后找零元素ai，從后向前找非零元素aj，將 ai與 aj交換?！舅惴ㄔ创a】void move(int a,int n)int i=0,j=n-1;int temp;while(i<j)while(ai!=0)i+;while(aj=

15、0)j-;if(i<j)temp=ai;ai=aj;aj=temp;2、【算法分析】為保證算法的時(shí)間復(fù)雜度為o（m+n），即需要對(duì)數(shù)組a和 b的數(shù)據(jù)元素僅掃描一次就能生成c數(shù)組，我們可采用設(shè)三個(gè)下標(biāo)指針i,j,k初始時(shí)分別指向 a數(shù)組的最后一個(gè)元素（a 數(shù)組的最大值）、b數(shù)組的第一個(gè)元素（b 數(shù)組的最大值）、c數(shù)組將存放最大值的位置，然后比較a與 b數(shù)組的最大值大者放c數(shù)組 k 所指單元；在上述比較中若a 數(shù)組 i所指單元數(shù)大，則送完后i前移，否則 j所指單元數(shù)送完后j后移，同時(shí)k 前移，直到把a(bǔ) 與 b 數(shù)組的所有元素掃描完。【算法源代碼】#define m 3#define n 4v

16、oidmerge(inta,int b,intc)inti,j,k;i=m-1;j=0;k=m+n-1;while(i>=0)&&(j<=n-1)if(ai>bj)ck=ai; i-;elseck=bj; j+; k-; while(i>=0) ck=ai;i-;k-;while(j<=n-1)ck=bj;j+;k-; 3、【算法分析】 三元組表示中要求按行的順序存放，所有轉(zhuǎn)置過(guò)程不能直接將行下標(biāo)和列下標(biāo)轉(zhuǎn)換，還必須使得列按順序存放。因此在a 中首先找出第一列中的所有元素，它們是轉(zhuǎn)置矩陣中第一行非0 元素，并把它們依次放在轉(zhuǎn)置矩陣三元組數(shù)組b 中；

17、然后依次找出第二列中的所有元素，把它們依次放在數(shù)組b 中；按照同樣的方法逐列進(jìn)行，直到找出第n 列的所有元素，并把它們依次放在數(shù)組b 中。【算法源代碼】void transpose(tsmatrix a,tsmatrix *b)/*a是稀疏矩陣的三元組形式，b 是存放 a 的轉(zhuǎn)置矩陣的三元組數(shù)組*/int i,j,k;b->mu=a.nu;b->nu=a.mu;b->tu=a.tu;if(b->tu>0)j=1;for(k=1;k<=a.nu;k+)for(i=1;i<=a.tu;i+)if(a.datai.col=k)b->dataj.row=

18、a.datai.col;b->dataj.col=a.datai.row;b->dataj.e=a.datai.e;j+;4、【算法分析】在求廣義表深度的遞歸算法中，若結(jié)點(diǎn)為原子則深度為0，若是空表深度為 1，否則返回頭指針與尾指針?biāo)笍V義表的深度最大值?！舅惴ㄔ创a】int glist_getdeph(glist l)int m,n;if(!l->tag) return 0;else if(!l) return 1;m=glist_getdeph(l->ptr.hp)+1;n=glist_getdeph(l->ptr.tp);return m>n?n:n;

19、第 6 章 樹一選擇題1、b2 、a3 、b4 、a5 、c6 、ca7、b8 、b9 、d10 、b11、b12 、b13 、b14 、a15 、c16 、d17 、a18 、a19 、c20 、d二填空題1 1前驅(qū)2一個(gè)前驅(qū)結(jié)點(diǎn)3后繼4后繼2.n-13.n0=n2 +14.1 22 103 115.1 a2 d g f3 b e4 a c5 b6 a c e7右8左9 210 46. 2507. 18. 2n0-19. 1 d2 f10. 1 geacbdf 2 111. 1 inordertraverse (t->left)2 printf(t->data)3 inorder

20、traverse (t->right)c。2n12. 1nn1三判斷題1×2×34×5×67×89×10四操作題1(1)(3)(2)gcabfed(4)(5)(6)23(1) 所有結(jié)點(diǎn)均沒(méi)有左孩子的二叉樹。(2) 所有結(jié)點(diǎn)均沒(méi)有右孩子的二叉樹(3) 只有一個(gè)根結(jié)點(diǎn)的二叉樹4. 證明：當(dāng) n=1 時(shí)，前序序列和中序序列均只有一個(gè)元素且相同，即為根，由此唯一地確定了這顆二叉樹。假設(shè) n<m-1 時(shí)，結(jié)論成立，現(xiàn)證明當(dāng)n=m時(shí)也成立。設(shè)前序序列為： a1 ， a2， am，中序序列為： b1 ，b2， bm。因?yàn)榍靶蛐蛄杏汕靶虮?/p>

21、歷得到，則a1 為根結(jié)點(diǎn)元素；又中序序列由中序遍歷得到，則在中序序列中必能找到和a1 相同的元素并設(shè)為bj (1 j m), 由此可得 b 1， bj-1 為左子樹的中序序列， b j+1， bm 為右子樹的中序序列。(1) 若 j=1 即 b1 為根，此時(shí)二叉樹的左子樹為空， a2 ， ， am 即為右子樹的前序序列， b 2 ， ， bm 即為右子樹的中序序列，右子樹的結(jié)點(diǎn)數(shù)為 m-1，由此，這兩個(gè)序列唯一確定了右子樹，也唯一確定了二叉樹。(2) 若 j=m 即 bm為根，此時(shí)二叉樹的右子樹為空，a2， am 即為左子樹的前序序列， b2 ， bm 即為左子樹的中序序列，同（1），這兩個(gè)序

22、列唯一確定了左子樹，也唯一確定了二叉樹。(3) 2j m-1，則子序列 a2 ， aj 和 b 1， bj-1 分別為左子樹的前序序列和中序序列，這兩個(gè)序列唯一確定了左子樹；子序列 a j+1， am 和 b j+1， bm 分別為右子樹的前序序列和中序序列，這兩個(gè)序列唯一確定了右子樹；由此，證明了知道一棵二叉樹的前序序列和中序序列，就能唯一地確定一棵二叉樹。56(a)(b)(c)(d)(e)7wpl=1*5+3*5+5*4+9*3+16*2+20*1=1198波蘭式： -+a*b-cd/ef五算法設(shè)計(jì)題/-二叉樹的二叉鏈表存儲(chǔ)表示-typedef struct bitnodetelemtyp

23、e data;struct bitnode *lchild,*rchild;bitree;1int nodes(bitree bt) /*求以 bt為根的二叉樹中度為1 的結(jié)點(diǎn)數(shù)目 */if(bt=null)return 0;/*bt為空時(shí)，結(jié)點(diǎn)數(shù)為0*/else if (bt->lchild=null ) && (bt->rchild=null )return 0; /*只有根節(jié)點(diǎn)時(shí)，結(jié)點(diǎn)數(shù)為0*/ else if (bt->lchild=null ) | (bt->rchild=null )return (1+nodes(bt->lchild)

24、+nodes(bt->rchild);/* 返回當(dāng)前根節(jié)點(diǎn)和左或右子樹中滿足條件的節(jié)點(diǎn)數(shù)目*/else return (nodes(bt->lchild)+nodes(bt->rchild);/* 返回左右子樹中滿足條件的節(jié)點(diǎn)數(shù)目*/nodes2void leafpath(bitree t, int num)/*求二叉樹根結(jié)點(diǎn)t 到所有葉子結(jié)點(diǎn)的路徑*/* 用數(shù)組 path存儲(chǔ)路徑（不包括t 在內(nèi)），其中已有的元素個(gè)數(shù)為num，其初值為 0*/bitree p;int top,i;if (t=null)/*如果二叉樹為空，則給出相應(yīng)信息，算法結(jié)束*/printf("

25、二叉樹為空 !"); return;if (t->lchild=null && t->rchild=null)printpath(path,t,num);/*輸出路徑 */elsepathnum+1=t; /*將 t 放到路徑中 */leafpath(t->lchild,num+1);leafpath(t->rchild,num+1);其中 printpath函數(shù)代碼如下：void printpath(bitnode *path, bitree t, int num)printf("%c：",t->data);for(

26、int i=1;i<=num;i+) printf("%c ",pathi->data);printf("%cn",t->data);3void preordertraverse(bitree t, int high )/*設(shè)二叉樹的根指針為t， t 所指結(jié)點(diǎn)的層次為high */if(t)printf("(%c, %d)",t->data,high);preordertraverse(t->lchild, high+1);preordertraverse(t->rchild, high+1);4b

27、itree change(bitree t)/*二叉樹左右子樹交換遞歸算法*/ bitree p;if(t!=null)if(t->lchild!=null|t->rchild!=null)p=(bitree)malloc(sizeof(bitnode);p->data=t->data;p->rchild=null;p->lchild=t->lchild;t->lchild=t->rchild;t->rchild=p->lchild;t->lchild=change(t->lchild);t->rchild=c

28、hange(t->rchild);return t;5bitnode *node(bitree bt)/*求二叉樹 t 的后序序列的第一個(gè)結(jié)點(diǎn)的指針，采用非遞歸算法*/ stackelemtype stackbitree_max_size;/*定義順序棧 */bitree p;int top;top = -1;/*棧初始化 */p=bt;while(p)/*二叉樹非空，根結(jié)點(diǎn)及其tag 標(biāo)記 0 一同入棧，然后遍歷其左子樹 */top+;stacktop.t=p;p=p->lchild;if(top != -1) return stacktop.t;else return null

29、;6bithrnode *preorder_next(bithrnode *p) /在先序后繼線索二叉樹中查找結(jié)點(diǎn)p 的先序后繼，并返回指針if(p->ltag=0) return p->lchild;else return p->rchild;/preorder_nextvoid preordertraverse_thr(bithrtree t)bithrnode *p;p=t;while(p!=null)visit(p->data);p=preorder_next(t);7typedef char telemtype;/-二叉樹的二叉鏈表存儲(chǔ)表示-typedef s

30、truct bitnodetelemtype data;struct bitnode *lchild,*rchild;*bitree;typedef struct qnodebitree t;struct qnode *next;linkqlist;typedef structlinkqlist *front,*rear;linkqueue;void initlinkqueue(linkqueue *q)/ 初始化廣度優(yōu)先遍歷算法中用到的鏈隊(duì)列q->front=malloc(sizeof(linkqlist);(q->front)->next=null;q->rear=

31、q->front;int emptylinkqueue(linkqueue *q) /判隊(duì)空？int v;if(q->front=q->rear)v=1;elsev=0;return v;void enlinkqueue(linkqueue *q,bitree t) /元素入隊(duì)列(q->rear)->next=malloc(sizeof(linkqlist);q->rear=(q->rear)->next;(q->rear)->t=t;(q->rear)->next=null;bitree dellinkqueue(lin

32、kqueue *q) /刪除隊(duì)頭元素linkqlist *p;bitree v;if(emptylinkqueue(q)printf("隊(duì)列空 .n");v=0;elsep=(q->front)->next;(q->front)->next=p->next;if(p->next=null) q->rear=q->front;v=p->t;free(p);return v;void visite(linkqueue *q, bitree p)if(p!=null)printf("%c",p->da

33、ta);enlinkqueue(q,p);void level_traverse(bitree t)/*按層次遍歷二叉樹*/linkqueue que,*q;bitree p;q=&que;initlinkqueue(q);if(t!=null)visite(q,t);while(!emptylinkqueue(q)p=dellinkqueue(q);visite(q,p->lchild);visite(q,p->rchild);printf("the pointer which points at the last node is %xn",p);/*

34、 給出離根結(jié)點(diǎn)最遠(yuǎn)的一個(gè)結(jié)點(diǎn)（即最后一個(gè)出隊(duì)的結(jié)點(diǎn)）的指針*/8intnode(bitreet)/*求以孩子兄弟鏈表存儲(chǔ)的樹或森林t 中的結(jié)點(diǎn)數(shù)，并通過(guò)函數(shù)值返回*/int count;bitree t1;if(t =null) return 0;/*bt為空時(shí)，結(jié)點(diǎn)數(shù)為0*/else if(t->firstchild =null) return 1;else count=0; t1=t->firstchild;while(t1) count=cout+node(t1);t1=t1->nextsibling?;return count?;9inthigh(bitreet)/*

35、求以孩子兄弟鏈表存儲(chǔ)的樹或森林t 的高度，并通過(guò)函數(shù)值返回*/int h1,h2;bitree t1;if(t =null) return 0;/*bt為空時(shí)，結(jié)點(diǎn)數(shù)為0*/ else h1=high(t->firstchild)+1;h2=high(t->nextsibling);return h1>h2? h1:h2;10char pred,midd; /前序序列和中序序列已經(jīng)分別儲(chǔ)存在數(shù)組pre 和 mid 中bitree build_sub(int pre_start,int pre_end,int mid_start,int mid_end)/由子樹的前序和中序序列

36、建立其二叉鏈表 bitree sroot,lroot,rroot;sroot=(bitnode*)malloc(sizeof(bitnode); /建根sroot->data=prepre_start;for(i=mid_start;midi!=sroot->data;i+); /在中序序列中查找子樹根leftlen=i-mid_start;rightlen=mid_end-i; /計(jì)算左右子樹的大小if(leftlen)lroot=build_sub(pre_start+1,pre_start+leftlen,mid_start,mid_start+leftle n-1);sro

37、ot->lchild=lroot; /建左子樹 , 注意參數(shù)表的計(jì)算if(rightlen)rroot=build_sub(pre_end-rightlen+1,pre_end,mid_end-rightlen+1,mid_end);sroot->rchild=rroot; /建右子樹 , 注意參數(shù)表的計(jì)算return sroot; /返回子樹根/build_submain().build_sub(1,n,1,n); /初始調(diào)用參數(shù) ,n為樹結(jié)點(diǎn)總數(shù).分析: 本算法利用了這樣一個(gè)性質(zhì), 即一棵子樹在前序和中序序列中所占的位置總是連續(xù)的 . 因此, 就可以用起始下標(biāo)和終止下標(biāo)來(lái)確定一

38、棵子樹.pre_start,pre_end,mid_start和 mid_end 分別指示子樹在前序子序列里的起始下標(biāo), 終止下標(biāo) , 和在中序子序列里的起始和終止下標(biāo).第 7 章 圖一、選擇題1b2 b3 b 和 c4 d和 e5 c6 d7 a8 a9 d10 b二、填空題1. 1n(n-1)2n(n-2)/23n-12. 1abcdfe2abcefd3. 1按深度2按廣度4. 極大5. 圖本身6. 主對(duì)角線7.1i2j8. 1 n-12大于 n-13小于 n-19. 2010. 1 n+2e22e3n11. 1 n+e2e3n12. 無(wú)環(huán)三、判斷題1×2 3 4×5

39、×6 × 7× 8× 四、（略）五、（略）第 8 章 查找一、選擇題1、c2 、b3 、a4、c5 、c6 、d7 、b8 、b9 、b10 、d11、c12 、c13 、d14 、d15 、d16 、c17 、a18 、b19 、d20 、b二、判斷題1. 【答案】錯(cuò)誤【分析】順序查找并沒(méi)有假設(shè)數(shù)有序或者無(wú)序，因此有序或無(wú)序?qū)ζ骄檎议L(zhǎng)度沒(méi)有影響。2. 【答案】錯(cuò)誤3. 【答案】正確4. 【答案】錯(cuò)誤【分析】鏈表表示的有序表不能用折半查找法查找。5. 【答案】錯(cuò)誤6. 【答案】錯(cuò)誤【分析】最優(yōu)二叉樹是靜態(tài)樹表，avl是動(dòng)態(tài)樹表，二者范圍不同。7【答案】

40、正確8. 【答案】正確9. 【答案】正確10. 【答案】正確11. 【答案】錯(cuò)誤【分析】除非被刪除的結(jié)點(diǎn)是葉子結(jié)點(diǎn)，否則刪除后再插入同一結(jié)點(diǎn)得到的二叉排序樹與原來(lái)的二叉排序樹不同。12. 【答案】錯(cuò)誤13. 【答案】錯(cuò)誤14. 【答案】錯(cuò)誤15. 【答案】正確16. 【答案】正確17. 【答案】錯(cuò)誤【分析】越小，只能說(shuō)發(fā)生沖突的可能性越小，但依然有可能發(fā)生沖突。18. 【答案】正確19. 【答案】正確20. 【答案】正確三、填空題1. 【分析】 最優(yōu)二叉樹是對(duì)葉子結(jié)點(diǎn)帶權(quán)平均查找路徑長(zhǎng)度最小的樹，最優(yōu)查找樹是對(duì)所有結(jié)點(diǎn)帶權(quán)查找路徑長(zhǎng)度最小的樹，構(gòu)造這兩種樹均需要知道關(guān)鍵字的查找概率?！窘獯稹咳~

41、子結(jié)點(diǎn)數(shù)結(jié)點(diǎn)數(shù)需要 n 個(gè)關(guān)鍵字的查找概率表2. 【分析】 折半查找法在查找成功與不成功時(shí)進(jìn)行比較的關(guān)鍵字個(gè)數(shù)最多不超過(guò)樹的深度，而具有n 個(gè)結(jié)點(diǎn)的判定樹的深度為?log 2n+1，所以，最大比較次數(shù)為?log 2 n+1。【答案】 ?log 2n+13. 【分析】平均檢索長(zhǎng)度aslss =(s+n/s)/2+1，所以當(dāng) s=n 時(shí)， aslss 取得最小值n +1。【解答】 16 17 214. 【分析】第4 層是葉子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)兩個(gè)關(guān)鍵字，2×12× 31 2×32=26?！敬鸢浮?26四、簡(jiǎn)答題1. 【解答】判定樹如下所示：10等概率查找時(shí)成功的平均查找長(zhǎng)

42、度為aslsucc = 1 (1 × 1+2×2+3× 4+4× 3)=2.92. 【解答】（ 1）按關(guān)鍵字的順序構(gòu)造的二叉排序樹：（ 2）根據(jù)構(gòu)造的二叉排序樹，求查找成功時(shí)的平均查找長(zhǎng)度： aslsucc=(1*1+2*2+3*3+4*3+5*2+6*1)/12=3.5（ 3）若對(duì)表中元素先進(jìn)行排序構(gòu)成有序表再構(gòu)造二叉排序樹，則構(gòu)造的二叉排序樹是一棵單支樹，在等概率的情況下查找成功的平均查找長(zhǎng)度則為：aslsucc=(1+2+12)/12=6.5這種情況就退化成為順序查找。3. 【解答】4. 【解答】5. 【解答】令fk 表示含有最少結(jié)點(diǎn)的深度為k 的

43、平衡二叉樹的結(jié)點(diǎn)數(shù)目。那么, 可知道 f1=1,f 2=2,.fn=fn-2 +fn-1 +1.含有 12 個(gè)結(jié)點(diǎn)的平衡二叉樹的最大深度為例如：地址0123456789106【解答】 4 個(gè)、 7 個(gè)。7【解答】8【分析】主要考察用線性探測(cè)再散列法和鏈地址法構(gòu)造哈希表。哈希表的裝填因子定義為：=表中添入的記錄數(shù)/ 哈希表的長(zhǎng)度【解答】使用線性探測(cè)再散列法來(lái)構(gòu)造哈希表見(jiàn)下表：數(shù)據(jù)331131234382722hashf1(1)=1hashf1(13)=2hashf1(12)=1hashf2(12) (1+1)%11=2hashf3(12)= (1+2)%11=3hashf1(34)=3hashf2(34)=(3+1)%11=4hashf1(38)=5hashf1(33)=0hashf1(27)=5hashf2(27)=(5+1)%11=6hashf1(22)=0hashf2(22)=(0+1)%11=1hashf3(22)=2 hashf4(22)=3hashf5(22)=4hashf6(22)=5hashf7(22)=6hashf8(22)=7裝填因子 ? 8/11查找成功所需的平均查找次數(shù)：(1+1+3+2+1+1+2+8)/8=19/8查找成功所需的平均查找次數(shù)：