數(shù)據(jù)結構作業(yè)及答案

1、第一章緒論一、選擇題1數(shù)據(jù)結構是一門研究非數(shù)值計算的程序設計問題中計算機的1以及它們之間的 2和運算等的學科。1 A.數(shù)據(jù)元素B.計算方法C邏輯存儲D.數(shù)據(jù)映像2A.結構B.關系C.運算D.算法2數(shù)據(jù)結構被形式地定義為（K, R），其中K是1的有限集，R是K上的 2 有限集。1 A.算法B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結構2 A.操作B.映像C.存儲D.關系3在數(shù)據(jù)結構中，從邏輯上可以把數(shù)據(jù)結構分成 A. 動態(tài)結構和靜態(tài)結構B. 緊湊結構和非緊湊結構C. 線性結構和非線性結構D. 內(nèi)部結構和外部結構4線性結構的順序存儲結構是一種1的存儲結構，線性表的鏈式存儲結構是一種存儲結構。A.隨機存取B.

2、順序存取C.索引存取D.散列存取5算法分析的目的是，算法分析的兩個主要方面其一是指，其二是指正確性和簡單性。 1A.找出數(shù)據(jù)結構的合理性B.研究算法中的輸入和輸出的關系C.分析算法的效率以求改進D.分析算法的易懂性和文檔性2A.空間復雜度和時間復雜度B.研究算法中的輸入和輸出的關系C.可讀性和文檔性D.數(shù)據(jù)復雜性和程序復雜性k6計算機算法指的是1，它必須具備輸入、輸出和 2等5個特性。1 A.計算方法B.排序方法C.解決問題的有限運算序列D.調(diào)度方法2 A可執(zhí)行性、可移植性和可擴充性B可行性、確定性和有窮性C確定性、有窮性和穩(wěn)定性D易讀性、穩(wěn)定性和安全性7. 線性表的邏輯順序與存儲順序總是一致

3、的，這種說法 。A正確 B不正確8線性表若米用鏈式存儲結構時，要求內(nèi)存中可用存儲單兀的地址。A必須連續(xù)的B部分地址必須連續(xù)的C一定是不續(xù)的D連續(xù)不連續(xù)都可以9. 以下的敘述中，正確的是 。A線性表的存儲結構優(yōu)于鏈式存儲結構B二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C棧的操作方式是先進先出D隊列的操作方式是先進后出10. 每種數(shù)據(jù)結構都具備三個基本運算：插入、刪除和查找，這種說法。A正確B不正確二、填空題1數(shù)據(jù)邏輯結構包括三種類型 、和,樹形結構和圖形結構合稱為 。2.在線性結構中，第一個結點 前驅結點，其余每個結點有且只有 個前驅結點；最后一個結點 后續(xù)結點，其余每個結點有且只有個后續(xù)結點。3.算

4、法的五個重要特性是 、。4. 下面程序段的時間復雜度是。6.下面程序段的時間復雜度是。for( i = 0; i n; i+) for( j = 0; j m; j+)Aij = 0;5. 下面程序段的時間復雜度是 i = s = 0;while ( s n)i +;/* i = i +1*/s += i;/* s = s + i*/s = 0;for( i = 0; i n; i+)for( j = 0; j n; j+) s += Bij;sum = s;7下面程序段的時間復雜度是 i = 1;while ( i = n )i = i * 3;第一章緒論(參考答案)一、選擇題：1. A.

5、B。 2. B. D。 3. C。4. A. B。(順序存儲結構的地址在內(nèi)存中是連 續(xù)的所以可以通過計算地址的相對變化而實現(xiàn)隨機存取，而鏈式存儲結構的存儲地址不一定連續(xù)，只能通過結點的指針按次序順序存取)5. C. A。6. C.B。7.B。8.D。9. B。10. B。、填空題：1.線性結構，樹形結構，圖形結構,非線性結構。2.沒有，1，沒有，1。3.有窮性，確定性，可行性，輸入，輸出。4. O (m*n )。5.O ( ： n )。6.2O (n2)7. O (log3n)。5. O ( jn)。解：設基本語句頻度為N。N=1 , i=1 , s=1; N=2 , i=2 , s=1+2;

