數(shù)據(jù)結(jié)構習題課

1、算法與數(shù)據(jù)結(jié)構第13章習題課中北大學信息與通信工程學院主講：金永 副教授第13章 習題課2/31算法與數(shù)據(jù)結(jié)構選擇題1.對于順序存儲的線性表，訪問結(jié)點和增加、刪除結(jié)點的時間復雜度為（C ）。AO(n) O(n) B. O(n) O(1) C. O(1) O(n) D. O(1) O(1)2.非空的循環(huán)單鏈表head的尾結(jié)點p滿足（ A）。AP-next=head BP-next=NIL Cp=NIL Dp= head3.在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是：（ B）。Ap-next=s;s-next=p-next; B s-next=p-next;p-next=s;Cp-

2、next=s;p-next=s-next; D p-next=s-next; p-next=s;第13章 習題課3/31算法與數(shù)據(jù)結(jié)構4.在雙向鏈表指針p的結(jié)點前插入一個指針q的結(jié)點操作是（C ）注:雙向鏈表的結(jié)點結(jié)構為(pre,data,next)。 A. p-pre=q;q-next=p;p-pre-next=q;q-pre=q；B. p-pre=q;p-pre-next=q;q-next=p;q-pre=p-pre;C. q-next=p;q-pre=p-pre;p-pre-next=q;p-pre=q;D. q-pre=p-pre;q-next=q;p-pre=q;p-pre=q;5.

3、棧的特點是（ B ）,隊列的特點是（ A）,棧和隊列都是（ C ）。若進棧序列為1,2,3,4 則（ C ）不可能是一個出棧序列（不一定全部進棧后再出棧）；若進隊列的序列為1,2,3,4 則（ E ）是一個出隊列序列。, : A. 先進先出 B. 后進先出 C. 進優(yōu)于出 D. 出優(yōu)于進: A.順序存儲的線性結(jié)構 B.鏈式存儲的線性結(jié)構 C.限制存取點的線性結(jié)構 D.限制存取點的非線性結(jié)構, : A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 4,3,2,1 E. 1,2,3,4 F. 1,3,2,4第13章 習題課4/31算法與數(shù)據(jù)結(jié)構6.一個棧的輸入序列為123n，

4、若輸出序列的第一個元素是n，輸出第i（1=inext; p2=pb-next; pa-next=null; s1=0; s2=0;While( p1& p2) if(p1-datadata) p=p1; p1=p1-next; s2=s2+1; delete(p) ;else if(p1-datap2-data) p2=p2-next; else (p1-data=p2-data) p=p1; p1=p1-next; p-next= pa-next; pa-next= p; p2= p2-next;s1=s1+1;While(p1) p=p1; p1=p1-next; delete(p); s

5、2=s2+1 3.設pa，pb分別指向兩個帶頭結(jié)點的有序（從小到大）單鏈表。仔細閱讀如下的程序，并回答問題： （1） 程序的功能。（2） s1，s2中值的含義。（3） pa，pb中值的含義。第13章 習題課9/31算法與數(shù)據(jù)結(jié)構解：本程序段功能是將pa和pb鏈表中的值相同的結(jié)點保留在pa鏈表中（pa中與pb中不同結(jié)點刪除），pa是結(jié)果鏈表的頭指針。鏈表中結(jié)點值與從前逆序。S1記結(jié)果鏈表中結(jié)點個數(shù)（即pa與pb中相等的元素個數(shù)）。S2記原pa鏈表中刪除的結(jié)點個數(shù)。第13章 習題課10/31算法與數(shù)據(jù)結(jié)構10231530p設 q=p-pre; 則q-next=p-next; p-next-pre=

6、q; p-pre=q-pre;q-pre-next=p; p-next=q; q-pre=p1.寫出下圖雙鏈表中對換值為23和15的兩個結(jié)點相互位置時修改指針的有關語句。結(jié)點結(jié)構為：(pre,data,next)算法題第13章 習題課11/31算法與數(shù)據(jù)結(jié)構Void Union(seqlist LA, seqlist LB) m=LA.length; n=LB.length; k=m+n-2; i=m-1;j=n-1; while(i=0&j=0) if(LA.elemi=LB.elemj) LA.elemk=LA.elemi;k=k-1;i=i-1; elseLA.elemk =LB.ele

7、mj;k=k-1;j=j-1; while(j=0)LA.elemk=LB.elemj;k=k-1;j=j-1;2.順序結(jié)構線性表LA與LB的結(jié)點關鍵字為整數(shù)。LA與LB的元素按非遞減有序，線性表空間足夠大。試給出一種高效算法，將LB中元素合到LA中，使新的LA的元素仍保持非遞減有序。高效指最大限度的避免移動元素。第13章 習題課12/31算法與數(shù)據(jù)結(jié)構3.給定一個帶表頭結(jié)點的單鏈表，設head為頭指針，結(jié)點的結(jié)構為(data,next),data為整型元素，next為指針;試寫出算法:按遞增次序輸出單鏈表中各結(jié)點的數(shù)據(jù)元素，并釋放結(jié)點所占的存儲空間。(要求;不允許使用數(shù)組作輔助空間)void

