數(shù)據(jù)結(jié)構(gòu)習(xí)題答案.doc

習(xí)題1參考答案一、單項(xiàng)選擇題1. A 2. C 3. D 4. B 5. C、A 6. C、B 7. B 8. D 9. B 10. B二、填空題1. 線性結(jié)構(gòu)，非線性結(jié)構(gòu)2. 集合，線性，樹(shù)，圖3. 一對(duì)一，一對(duì)多或多對(duì)多4. 時(shí)間，空間5. 前趨，一，后繼，多6. 有多個(gè)7. 一對(duì)一，一對(duì)多，多對(duì)多8. O()9. O()10. O()11. O(logn)12. 程序?qū)τ诰脑O(shè)計(jì)的典型合法數(shù)據(jù)輸入能得出符合要求的結(jié)果。13. 事后統(tǒng)計(jì)，事前估計(jì)三、算法設(shè)計(jì)題1. O() 2. O() 3. O(n) 4. O(n) 5. O(n)習(xí)題2參考答案一、單項(xiàng)選擇題1A 2A 3D 4C 5D 6A 7B 8B 9C 10A 11D 12B 13C 14B 15C 16C 17B 18D 19C20A二、填空題1線性 2n-i+1 3相鄰 4前移，前，后5物理存儲(chǔ)位置，鏈域的指針值 6前趨，后繼7順序，鏈接 8一定，不一定9線性，任何，棧頂，隊(duì)尾，隊(duì)頭10單鏈表，雙鏈表，非循環(huán)鏈表，循環(huán)鏈表11使空表和非空表統(tǒng)一；算法處理一致12O(1)，O(n)13棧滿，?？眨琺，棧底，兩個(gè)棧的棧頂在?？臻g的某一位置相遇142、315O(1)三、簡(jiǎn)答題1頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）的指針；在表頭結(jié)點(diǎn)之前附設(shè)的結(jié)點(diǎn)稱(chēng)為頭結(jié)點(diǎn)；表頭結(jié)點(diǎn)為鏈表中存儲(chǔ)線性表中第一個(gè)數(shù)據(jù)元素的結(jié)點(diǎn)。若鏈表中附設(shè)頭結(jié)點(diǎn)，則不管線性表是否為空表，頭指針均不為空，否則表示空表的鏈表的頭指針為空。2線性表具有兩種存儲(chǔ)結(jié)構(gòu)即順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)。線性表的順序存儲(chǔ)結(jié)構(gòu)可以直接存取數(shù)據(jù)元素，方便靈活、效率高，但插入、刪除操作時(shí)將會(huì)引起元素的大量移動(dòng)，因而降低效率：而在鏈接存儲(chǔ)結(jié)構(gòu)中內(nèi)存采用動(dòng)態(tài)分配，利用率高，但需增設(shè)指示結(jié)點(diǎn)之間關(guān)系的指針域，存取數(shù)據(jù)元素不如順序存儲(chǔ)方便，但結(jié)點(diǎn)的插入、刪除操作較簡(jiǎn)單。3應(yīng)選用鏈接存儲(chǔ)結(jié)構(gòu)，因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)是用一組任意的存儲(chǔ)單元依次存儲(chǔ)線性表中的各元素，這里存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的：這種存儲(chǔ)結(jié)構(gòu)對(duì)于元素的刪除或插入運(yùn)算是不需要移動(dòng)元素的，只需修改指針即可，所以很容易實(shí)現(xiàn)表的容量的擴(kuò)充。4應(yīng)選用順序存儲(chǔ)結(jié)構(gòu)，因?yàn)槊總€(gè)數(shù)據(jù)元素的存儲(chǔ)位置和線性表的起始位置相差一個(gè)和數(shù)據(jù)元素在線性表中的序號(hào)成正比的常數(shù)。因此，只要確定了其起始位置，線性表中的任一個(gè)數(shù)據(jù)元素都可隨機(jī)存取，因此，線性表的順序存儲(chǔ)結(jié)構(gòu)是一種隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)，而鏈表則是一種順序存取的存儲(chǔ)結(jié)構(gòu)。5設(shè)尾指針比設(shè)頭指針好。尾指針是指向終端結(jié)點(diǎn)的指針，用它來(lái)表示單循環(huán)鏈表可以使得查找鏈表的開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)都很方便，設(shè)一帶頭結(jié)點(diǎn)的單循環(huán)鏈表，其尾指針為rear，則開(kāi)始結(jié)點(diǎn)和終端結(jié)點(diǎn)的位置分別是rear-next-next 和 rear, 查找時(shí)間都是O(1)。若用頭指針來(lái)表示該鏈表，則查找終端結(jié)點(diǎn)的時(shí)間為O(n)。6共有14種可能的出棧序列，即為：ABCD, ABDC，ACBD, ACDB，BACD，ADCB，BADC，BCAD, BCDA，BDCA,CBAD, CBDA，CDBA, DCBA7在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，設(shè)隊(duì)頭指針為front，隊(duì)尾指針為rear，隊(duì)列的容量（即存儲(chǔ)的空間大?。閙axnum。當(dāng)有元素要加入隊(duì)列（即入隊(duì)）時(shí)，若rear=maxnum，則會(huì)發(fā)生隊(duì)列的上溢現(xiàn)象，此時(shí)就不能將該元素加入隊(duì)列。對(duì)于隊(duì)列，還有一種“假溢出”現(xiàn)象，隊(duì)列中尚余有足夠的空間，但元素卻不能入隊(duì)，一般是由于隊(duì)列的存儲(chǔ)結(jié)構(gòu)或操作方式的選擇不當(dāng)所致，可以用循環(huán)隊(duì)列解決。 一般地，要解決隊(duì)列的上溢現(xiàn)象可有以下幾種方法：（1）可建立一個(gè)足夠大的存儲(chǔ)空間以避免溢出，但這樣做往往會(huì)造成空間使用率低，浪費(fèi)存儲(chǔ)空間。（2）要避免出現(xiàn)“假溢出”現(xiàn)象可用以下方法解決： 第一種：采用移動(dòng)元素的方法。每當(dāng)有一個(gè)新元素入隊(duì)，就將隊(duì)列中已有的元素向隊(duì)頭移動(dòng)一個(gè)位置，假定空余空間足夠。 第二種：每當(dāng)刪去一個(gè)隊(duì)頭元素，則可依次移動(dòng)隊(duì)列中的元素總是使front指針指向隊(duì)列中的第一個(gè)位置。 第三種：采用循環(huán)隊(duì)列方式。將隊(duì)頭、隊(duì)尾看作是一個(gè)首尾相接的循環(huán)隊(duì)列，即用循環(huán)數(shù)組實(shí)現(xiàn)，此時(shí)隊(duì)首仍在隊(duì)尾之前，作插入和刪除運(yùn)算時(shí)仍遵循“先進(jìn)先出”的原則。8該算法的功能是：將開(kāi)始結(jié)點(diǎn)摘下鏈接到終端結(jié)點(diǎn)之后成為新的終端結(jié)點(diǎn)，而原來(lái)的第二個(gè)結(jié)點(diǎn)成為新的開(kāi)始結(jié)點(diǎn)，返回新鏈表的頭指針。四、算法設(shè)計(jì)題 1算法思想為：（1）應(yīng)判斷刪除位置的合法性，當(dāng)in-1時(shí)，不允許進(jìn)行刪除操作；（2）當(dāng)i=0時(shí)，刪除第一個(gè)結(jié)點(diǎn)：（3）當(dāng)in時(shí)，允許進(jìn)行刪除操作，但在查找被刪除結(jié)點(diǎn)時(shí)，須用指針記住該結(jié)點(diǎn)的前趨結(jié)點(diǎn)。算法描述如下：delete(LinkList *q,int i) /在無(wú)頭結(jié)點(diǎn)的單鏈表中刪除第i個(gè)結(jié)點(diǎn) LinkList *p,*s; int j; if(inext; free(s); else j=0; s=q; while(jnext;j+;if (s= =NULL) printf(Cantt delete); else p-next=s-next; free(s); 2由于在單鏈表中只給出一個(gè)頭指針，所以只能用遍歷的方法來(lái)數(shù)單鏈表中的結(jié)點(diǎn)個(gè)數(shù)了。算法描述如下：int ListLength ( LinkList *L ) /求帶頭結(jié)點(diǎn)的單鏈表的表長(zhǎng) int len=0; ListList *p; p=L; while ( p-next!=NULL ) p=p-next;len+; return (len);3設(shè)單循環(huán)鏈表的頭指針為head，類(lèi)型為L(zhǎng)inkList。逆置時(shí)需將每一個(gè)結(jié)點(diǎn)的指針域作以修改，使其原前趨結(jié)點(diǎn)成為后繼。如要更改q結(jié)點(diǎn)的指針域時(shí)，設(shè)s指向其原前趨結(jié)點(diǎn)，p指向其原后繼結(jié)點(diǎn)，則只需進(jìn)行q-next=s;操作即可，算法描述如下：void invert(LinkList *head) /逆置head指針?biāo)赶虻膯窝h(huán)鏈表linklist *p, *q, *s; q=head; p=head-next; while (p!=head) /當(dāng)表不為空時(shí)，逐個(gè)結(jié)點(diǎn)逆置 s=q; q=p; p=p-next; q-next=s; p-next=q; 4定義類(lèi)型LinkList如下：typedef struct node int data; struct node *next,*prior;LinkList;此題可采用插入排序的方法，設(shè)p指向待插入的結(jié)點(diǎn)，用q搜索已由prior域鏈接的有序表找到合適位置將p結(jié)點(diǎn)鏈入。算法描述如下：insert (LinkList *head) LinkList *p,*s,*q; p=head-next; /p指向待插入的結(jié)點(diǎn)，初始時(shí)指向第一個(gè)結(jié)點(diǎn) while(p!=NULL) s=head; / s指向q結(jié)點(diǎn)的前趨結(jié)點(diǎn) q=head-prior; /q指向由prior域構(gòu)成的鏈表中待比較的結(jié)點(diǎn) while(q!=NULL) & (p-dataq-data) /查找插入結(jié)點(diǎn)p的合適的插入位置 s=q; q=q-prior; s-prior=p; p-prior=q; /結(jié)點(diǎn)p插入到結(jié)點(diǎn)s和結(jié)點(diǎn)q之間 p=p-next;5算法描述如下：delete(LinkList *head, int max, int min) linklist *p, *q; if (head!=NULL) q=head; p=head-next; while(p!=NULL) & (p-datanext;while(p!=NULL) & (p-datanext; q-next=p;6算法描述如下：delete(LinkList *head, int max, int min) LinkList *p,*q; q=head; p=head-next; while (p!=NULL) if(p-datadata=max) q=p; p=p-next; else q-next=p-next;free(p);p=q-next; 7本題是對(duì)一個(gè)循環(huán)鏈隊(duì)列做插入和刪除運(yùn)算，假設(shè)不需要保留被刪結(jié)點(diǎn)的值和不需要回收結(jié)點(diǎn)，算法描述如下：（1）插入（即入隊(duì)）算法：insert(LinkList *rear, elemtype x) /設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rear,x為待插入的元素 LinkList *p;p=(LinkList *)malloc(sizeof(LinkList);if(rear= =NULL) /如為空隊(duì)，建立循環(huán)鏈隊(duì)列的第一個(gè)結(jié)點(diǎn) rear=p;rear-next=p; /鏈接成循環(huán)鏈表else /否則在隊(duì)尾插入p結(jié)點(diǎn) p-next=rear-next;rear-next=p; rear=p;（2）刪除（即出隊(duì)）算法：delete(LinkList *rear) /設(shè)循環(huán)鏈隊(duì)列的隊(duì)尾指針為rearif (rear= =NULL) /空隊(duì) printf(underflown); if(rear-next= =rear) /隊(duì)中只有一個(gè)結(jié)點(diǎn)rear=NULL;elserear-next=rear-next-next; /rear-next指向的結(jié)點(diǎn)為循環(huán)鏈隊(duì)列的隊(duì)頭結(jié)點(diǎn)8只要從終端結(jié)點(diǎn)開(kāi)始往前找到第一個(gè)比x大(或相等)的結(jié)點(diǎn)數(shù)據(jù)，在這個(gè)位置插入就可以了。算法描述如下：int InsertDecreaseList( SqList *L, elemtype x ) int i;if ( (*L).len= maxlen) printf(“overflow);return(0);for ( i=(*L).len ; i0 & (*L).elem i-1 x ; i-) (*L).elem i =(*L).elem i-1 ; / 比較并移動(dòng)元素 (*L).elem i =x; (*L).len+;return(1);習(xí)題3參考答案一、單項(xiàng)選擇題1B2D3C4D5B6C7D8C9D二、填空題1. 固定長(zhǎng)度，設(shè)置長(zhǎng)度指針2. 兩個(gè)串的長(zhǎng)度相等，對(duì)應(yīng)位置的字符相等3. “BCDEDE”4. 含n個(gè)字符的有限序列 （n0）5. 不含任何字符的串，僅含空格字符的字符串三、算法設(shè)計(jì)題1算法描述為：int delete(r,s,t,m) /從串的第m個(gè)字符以后刪除長(zhǎng)度為t的子串char r ;int s,t,m; int i,j; for(i=1;i=m;i+)rs+i=ri; for(j=m+t-i;jdata!=pt-data) pt=pt-next; if(pt= =NULL) ps=NULL; else ps=ps-next;s=ps; return s; /find習(xí)題4參考答案一、單項(xiàng)選擇題1. A 2. A 3. A 4. B 5. BA 6. C 7. A 8. A 9. C 10. C 11. C 12. C 13. B 14. D 15.A 16.B 二、填空題1. 線性結(jié)構(gòu)，順序結(jié)構(gòu)，以行為主序，以列為主序2. in+j個(gè)元素位置3. 5，34.（0，2，2），（1，0，3），（2，2，-1），（2，3，5）5. n(n+1)/26. e7. 418. head(head(tail(Ls)9.（d-c+1）（d-c+1）（d-c+1）10. 913三、判斷題1. 2. 3. 4. 5. 6. 7. 8. 9. 10. 11. 12. 13. 14. 15.習(xí)題5參考答案一、單項(xiàng)選擇題1. C 2. B 3. C 4. D 5. B 6. D 7. C 8. B 9. B 10. B 11. A 12. D 13. A 14. B 15. A二、判斷題1. 2. 3. 4. 5. 6. 7. 8. 9. 10.三、填空題1. 3，4，6，1，1，2，A，F(xiàn)，G2. n+13. 完全，最大，n4. 555. 中序6. 2n，n-1，n+17. n2+18. 2k-1，2k-1，2k-19. 510. 2h-111. 單支樹(shù)，完全二叉樹(shù)12. 2i，2i+1，i/2（或i/2）13. 2n，n-1，n+114. 帶權(quán)路徑長(zhǎng)度最小15. 結(jié)點(diǎn)數(shù)為0，只有一個(gè)根結(jié)點(diǎn)的樹(shù)16. 二叉鏈表，三叉鏈表17. 雙親結(jié)點(diǎn)18. 指向結(jié)點(diǎn)前驅(qū)和后繼信息的指針19. 1，RChild20. 孩子表示法，雙親表示法，長(zhǎng)子兄弟表示法四、應(yīng)用題1. 解答：abcdegfhimnjki圖5-15根據(jù)給定的邊確定的樹(shù)如圖5-15所示。其中根結(jié)點(diǎn)為a；葉子結(jié)點(diǎn)有：d、m、n、j、k、f、l；c是結(jié)點(diǎn)g的雙親；a、c是結(jié)點(diǎn)g的祖先；j、k是結(jié)點(diǎn)g的孩子；m、n是結(jié)點(diǎn)e的子孫；e是結(jié)點(diǎn)d的兄弟；g、h是結(jié)點(diǎn)f的兄弟；結(jié)點(diǎn)b和n的層次號(hào)分別是2和5；樹(shù)的深度為5。2. 解答：度為2的樹(shù)有兩個(gè)分支，但分支沒(méi)有左右之分；一棵二叉樹(shù)也有兩個(gè)分支，但有左右之分，左右子樹(shù)不能交換。3. 解答：略4. 解答：先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA5. 解答：（1）第i層上的結(jié)點(diǎn)數(shù)目是mi-1。（2）編號(hào)為n的結(jié)點(diǎn)的父結(jié)點(diǎn)如果存在，編號(hào)是(n-2)/m)+1。（3）編號(hào)為n的結(jié)點(diǎn)的第i個(gè)孩子結(jié)點(diǎn)如果存在，編號(hào)是(n-1)*m+i+1。（4）編號(hào)為n的結(jié)點(diǎn)有右兄弟的條件是(n-1)%m0。其右兄弟的編號(hào)是n+1。6. 解答：（1）先序序列和中序序列相同的二叉樹(shù)為：空樹(shù)或者任一結(jié)點(diǎn)均無(wú)左孩子的非空二叉樹(shù)；（2）中序序列和后序序列相同的二叉樹(shù)為：空樹(shù)或者任一結(jié)點(diǎn)均無(wú)右孩子的非空二叉樹(shù)；（3）先序序列和后序序列相同的二叉樹(shù)為：空樹(shù)或僅有一個(gè)結(jié)點(diǎn)的二叉樹(shù)。7. 解答：后序序列：ACDBGJKIHFE8. 解答：先序序列：ABCDGEIHFJK9. 解答：先根遍歷：ABCDEFGHIJKLMNO后根遍歷：BDEFCAHJIGKNOML森林轉(zhuǎn)換成二叉樹(shù)如圖5-16所示。10. 解答：構(gòu)造而成的哈夫曼樹(shù)如圖5-17所示。BGDCHKEIFJLMNOA圖5-1650 92030111614 7 7 2 5圖5-17五、算法設(shè)計(jì)題1. 解答：這個(gè)問(wèn)題可以用遞歸算法，也可用非遞歸算法，下面給出的為非遞歸算法。假設(shè)該完全二叉樹(shù)的結(jié)點(diǎn)以層次為序，按照從上到下，同層從左到右順序編號(hào)，存放在一個(gè)一維數(shù)組R1.n中，且用一個(gè)有足夠大容量為maxlen的順序棧作輔助存儲(chǔ)，算法描述如下：preorder (R) /先序遍歷二叉樹(shù)Rint Rn; int root;SqStack *s; /s為一個(gè)指針棧，類(lèi)型為seqstack，其中包含top域和數(shù)組datas-top= -1; /s棧置空root=1;while (roottop-1) while (roottop+;s-datas-top=root;root=2*root; if (s-top-1) /棧非空訪問(wèn)，遍歷右子樹(shù) root=s-datas-top*2+1; s-top-;2. 解答：考慮用一個(gè)順序隊(duì)que來(lái)保存遍歷過(guò)程中的各個(gè)結(jié)點(diǎn)，由于二叉樹(shù)以二叉鏈表存儲(chǔ)，所以可設(shè)que為一個(gè)指向數(shù)據(jù)類(lèi)型為bitree的指針數(shù)組，最大容量為maxnum，下標(biāo)從1開(kāi)始，同層結(jié)點(diǎn)從左到右存放。算法中的front為隊(duì)頭指針，rear為隊(duì)尾指針。levelorder (BiTree *t) /按層次遍歷二叉樹(shù)t BiTree *quemaxnum;int rear,front;if (t!=NULL) front=0; /置空隊(duì)列rear=1;que1=t;do front=front%maxsize+1; /出隊(duì) t=quefront; printf(t-data); if (t-lchild!=NULL) /左子樹(shù)的根結(jié)點(diǎn)入隊(duì) rear=rear%maxsize+1; querear=t-lchild; if (t-rchild!=NULL) /右子樹(shù)的根結(jié)點(diǎn)入隊(duì) rear=rear%maxsize+1; querear=t-rchild;while (rear= =front); /隊(duì)列為空時(shí)結(jié)束3. 解答：設(shè)該線索二叉樹(shù)類(lèi)型為bithptr，包含5個(gè)域：lchild，ltag，data，rchild，rtag。insert(p, s) /將s結(jié)點(diǎn)作為p的右子樹(shù)插入BiThrNode *p,*s; BiThrNode *q;if (p-rtag= =1) /無(wú)右子樹(shù)，則有右線索 s-rchild=p-rchild;s-rtag=1;p-rchild=s;p-rtag=0;else q=p-rchild;while(q-ltag= =0) /查找p所指結(jié)點(diǎn)中序后繼，即為其右子樹(shù)中最左下的結(jié)點(diǎn) q=q-lchild;q-lchild=p-rchild;s-rtag=0;p-rchild=s;s-lchild=p; /將s結(jié)點(diǎn)的左線索指向p結(jié)點(diǎn)s-ltag=1;4. 解答：利用一個(gè)隊(duì)列來(lái)完成，設(shè)該隊(duì)列類(lèi)型為指針類(lèi)型，最大容量為maxnum。算法中的front為隊(duì)頭指針，rear為隊(duì)尾指針，若當(dāng)前隊(duì)頭結(jié)點(diǎn)的左、右子樹(shù)的根結(jié)點(diǎn)不是所求結(jié)點(diǎn)，則將兩子樹(shù)的根結(jié)點(diǎn)入隊(duì)，否則，隊(duì)頭指針?biāo)附Y(jié)點(diǎn)即為結(jié)點(diǎn)的雙親。parentjudge(t,n)BiTree *t;int n; BiTree *quemaxnum;int front,rear;BiTree *parent;parent=NULL;if (t)if (t-data= =n)printf(“no parent!”); /n是根結(jié)點(diǎn)，無(wú)雙親else front=0; /初始化隊(duì)列rear=1;que1=t; /根結(jié)點(diǎn)進(jìn)隊(duì)do front=front%maxsize+1; t=quefront; if(t-lchild-data= =n)| (t-rchild-data= =n) /結(jié)點(diǎn)n有雙親 parent=t; front=rear; printf(“parent”,t-data); else if (t-lchild!=NULL) /左子樹(shù)的根結(jié)點(diǎn)入隊(duì) rear=rear%maxsize+1;querear=t-lchild; if (t-rchild!=NULL) /右子樹(shù)的根結(jié)點(diǎn)入隊(duì) rear=rear%maxsize+1; querear=t-rchild;while(rear= =front); /隊(duì)空時(shí)結(jié)束if (parent = =NULL) printf(“結(jié)點(diǎn)不存在”);習(xí)題6參考答案一、單項(xiàng)選擇題1. A 2. D 3. D 4. C 5. B 6. B 7. B 8. A 9. C 10. D 11. C 12. D 13. A 14. B 15. B 16. C 17. A 18. A 19. B 20. D 21. A 22. C 23. B 24. A二、填空題1. 2 2. n(n-1)/2，n(n-1)3. 2，4 4. n-1 5. 鄰接矩陣，鄰接表 6. 1 7. k+1 8. 3 9. n，n 10. 2e，e 11. 出邊，入邊 12. O（n），O（e/n） 13.O（n2），O（n+e） 14. acdeb，acedb （答案不唯一）15. acfebd，acefbd （答案不唯一） 16. 深度，廣度17. n，n-1 18. 唯一19. 唯一 20. aebdcf（答案不唯一）三、應(yīng)用題1. 深度優(yōu)先搜索序列：0,1,2,8,3,4,5,6,7,9 廣度優(yōu)先搜索序列：0,1,4,2,7,3,8,6,5,92. 深度優(yōu)先搜索序列：0,4,7,5,8,3,6,1,2 廣度優(yōu)先搜索序列：0,4,3,1,7,5,6,2,83. 深度優(yōu)先搜索序列：0,2,3,5,6,1,4 廣度優(yōu)先搜索序列：0,2,3,5,6,1,44. 深度優(yōu)先搜索序列：0,3,6,4,1,5,2 廣度優(yōu)先搜索序列：0,3,2,6,5,4,1(a)V1V2V3V4V5V6V760506540457050524230V1V2V3V4V5V6V750(c)V1V2V3V4V5V6V7(b)5. 過(guò)程如圖6-16所示 V1V2V3V4V5V6V7504045504230(h)圖6-16V1V2V3V4V5V6V75040504230(g)V1V2V3V4V5V6V750405030(f)V1V2V3V4V5V6V75040(d)V1V2V3V4V5V6V7504050(e)6. 求解過(guò)程如圖6-17所示。V1V2V3V4V5V6V7(a)30V1V2V3V4V5V6V7(b)3040V1V2V3V4V5V6V7(c)304042圖6-17V1V2V3V4V5V6V7(e)3040424550V1V2V3V4V5V6V7(f)304042455050V1V2V3V4V5V6V7(d)304042457. 求解過(guò)程如下表所示。終點(diǎn) 從v0到各終點(diǎn)的D值和最短路徑的求解過(guò)程 i=1 i=2 i=3 i=4 i=5 V1 無(wú) V2 10 (v0,v2) V3 60 (v0,v2,v3) 50 (v0,v4,v3) V4 30 (v0,v4) 30 (v0,v4) V5 100 (v0,v5) 100 (v0,v5) 90 (v0,v4,v5) 60 (v0,v4,v3,v5) Vj V2 V4 V3 V5 S v0,v2 v0,v2,v4v0,v2,v3,v4v0,v2,v3,v4,v58. 求解過(guò)程如下：事件的最早發(fā)生時(shí)間vek。 ve (1)=0 ve (2)=3 ve (3)=4 ve (4)=ve(2)+2=5 ve (5)=maxve(2)+1,ve(3)+3=7 ve (6)=ve(3)+5=9 ve (7)=maxve(4)+6,ve(5)+8=15 ve (8)=ve(5)+4=11 ve (9)=maxve(8)+10,ve(6)+2=21 ve (10)=maxve(8)+4,ve(9)+1=22 ve (11)=maxve(7)+7,ve(10)+6=28事件的最遲發(fā)生時(shí)間vlk。 vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21 vl (8)=min vl (10)-4, vl (9)-10=11 vl (7)= vl (11)-7=21 vl (6)= vl (9)-2=19 vl (5)=min vl (7)-8,vl (8)-4=7 vl (4)= vl (7)-6=15 vl (3)=min vl (5)-3, vl (6)-5=4 vl (2)=min vl (4)-2, vl (5)-1=6 vl (1)=minvl (2)-3, vl (3)-4=0活動(dòng)ai的最早開(kāi)始時(shí)間ei和最晚開(kāi)始時(shí)間li。 活動(dòng)a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活動(dòng)a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活動(dòng)a3 e (3)=ve (2)=3 l (3)=vl (4) - 2=13 活動(dòng)a4 e (4)=ve (2)=3 l (4)=vl (5) - 1=6 活動(dòng)a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4 活動(dòng)a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活動(dòng)a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活動(dòng)a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活動(dòng)a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活動(dòng)a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活動(dòng)a11 e (11)=ve (7)=15 l (11)=vl (11) - 7=21 活動(dòng)a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活動(dòng)a13 e (13)=ve (8)=11 l (13)=vl (9) - 10=11 活動(dòng)a14 e (14)=ve (9)=21 l (14)=vl (10) -1=21 活動(dòng)a15 e (15)=ve (10)=22 l (15)=vl (11) -6 =22最后，比較ei和li的值可判斷出a2,a5,a9,a13,a14,a15是關(guān)鍵活動(dòng)，關(guān)鍵路徑如圖6-18所示。v1v5v3v8v11v9v1001a2=4a5=3a9=4a13=10a14=1a15=6圖6-18四、算法設(shè)計(jì)題1. int degree1(Graph & ga, int numb) /根據(jù)無(wú)向圖的鄰接矩陣求出序號(hào)為numb的頂點(diǎn)的度數(shù) int j,d=0; for(j=0; jga.vexnum; j+)if (ga.costnumbj!=0 & ga.costnumbj!=MAXINT)d+; return (d);2. int degree2(Graph & ga, int numb)/根據(jù)有向圖的鄰接矩陣求出序號(hào)為numb的頂點(diǎn)的度數(shù) int i,j,d=0; /求出頂點(diǎn)numb的出度 for(j=0; jga.vexnum; j+) if(ga.costnumbj!=0 & ga.costnumbj!=MAXINT) d+; /求出頂點(diǎn)numb的入度 for(i=0; inext; return (d);4. int degree4(GraphL & gl, int numb)/根據(jù)有向圖的鄰接表求出序號(hào)為numb的頂點(diǎn)的度數(shù) int d=0, i;vexnode * p=gl.adjlistnumb; while (p!=NULL) d+;p=p-next; /求出頂點(diǎn)numb的出度f(wàn)or(i=0; ivertex= =numb) d+; p=p-next;/求出頂點(diǎn)numb的入度 return (d); /返回頂點(diǎn)numb的度數(shù)習(xí)題7參考答案一、單項(xiàng)選擇題1. D 2. A 3. B 4. C 5. D 6. D 7. A 8. C 9. A 10. A 11. C 12. B 13. D 二、填空題1. (n+1)/2, O(n) 2. 3. 20.5, 41 4. log2(n+1)，O(log2n)5. 順序 有序 6. 1，3 7. 6， 19 8. (n/s+s)/2+1 9. 11 10. 小于，大于11. 有序序列 12. 查找成功，左子樹(shù)，右子樹(shù) 13. 左子樹(shù)，右子樹(shù) 14. O(nlog2n) 15. 1 16. 5 17. 2 18. n/m 19. 3， 2 三、應(yīng)用題1. 折半查找判定樹(shù)如圖7-3所示，平均查找長(zhǎng)度等于29/10。圖7-3中的結(jié)點(diǎn)與有序表中元素的對(duì)應(yīng)關(guān)系如下表所示。圖7-3109456781231234567891015263439455658637476圖7-4385225167430689054722. 二叉排序樹(shù)如圖7-4所示，平均查找長(zhǎng)度等于32/10。3. H(K)=K % 13平均查找長(zhǎng)度為14/10，其余解答如下。 元素 32 75 29 63 48 94 25 46 18 70 初始哈希地址 6 10 3 11 9 3 12 7 5 5 最終哈希地址 6 10 3 11 9 4 12 7 5 8 0 1 2 3 4 5 6 7 8 9 10 11 12 哈希表 29 94 18 32 46 70 48 75 63 254. H(K)=K % 11，哈希表如圖7-5所示，平均查找長(zhǎng)度17/12。圖7-50 四、算法設(shè)計(jì)題1. 設(shè)計(jì)思路：進(jìn)入判別算法之前，pre取初值為min(小于樹(shù)中任一結(jié)點(diǎn)值)，fail=FALSE,即認(rèn)為bt是二叉排序樹(shù)。按中序遍歷bt，并在沿向根結(jié)點(diǎn)，與前趨比較，若逆序，則fail為T(mén)RUE,則bt不是二叉排序樹(shù)。void bisorttree(bitree bt,keytype pre, bool &fail) /fail初值為FALSE，若非二叉序樹(shù)，則fail值TRUE if (!fail) if (bt) bisosrttree(bt-lchild,pre,fail); /判斷左子樹(shù) if (bt-data_keydata_key; bisorttree(bt-rchild,pre,fail); /判斷右子樹(shù) /bisorttree說(shuō)明：較為直觀的方法，可套用中序遍歷非遞歸算法。2. int search_bin(SeqTable st , keytype k , int low , int high) if (lowhigh) return (0); /不成功else mid=(low+high)/2;if (k= =st.elemmid.key) return (mid) ; /成功else if (kst.elemmid.key) return (st,k,low,mid-1);else return(st,k,mid+1,high); /search-bin習(xí)題8