6、 N=1 , i=1 , s=1; N=3 , i=3 , s=1+2+3 ;當頻度為 N時，i=N , s=1+2+3+N。則根據(jù)循環(huán)條件，s=1+2+3+Nn ,即：N(N +1) n2所以，時間復雜度為 T(n) = O(jn)7. O (log 3n)。解：設基本語句的頻度為 N。(注意此題沒有限制語句頻度)N=1,i=3;N=2,i=9;N=3,i=27;當頻度為N時，i=3N所以3Nn (據(jù)語句in) Ntop!=0 B. ST-top=NULL C. ST-top!= m D. ST-top= m6. 判斷一個棧ST (最多元素為m)為滿棧的條件是。A.ST-top!=0 B.

7、ST-top=0 C. ST-top!= m-1 D. ST-top= m7. 棧的特點是1 ，隊列的特點是2-。A.先進先出B.先進后出8. 一個隊列的入隊序列是1、2、3、4，則隊列輸出序列是 。9判斷一個隊列 QU （最多元素為 m）為空的條件是 。A. QU-rear QU-front = mB. QU-rear QU-front 1= mC. QU-fro nt = QU-rearD. QU-fro nt QU-rear + 110判斷一個隊列 QU （最多元素為m）為滿隊列的條件是 。A. QU-rear QU-fro nt = mB. QU-rear QU-fro nt 1= m

8、C. QU-fro nt = QU-rearD. QU-fro nt QU-rear + 111. 判斷一個循環(huán)隊列 QU （最多元素為m）為空的條件是 。A. QU-fro nt = QU-rearB. QU-fro nt != QU-rearC. QU-fro nt = （QU-rear +1）%mD. QU-fro nt != （QU-rear +1） %m12. 判斷一個循環(huán)隊列 QU （最多元素為m）為滿隊列的條件是。A. QU-fro nt = QU-rearB. QU-fro nt != QU-rearC. QU-fro nt = （QU-rear +1）%mD. QU-fro

9、nt != （QU-rear +1） %m13循環(huán)隊列用數(shù)組 A0, m-1存放其元素值，已知其頭尾指針分別是front和rear,則當前隊列中的元素個數(shù)是。A.（rear front + m） %m B. rear front + 1C. rear front 1D. rear front14.棧和隊列的共同點是。A.都是先進后出B.都是先進先出C.只允許在端點處插入、刪除元素D.沒有共同點填空題1. 線性表、棧和隊列都是 結構，可以在線性表的 位置插入和刪除元素；對于棧只能在 插入和刪除元素；對于隊列只能在 插入元素和 刪除元素。2. 在一個長度為n的線性表的第i個元素（1 i n）之前插

10、入一個元素時，需向后移動 個3. 在一個長度為n的向量中的刪除第i個元素（1 i next=NULLC.head- next=headD.head!=NULL2. 帶頭結點的單鏈表 head為空的判定條件是。A. head=NULLB.head- next=NULLC.head- next=headD.head!=NULL3. 非空的循環(huán)單鏈表head的尾結點（由指針p所指向）滿足 。A. p- next=NULL B.p=NULL C.p- next=head D.p=head4. 在循環(huán)雙鏈表的p所指結點之后插入s所指結點的操作是 。A. p_right=s;s_left=p;p_righ

11、t_left=s;s_right=p_right;B. p_right=s;p_right_left=s;s_left=p;s_right=p_right;C. s_left=p;s_right=p_right;p_right=s;p_right_left=s;D. s-left=p;s-right=p-right; p-right-left=s;p-right=s;5. 在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點, 則執(zhí)行。A. s-next= p-n ext; p-n ext=s;B.p-n ext= s-n ext; s-next=p;C. q_nex

12、t= s; s_next = p;D.p_n ext= s; s_n ext = q;6. 在一個單鏈表中，已知p所指結點不是最后結點，在p之后插入s所指結點，則執(zhí)行next= p; p-n ext=s;B.s-n ext= p-n ext; p-next=s;C. s-n ext= p-n ext; p = s;D.p-n ext= s; s-n ext = p;7. 在一個單鏈表中，若刪除 p所指結點的后續(xù)結點，則執(zhí)行 。A. p-n ext = p-n ext-n ext;B. p = p-n ext; p-n ext=p-n ext- n ext;C. p_next = p_n ext