8、 MiniDelete(LinkedList head) LinkedList *pre,*p,*u; while（head-next!=null） 循環(huán)到僅剩頭結(jié)點。 pre=head; p=pre-next；p為工作指針,pre為最小值的前驅(qū) while（p-next!=null） if（p-next-datanext-data）pre=p； p=p-next； 記住當前最小值結(jié)點的前驅(qū) print(%2d,pre-next-data);輸出最小值。 u=pre-next；pre-next=u-next; free(u);刪除最小結(jié)點 free(head)； 釋放頭結(jié)點。第13章 習題課1

9、3/31算法與數(shù)據(jù)結(jié)構4.試寫一算法在帶頭結(jié)點的單鏈表結(jié)構上實現(xiàn)線性表操作Locate(L,x); int LocateElem_L(LinkList &L,ElemType x)int i=0;LinkList p=L;while(p&p-data!=x)p=p-next;i+;if(!p) return 0;else return i;第13章 習題課14/31算法與數(shù)據(jù)結(jié)構5.已知單鏈表中的元素以值遞增有序排列。試寫一高效的算法，刪除表中所有值大于mink且小于maxk的元素，同時釋放被刪結(jié)點空間。 mink =maxkpreqp修改指針修改指針: pre-next = p;釋放結(jié)點釋放

