中北大學(xué)數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題第一到三章習(xí)題選擇題1 .對(duì)于順序存儲(chǔ)的線性表，訪問(wèn)結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度為(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 的尾結(jié)點(diǎn) p 滿足(A)。A.P-next=headB.P-next=NILC,p=NILD,p=head3 .在單鏈表指針為 p 的結(jié)點(diǎn)之后插入指針為 s 的結(jié)點(diǎn)，正確的操作是：(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 的結(jié)點(diǎn)前插入一個(gè)指針 q 的結(jié)點(diǎn)操作是(C)注：雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(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 .棧的特點(diǎn)是(B),隊(duì)列的特點(diǎn)是(A)，棧和隊(duì)列都是(AA)。若進(jìn)棧序列為 1,2,3,4 則(C)不可能是一個(gè)出棧序

3、列(不一定全部進(jìn)棧后再出棧)；若進(jìn)隊(duì)列的序列為 1,2,3,4 則(E)是一個(gè)出隊(duì)列序列。，:A.先進(jìn)先出 B.后進(jìn)先出 C.進(jìn)優(yōu)于出 D.出優(yōu)于進(jìn)：A.順序存儲(chǔ)的線性結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C.限制存取點(diǎn)的線性結(jié)構(gòu) D.限制存取點(diǎn)的非線性結(jié)構(gòu)，: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 .一個(gè)棧的輸入序列為 123,n,若輸出序列的第一個(gè)元素是 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)隊(duì)列 A0.m-1存放其元素值，用則當(dāng)前隊(duì)列中的元素?cái)?shù)是(A)0A.(rear-front+m)%mB.rear-front+1和 2D.5 和 1front 和 rear 分別表示隊(duì)頭和隊(duì)尾,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 鏈表中的值相同的結(jié)點(diǎn)保留在 pa 鏈表中(pa 中與 pb中不同結(jié)點(diǎn)刪除)，pa 是結(jié)果鏈表的頭指針。鏈表中結(jié)點(diǎn)值與從前逆序。S1 記結(jié)果鏈表中結(jié)點(diǎn)個(gè)數(shù)(即 pa 與 pb 中相等的元素個(gè)數(shù))。S2 記原 pa 鏈表中刪除的結(jié)點(diǎn)個(gè)數(shù)。算法題1.寫(xiě)出下圖雙鏈表中對(duì)換值為 23 和 15 的兩個(gè)結(jié)點(diǎn)相互位置時(shí)修改指針的有關(guān)語(yǔ)句。結(jié)點(diǎn)結(jié)構(gòu)為：(pre,data,next)解：設(shè) 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 .順序結(jié)構(gòu)線性表 LA 與 LB 的結(jié)點(diǎn)關(guān)鍵字為整數(shù)。LA 與 LB 的元素按非遞減有序，線性表空間足夠大。試給出一種高效算法，將 LB 中元素合到 LA 中，使新的 LA的元素仍保持非遞減有序。高效指最大限度的避免移動(dòng)元素。解：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 .給定一個(gè)帶表頭結(jié)點(diǎn)的單鏈表，設(shè) head 為頭指針，結(jié)點(diǎn)的結(jié)構(gòu)為(data,next),data 為整型元素，next 為指針；試寫(xiě)出算法：按遞增次序輸出單鏈表中各結(jié)點(diǎn)的數(shù)據(jù)元素，并釋放結(jié)點(diǎn)所占的存儲(chǔ)空間。(要求；不允許使用數(shù)組作輔助空間)解：voidMiniDelete(LinkedListhead)LinkedList*pre,*p,*u;while(head-next!=n

8、ull)/循環(huán)到僅剩頭結(jié)點(diǎn)。pre=head;p=pre-next;/p 為工作指針,pre 為最/4 值的前驅(qū)while(p-next!=null)if(p-next-datanext-data)pre=p；p=p-next;/記住當(dāng)前最小值結(jié)點(diǎn)的前驅(qū)print(%2d,pre-next-data);/輸出最小值。u=pre-next;pre-next=u-next;free(u);/刪除最小結(jié)點(diǎn)free(head)；/釋放頭結(jié)點(diǎn)。4,試寫(xiě)一算法在帶頭結(jié)點(diǎn)的單鏈表結(jié)構(gòu)上實(shí)現(xiàn)線性表操作 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,已知單鏈表中的元素以值遞增有序排列。試寫(xiě)一高效的算法，刪除表中所有值大于mink 且小于 maxk 的元素，同時(shí)釋放被刪結(jié)點(diǎn)空間。解：voiddelete(LinkList&L,intmink,intmaxk)p=L-next;pre匚umaxk=maL?cldatanext;/查找第一個(gè)值mink 的結(jié)點(diǎn)if(P)while(p&p-datanext;/查找第一個(gè)值maxk 的結(jié)點(diǎn)q=pre-next;pre-ne

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

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

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

13、.用既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)2 .設(shè)有兩個(gè)用 p 和 q,其中 q 是 p 的子用，求 q 在 p 中首次出現(xiàn)的位置的算法稱(chēng)為(C)A.求子用 B.聯(lián)接 C.匹配 D.求用長(zhǎng)3 .用ababaaababaa的 next 數(shù)組為(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、設(shè)字符用

14、 S=aabaabaabaac,T=aabaac(1)給出 S 和 T 的 next 值和 nextval 值；(2)若 S 作主用，T 作模式用，試給出利用 BF 算法和 KMPJ 法的匹配過(guò)程。解：(1)S 的 next 與 nextval 值分另為 012123456789 和 002002002009;t 的 next 與 nextval 值分別為 012123 和 002003。(2)利用 BF 算法的匹配過(guò)程:第趟匹酉己：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 法的匹配過(guò)程:第趟匹酉己：aabaabaabaac第二趟匹酉己：aabaabaabaac第三趟匹酉己：aabaabaabaac第6章樹(shù)和二叉樹(shù)習(xí)題選擇題1、 已知一算術(shù)表達(dá)式的中綴形式為 A+B*C-D/E,后綴形式為 ABC*+DE/-,其前綴形式為（D）A. -A+B*C/D

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

17、的結(jié)點(diǎn)數(shù)為（C）。A.2kB.2k-1C.2k-1D.2k-1-17、利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（C）。A.指向最左孩子 B.指向最右孩子C.空 D.非空8、對(duì)二叉樹(shù)的結(jié)點(diǎn)從 1 開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子的編號(hào)小于其右孩子的編號(hào)，可采用（C）次序的遍歷實(shí)現(xiàn)編號(hào)。A.先序 B.中序 C.后序 D.從根開(kāi)始按層次遍歷9、某二叉樹(shù)中序序列為 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、都不對(duì)10、上題的二叉樹(shù)對(duì)應(yīng)的森林包括多少棵樹(shù)（B）A.lB.2C.3D.概念上是錯(cuò)誤的11、一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足（C）A.所有的結(jié)點(diǎn)均無(wú)左孩子 B.所有的結(jié)點(diǎn)均無(wú)右孩子C.只有一個(gè)葉子結(jié)點(diǎn) D.是任意一棵二叉樹(shù)12、在二叉樹(shù)結(jié)點(diǎn)的先序序列，中序序列和后序序列中，所有葉子結(jié)點(diǎn)的先后順序（B）A.都不相同 B.完全相同成功）aabaac(i=13,j=7)A.M1B.M1+M2C.M2+M310 至 1024 之間C.先序和中序相同，而與后序不同 D.中序和后序相同，而與先序不同 13、在完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)，則它沒(méi)（C）。A.左子

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

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

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

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