13、;D. p =p-next _n ext;8. 從一個具有n個結點的單鏈表中查找其值等于x的結點時，在查找成功的情況下，需平均比較個結點。A. nB. n/2C. (n-1)/2D. (n+1)/29. 在一個具有n個結點的有序單鏈表中插入一個新結點并仍然有序的時間復雜度是。A. 0(1)B. 0(n)C. 0(n2)D. 0(nlog 2n)10. 給定有n個元素的向量，建立一個有序單鏈表的時間復雜度是 。2A. O(1)B. O(n)C. O(n )D. O(nlog 2n)11. 向一個棧頂指針為 HS的鏈棧中插入s所指結點，則執(zhí)行 。A. HS- next = s;B. s-n ext

14、 = HS- next; HS- next = s;C. s- next = HS; HS = s;D. s- next = HS; HS = HS- next;12. 從一個棧頂指針為 HS的鏈棧中刪除一個結點，用x保存被刪除結點的值，則執(zhí)行A. x = HS; HS = HS- next;B. x = HS-data;C. HS = HS-n ext; x = HS-data;D. x = HS-data; HS = HS- next;13. 在一個鏈隊中，假設f和r分別為隊首和隊尾指針，插入s所指結點，則執(zhí)行 。A. f-n ext = s;f =s;B. r-next = s;r=s;

15、C. s-n ext = r;r =s;D. s-n ext = f;f =s;14. 在一個鏈隊中，假設 f和r分別為隊首和隊尾指針，刪除一個結點，則執(zhí)行 。A. r = f-n ext;B. r = r-n ext;C. f = f-n ext;D. f = r-n ext;填空題1單鏈表是的鏈接存儲表示。2在雙鏈表中，每個結點有兩個指針域，一個指向 ，另一個指向 。3. 在一個單鏈表中，p所指結點之前插入s所指向結點，可執(zhí)行如下操作：（1）s_next = p_next ；（2）p_next = s ；（3）t = p-data ；（4） p-data =；（5） s-data =；4.

16、 在一單鏈表中，刪除p所指結點時，應執(zhí)行以下操作：（1）q = p_next ；（2）p-data = p-next-data ；（3）p_next = ；（4）free （q）；5. 帶頭結點（head）的單鏈表為空的條件是 。6. 在一個單鏈表中，p所指結點之后插入 s所指向結點，應執(zhí)行 s-next = 和p-next = 的操作。7. 非空的單循環(huán)鏈表head的尾結點（由p所指向），滿足。8. 在棧頂指針為HS的鏈棧中，判定?？盏臈l件是 。9. 在帶頭結點的鏈隊列HQ中，判定只有一個頭結點的條件是 。編程題1. 已知有一棧頂指針為HS的鏈棧，請編寫一計算該鏈棧中結點個數(shù)的函數(shù)。2. 已

17、知有一帶頭結點的鏈隊列HQ中，請編寫求該鏈隊列中結點個數(shù)的函數(shù)。第三章鏈表（參考答案）選擇題：1. A。2. B。3. C。4. D。 5. C。6. B。7. A。8. D。9. B。10. Co 11. Co 12. D。13. B。14. C。（8. D。說明：可能查找的次數(shù)從1到n次不等，這樣的話，總的查找次數(shù)是（n+1）n/2，除以n為平均查找次數(shù)，即為D. （n+1）/210. C。說明：這本質上是一個排序問題，要寫雙重循環(huán)來排序，根據(jù)已經(jīng)學習過的程序知識，比如起泡法排序等，其時間復雜度是C. O（ n2）。11. C。說明：注意這是一個棧頂指針，而非棧頂結點，所以選 C不選B。填

18、空題：1.線性表。2.前驅結點，后續(xù)結點。3.s-data,t。4.p-next-next或 q-next。5. head-next=NULL。6. p-next, s。7. p -next= head。8. HS=NULL。9. HQ-front=HQ-rear。(3. s-data, t。 這道題實質上是在 p后面插入了 s結點，然后將p和s結點中的數(shù)據(jù)作 了交換，結果就如同是“真正”在p前面插入了一個s結點一樣。其中的t是一個數(shù)據(jù)域變量。4. p-next-next或q-next。其實是把被刪結點之后的結點做了前移。)編程題1. int count (node *HS) node *p;

19、int n=0;p=HS;while (p!=NULL)n+;p=p-n ext;return (n);2. int coun t (strruct li nkqueue*HQ) strruct li nkqueue *p;int n;p=HQ-first;if (p=NULL) retur n (0 );n=1;while (p!=HQ-rear)n+;p=p-n ext; return (n);第四章串 單項選擇題 1空串與空格串是相同的，這種說法.A.正確B.不正確2串是一種特殊的線性表，其特殊性體現(xiàn)在 。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符3

