中北大學數據結構習題

1、算法與數據結構習題第一到三章習題選擇題1 .對于順序存儲的線性表，訪問結點和增加、刪除結點的時間復雜度為(C)0A.O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)2 .非空的循環(huán)單鏈表 head 的尾結點 p 滿足(A)。A.P-next=headB.P-next=NILC,p=NILD,p=head3 .在單鏈表指針為 p 的結點之后插入指針為 s 的結點，正確的操作是：(B)oA.p-next=s;s-next=p-next;Bs-next=p-next;p-next=s;C.p-next=s;p-next=s-next;Dp-next=s-next;p-ne

2、xt=s;4 .在雙向鏈表指針 p 的結點前插入一個指針 q 的結點操作是(C)注：雙向鏈表的結點結構為(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 .棧的特點是(B),隊列的特點是(A)，棧和隊列都是(AA)。若進棧序列為 1,2,3,4 則(C)不可能是一個出棧序

3、列(不一定全部進棧后再出棧)；若進隊列的序列為 1,2,3,4 則(E)是一個出隊列序列。，:A.先進先出 B.后進先出 C.進優(yōu)于出 D.出優(yōu)于進：A.順序存儲的線性結構 B.鏈式存儲的線性結構C.限制存取點的線性結構 D.限制存取點的非線性結構，:A.3,2,1,4B.3,2,4,1C.4,2,3,1D.4,3,2,1E.1,2,3,4F.1,3,2,46 .一個棧的輸入序列為 123,n,若輸出序列的第一個元素是 n,輸出第 i(1=inext;p2=pb-next;pa-next=null;s1=0;s2=0;Q.front=(Q.front+1)%Q.queuesize;Q.rear

4、=(Q.rear+1)%Q.queuesize;A.1 和 5B.2C.414.循環(huán)隊列 A0.m-1存放其元素值，用則當前隊列中的元素數是(A)0A.(rear-front+m)%mB.rear-front+1和 2D.5 和 1front 和 rear 分別表示隊頭和隊尾,C.rear-front-1D.rear-frontWhile(p1&p2)if(p1-datadata)p=p1;p1=p1-next;s2=s2+1;delete(p);elseif(p1-datap2-data)p2=p2-next;else(p1-data=p2-data)p=p1;p1=p1-next;

5、p-next=pa-next;pa-next=p;p2=p2-next;s1=s1+1;While(p1)p=p1;p1=p1-next;delete(p);s2=s2+1解：本程序段功能是將 pa 和 pb 鏈表中的值相同的結點保留在 pa 鏈表中(pa 中與 pb中不同結點刪除)，pa 是結果鏈表的頭指針。鏈表中結點值與從前逆序。S1 記結果鏈表中結點個數(即 pa 與 pb 中相等的元素個數)。S2 記原 pa 鏈表中刪除的結點個數。算法題1.寫出下圖雙鏈表中對換值為 23 和 15 的兩個結點相互位置時修改指針的有關語句。結點結構為：(pre,data,next)解：設 q=p-pre

6、;貝 Uq-next=p-next;p-next-pre=q;p-pre=q-pre;q-pre-next=p;p-next=q;q-pre=p2 .順序結構線性表 LA 與 LB 的結點關鍵字為整數。LA 與 LB 的元素按非遞減有序，線性表空間足夠大。試給出一種高效算法，將 LB 中元素合到 LA 中，使新的 LA的元素仍保持非遞減有序。高效指最大限度的避免移動元素。解：VoidUnion(seqlistLA,seqlistLB)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.elem

7、j)LA.elemk=LA.elemi;k=k-1;i=i-1;elseLA.elemk=LB.elemj;k=k-1;j=j-1;while(j=0)LA.elemk=LB.elemj;k=k-1;j=j-1;3 .給定一個帶表頭結點的單鏈表，設 head 為頭指針，結點的結構為(data,next),data 為整型元素，next 為指針；試寫出算法：按遞增次序輸出單鏈表中各結點的數據元素，并釋放結點所占的存儲空間。(要求；不允許使用數組作輔助空間)解：voidMiniDelete(LinkedListhead)LinkedList*pre,*p,*u;while(head-next!=n

8、ull)/循環(huán)到僅剩頭結點。pre=head;p=pre-next;/p 為工作指針,pre 為最/4 值的前驅while(p-next!=null)if(p-next-datanext-data)pre=p；p=p-next;/記住當前最小值結點的前驅print(%2d,pre-next-data);/輸出最小值。u=pre-next;pre-next=u-next;free(u);/刪除最小結點free(head)；/釋放頭結點。4,試寫一算法在帶頭結點的單鏈表結構上實現線性表操作 Locate(L,x);解：intLocateElem_L(LinkList&L,ElemTypex

9、)inti=0;LinkListp=L;while(p&p-data!=x)p=p-next;i+;if(!p)return0;elsereturni;5,已知單鏈表中的元素以值遞增有序排列。試寫一高效的算法，刪除表中所有值大于mink 且小于 maxk 的元素，同時釋放被刪結點空間。解：voiddelete(LinkList&L,intmink,intmaxk)p=L-next;pre匚umaxk=maL?cldatanext;/查找第一個值mink 的結點if(P)while(p&p-datanext;/查找第一個值maxk 的結點q=pre-next;pre-ne

10、xt=p;/修改指針while(q!=p)s=q-next;deleteq;q=s;/釋放結點空間/delete6.試寫一高效的算法，刪除表中所有值相同的多余元素(使得操作后的線性表中所有元素的值均不相同)，同時釋放被刪結點空間，并分析你的算法的時間復雜度。已知一個非純集合 B,試構造一個純集合 A,使 A中只包含 B中所有值各不相同的數據元素從集合 B 取出物件放入集合 A要求集合 A 中同樣物件不能有兩件以上因此，算法的策略應該和例 2-1 基本相同，差別僅在于集合 A 的初始狀態(tài)是“空集”voidunion(List&La,ListLb)InitList(La);/構造(空的)線

11、性表 LALa_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取 Lb 中第 i 個數據元素賦給 eif(!LocateElem(La,e,equal()ListInsert(La,+La_len,e);/LaG 未存在和 e 相同的數據元素，則插入之/for/union例如：(2,3,3,5,6,6,6,8,12)對集合 B 而言，值相同的數據元素必定相鄰對集合 A 而言，數據元素依值從小至大的順序插入因此，數據結構改變了，解決問題的策略也相應要改變。voidpurge(List&a

12、mp;La,ListLb)InitList(LA);La_len=ListLength(La);Lb_len=ListLength(Lb);/求線性表的長度for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);/取 Lb 中第 i 個數據元素賦給 eif(ListEmpty(La)|!equal(en,e)ListInsert(La,+La_len,e);en=e;/La 中不存在和 e 相同的數據元素，則插入之/for/purge第四章串習題1 .下面關于用的的敘述中，哪一個是不正確的？(B)A.用是字符的有限序列 B.空用是由空格構成的用C.模式匹配是用的一種重要運算 D

13、.用既可以采用順序存儲，也可以采用鏈式存儲2 .設有兩個用 p 和 q,其中 q 是 p 的子用，求 q 在 p 中首次出現的位置的算法稱為(C)A.求子用 B.聯接 C.匹配 D.求用長3 .用ababaaababaa的 next 數組為(C)。A.012345678999B.012121111212C.011234223456D.01230123223454 .字符用ababaabab的 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)5、設字符用

14、 S=aabaabaabaac,T=aabaac(1)給出 S 和 T 的 next 值和 nextval 值；(2)若 S 作主用，T 作模式用，試給出利用 BF 算法和 KMPJ 法的匹配過程。解：(1)S 的 next 與 nextval 值分另為 012123456789 和 002002002009;t 的 next 與 nextval 值分別為 012123 和 002003。(2)利用 BF 算法的匹配過程:第趟匹酉己：aabaabaabaacaabaac(i=6,j=6)aabaac(i=6,j=6)第二趟匹酉己：aabaabaabaacaa(i=3,j=2)(aa)baac第

15、三趟匹酉己：aabaabaabaaca(i=3,j=1)(成功)(aa)baac第四趟匹酉己：aabaabaabaacaabaac(i=9,j=6)第五趟匹酉己：aabaabaabaacaa(i=6,j=2)第六趟匹酉己：aabaabaabaaca(i=6,j=1)第七趟匹酉己：aabaabaabaac利用 KMPJ 法的匹配過程:第趟匹酉己：aabaabaabaac第二趟匹酉己：aabaabaabaac第三趟匹酉己：aabaabaabaac第6章樹和二叉樹習題選擇題1、 已知一算術表達式的中綴形式為 A+B*C-D/E,后綴形式為 ABC*+DE/-,其前綴形式為（D）A. -A+B*C/D

16、EB.-A+B*CD/EC.-+*ABC/DED.-+A*BC/DE2、設森林 F 中有三棵樹，第一，第二，第三棵樹的結點個數分別為 M1,M2 和M3 與森林 F 對應的二叉樹根結點的右子樹上的結點個數是（D）。3、有關二叉樹下列說法正確的是（A.二叉樹的度為 2B. 一棵二叉樹白度可以小于 2C.二叉樹中至少有一個結點的度為D.二叉樹中任何一個結點的度都為 4、二叉樹的第 I 層上最多含有結點數為（C）A.2IB.2I-1-1C.2I-1D.2I-15、一個具有 1025 個結點的二叉樹的高八為（C）A.11B.10C.11 至 1025 之間 D解析：具有 n6、高度為 K 的二叉樹最大

17、的結點數為（C）。A.2kB.2k-1C.2k-1D.2k-1-17、利用二叉鏈表存儲樹，則根結點的右指針是（C）。A.指向最左孩子 B.指向最右孩子C.空 D.非空8、對二叉樹的結點從 1 開始進行連續(xù)編號，要求每個結點的編號大于其左、右孩子的編號，同一結點的左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（C）次序的遍歷實現編號。A.先序 B.中序 C.后序 D.從根開始按層次遍歷9、某二叉樹中序序列為 A,B,C,D,E,F,G,后序序列為 B,D,C,A,F,G,E 則先序序列是：BA.E,G,F,A,C,D,BB.E,A,C,B,D,G,FC.E,A,G,C,F,B,DD.上面的

18、都不對10、上題的二叉樹對應的森林包括多少棵樹（B）A.lB.2C.3D.概念上是錯誤的11、一棵非空的二叉樹的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹一定滿足（C）A.所有的結點均無左孩子 B.所有的結點均無右孩子C.只有一個葉子結點 D.是任意一棵二叉樹12、在二叉樹結點的先序序列，中序序列和后序序列中，所有葉子結點的先后順序（B）A.都不相同 B.完全相同成功）aabaac(i=13,j=7)A.M1B.M1+M2C.M2+M310 至 1024 之間C.先序和中序相同，而與后序不同 D.中序和后序相同，而與先序不同 13、在完全二叉樹中，若一個結點是葉結點，則它沒（C）。A.左子

19、結點 B.右子結點C.左子結點和右子結點 D.左子結點，右子結點和兄弟結點14、n 個結點的線索二叉樹上含有的線索數為（C）A.2nB.n-lC.n+1D.n（解析：一棵 n 結點樹包含 n-1 條邊，而每個結點有兩個指針域即總共 2n 個指針，減去表示邊的指向關系（即左右子樹）的 n-1 條邊，剩下 n+1 條邊即為線索。）15、下述編碼中哪一個不是前綴碼（B）。A.（00,01,10,11）B.（0,1,00,11）C.（0,10,110,111）D.（1,01,000,001）（解析：一組編碼中任何一個編碼均不為其他編碼的前綴.避免了多義性，且縮短了報文總長）16、在下述結論中，正確的是

20、（D）只有一個結點的二叉樹的度為 0；二叉樹的度為 2;二叉樹的左右子樹可任意交換；深度為 K 的完全二叉樹的結點個數小于或等于深度相同的滿二叉樹。A.B.C.D.17、若一棵二叉樹具有 10 個度為 2 的結點，5 個度為 1 的結點，則度為 0 的結點個數是（B）A.9B.11C.15D.不確定（解析： 任意一棵二叉樹， 度為零的節(jié)點即葉子節(jié)點的數比度為二的節(jié)點多一。 ） 18、具有 10 個葉結點的二叉樹中有（B）個度為 2 的結點A.8B.9C.10D.1l19、一棵完全二叉樹上有 1001 個結點，其中葉子結點的個數是（D）（1023 是滿二叉樹，有 512 片葉子。1001 比 1

21、023 少 22 個結點，所以有 512-22+22/2=501 片葉子。511 是滿二叉樹，有 256 片葉子。1001 比 511 多 490 個結點，所以有 256+490-（490+1）/2=501 片葉子。所以答案就是 501 了。）A.250B.500C.254D.50120、有 n 個葉子的哈夫曼樹的結點總數為（D）。A,不確定 B.2nC.2n+1D.2n-121、二叉樹的先序遍歷和中序遍歷如下：先序遍歷：EFHIGJK 中序遍歷:HFIEJKG。該二叉樹根的右子樹的根是（C）。A、EB、FC、GD、H22、設森林 F 對應的二叉樹為 B,它有 m 個結點，B 的根為 p,p

22、的右子樹結點個數為 n,森林 F 中第一棵樹的結點個數是（A）A.m-nB.m-n-1C.n+1D.條件不足，無法確定23、用一維數組存儲二叉樹時，總是以（D）遍歷順序存儲結點A.先序 B.中序 C.后序 D,按層次遍歷24、對一棵二叉樹進行層次遍歷時，應借助于一個（D）。A.順序表 B.數組 C.棧 D.隊列25、某二叉樹的先序序列和后序序列正好相反，則該二叉樹一定是（C）的二叉樹。A.空或只有一個結點 B.任一結點無左子樹 C,高度等于其結點數 D.任一結點無右子樹26、設樹 T 的度為 4,其中度為 1,2,3 和 4 的結點個數分別為 4,2,1,1 則 T 中的葉子數為（D）A.5B

23、.6C.7D.8（設度為 0 的結點數為 n0,度為 1 的結點數為 n1,度為 2 的結點數為 n2,度為 3 的結點數為 n3,度為 4 的結點數為 n4,那么這棵樹總的結點數為 n0+n1+n2+n3+n4;又因為樹中的每個結點（除了根結點外）都有一個指針指向它，那么這棵樹總的結點數為總的指針數加上 1;總的指針數=1*n1+2*n2+3*n3+4*n4;故有：1+1*n1+2*n2+3*n3+4*n4=n0+n1+n2+n3+n4;從而有n0=1+n2+2*n3+3*n4=1+2+2*1+3*1=8;）27、將一棵樹 t 轉換為孩子一兄弟鏈表表示的二叉樹 h,則 t 的后根序遍歷是 h

24、 的（B）A.先序遍歷 B.中序遍歷 C.后序遍歷28、某二叉樹 T 有 n 個結點，設按某種順序對 T 中的每個結點進行編號，編號為 1,2,n,且有如下性質：T 中任一結點 V,其編號等于左子樹上的最小編號減 1,而 V 的右子樹的結點中，其最小編號等于 V左子樹上結點的最大編號加 1。這時是按（B）編號的。A.中序遍歷序列 B.先序遍歷序列 C.后序遍歷序列 D.層次順序應用題1、從概念上講，樹，森林和二叉樹是三種不同的數據結構，將樹，森林轉化為二叉樹的基本目的是什么，并指出樹和二叉樹的主要區(qū)別。答：樹的孩子兄弟鏈表表示法和二叉樹二叉鏈表表示法，本質是一樣的，只是解釋不同，也就是說樹（森

25、林的特例）可用二叉樹唯一表示，并可使用二叉樹的一些算法去解決樹和森林中的問題。樹和二叉樹的區(qū)別有：一是二叉樹的度至多為 2,樹無此限制；二是二叉樹有左右子樹之分，即使在只有一個分枝的情況下，也必須指出是左子樹還是右子樹，樹無此限制。2、試找出滿足下列條件的二叉樹1）先序序列與后序序列相同；2）中序序列與后序序列相同；3）先序序列與中序序列相同；1）、既不含左子樹，也不含右子樹的二叉樹。2）、不含右子樹的二叉樹。3)、不含左子樹的二叉樹。3、已知一棵度為 k 的樹中有 ni個度為 1 的結點，奧個度為 2 的結點，一個度為 k 的結點，問該樹中有多少個葉子結點？解：根據樹的定義，在一顆樹中，除樹

26、根結點外，每個結點有且僅有一個前驅結點，也就是說，每個結點與指向它的一個分支一一對應，所以除樹根結點之外的結點樹等于所有結點的分支數，即度數，從而可得樹中的結點數等于所有結點的度數加 1?？偨Y點數為1n12n23n3knk而度為 0 的結點數就應為總結點數減去度不為 0 的結點數的總和，即kn0=1n12n23n3.knk-(nn2n3nk)=1%(i1)ni-J5、用一維數組存放的一棵完全二叉樹如下圖所示:ABCDEFGHIJKL寫出后序遍歷該二叉樹時訪問結點的順序。解析：用一維數組存儲二叉樹時，總是以層次遍歷順序存儲結點答：HIDJKEBLFGCA6、對下圖所示二叉樹分別按先序、中序、后序

27、遍歷，給出相應的結點序列，同時給二叉樹加上中序線索。(1)先序序列：ABDEHCFG(2)中序序列：DHEBAFCG(3)后序序列：HEDBFGCAA7、設一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列：CnullABDFCEGH中A序遍歷 JWhBFDAGEHC(1)畫出這棵二叉樹。(2)將這棵二叉樹轉換成對應的樹(或森林)尸Q(0(8、將森林轉換成對應的二叉樹 oa11i?J)cMJo)Pb9、一棵二叉樹的先序、中序、后序序列如下，其中一部分未標出，請構造出該二叉樹。先序序列：_CDE_GHI_K 中序序列：CB_FA_JKIG 后序序列：EFDBJIHA12345678910Lchil

28、d00237580101DataJHFDBACEGIRchild0009400000其中 BT 為樹根結點的指針，具值為 6,Lchild,Rchild 分別為結點的左、右孩子指針域,data 為結點的數據域。試完成下列各題：(l)畫出二叉樹 BT 的邏輯結構；(2)寫出按先序、中序、后序遍歷該二叉樹所得到的結點序列；(3)畫出二叉樹的后序線索樹。先序序列：ABCEDFHGIJ中序序列：ECBHFDJIGA后序序列：ECHFJIGDBA11、給定集合15,3,14,2,6,9,16,17,(1)構造相應的 huffman 樹，(2)計算它的帶權路徑長度，(3)寫出它的 huffman 編碼。編

29、碼為：15:111,3:10101,14:110,2:101006:10119:10016:0017:01字符weightparentlchrch1A38002B1212003C710004D49005E28006F810007G11110012、已知下列字符 A、B、C、DE、F、G 的權值分別為 3、12、7、4、2、8,試填寫出其對應哈夫曼樹11,nullHT 的存儲結構的初態(tài)和終859519911481015123611201397122713210134701112第七章圖習題選擇題1、設無向圖的頂點個數為 n,則該圖最多有（B）條邊。_一_2A.n-1B.n（n-1）/2C.n（n

30、+1）/2D.0E.n2、一個 n 個頂點的連通無向圖，其邊的個數至少為（A）。A.n-1B.nC.n+1D.nlogn；3、要連通具有 n 個頂點的有向圖，至少需要（B）條邊。A.n-lB.nC.n+lD.2n4、一個有 n 個頂點的圖，最少有（B）個連通分量，最多有（D）個連通分量。A.0B.1C.n-1D.n5、在一個無向圖中，所有頂點的度數之和等于所有邊數（B）倍，在一個有向圖中，所有頂點的入度之和等于所有頂點出度之和的（C）倍。A.1/2B.2C,1D6、下列哪一種圖的鄰接矩陣是對稱矩陣？（B）A.有向圖 B.無向圖 C.AOD.AO 如7、無向圖 G=(V,E),E=(a,b),(

31、a,e),(a,c),(b,e),(c,f),(f,d),(e,d)歷,得到的頂點序列正確的是(D)A.a,b,e,c,d,fBC.a,e,b,c,f,dD其中：V=a,b,c,d,e,f,對該圖進行深度優(yōu)先遍.a,c,f,e,b,d.a,e,d,f,c,b8、圖中給出由 7 個頂點組成的無向圖。從頂點1 出發(fā)，對它進行深度優(yōu)先遍歷得到的序列是（C）,而進行廣度優(yōu)先遍歷得到的頂點序列是（C）.A,1354267B.1347652C.1534276D.1247653.A.1534267B.1726453C.l354276D.124765310、已知有向圖 G=（V,E）,其中 V=V1,V2,V

32、3,V4,V5,V6,V7,E=,G 的拓撲序列是（A）。A.V1,V3,V4,V6,V2,V5,V7BC.V1,V3,V4,V5,V2,V6,V7D11、一個有向無環(huán)圖的拓撲排序序列（A.一定 B.不一定出現的是(D)。A.G 中有弧B.G 中有一條從 Vi 到 Vj 的路徑C.G 中沒有弧D.G 中有一條從 Vj 到 Vi 的路徑 13、 關鍵路徑是事件結點網絡中(A)。A.從源點到匯點的最長路徑 B.從源點到匯點的最短路徑C.最長回路 D.最短回路14、下列關于 AOEH 的敘述中，不正確的是(B)A.關鍵活動不按期完成就會影響整個工程的完成時間B.任何一個關鍵活動提前完成，那么整個工程

33、將會提前完成C.所有的關鍵活動提前完成，那么整個工程將會提前完成D.某些關鍵活動提前完成，那么整個工程將會提前完成填空題1、判斷一個無向圖是一棵樹的條件是有(n 個頂點，n-1 條邊的連通圖)2、具有 10 個頂點的無向圖，邊的總數最多為(45)。3、BFS 遍歷和 DFS 遍歷圖的不同之處在于(訪問的次序不同)，反映在數據結構上的差別是(深度優(yōu)先遍歷采用遞歸算法，廣度優(yōu)先遍歷采用隊列算法)4、已知一無向圖 G=(V,E),其中 V=a,b,c,d,eE=(a,b),(a,d),(a,c),(d,c),(b,e)現用某一種圖遍歷方法從頂點 a 開始遍歷圖，得到的序列為 abecd,則采用的是(

34、深度優(yōu)先)遍歷方法。5、一無向圖 G(V,E),其中 V(G)=1,2,3,4,5,6,7,E(G)=(1,2),(1,3),(2,4),(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),則采用的遍歷方法是（廣度優(yōu)先遍歷）6、為了實現圖的廣度優(yōu)先搜索，除了一個標志數組標志已訪問的圖的結點外，還需（隊.V1,V3,V2,V6,V4,V5,V7.V1,V2,V5,V3,V4,V6,V7B）是唯一的。12、在有

35、向圖 G 的拓撲序列中，若頂點Vi 在頂點 Vj 之前，則下列情形不可能9、當各邊上的權伯：(A)時，BFSlT 度優(yōu)先)算法可用來解決單源最短路徑問題A.均相等 B.均互不相等 C.不一定相等列）存放被訪問的結點以實現遍歷。7、構造連通網最小生成樹的兩個典型算法是（Prim/普里姆算法和 kruskal/克魯斯卡爾算法）。8、Prim（普里姆）算法適用于求（偏稠密）網的最小生成樹；kruskal（克魯斯卡爾）算法適用于求（偏稀疏）網的最小生成樹。9、有一個用于 n 個頂點連通帶權無向圖的算法描述如下：（1）設集合 T1 與 T2,初始均為空；（2）在連通圖上任選一點加入 T1;（3）以下步驟

36、重復 n-1 次：a.在 i 屬于 T1,j 不屬于 T1 的邊中選最小權的邊；b.該邊加入 T2。上述算法完成后，T2 中共有（n-1）條邊，該算法稱（Prim）算法，T2 中的邊構成圖的（最小生成邊）。10、有向圖 G 可拓撲排序的判別條件是（圖中不存在環(huán)）。11、Dijkstra 最短路徑算法從源點到其余各頂點的最短路徑的路徑長度按（遞增）次序依次產生，該算法弧上的權出現（負值）情況時，不能正確產生最短路徑。12、有向圖 G=（V,E）,其中 V（G 尸0,1,2,3,4,5,用三元組表示弧及弧上的權 d.E（G）為,則從源點 0 到頂點 3 的最短路徑長度是（50）,經過的中間頂點是（

37、4）0圖去掉有向弧看成無向圖則對應的最小生成樹的邊權之和為（75）。13、AOV3 中，頂點表示（事件），邊表示（各事件的優(yōu)先關系）。AO 刎中，頂點表?。ㄊ录?，邊表小（活動）。應用題1、設有數據邏輯結構為：B=（K,R）,K=k1,k2,kR=,（1） .畫出這個邏輯結構的圖示。（2） .相對于關系 r,指出所有的開始頂點和終端頂點。（3） .分別對關系 r 中的開始頂點，舉出一個拓撲序列的例子。（4） .分別畫出該邏輯結構的正向鄰接表和逆向鄰接表。9(2)開始頂點：K1,K2;終端頂點:K6,K7;(3)拓撲序列,K2,K3,K4,K5,K6,K8,K9,K1,K3,K4,K5,K6,K

38、8,K9,K1K2K3K4K5K6K7K8K92、已知某圖的鄰接表為(2)V1V2V5V3V4V612345(y7S9K1K2K3K4K5K6K7K8K9囚*O卡|6H7H1|6|A|-FTIAK7;(1).寫出此鄰接表對應的鄰接矩陣；(2).寫出由 v1 開始的深度優(yōu)先遍歷的序列;(3).寫出由 v1 開始的深度優(yōu)先的生成樹；(4),寫出由 v1 開始的廣度優(yōu)先遍歷的序列;(5).寫出由 v1 開始的廣度優(yōu)先的生成樹；K1K2K7;23456789-2A|(3) V1V2V3V4V5V6(4)3、如下所示的連通圖,(1) .以頂點為根的深度優(yōu)先生成樹；(2) .如果有關節(jié)點，請找出所有的關節(jié)

39、點(2)關節(jié)點有 3,1,8,7,24、 對圖示的AOES絡， 計算各活動弧的ee(Vi)和el(Vi)的函數值， 各事件(頂點)的ve(Vj)和 vl(Vj)的函數值，列出各條關鍵路徑。課堂練習題Kruskal)算法構造下圖的一棵最小生成樹的過程。1、試寫出用克魯斯卡爾(請畫出:03、試利用 Dijkstra 算法求下圖中從頂點 a 到其他個頂點間的最短路徑，寫出執(zhí)行算法過程中各步的狀態(tài)第九、十章查找和內部排序習題1、對線性表進行二分查找時，要求線性表必須（B）A.以順序方式存儲B.以順序方式存儲,且數據元素有序C.以鏈接方式存儲D.以鏈接方式存儲,且數據元素有序2、用二分（折半）查找表的元

40、素的速度比用直接插入法（D）A 必然快 B.必然慢 C.相等 D.不能確定3、二叉查找樹的查找效率與二叉樹的（C）有關，在（C）時其查找效率最低（1）:A.高度 B.結點的多少 C.樹型 D.結點的位置（2）:A.結點太多 B.完全二叉樹 C.呈單枝樹 D.結點太復雜。4、 設有一組記錄的關鍵字為19,14,23,1,68,20,84,27,55,11,10,79,用鏈地址法構造散列表，散列函數為 H（key）=keyMOD11,散列地址為 1 的鏈中有（B）個記錄。A.1B.2C.3D.45、下面關于哈希（Hash）查找的說法正確的是（C）A.哈希函數構造的越復雜越好，因為這樣隨機性好，沖突

41、小B.除留余數法是所有哈希函數中最好的C.不存在特別好與壞的哈希函數，要視情況而定D.若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要簡單的將該元素刪去即可6、 設哈希表長為14,哈希函數是H （key尸key%11,表中已有數據的關鍵字為15,38,61,84共四個，現要將關鍵字為 49 的結點加到表中，用二次探測再散列法解決沖突，則放入的位置是（D）A.8B.3C.5D.97、散列表的地址區(qū)間為 0-17,散列函數為 H（K）=Kmod17。采用線性探測法處理沖突，助數組的各分量值并將關鍵字序列 26,25,72,38,8,18,59 依次存儲到散列表中。（1）元素 59 存放在散列表中的地址是（D）。A.8B.9C.10D.11（2）存放元素 59 需要搜索的次數是（B）。A.2B.3C.4D.58、下面給出的四種排序法中（D）排序法是不穩(wěn)定性排序法A、插入 B.冒泡 C.二路歸并 D.堆9、 如果待排序序列中兩個數據元素具有相同的值， 在排序前后它們的相互位置發(fā)生顛倒，則稱該排序算法是不穩(wěn)定的。（C）就是