10、結(jié)點: while (q!=p) s=q-next; free(q); q=s; 第13章 習題課15/31算法與數(shù)據(jù)結(jié)構void delete(LinkList &L, int mink, int maxk) / delete while (p & p-datanext; /查找第一個值mink的結(jié)點if (p) / ifq=pre-next; pre-next=p; / 修改指針while (q!=p) s=q-next; delete q; q=s; / 釋放結(jié)點空間p=L-next; while (p & p-datanext; / 查找第一個值 maxk 的結(jié)點第13章 習題課16/

11、31算法與數(shù)據(jù)結(jié)構6.試寫一高效的算法，刪除表中所有值相同的多余元素（使得操作后的線性表中所有元素的值均不相同），同時釋放被刪結(jié)點空間，并分析你的算法的時間復雜度。 此題即為例此題即為例2-22-2的第二種算法在單鏈表中的具體實現(xiàn)。的第二種算法在單鏈表中的具體實現(xiàn)。第13章 習題課17/31算法與數(shù)據(jù)結(jié)構void purge_L( LinkList La ) / 刪除帶頭結(jié)點的單鏈表刪除帶頭結(jié)點的單鏈表 La 中所有多余的結(jié)點中所有多余的結(jié)點 if (La-next) / 只需要處理非空表只需要處理非空表 p = La-next; suc = p-next; while (suc) / 尚有后

12、繼未檢查完 if (suc-data = p-data) q = suc; suc = suc-next; delete q; / 釋放值相同的結(jié)點空間釋放值相同的結(jié)點空間 else / 鏈接值不同的結(jié)點鏈接值不同的結(jié)點 p-next= suc; p = suc; suc = suc-next; / if/purge_L第13章 習題課18/31算法與數(shù)據(jù)結(jié)構a1a2a3LLpsucca1psucca2p succa3p基本操作基本操作：1 1）標志后繼結(jié)點標志后繼結(jié)點；2 2）修改指針（將修改指針（將*p插入在頭結(jié)點之后）插入在頭結(jié)點之后）；3 3）重置結(jié)點重置結(jié)點*p（p重新指向原表中后繼

13、）重新指向原表中后繼）；7.試寫一算法，對單鏈表實現(xiàn)就地逆置。試寫一算法，對單鏈表實現(xiàn)就地逆置。 第13章 習題課19/31算法與數(shù)據(jù)結(jié)構void inverse(LinkList &L) / 逆置帶頭結(jié)點的單鏈表逆置帶頭結(jié)點的單鏈表 L p=L-next; L-next=NULL; while ( p) succ=p-next; / succ指向*p的后繼 p-next=L-next; L-next=p; / *p插入在頭結(jié)點之后 p = succ; 第13章 習題課20/31算法與數(shù)據(jù)結(jié)構8.有兩個遞增有序排列的線性表A和B，均以單鏈表作存儲結(jié)構，請編寫算法將A表和B表歸并成一個非遞增有序

14、有序排列的線性表C，并利用原表的結(jié)點空間構造C表。 12233445561132434854LaLbLcpapbqpbqpaqpaq第13章 習題課21/31算法與數(shù)據(jù)結(jié)構void union( LinkList& Lc, LinkList& La, LinkList& Lb) Lc = new LNode; Lc-next = NULL;pa = La-next; pb = Lb-next; / 初始化初始化delete La; delete Lb; / 釋放釋放La 和和 Lb的頭結(jié)點的頭結(jié)點 / unionwhile ( pa | pb ) if ( !pa ) q = pb; pb =

15、 pb-next; else if ( !pb ) q = pa; pa = pa-next; else (pa-data data ) q = pa; pa = pa-next; else q = pb; pb = pb-next; q-next = Lc-next; Lc-next = q; / 插入插入第13章 習題課22/31算法與數(shù)據(jù)結(jié)構9.設有一個雙向循環(huán)鏈表，每個結(jié)點中除有pre，data和next三個域外，還增設了一個訪問頻度域freq。在鏈表被起用之前，頻度域freq的值均初始化為零，而每當對鏈表進行一次Locate(L,x)的操作后，被訪問的結(jié)點（即元素值等于x的結(jié)點）中的

16、頻度域freq的值便增1，同時調(diào)整鏈表中結(jié)點之間的次序，使其按訪問頻度非遞增的次序順序排列，以便始終保持被頻繁訪問的結(jié)點總是靠近表頭結(jié)點。試編寫符合上述要求的Locate操作的算法。 (1) 算法的基本操作基本操作應該是在鏈表中進行搜索在鏈表中進行搜索, 直至直至( ( p=L | p-data=x )為止為止; (2) 在訪問頻度 freq 增 1 之后，需將該結(jié)點調(diào)整到適當調(diào)整到適當位置位置。向前搜索直至找到一個訪問頻度大于它的結(jié)點為止。第13章 習題課23/31算法與數(shù)據(jù)結(jié)構DuLinkList ListLocate_DuL(DuLinkList &L,ElemType e) DuLin

17、kList p,q; p=L-next; while(p!=L & p-data!=e)p=p-next; if(p=L) return NULL; elsep-freq+; p-pre-next=p-next; p-next-pre=p-pre; / 刪除結(jié)點 q=p-pre; while (q!=L & q-freqfreq) q=q-pre; /搜索訪問頻度不小于它的結(jié)點*q p-next=q-next; q-next=p; p-next-pre=p; p-pre=q; / 在q之后插入 第13章 習題課24/31算法與數(shù)據(jù)結(jié)構10.試以循環(huán)鏈表作稀疏多項式的存儲結(jié)構，結(jié)點有三個域，系數(shù)

18、域coef ，指數(shù)域exp和指針域 next；編寫求其導函數(shù)的方法，要求利用原多項式中的結(jié)點空間存放其導函數(shù)多項式，同時釋放所有無用結(jié)點。void Difference_L( LinkedPoly pa ) p = pa-next; pre = pa; while ( p !=pa ) if ( p-exp != 0) p-coef*=p-exp- ; pre = p; else pre-next = p-next; delete p; / 刪除零次項 p = pre-next; /while/Difference_L第13章 習題課25/31算法與數(shù)據(jù)結(jié)構11.假設稱正讀和反讀都相同的字符序

19、列為“回文”，例如，abba和abcba是回文，abcde和ababab則不是回文。試寫一個算法判別讀入的一個以為結(jié)束符的字符序列是否是“回文”。 Status SymmetryString(char* p) Queue q;InitQueue(q); Stack s; InitStack(s); ElemType e1,e2; while(*p!=)Push(s,*p); EnQueue(q,*p); p+; while(!StackEmpty(s)Pop(s,e1);DeQueue(q,e2);if(e1!=e2) return FALSE; return OK;第13章 習題課26/31

20、算法與數(shù)據(jù)結(jié)構12.設有兩個棧S1,S2都采用順序棧方式，并且共享一個存儲區(qū)O.maxsize-1,為了盡量利用空間，減少溢出的可能，可采用棧頂相向，迎面增長的存儲方式。試設計S1,S2有關入棧和出棧的操作算法。int top2; /top為兩個棧頂指針(1)int push(int i,int x)/i=0棧s1，i=1棧s2if(i1) exit(0); if(s.top1-s.top0=0) print(“棧滿”);return(0); switch(i) case 0: s.bases.top0=x; s.top0 +; return(1); break; case 1: s.base

21、s.top1=x; s.top1 -; return(1); 第13章 習題課27/31算法與數(shù)據(jù)結(jié)構（2）int pop(int i,int &x)/i=0為s1棧，i=1為s2棧 if(i1) exit(0); switch(i) case 0: if(s.top0=0) print(“?？铡? ；return (0); else s.top0-; x=s.bases.top0; return (1);); case 1: if(s.top1=maxsize print(“?？铡? ;return(0); elses.top1+; x=s.bases.top1); return (1);

22、第13章 習題課28/31算法與數(shù)據(jù)結(jié)構13.設結(jié)點結(jié)構為(data,next)，試用一個全局指針p和某種鏈接結(jié)構實現(xiàn)一個隊列,并給出入隊addq和出隊deleteq過程,要求它們的時間復雜性都是O(1)void addq(node *p,elemtp x); s=new node; /申請新結(jié)點。s-data=x; s-next=p-next;/將s結(jié)點入隊。p-next=s; p=s; /尾指針p移至新的隊尾。p是循環(huán)鏈表表示的隊列的尾指針void deleq(node *p,elemtp &x); if(p-next=p）print(“空隊列”);exit(0); else s=p-ne

23、xt-next; /找到隊頭元素。 p-next-next=s-next; /刪隊頭元素。 x=s-data; delete(s); /返回出隊元素。第13章 習題課29/31算法與數(shù)據(jù)結(jié)構14.請利用兩個棧S1和S2來模擬一個隊列。已知棧的三個運算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。如何利用棧的運算來實現(xiàn)該隊列的三個運算：enqueue:插入一個元素入隊列；dequeue:刪除一個元素出隊列；queue_empty：判隊列為空。請寫明算法的思想及必要的注釋 第13章 習題課30/31算法與數(shù)

24、據(jù)結(jié)構(1) int enqueue(stack S1, stack S2,elemtp x)/S1是容量為n的棧，棧中元素類型是elemtp。本算法將x入棧，若入棧成功返回1，否則返回0。 elemtp x1; if(S1.top=n & !Sempty(S2) print(“棧滿”);return(0); /S1滿S2非空,這時S1不能再入棧。 if(S1.top=n & Sempty(S2) while(!Sempty(S1) POP(S1,x1);PUSH(S2,x1); /先將S1退棧,元素再壓棧到S2。 PUSH(S1,x); return(1); /x入棧，實現(xiàn)了隊列元素的入隊。

25、第13章 習題課31/31算法與數(shù)據(jù)結(jié)構(2) void dequeue(stack S1, stack S2, elemtp &x)/S2是輸出棧，S2棧頂元素退棧，實現(xiàn)隊列元素的出隊。 elemtp x1; if(!Sempty(S2) POP(S2,x);/棧S2不空，則直接出隊。 else if(Sempty(S1) print(“隊列空”);exit(0);/若輸入棧也為空，則判定隊空。 else while(!Sempty(S1) POP(S1,x1);PUSH(S2,x1); /先將棧S1倒入S2中，再作出隊操作。 POP(S2,x); /S2退棧相當隊列出隊。第13章 習題課3

26、2/31算法與數(shù)據(jù)結(jié)構(3) int queue_empty(stack S1, stack S2 ) /本算法判用棧S1和S2模擬的隊列是否為空。 if(Sempty(S1)&Sempty(S2) return(1);/隊列空。 else return(0); /隊列不空。第4章 串中北大學信息與通信工程學院主講：金永 副教授第4章 串34/60算法與數(shù)據(jù)結(jié)構練習1下面關于串的的敘述中，哪一個是不正確的？（B）A串是字符的有限序列 B空串是由空格構成的串C模式匹配是串的一種重要運算 D串既可以采用順序存儲，也可以采用鏈式存儲2設有兩個串p和q，其中q是p的子串，求q在p中首次出現(xiàn)的位置的算法

27、稱為（ C ）A求子串 B聯(lián)接 C匹配 D求串長3串 ababaaababaa 的next數(shù)組為（ C ）。A012345678999 B012121111212 C011234223456 D01230123223454字符串a(chǎn)babaabab 的nextval 為（ A ）A(0,1,0,1,0,4,1,0,1) B(0,1,0,1,0,2,1,0,1)C(0,1,0,1,0,0,0,1,1) D(0,1,0,1,0,1,0,1,1 )BCCA第4章 串35/60算法與數(shù)據(jù)結(jié)構設字符串S=aabaabaabaac，T=aabaac（1）給出S和T的next值和nextval值； （2）若S

28、作主串，T作模式串，試給出利用BF算法和KMP算法的匹配過程。（1）S的next與nextval值分別為012123456789和002002002009； t的next與nextval值分別為012123和002003。 第4章 串36/60算法與數(shù)據(jù)結(jié)構（2）利用BF算法的匹配過程： 利用KMP算法的匹配過程：第一趟匹配： aabaabaabaac 第一趟匹配：aabaabaabaac aabaac(i=6,j=6) aabaac(i=6,j=6) 第二趟匹配： aabaabaabaac 第二趟匹配：aabaabaabaac aa(i=3,j=2) (aa)baac 第三趟匹配： aaba

29、abaabaac 第三趟匹配：aabaabaabaac a(i=3,j=1) (成功) (aa)baac第四趟匹配： aabaabaabaac aabaac(i=9,j=6)第五趟匹配： aabaabaabaac aa(i=6,j=2)第六趟匹配： aabaabaabaac a(i=6,j=1)第七趟匹配： aabaabaabaac (成功) aabaac(i=13,j=7)第6章 樹和二叉樹習題課中北大學信息與通信工程學院主講：金永 副教授第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構1、已知一算術表達式的中綴形式為 A+B*C-D/E，后綴形式為ABC*+DE/-，其前綴形式為( D )A-A+B

30、*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE2、設森林F中有三棵樹，第一，第二，第三棵樹的結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應的二叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是（ D ）。AM1 BM1+M2 CM3 DM2+M33、有關二叉樹下列說法正確的是（ B ）A二叉樹的度為2 B一棵二叉樹的度可以小于2C二叉樹中至少有一個結(jié)點的度為2 D二叉樹中任何一個結(jié)點的度都為2選擇題第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構4、二叉樹的第I層上最多含有結(jié)點數(shù)為（ C ）A2I B 2I-1-1 C 2I-1 D2I -15、一個具有1025個結(jié)點的二叉樹的高h為（

31、 C ）A11 B10 C11至1025之間 D10至1024之間6、高度為 K的二叉樹最大的結(jié)點數(shù)為（ C ）。A2k B2k-1 C2k -1 D2k-1-1 7、利用二叉鏈表存儲樹，則根結(jié)點的右指針是（ C）。A指向最左孩子 B指向最右孩子 C空 D非空8、對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用( C )次序的遍歷實現(xiàn)編號。A先序 B. 中序 C. 后序 D. 從根開始按層次遍歷第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構9、某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,

32、A,F,G,E 則先序序列是：(B)AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不對 10、上題的二叉樹對應的森林包括多少棵樹（ B ）Al B2 C3 D概念上是錯誤的 11、一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（ C ）A所有的結(jié)點均無左孩子B所有的結(jié)點均無右孩子C只有一個葉子結(jié)點 D是任意一棵二叉樹12、在二叉樹結(jié)點的先序序列，中序序列和后序序列中，所有葉子結(jié)點的先后順序（ B ）A都不相同B完全相同 C先序和中序相同，而與后序不同D中序和后序相同，而與先序不同第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)

33、構13、在完全二叉樹中，若一個結(jié)點是葉結(jié)點，則它沒( C )。 A左子結(jié)點 B右子結(jié)點 C左子結(jié)點和右子結(jié)點 D左子結(jié)點，右子結(jié)點和兄弟結(jié)點14、n個結(jié)點的線索二叉樹上含有的線索數(shù)為（ C ）A2n Bnl Cnl Dn 15、下述編碼中哪一個不是前綴碼（ B ）。A（00，01，10，11） B（0，1，00，11） C（0，10，110，111） D（1，01，000，001）16、在下述結(jié)論中，正確的是（ D ）只有一個結(jié)點的二叉樹的度為0; 二叉樹的度為2； 二叉樹的左右子樹可任意交換;深度為K的完全二叉樹的結(jié)點個數(shù)小于或等于深度相同的滿二叉樹。 A B C D第6章 樹和二叉樹習題課

34、算法與數(shù)據(jù)結(jié)構17、若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（ C ） A9 B11 C15 D不確定 18、具有10個葉結(jié)點的二叉樹中有（ B ）個度為2的結(jié)點 A8 B9 C10 D1l19、一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是（ D ）A 250 B 500 C254 D50120、有n個葉子的哈夫曼樹的結(jié)點總數(shù)為（ D ）。A不確定 B2n C2n+1 D2n-121、二叉樹的先序遍歷和中序遍歷如下： 先序遍歷：EFHIGJK；中序遍歷: HFIEJKG 。該二叉樹根的右子樹的根是（ C ） 。A、 E B、 F C、 G D、 H

35、第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構22、設森林F對應的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（ C ）Am-n Bm-n-1 Cn+1 D條件不足，無法確定 23、用一維數(shù)組存儲二叉樹時，總是以（A）遍歷順序存儲結(jié)點A先序 B. 中序 C. 后序 D. 按層次遍歷24、對一棵二 叉樹進行 層次遍歷時 ，應借 助于 一 個（A）。A順序表 B. 數(shù)組 C. 棧 D.隊列25、某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（B）的二叉樹。A空或只有一個結(jié)點 B任一結(jié)點無左子樹 C高度等于其結(jié)點數(shù) D任一結(jié)點無右子樹第6章 樹和二叉樹習

36、題課算法與數(shù)據(jù)結(jié)構26、設樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1 則T中的葉子數(shù)為（ D ）A5 B6 C7 D827、將一棵樹t 轉(zhuǎn)換為孩子兄弟鏈表表示的二叉樹h，則t的后根序遍歷是h 的（ ） A先序遍歷 B中序遍歷 C后序遍歷28、某二叉樹T有n個結(jié)點，設按某種順序?qū)中的每個結(jié)點進行編號，編號為1，2， ，n，且有如下性質(zhì)：T中任一結(jié)點V，其編號等于左子樹上的最小編號減1，而V的右子樹的結(jié)點中，其最小編號等于V左子樹上結(jié)點的最大編號加1。這時是按( )編號的。A.中序遍歷序列 B.先序遍歷序列 C.后序遍歷序列 D.層次順序 第6章 樹和二叉樹習題課算法與數(shù)

37、據(jù)結(jié)構1、從概念上講，樹，森林和二叉樹是三種不同的數(shù)據(jù)結(jié)構，將樹，森林轉(zhuǎn)化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。 樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質(zhì)是一樣的，只是解釋不同，也就是說樹（森林的特例）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)別有：一是二叉樹的度至多為2，樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分枝的情況下， 也必須指出是左子樹還是右子樹，樹無此限制。應用題第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構 2、試找出滿足下列條件的二叉樹1）先序序列與后序序列相同；2）中序序列與后序序列相同；3）先序序列與中序

38、序列相同；1)、既不含左子樹，也不含右子樹的二叉樹。2)、不含右子樹的二叉樹。3)、不含左子樹的二叉樹。解：提示 先序遍歷：根-左-右 中序遍歷：左-根-右 后序遍歷：左-右-根第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構3、已知一棵度為、已知一棵度為k的樹中有的樹中有n1個度為個度為1的結(jié)點，的結(jié)點，n2個個度為度為2的結(jié)點，的結(jié)點，nk個度為個度為k的結(jié)點，問該樹中有的結(jié)點，問該樹中有多少個葉子結(jié)點？多少個葉子結(jié)點？根據(jù)樹的定義，在一顆樹中，除樹根結(jié)點外，每個結(jié)點有且僅有一個前驅(qū)結(jié)點，也就是說，每個結(jié)點與指向它的一個分支一一對應，所以除樹根結(jié)點之外的結(jié)點樹等于所有結(jié)點的分支數(shù)，即度數(shù)，從而可得樹

39、中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1?？偨Y(jié)點數(shù)為而度為0的結(jié)點數(shù)就應為總結(jié)點數(shù)減去度不為0的結(jié)點數(shù)的總和，即kknnnn.321321kiikkninnnnknnnnn13213210) 1(1).(.321第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構4、將算術表達式 (a+b)+c*(d+e)+f)*(g+h)轉(zhuǎn)化為二叉樹。 +*+fhg*+abc+de5、用一維數(shù)組存放的一棵完全二叉樹如下圖所示：ABCDEFGHIJKL寫出后序遍歷該二叉樹時訪問結(jié)點的順序。HIDJKEBLFGCA 第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構6、對下圖所示二叉樹分別按先序、中序后序遍歷，給出相應的結(jié)點序列，同時給二叉樹加

40、上中序線索。 （1）先序序列：ABDEHCFG（2）中序序列：DHEBAFCG（3）后序序列：HEDBFGCA ABCDFGEHnullnull第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構7、設一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列： ABDFCEGH 中序遍歷序列：BFDAGEHC（1）畫出這棵二叉樹。（2）將這棵二叉樹轉(zhuǎn)換成對應的樹（或森林）AEDCBHGFABFDCEHG第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構BACEDFNPGHJMOLIKHGDACJIBFEMPONKL8、將森林轉(zhuǎn)換成對應的二叉樹第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構9、一棵二叉樹的先序、中序、后序序列如下，其中一

41、部分未標出，請構造出該二叉樹。先序序列 ：_ _ C D E _ G H I _ K 中序序列 ：C B _ _ F A _ J K I G后序序列 ：_ E F D B _ J I H _ A ABCEDGIHFJK第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構10、設二叉樹BT的存儲結(jié)構如下: 12345678910Lchild 0 0 2 3 7 5 8 0 10 1DataJ H F D B A C E G IRchild 0 0 0 9 4 0 0 0 0 0其中BT為樹根結(jié)點的指針，其值為6,Lchild,Rchild分別為結(jié)點的左、右孩子指針域,data為結(jié)點的數(shù)據(jù)域。試完成下列各題:（

42、l）畫出二叉樹BT的邏輯結(jié)構;（2）寫出按先序、中序、后序遍歷該二叉樹所得到的結(jié)點序列;（3）畫出二叉樹的后序線索樹 。第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構BACEDFGHIJ先序序列：J中序序列： E C B H F D J I G A后序序列： BACEDFGHIJnullnull第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構11、給定集合15,3,14,2,6,9,16,17，(1) 構造相應的huffman樹，(2) 計算它的帶權路徑長度，(3) 寫出它的huffman編碼。16296170 115314011100001101wpl=(2+3)*5+6*4+(9+14+15)*3+(16+

43、17)*2=229 編碼為：15:111,3:10101,14:110,2:101006:10119:10016:0017:01 第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構12、已知下列字符A、B、C、D、E、F、G的權值分別為3、12、7、4、2、8，11，試填寫出其對應哈夫曼樹HT的存儲結(jié)構的初態(tài)和終態(tài)。 字符weightparentlchrch1A38002B1212003C710004D49005E28006F810007G111100859519911481015123611201397122713210134701112第7章 圖習題課中北大學信息與通信工程學院主講：金永 副教授第6章

44、 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構選擇題1、設無向圖的頂點個數(shù)為n，則該圖最多有（ B ）條邊。An-1 Bn(n-1)/2 C n(n+1)/2 D0 En22、一個n個頂點的連通無向圖，其邊的個數(shù)至少為（ A ）。An-1 Bn Cn+1 Dnlogn； 3、要連通具有n個頂點的有向圖，至少需要（ B ）條邊。An-l Bn Cn+l D2n4、一個有n個頂點的圖，最少有（ B ）個連通分量，最多有（ D ）個連通分量。A0 B1 Cn-1 Dn5、在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)（ B ）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（ C ）倍。 A1/2 B

45、2 C1 D4第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構6、下列哪一種圖的鄰接矩陣是對稱矩陣？（ B ）A有向圖 B無向圖 CAOV網(wǎng) DAOE網(wǎng) 7、無向圖G=(V,E),其中：V=a,b,c,d,e,f, E=(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（ D ）。 Aa,b,e,c,d,f Ba,c,f,e,b,d Ca,e,b,c,f,d Da,e,d,f,c,b8、圖中給出由7個頂點組成的無向圖。從頂點1出發(fā)，對它進行深度優(yōu)先遍歷得到的序列是( C)，而進行廣度優(yōu)先遍歷得到的頂點序列是（ C）。A135

46、4267 B1347652 C1534276 D1247653 A1534267 B1726453 Cl354276 D1247653第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構9、當各邊上的權值( A )時，BFS(廣度優(yōu)先搜索)算法可用來解決單源最短路徑問題。A均相等 B均互不相等 C不一定相等10、已知有向圖G=(V,E)，其中V=V1,V2,V3,V4,V5,V6,V7，E=, ,G的拓撲序列是（ A ）。AV1,V3,V4,V6,V2,V5,V7 BV1,V3,V2,V6,V4,V5,V7CV1,V3,V4,V5,V2,V6,V7 DV1,V2,V5,V3,V4,V6,V711、一個有向無

47、環(huán)圖的拓撲排序序列（ B ）是唯一的。A一定 B不一定12、在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是（ D ）。 AG中有弧 BG中有一條從Vi到Vj的路徑 CG中沒有弧 DG中有一條從Vj到Vi的路徑 第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構 13、關鍵路徑是事件結(jié)點網(wǎng)絡中（ A ）。A從源點到匯點的最長路徑 B從源點到匯點的最短路徑C最長回路 D最短回路 14、下列關于AOE網(wǎng)的敘述中，不正確的是（ B ）。A關鍵活動不按期完成就會影響整個工程的完成時間B任何一個關鍵活動提前完成，那么整個工程將會提前完成C所有的關鍵活動提前完成，那么整個工程將會提前完成D某

48、些關鍵活動提前完成，那么整個工程將會提前完成第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構1、判斷一個無向圖是一棵樹的條件是:n個頂點，n-1條邊的連通圖_2、具有10個頂點的無向圖，邊的總數(shù)最多為_45_。3、BFS遍歷和DFS遍歷圖的不同之處在于_，反映在數(shù)據(jù)結(jié)構上的差別是_。4、已知一無向圖G=（V，E），其中V=a,b,c,d,e E=(a,b),(a,d),(a,c),(d,c),(b,e)現(xiàn)用某一種圖遍歷方法從頂點a開始遍歷圖，得到的序列為abecd，則采用的是_遍歷方法。5、 一無向圖G(V,E)，其中V(G)=1,2,3,4,5,6,7，E(G)=(1,2),(1,3)，(2,4)，(

49、2,5)，(3,6)，(3,7)，(6,7)，(5,1),對該圖從頂點3開始進行遍歷，去掉遍歷中未走過的邊，得一生成樹G(V,E),V(G)=V(G)，E(G)=(1,3)，(3,6)，(7,3)，(1,2)，(1,5)，(2,4)，則采用的遍歷方法是_。 填空題第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構6、為了實現(xiàn)圖的廣度優(yōu)先搜索，除了一個標志數(shù)組標志已訪問的圖的結(jié)點外，還需_存放被訪問的結(jié)點以實現(xiàn)遍歷。7、構造連通網(wǎng)最小生成樹的兩個典型算法是_。 8、Prim（普里姆）算法適用于求_網(wǎng)的最小生成樹；kruskal（克魯斯卡爾）算法適用于求_網(wǎng)的最小生成樹。9、有一個用于n個頂點連通帶權無向圖的

50、算法描述如下：（1）設集合T1與T2，初始均為空；（2）在連通圖上任選一點加入T1；（3）以下步驟重復n-1次：a.在i屬于T1，j不屬于T1的邊中選最小權的邊；b.該邊加入T2。上述算法完成后，T2中共有_條邊，該算法稱_算法，T2中的邊構成圖的_。 第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構10、有向圖G可拓撲排序的判別條件是_。11、Dijkstra最短路徑算法從源點到其余各頂點的最短路徑的路徑長度按_次序依次產(chǎn)生，該算法弧上的權出現(xiàn)_情況時，不能正確產(chǎn)生最短路徑。 12、有向圖G=(V,E),其中 V(G)=0,1,2,3,4,5，用三元組表示弧及弧上的權d.E(G)為,，則從源點0到頂點

51、3的最短路徑長度是_，經(jīng)過的中間頂點是_。圖去掉有向弧看成無向圖則對應的最小生成樹的邊權之和為_。13、AOV網(wǎng)中,頂點表示_,邊表示_。AOE網(wǎng)中,頂點表示_,邊表示_。 第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構應用題1、設有數(shù)據(jù)邏輯結(jié)構為：B = (K, R), K = k1, k2, , k9R=, , , , , , , , （1）畫出這個邏輯結(jié)構的圖示。（2）相對于關系r, 指出所有的開始頂點和終端頂點。（3）分別對關系r中的開始頂點，舉出一個拓撲序列的例子。（4）分別畫出該邏輯結(jié)構的正向鄰接表和逆向鄰接表。第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構K9K1K3K8K7K5K4K2K6（2

52、）開始頂點：K1，K2; 終端頂點:K6，K7;（3）拓撲序列 K1，K2，K3，K4，K5，K6，K8，K9，K7; K2，K1，K3，K4，K5，K6，K8，K9，K7;（1）（4）第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構2、已知某圖的鄰接表為（1）寫出此鄰接表對應的鄰接矩陣；（2）寫出由v1開始的深度優(yōu)先遍歷的序列；（3）寫出由v1開始的深度優(yōu)先的生成樹；（4）寫出由v1開始的廣度優(yōu)先遍歷的序列；（5）寫出由v1開始的廣度優(yōu)先的生成樹；v1v2v3v4v5v6121124355634第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構（2）V1V2V5V3V4V6（3）（5）（4） V1V2V3V4V5

53、V6第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構3、如下所示的連通圖，請畫出：（1）以頂點為根的深度優(yōu)先生成樹；（2）如果有關節(jié)點，請找出所有的關節(jié)點。（2）關節(jié)點有3，1，8，7，2（1）第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構4、對圖示的AOE網(wǎng)絡，計算各活動弧的ee(Vi)和el(Vi)的函數(shù)值，各事件（頂點）的ve(Vj）和vl (Vj)的函數(shù)值，列出各條關鍵路徑。 第6章 樹和二叉樹習題課算法與數(shù)據(jù)結(jié)構1、試寫出用克魯斯卡爾（Kruskal）算法構造下圖的一棵最小生成樹的過程。 3、試利用Dijkstra算法求下圖中從頂點a到其他個頂點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)。 bgdea

54、fc122894510246152、按Prim算法求無向加權圖的最小生成樹，并給出構造最小生成樹過程中輔助數(shù)組的各分量值課堂練習題第10章 排序算法與數(shù)據(jù)結(jié)構第910章 習題課第10章 排序算法與數(shù)據(jù)結(jié)構1、對線性表進行二分查找時，要求線性表必須（ D ）A.以順序方式存儲 B.以順序方式存儲,且數(shù)據(jù)元素有序 C.以鏈接方式存儲D.以鏈接方式存儲,且數(shù)據(jù)元素有序2、用二分（折半）查找表的元素的速度比用直接插入法( D )A 必然快 B. 必然慢 C. 相等 D. 不能確定3、二叉查找樹的查找效率與二叉樹的( （1）C )有關, 在 (（2）C )時其查找效率最低。 (1): A. 高度 B. 結(jié)點的多少 C. 樹型 D. 結(jié)點的位置 (2): A. 結(jié)點太多 B. 完全二叉樹 C. 呈單枝樹 D. 結(jié)點太復雜。第10章 排序算法與數(shù)據(jù)結(jié)構4、設有一組記錄的關鍵字為19，14，23，1，68，20，84，27，55，11，10，79，用鏈地址法構造散列表，散列函數(shù)為H（key）=key MOD 11,散列地址為1的鏈中有（ B ）個記錄。A1 B. 2 C. 3 D. 4 5、下面關于哈希(Hash)查找的說法正確的是( C )A哈希函數(shù)構造的越復雜越好，因為這樣隨機