20、設兩個字符串p和q,求q在p中首次出現(xiàn)的位置的運算稱作 。A.連接B.模式匹配C.求子串 D.求串長4設串s仁ABCDEFG s2=PQRST,函數(shù)con (x, y)返回x與y串的連接串， 函數(shù)subs (s, i, j)返回串s的從序號i的字符開始的j個字符組成的子串，函數(shù)len (s)返回串s的長度， 貝U con (subs (s1,2, len (s2), subs (s1, len (s2), 2)的結果串是 。A. BCDEF B. BCDEFG C. BCPQRSTD. BCDEFEF填空題1. 串的兩種最基本的存儲方式是 。2. 兩個串相等的充分必要條件是 。3. 空串是，其

21、長度等于。4. 空格串是 ，其長度等于 。5設 s = I AM A TEACHER ”其長度是 。第四章串（參考答案）單項選擇題：1. B。2. B。3. B。4. D。填空題：1.順序存儲方式和鏈接存儲方式。2.兩個串的長度相等且對應位置的字符相同。 3.零個字符的串，0。4.由一個或多個空格字符組成的串，其包含的空格個數(shù)。5.14。第六章樹形結構單項選擇題1. 如圖所示的4棵二叉樹中， 不是完全二叉樹。ABCD2. 在線索化二叉樹中，t所指結點沒有左子樹的充要條件是 。A.t-left = NULL B.t-ltag = 1 C.t-ltag = 1 且 t-left = NULLD.以

22、上都不對3. 二叉樹按某種順序線索化后，任一結點均有指向其前趨和后繼的線索，這種說法A.正確B.錯誤4. 二叉樹的前序遍歷序列中，任意一個結點均處在其子女結點的前面，這種說法。A.正確B.錯誤5. 由于二叉樹中每個結點的度最大為2,所以二叉樹是一種特殊的樹，這種說法 。A.正確B.錯誤6. 設高度為h的二叉樹上只有度為0和度為2的結點，則此類二叉樹中所包含的結點數(shù)至少為。A. 2hB. 2h-1C. 2h +1D. h +17. 如圖所示二叉樹的中序遍歷序列是 。A. abcdgefB. dfebagcC. dbaefcgD. defbagca8. 已知某二叉樹的后序遍歷序列是dabec,中序

23、遍歷序列是debac,前序遍歷序列是D. cedbaC. deabcA. acbedB. decabT中結點的前序就是 T2中結點的D.層次序T中結點的后序就是 T2中結點的D.層次序9如果T2是由樹T轉換而來的二叉樹，那么A.前序B.中序C.后序10. 如果T2是由樹T轉換而來的二叉樹，那么A.前序B.中序C.后序11.某二叉樹的先序遍歷結點訪問順序是abdgcefh,中序遍歷結點訪問順序是dgbaechf,貝U其后序遍歷結點訪問順序是 。A. bdgcefhaB. gdbecfhaC. bdgaechfD. gdbehfca12. 二叉樹為二叉排序樹的充分必要條件是任一結點的值均大于其左孩

24、子的值、小于其右孩子的值，這種說法。A.正確B.錯誤13. 按照二叉樹的定義，具有3個結點的二叉樹有 種。A. 3 B. 4C. 5D. 614. 如圖所示二叉樹的中序遍歷序列是 。A. abdgcefhB. dgbaechfC. gdbehfcaD. abcdefgh15. 樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這時，我們把由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。結論是正確的。A. 樹的先根遍歷序列與二叉樹的先序遍歷序列相同B. 樹的后根遍歷序列與二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與二叉樹的中序遍歷序列相同D. 以上都

25、不對16. 深度為5的二叉樹至多有 個結點。A. 16B. 32C. 31D. 1017. 在一非空二叉樹的中序遍歷序列中，根結點的右邊 。A.只有右子樹上的所有結點B.只有右子樹上的部分結點C.只有左子樹上的所有結點D.只有左子樹上的部分結點18. 樹最適合用來表示。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)19. 任何一棵二叉樹的葉結點在先序、中序和后序遍歷序列中的相對次序。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對20. 實現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不使用棧結構，最佳方案是二叉樹采用 存儲結構。A.二叉鏈表21.對于一個

26、滿二叉樹,A. n = h + mB. 廣義表存儲結構C.三叉鏈表D.順序存儲結構m 個樹葉，n個結點，深度為 h，則。B. h + m = 2nC. m = h-1D. n = 2 h -122. 如果某二叉樹的前序為stuwv，中序為uwtvs，那么該二叉樹的后序 A. uwvtsB. vwutsC. wuvtsD. wutsv23. 如圖所示的T2是由有序樹T1轉換而來的二叉樹，那么樹 T1有個葉結點。A. 4B. 5C. 6D. 7a棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是 24. 設n、m為A. n在m右方B. n是m祖先25. 線索二叉樹是一種結構。A.邏輯B.邏輯和存

27、儲填空題1.有一棵樹如圖所示，回答下面問題：（1） 這棵樹的根結點是 ；（2）這棵樹的葉子結點是 ；（3）結點c的度是；（4）這棵樹的度是；（5 ）這棵樹的深度是；（6）結點c的子女是；（7） 結點c的父母結點是 。C. n在m左方D. n是m子孫C.物理D.線性a2. 指出樹和二叉樹的三個主要差別 3. 從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結構，4. 一棵二叉樹的結點數(shù)據(jù)采用順序存儲結構，存儲于數(shù)組接表示形式為 。將樹轉化為二叉樹的基本目的是 T中，如圖所示，則該二叉樹的鏈eafdgcjihb123456 7891011121314151617181920 215. 深度為k的完全二叉樹至

28、少有 個結點，至多有 個結點，若按自上而下、從左到右次序給結點編號（從 1開始），則編最小的葉子結點的編號是 。6. 在一棵二叉樹中，度為零的結點的個數(shù)為 no,度為2的結點的個數(shù)為n2,則有n = 。7. 棵二叉樹的第k層最多有 個結點；一棵有n個結點的滿二叉樹共有 個葉子和個非終端結點。8. 結點最少的樹為，結點最少的二叉樹為9. 現(xiàn)有按中序遍歷二叉樹的結果是abc,問有歷結果，這些二叉樹分別是 。10. 根據(jù)二叉樹的定義，具有三個結點的二叉樹有 是11. 由如圖所示的二叉樹，回答以下問題：（1）（2）（3）（4）（5）（6）其中序遍歷序列 其前序遍歷序列 其后序遍歷序列 該二叉樹的中序線

29、索二叉樹為 該二叉樹的后序線索二叉樹為 該二叉樹對應的森林是 O種不同形態(tài)的二叉樹可以得到這一遍種不同的形態(tài)，它們分別12. 已知一棵樹如圖所示，其孩子兄弟表示為 。13. 以數(shù)據(jù)集 4, 5, 6, 7, 10, 12 , 18為結點權值所構造的哈夫曼樹為，其帶權路徑長度為 第六章樹形結構(參考答案)選擇題：1. C。2. B。3. B。4. A。5. B。6. B。7. B。8. D。9. A。10. B。11. D。12. B。13. C。14. B。15. A。16. C。17. A。18. Co 19. A。20. C。21. D。22. C。23. D。24. C。25. C o(

30、說明:6. B (除根結點，其余每層至少是2個，所以至少是2h-1 )o8. D (cedba方法很簡單dabec是后序遍歷則c是根節(jié)點將中序遍歷以c為中心分為兩邊如此操作即可得到一棵樹(dabec),(debac)(dabe)c),(deba)c)(dab)e)c),(d)e(ba)c)(d)(a)b)e)c),(d)e(b(a)c)這樣就把樹給構造了出來(11. D。從先序訪問中可知 a為根結點，從中序訪問中可知 d為最左側結點，因而在中序訪問次序中, 以a為中點，將結點分為兩部分，左側為 dgb，右側為echf，然后結合先序遍歷次序，畫出 二叉樹，最后可得結果為 D)填空題：1. a,