23、.6C.7D.8（設(shè)度為 0 的結(jié)點(diǎn)數(shù)為 n0,度為 1 的結(jié)點(diǎn)數(shù)為 n1,度為 2 的結(jié)點(diǎn)數(shù)為 n2,度為 3 的結(jié)點(diǎn)數(shù)為 n3,度為 4 的結(jié)點(diǎn)數(shù)為 n4,那么這棵樹(shù)總的結(jié)點(diǎn)數(shù)為 n0+n1+n2+n3+n4;又因?yàn)闃?shù)中的每個(gè)結(jié)點(diǎn)（除了根結(jié)點(diǎn)外）都有一個(gè)指針指向它，那么這棵樹(shù)總的結(jié)點(diǎn)數(shù)為總的指針數(shù)加上 1;總的指針數(shù)=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、將一棵樹(shù) t 轉(zhuǎn)換為孩子一兄弟鏈表表示的二叉樹(shù) h,則 t 的后根序遍歷是 h

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

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

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

27、遍歷，給出相應(yīng)的結(jié)點(diǎn)序列，同時(shí)給二叉樹(shù)加上中序線索。(1)先序序列：ABDEHCFG(2)中序序列：DHEBAFCG(3)后序序列：HEDBFGCAA7、設(shè)一棵二叉樹(shù)的先序、中序遍歷序列分別為先序遍歷序列：CnullABDFCEGH中A序遍歷 JWhBFDAGEHC(1)畫(huà)出這棵二叉樹(shù)。(2)將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)(或森林)尸Q(0(8、將森林轉(zhuǎn)換成對(duì)應(yīng)的二叉樹(shù) oa11i?J)cMJo)Pb9、一棵二叉樹(shù)的先序、中序、后序序列如下，其中一部分未標(biāo)出，請(qǐng)構(gòu)造出該二叉樹(shù)。先序序列：_CDE_GHI_K 中序序列：CB_FA_JKIG 后序序列：EFDBJIHA12345678910Lchil

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

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

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