31、b、e、d、g， 2， 3，4， e、f，a。結點個數(shù)可以為0,樹中結點最大度數(shù)沒有限制而二叉樹的結點的最大度數(shù)為，樹的結點沒 有無左右之分而二叉樹的結點有左右之分。3.樹可采用二叉樹的存儲結構并利用二叉樹的已有算法解決樹的有關問題。4.略。5.2 k-1，2 k -1，2 k-27.2 k-1，2 log n ，2 log n - 1。8.只有一個結點的樹，空的叉樹。10.5，略。 11. dgbaechif， abdgcefhi， gdbeihfca，略，略，略。13.略，165。2.樹的結點個數(shù)至少為1而二叉樹的+1。6. n 2 +1。9.5，略。12.略。第七章圖1. 在一個圖中，所

32、有頂點的度數(shù)之和等于所有邊數(shù)的 A. 1/2B. 1C. 2D. 42. 在一個有向圖中，所有頂點的入度之和等于所有頂點的出度這和A. 1/2B. 1C. 2D. 43. 個有n個頂點的無向圖最多有 條邊。A. nB. n(n-1)C. n(n-1)/2D. 2n4. 具有4個頂點的無向完全圖有A. 6B. 12C. 165. 具有6個頂點的無向圖至少應有_A. 56. 在一個具有n個頂點的無向圖中，要連通全部頂點至少需要A. n7. 對于一個具有A. n8. 對于一個具有;所有鄰接矩陣中的結點總數(shù)是1 A. nB. n+1B. 6C. 7倍。倍。C. n(n-1)/2條邊。D. 20條邊才能

33、確保是一個連通圖。D. 8條邊。B. n+1C. n-1D. n/2n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是 2 2B. (n-1)C. n-1D. nn個頂點和e條邊的無向圖，若采用鄰接矩陣表示，則表頭向量的大小是2C. n-1D. n+e2 A. e/2B. e9已知一個圖如圖所示，若從頂點 到頂點序列為1為2C. 2eD. n+ea出發(fā)按深度搜索法進行遍歷，則可得 ;按寬度搜索法進行遍歷，則可得到頂點序列1 A. abecdfB. acfebdC. aebcfd2 A. abcedfB. abcefdC. aebcfd10.已知一有向圖的鄰接表存儲結構如圖所示(1) 根據(jù)有

34、向圖的深度優(yōu)先遍歷算法，所得到的頂點序列是 1。(2) 根據(jù)有向圖的寬度優(yōu)先遍歷算法，D. aedfcbD. acfdeb12A34A5從v1頂點出發(fā)，從v1頂點出發(fā)，*2 a3-42所得到的頂點序列是B. v1,v2,v3,v4,v5D. v1,v4,v3,v5,v2B. v1,v3,v2,v4,v5D. v1,v4,v3,v5,v21 A. v1,v2,v3,v5,v4C. v1,v3,v4,v5,v22 A. v1,v2,v3,v4,v5C. v1,v2,v3,v5,v4OD.按層遍歷。D.按層遍歷11. 采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的A.先序遍歷B.中序遍歷C.后序

35、遍歷12. 采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的A.先序遍歷B.中序遍歷C.后序遍歷13. 判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用。A.求關鍵路徑方法B.求最短路徑的 Dijkstra方法C.寬度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法填空題1. n個頂點的連通圖至少條邊。2. 在無權圖G的鄰接矩陣中，若(vi, vj)或vi, vj屬于圖G的邊集，則對應元素Aij等 于，否則等于。3. 在無權圖G的鄰接矩陣中，若 Aij等于1，則等于Aji =。4. 已知圖G的鄰接表如圖所示，其從v1頂點出發(fā)的深度優(yōu)先搜索序列為 其從v1頂點出發(fā)的廣度優(yōu)先搜索序列為 。5.

36、已知一圖的鄰接矩陣表示，計算第i個結點的入度的方法是6.已知一圖的鄰接矩陣表示,刪除所有從第i個結點出發(fā)的邊的方法是第七章圖(參考答案)選擇題：1.C。2.B。3.Co4. A o5. A o 6. C o7. D o 8. A, C o9. D， B。10. C,B。11.A o12. D o13. D o填空值：1.n-1。2.1,0。3.1 o 4.1、2、3、6、5、4,1、2、5、4、3、6 o5.求矩陣第i列非0 :兀素之和。6.將矩陣第i行全部置為0o第九章查找單項選擇題1. 順序查找法適合于存儲結構為 的線性表。A.散列存儲B.順序存儲或鏈接存儲C.壓縮存儲D.索引存儲2. 對線性表進行二分查找時，要求線性表必須 。A.以順序方式存儲B.以順序方式存儲，且結點按關鍵字有序排列C.以鏈接方式存儲D.以鏈接方式存儲，且結點按關鍵字有序排列3采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為 。A. n B. n/2 C. (n+1)/2D. (n-1)/24采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為 。2A. O(n ) B. 0(nlog 2n)C. 0(n)D. O (log 2n)5二分查找和二叉排序樹的時間性能 。A.相同B.不相同6有一個有序表為 1 , 3, 9, 12, 32, 41, 45, 62, 7