31、a,e),(a,c),(b,e),(c,f),(f,d),(e,d)歷,得到的頂點(diǎn)序列正確的是(D)A.a,b,e,c,d,fBC.a,e,b,c,f,dD其中：V=a,b,c,d,e,f,對(duì)該圖進(jìn)行深度優(yōu)先遍.a,c,f,e,b,d.a,e,d,f,c,b8、圖中給出由 7 個(gè)頂點(diǎn)組成的無(wú)向圖。從頂點(diǎn)1 出發(fā)，對(duì)它進(jìn)行深度優(yōu)先遍歷得到的序列是（C）,而進(jìn)行廣度優(yōu)先遍歷得到的頂點(diǎn)序列是（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 的拓?fù)湫蛄惺牵ˋ）。A.V1,V3,V4,V6,V2,V5,V7BC.V1,V3,V4,V5,V2,V6,V7D11、一個(gè)有向無(wú)環(huán)圖的拓?fù)渑判蛐蛄校ˋ.一定 B.不一定出現(xiàn)的是(D)。A.G 中有弧B.G 中有一條從 Vi 到 Vj 的路徑C.G 中沒(méi)有弧D.G 中有一條從 Vj 到 Vi 的路徑 13、 關(guān)鍵路徑是事件結(jié)點(diǎn)網(wǎng)絡(luò)中(A)。A.從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑 B.從源點(diǎn)到匯點(diǎn)的最短路徑C.最長(zhǎng)回路 D.最短回路14、下列關(guān)于 AOEH 的敘述中，不正確的是(B)A.關(guān)鍵活動(dòng)不按期完成就會(huì)影響整個(gè)工程的完成時(shí)間B.任何一個(gè)關(guān)鍵活動(dòng)提前完成，那么整個(gè)工程

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

34、深度優(yōu)先)遍歷方法。5、一無(wú)向圖 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),對(duì)該圖從頂點(diǎn) 3 開(kāi)始進(jìn)行遍歷,去掉遍歷中未走過(guò)的邊， 得一生成樹(shù) G(V,E),V(G尸 V(G),E(G尸(1,3),(3,6),(7,3),(1,2),(1,5),(2,4),則采用的遍歷方法是（廣度優(yōu)先遍歷）6、為了實(shí)現(xiàn)圖的廣度優(yōu)先搜索，除了一個(gè)標(biāo)志數(shù)組標(biāo)志已訪問(wèn)的圖的結(jié)點(diǎn)外，還需（隊(duì).V1,V3,V2,V6,V4,V5,V7.V1,V2,V5,V3,V4,V6,V7B）是唯一的。12、在有

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

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

37、4）0圖去掉有向弧看成無(wú)向圖則對(duì)應(yīng)的最小生成樹(shù)的邊權(quán)之和為（75）。13、AOV3 中，頂點(diǎn)表示（事件），邊表示（各事件的優(yōu)先關(guān)系）。AO 刎中，頂點(diǎn)表?。ㄊ录?，邊表?。ɑ顒?dòng)）。應(yīng)用題1、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)為：B=（K,R）,K=k1,k2,kR=,（1） .畫(huà)出這個(gè)邏輯結(jié)構(gòu)的圖示。（2） .相對(duì)于關(guān)系 r,指出所有的開(kāi)始頂點(diǎn)和終端頂點(diǎn)。（3） .分別對(duì)關(guān)系 r 中的開(kāi)始頂點(diǎn)，舉出一個(gè)拓?fù)湫蛄械睦?。?） .分別畫(huà)出該邏輯結(jié)構(gòu)的正向鄰接表和逆向鄰接表。9(2)開(kāi)始頂點(diǎn)：K1,K2;終端頂點(diǎn):K6,K7;(3)拓?fù)湫蛄?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).寫(xiě)出此鄰接表對(duì)應(yīng)的鄰接矩陣；(2).寫(xiě)出由 v1 開(kāi)始的深度優(yōu)先遍歷的序列;(3).寫(xiě)出由 v1 開(kāi)始的深度優(yōu)先的生成樹(shù)；(4),寫(xiě)出由 v1 開(kāi)始的廣度優(yōu)先遍歷的序列;(5).寫(xiě)出由 v1 開(kāi)始的廣度優(yōu)先的生成樹(shù)；K1K2K7;23456789-2A|(3) V1V2V3V4V5V6(4)3、如下所示的連通圖,(1) .以頂點(diǎn)為根的深度優(yōu)先生成樹(shù)；(2) .如果有關(guān)節(jié)點(diǎn)，請(qǐng)找出所有的關(guān)節(jié)

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

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

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