數(shù)據(jù)結(jié)構(gòu)習題集2

1、數(shù)據(jù)結(jié)構(gòu)課程組編著：數(shù)據(jù)結(jié)構(gòu)（C語言篇）習題與解析（修訂版）陜西理工學院計算機科學與技術(shù)系一、緒論選擇題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機的1以及它們之間的2和運算等的學科。1A.數(shù)據(jù)元素 B.計算方法C.邏輯存儲D.數(shù)據(jù)映像2A.結(jié)構(gòu) B.關(guān)系C.運算D.算法2.數(shù)據(jù)結(jié)構(gòu)被形式地定義為 (K, R)，其中K是1的有限集，R是K上的2有限集。1A.算法 B.數(shù)據(jù)元素C.數(shù)據(jù)操作D.邏輯結(jié)構(gòu)2A.操作 B.映像C.存儲D.關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成。A.動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線性結(jié)構(gòu)和非線性結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4.線性結(jié)

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

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

4、，其余每個結(jié)點有且只有個前驅(qū)結(jié)點；最后一個結(jié)點后續(xù)結(jié)點，其余每個結(jié)點有且只有個后續(xù)結(jié)點。3.在樹形結(jié)構(gòu)中，樹根結(jié)點沒有結(jié)點，其余每個結(jié)點有且只有個前驅(qū)結(jié)點；葉子結(jié)點沒有結(jié)點，其余每個結(jié)點的后續(xù)可以。4.在圖形結(jié)構(gòu)中，每個結(jié)點的前驅(qū)結(jié)點數(shù)和后續(xù)結(jié)點數(shù)可以。5.線性結(jié)構(gòu)中元素之間存在關(guān)系，樹形結(jié)構(gòu)中元素之間存在關(guān)系，圖形結(jié)構(gòu)中元素之間存在關(guān)系。6.算法的五個重要特性是、。7.下面程序段的時間復(fù)雜度是。for( i = 0; i n; i+) for( j = 0; j m; j+) Aij = 0;8.下面程序段的時間復(fù)雜度是。i = s = 0;while ( s n) i +; /* i =

5、i +1*/ s += i; /* s = s + i*/9.下面程序段的時間復(fù)雜度是。s = 0;for( i = 0; i n; i+) for( j = 0; j n; j+) s += Bij;sum = s;10.下面程序段的時間復(fù)雜度是。i = 1;while ( i top!=0 B. ST-top=0 C. ST-top!= m D. ST-top= m6.判斷一個棧ST (最多元素為m) 為滿棧的條件是。 A.ST-top!=0 B. ST-top=0 C. ST-top!= m-1 D. ST-top= m-17.棧的特點是1，隊列的特點是2。A.先進先出 B.先進后出8.

6、一個隊列的入隊序列是1、2、3、4，則隊列輸出序列是。A.4、3、2、1B.1、2、3、4C.1、4、3、2 D.3、2、4、19.判斷一個隊列QU (最多元素為m) 為空的條件是。A. QU-rearQU-front = m B. QU-rearQU-front1 = m C. QU-front = QU-rear D. QU-frontQU-rear + 110.判斷一個隊列QU (最多元素為m) 為滿隊列的條件是。A. QU-rearQU-front = m B. QU-rearQU-front1 = m C. QU-front = QU-rear D. QU-frontQU-rear

7、+ 111.判斷一個循環(huán)隊列QU (最多元素為m) 為空的條件是。A. QU-front = QU-rear B. QU-front != QU-rear C. QU-front = (QU-rear + 1) %m D. QU-front != (QU-rear + 1) %m12.判斷一個循環(huán)隊列QU (最多元素為m) 為滿隊列的條件是。A. QU-front = QU-rear B. QU-front != QU-rear C. QU-front = (QU-rear + 1) %m D. QU-front != (QU-rear + 1) %m13循環(huán)隊列用數(shù)組A0, m-1存放其元素

8、值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數(shù)是。A.(rearfront + m) %m B. rearfront + 1 C. rearfront1 D. rearfront 14.棧和隊列的共同點是。A.都是先進后出 B.都是先進先出C.只允許在端點處插入、刪除元素 D.沒有共同點填空題1.向量、棧和隊列都是結(jié)構(gòu)，可以在向量的 位置插入和刪除元素；對于棧只能在 插入和刪除元素；對于隊列只能在 插入元素和刪除元素。2.在一個長度為n的向量中的第i個元素(1in)之前插入一個元素時，需向后移動個元素。3.在一個長度為n的向量中的刪除第i個元素(1in)時，需要向前移動個

9、元素。4.向棧中壓入元素的操作是。5.對棧進行退棧時的操作是。6.在一個循環(huán)隊列中，隊首指針指向隊首元素的。7.從循環(huán)隊列中刪除一個元素時，其操作是。8.在具有n個單元的循環(huán)隊列中，隊滿時共有個元素的。9.一個棧的輸入序列是12345，則棧的輸出序列43512是。10.一個棧的輸入序列是12345，則棧的輸出序列12345是。三、鏈表單項選擇題1.不帶頭結(jié)點的單鏈表head為空的判定條件是。A.head=NULLB.head-nxt=NULLC.head-next=headD.head!=NULL2.帶頭結(jié)點的單鏈表head為空的判定條件是。A.head=NULLB.head-nxt=NULL

10、C.head-next=headD.head!=NULL3.非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足。A.p-next=NULLB.p=NULLC.p-next=headD.p=head4.在循環(huán)雙鏈表的p所指結(jié)點之后插入s所指結(jié)點的操作是。A. p-right=s;s-left=p;p-right-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-r

11、ight=p-right; p-right-left=s;p-right=s; 5.在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的前驅(qū)結(jié)點，若在q和p之間插入s結(jié)點，則執(zhí)行。A. s-next = p-next; p-next=s;B. p-next = s-next; s-next = p;C. q-next = s; s-next = p; D. p-next = s; s-next = q;6.在一個單鏈表中，已知p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行。A. s-next = p; p-next=s; B. s-next = p-next; p-next = s;C. s-

12、next = p-next; p = s; D. p-next = s; s-next = p;7.在一個單鏈表中，若刪除p所指結(jié)點的后續(xù)結(jié)點，則執(zhí)行。A. p-next = p-next-next; B. p = p-next; p-next=p-next-next;C. p-next = p-next; D. p =p-next -next;9.從一個具有n個結(jié)點的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較個結(jié)點。A. n B. n/2 C. (n-1)/2 D. (n+1)/210.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是。A. O(1)

13、B. O(n) C. O(n2) D. O(nlog2n)11.給定有n個元素的向量，建立一個有序單鏈表的時間復(fù)雜度是。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)12.向一個棧頂指針為HS的鏈棧中插入s所指結(jié)點，則執(zhí)行。A. HS-next = s; B. s-next = HS-next; HS-next = s;C. s-next = HS; HS = s; D. s-next = HS; HS = HS-next;13.從一個棧頂指針為HS的鏈棧中刪除一個結(jié)點，用x保存被刪除結(jié)點的值，則執(zhí)行。A. x = HS; HS = HS-next; B. x =

14、HS-data;C. HS = HS-next; x = HS-data; D. x = HS-data; HS = HS-next;14.在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，插入s所指結(jié)點，則執(zhí)行。A. f-next = s; f = s; B. r-next = s; r = s;C. s-next = r; r = s; D. s-next = f; f = s;15. 在一個鏈隊中，假設(shè)f和r分別為隊首和隊尾指針，刪除一個結(jié)點，則執(zhí)行。A. r = f-next; B. r = r-next;C. f = f-next; D. f = r-next;填空題1.單鏈表是的鏈接存

15、儲表示。2.可以使用表示樹形結(jié)構(gòu)。3.在雙鏈表中，每個結(jié)點有兩個指針域，一個指向，另一個指向。4. 在一個單鏈表中，p所指結(jié)點之前插入s所指向結(jié)點，可執(zhí)行如下操作：（1）s-next = ；（2）p-next = s；（3）t = p-data；（4）p-data =；（5）s-data =；5.在一單鏈表中，刪除p所指結(jié)點時，應(yīng)執(zhí)行以下操作：（1）q = p-next；（2）p-data = p-next-data；（3）p-next = ；（4）free (q)；6.帶頭結(jié)點的單鏈表head為空的條件是。7.在一個單鏈表中，p所指結(jié)點之后插入s所指向結(jié)點，應(yīng)執(zhí)行s-next = 和p-ne

16、xt = 的操作。8.非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向），滿足。9.在棧頂指針為HS的鏈棧中，判定?？盏臈l件是。10. 在棧頂指針為HS的鏈棧中，計算該鏈棧中結(jié)點個數(shù)的函數(shù)是。11.在HQ的鏈隊中，判定只有一個結(jié)點的條件是。12.在HQ的鏈隊中，計算該棧鏈中結(jié)點個數(shù)的函數(shù)是。四、串單項選擇題1.空串與空格串是相同的，這種說法。A.正確B.不正確2.串是一種特殊的線性表，其特殊性體現(xiàn)在。A.可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以鏈接存儲D.數(shù)據(jù)元素可以是多個字符3.設(shè)兩個字符串p和q，求q在p中首次出現(xiàn)的位置的運算稱作。A.連接B.模式匹配C.求子串D.求串長4.設(shè)串s1=ABC

17、DEFG，s2=PQRST，函數(shù)con (x, y) 返回x與y串的連接串，函數(shù)subs (s, i, j) 返回串s的從序號i的字符開始的j個字符組成的子串，函數(shù)len (s) 返回串s的長度，則con (subs (s1, 2, len (s2), subs (s1, len (s2), 2) 的結(jié)果串是。A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF填空題1.串的兩種最基本的存儲方式是。2.兩個串相等的充分必要條件是。3.空串是，其長度等于。4.空格串是，其長度等于。5.設(shè)s = I AM A TEACHER，其長度是。6.設(shè)s1 = GOOD，s2 =

18、 ，s3 = BYE!，則s1、s2和s3連接后的結(jié)果是。五、數(shù)組與稀疏矩陣單項選擇題1.常對數(shù)組進行的兩種基本操作是。A.建立與刪除B.索引和修改C.查找和修改D.查找與索引2.二維數(shù)組M的成員是6個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到8，列下標j的范圍從1到10，則存放M至少需要 1 個字節(jié)；M的第8列和第5行共占2 個字節(jié)；若M按行優(yōu)先方式存儲，元素M85的起始地址與當M按列優(yōu)先方式存儲時的3元素的起始地址一致。1 A.90 B.180 C.240 D.5402 A.108 B.114 C.54 D.603 A.M85B.M310 C.M58 D.M093.二維數(shù)

19、組M的成員是4個字符（每個字符占一個存儲單元）組成的串，行下標i的范圍從0到4，列下標j的范圍從0到5，M按行存儲時元素M35的起始地址與M按列存儲時元素的元素的起始地址一致。 A.M24B.M34 C.M35 D.M444.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，存放該數(shù)組至少需要的單元素是。A. 80 B. 120 C. 240 D. 2705.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按行存放時，元素A85的起始地址為。A. SA+141 B.

20、SA+144 C. SA+222 D. SA+2256.數(shù)組A中，每個元素的長度為3個字節(jié)，行下標i從1到8，列下標j從1到10，從首地址SA開始連續(xù)存放在存儲器內(nèi)，該數(shù)組按列存放時，元素A58的起始地址為。A. SA+141 B. SA+180 C. SA+222 D. SA+2257.稀疏矩陣一般的壓縮存儲方法有兩種，即。A. 二維數(shù)組和三維數(shù)組 B. 三元組與散列C. 三元組與十字鏈表 D. 散列和十字鏈表8.若用三元組壓縮技術(shù)存儲稀疏矩陣，只要把每個元素的行下標和列下標互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種觀點。A.正確B.不正確9.設(shè)矩陣A是一個對稱矩陣，為節(jié)省存儲，將其下三角部分按

21、行序存放在一信數(shù)組B1, n(n-1)/2中，對下三角部分中任一元素aij (ij)，在一組數(shù)組B的下標位置k的值是。A. i (i-1)/2+j-1 B. i (i-1)/2+j C. i (i+1)/2+j-1 D. i (i+1)/2+j填空題1.已知二維數(shù)組Amn采用行序為主方式存儲，每個元素占k個存儲單元，并且第一個元素的存儲地址是LOC(A00)，則Aij的地址是。2.二維數(shù)組A1020采用列序為主方式存儲，每個元素占一個存儲單元，并且A00的存儲地址是200，則A610的地址是。3.二維數(shù)組A10.205.20采用行序為主方式存儲，每個元素占4個存儲單元，并且A105的存儲地址是

22、1000，則A189的地址是。4.有一個10階對稱矩陣A，采用壓縮存儲方式（以行為主存儲，且LOC(A00)=1），則A85的地址是。5.設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組S1.n*(n+1)/2中，若按行序為主存儲，則Aij對應(yīng)的S中的存儲位置是。6.一個稀疏矩陣如圖所示，則對應(yīng)的三元數(shù)組表示為。八、樹形結(jié)構(gòu)單項選擇題1.如圖所示的4棵二叉樹中，不是完全二叉樹。3.在線索化二叉樹中，t所指結(jié)點沒有左子樹的充要條件是 。A.t-left = NULL B.t-ltag = 1 C.t-ltag = 1且t-left = NULL D.以上都不對4.二叉樹按某種順序線索化后，任一結(jié)點均有指

23、向其前趨和后繼的線索，這種說法。A.正確B.錯誤 5.二叉樹的前序遍歷序列中，任意一個結(jié)點均處在其子女結(jié)點的前面，這種說法。A.正確B.錯誤 6.由于二叉樹中每個結(jié)點的度最大為2，所以二叉樹是一種特殊的樹，這種說法。A.正確B.錯誤 7.設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點，則此類二叉樹中所包含的結(jié)點數(shù)至少為。A. 2h B. 2h-1 C. 2h +1 D. h +18.如圖所示二叉樹的中序遍歷序列是。A. abcdgef B. dfebagc C. dbaefcg D. defbagc9.已知某二叉樹的后序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列是。A. acb

24、ed B. decab C. deabc D. cedba10.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的前序就是T2中結(jié)點的。A. 前序 B. 中序C. 后序 D. 層次序11.如果T2是由有序樹T轉(zhuǎn)換而來的二叉樹，那么T中結(jié)點的后序就是T2中結(jié)點的。A. 前序 B. 中序C. 后序 D. 層次序12某二叉樹的前序遍歷結(jié)點訪問順序是abdgcefh，中序遍歷結(jié)點訪問順序是dgbaechf，則其后序遍歷結(jié)點訪問順序是。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca13.二叉樹為二叉排序樹的充分必要條件是任一結(jié)點的值均大于其左孩子的值、小

25、于其右孩子的值，這種說法。A. 正確 B. 錯誤14.按照二叉樹的定義，具有3個結(jié)點的二叉樹有種。A. 3 B. 4C. 5 D. 615.如圖所示二叉樹的中序遍歷序列是。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh16.樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這時，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對應(yīng)的二叉樹。結(jié)論是正確的。A. 樹的先根遍歷序列與二叉樹的先序遍歷序列相同B. 樹的后根遍歷序列與二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與二叉樹的中序遍歷序列相同D. 以上都不對1

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

27、 二叉鏈表 B. 廣義表存儲結(jié)構(gòu) C. 三叉鏈表 D. 順序存儲結(jié)構(gòu)22.對于一個滿二叉樹，m個樹葉，n個結(jié)點，深度為h，則。A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2 h -123.如果某二叉樹的前序為stuwv，中序為uwtvs，那么該二叉樹的后序。A. uwvts B. vwuts C. wuvts D. wutsv25.如圖所示的T2是由有序樹T1轉(zhuǎn)換而來的二叉樹，那么樹T1有個葉結(jié)點。A. 4 B. 5 C. 6 D. 7 26.設(shè)n、m為一棵二叉樹上的兩個結(jié)點，在中序遍歷時，n在m前的條件是。A. n在m右方 B. n是m祖先 C.

28、 n在m左方 D. n是m子孫27.線索二叉樹是一種結(jié)構(gòu)。A. 邏輯 B. 邏輯和存儲 C. 物理 D. 線性填空題1.有一棵樹如圖所示，回答下面問題：（1）這棵樹的根結(jié)點是；（2）這棵樹的葉子結(jié)點是；（3）結(jié)點c的度是；（4）這棵樹的度是；（5）這棵樹的深度是；（6）結(jié)點c的子女是；（7）結(jié)點c的父母結(jié)點是。2.指出樹和二叉樹的三個主要差別、。3.從概念上講，樹與二叉樹是二種不同的數(shù)據(jù)結(jié)構(gòu)，將樹轉(zhuǎn)化為二叉樹的基本目的是。4.一棵二叉樹的結(jié)點數(shù)據(jù)采用順序存儲結(jié)構(gòu)，存儲于數(shù)組T中，如圖所示，則該二叉樹的鏈接表示形式為。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

29、17 18 19 20 21eafdgcjihb5.深度為k的完全二叉樹至少有個結(jié)點，至多有個結(jié)點，若按自上而下、從左到右次序給結(jié)點編號（從1開始），則編最小的葉子結(jié)點的編號是。6.在一棵二叉樹中，度為零的結(jié)點的個數(shù)為n0，度為2的結(jié)點的個數(shù)為n2，則有n0 = 。7.一棵二叉樹的第k層最多有個結(jié)點；一棵有n個結(jié)點的滿二叉樹共有 個葉子和 個非終端結(jié)點。8.結(jié)點最少的樹為，結(jié)點最少的二叉樹為。9.現(xiàn)有按中序遍歷二叉樹的結(jié)果是abc，問有種不同形態(tài)的二叉樹可以得到這一遍歷結(jié)果，這些二叉樹分別是。10.根據(jù)二叉樹的定義，具有三個結(jié)點的二叉樹有種不同的形態(tài)，它們分別是。11.由如圖所示的二叉樹，回答

30、以下問題：（1）其中序遍歷序列；（2）其前序遍歷序列；（3）其后序遍歷序列；（4）該二叉樹的中序線索二叉樹為；（5）該二叉樹的后序線索二叉樹為；（6）該二叉樹對應(yīng)的森林是。12.已知一棵樹如圖所示，其孩子兄弟表示為。13.以數(shù)據(jù)集4，5，6，7，10，12，18為結(jié)點權(quán)值所構(gòu)造的哈夫曼樹為，其帶權(quán)路徑長度為。九、圖1.在一個圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的倍。A. 1/2 B. 1 C. 2 D. 42.在一個有向圖中，所有頂點的入度之和等于所有頂點的出度這和倍。A. 1/2 B. 1 C. 2 D. 43.一個有n個頂點的無向圖最多有條邊。A. n B. n(n-1) C. n(n-1

31、)/2 D. 2n4.具有4個頂點的無向完全圖有條邊。A. 6 B. 12 C. 16 D. 205.具有6個頂點的無向圖至少應(yīng)有條邊才能確保是一個連通圖。A. 5 B. 6 C. 7 D. 86.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要條邊。A. n B. n+1 C. n-1 D. n/27.對于一個具有n個頂點的無向圖，若采用鄰接矩陣表示，則該矩陣的大小是。A. n B. (n-1)2 C. n-1 D. n28.對于一個具有n個頂點和e條邊的無向圖，若采用鄰接矩陣表示，則表頭向量的大小是1；所有鄰接矩陣中的結(jié)點總數(shù)是 2 。1 A. n B. n+1 C. n-1 D. n

32、+e2 A. e/2 B. e C. 2e D. n+e9.已知一個圖如圖所示，若從頂點a出發(fā)按深度搜索法進行遍歷，則可得到頂點序列為1；按寬度搜索法進行遍歷，則可得到頂點序列為2。1 A. abecdf B. acfebd C. aebcfd D. aedfcb2 A. abcedf B. abcefd C. aebcfd D. acfdeb10.已知一有向圖的鄰接表存儲結(jié)構(gòu)如圖所示（1）根據(jù)有向圖的深度優(yōu)先遍歷算法，從v1頂點出發(fā)，所得到的頂點序列是1。（2）根據(jù)有向圖的寬度優(yōu)先遍歷算法，從v1頂點出發(fā)，所得到的頂點序列是2。1 A. v1,v2,v3,v5,v4 B. v1,v2,v3,

33、v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v22 A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5 C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v211.采用鄰接表存儲的圖的深度優(yōu)先遍歷算法類似于二叉樹的。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷12.采用鄰接表存儲的圖的寬度優(yōu)先遍歷算法類似于二叉樹的。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷13.判定一個有向圖是否存在回路除了可以利用拓撲排序方法外，還可以利用。A. 求關(guān)鍵路徑方法 B. 求最短路徑的Dijkstra方法

34、C. 寬度優(yōu)先遍歷算法 D. 深度優(yōu)先遍歷算法填空題1.n個頂點的連通圖至少條邊。2.在無權(quán)圖G的鄰接矩陣中，若 (vi, vj) 或 屬于圖G的邊集，則對應(yīng)元素Aij 等于，否則等于。3.在無權(quán)圖G的鄰接矩陣中，若Aij等于1，則等于Aji = 。4. 已知圖G的鄰接表如圖所示，其從v1頂點出發(fā)的深度優(yōu)先搜索序列為，其從v1頂點出發(fā)的寬度優(yōu)先搜索序列為。5.已知一圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是 。6.已知一圖的鄰接矩陣表示，刪除所有從第i個結(jié)點出發(fā)的邊的方法是 。十、查找單項選擇題1.順序查找法適合于存儲結(jié)構(gòu)為的線性表。A. 散列存儲 B. 順序存儲或鏈接存儲C. 壓縮存儲

35、D. 索引存儲2.對線性表進行二分查找時，要求線性表必須。A. 以順序方式存儲 B. 以順序方式存儲，且結(jié)點按關(guān)鍵字有序排列C. 以鏈接方式存儲 D. 以鏈接方式存儲，且結(jié)點按關(guān)鍵字有序排列3.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為。A. n B. n/2 C. (n+1)/2 D. (n-1)/24.采用二分查找方法查找長度為n的線性表時，每個元素的平均查找長度為。A. O(n2) B. O(nlog2n) C. O(n) D. O (log2n)5.二分查找和二叉排序樹的時間性能。A. 相同 B. 不相同6.有一個有序表為1，3，9，12，32，41，45，62，

36、75，77，82，95，100，當二分查找值為82的結(jié)點時，次比較后查找成功。A. 1 B. 2 C. 4 D. 87.設(shè)哈希表長m=14，哈希函數(shù)H(key)=key%11。表中有4個結(jié)點：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點的地址是。A. 8 B. 3 C. 5 D. 98.有一個長度為12的有序表，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為。A. 35/12 B. 37/12 C. 39/12 D. 43/129.采用分塊查找時，若線性表中共有625

37、個元素，查找每個元素的概率相同，假設(shè)采用順序查找來確定結(jié)點所在的塊時，每塊應(yīng)分 個結(jié)點最佳地。A. 10 B. 25 C. 6 D. 62510.如果要求一個線性表既能較快地查找，又能適應(yīng)動態(tài)變化的要求，可以采用查找方法。A. 分塊 B. 順序 C. 二分 D. 散列填空題1.順序查找法的平均查找長度為；二分查找法的平均查找長度為；分塊查找法（以順序查找確定塊）的平均查找長度為；分塊查找法（以二分查找確定塊）的平均查找長度為；哈希表查找法采用鏈接法處理沖突時的平均查找長度為。2.在各種查找方法中，平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是。3.二分查找的存儲結(jié)構(gòu)僅限于，且是。4.在分塊查找方法中

38、，首先查找，然后再查找相應(yīng)的。5.長度為255的表，采用分塊查找法，每塊的最佳長度是。6.在散列函數(shù)H(key)=key%p中，p應(yīng)取。7.假設(shè)在有序線性表A1.20上進行二分查找，則比較一次查找成功的結(jié)點數(shù)為，則比較二次查找成功的結(jié)點數(shù)為，則比較三次查找成功的結(jié)點數(shù)為，則比較四次查找成功的結(jié)點數(shù)為，則比較五次查找成功的結(jié)點數(shù)為，平均查找長度為。8.對于長度為n的線性表，若進行順序查找，則時間復(fù)雜度為 ；若采用二分法查找，則時間復(fù)雜度為；若采用分塊查找（假設(shè)總塊數(shù)和每塊長度均接近n1/2），則時間復(fù)雜度為 。9.在散列存儲中，裝填因子的值越大，則；的值越小，則。十一、內(nèi)排序1.在所有排序方法中

39、，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序2.設(shè)有1000個無序的元素，希望有最快的速度挑選出其中前10個最大的元素，最好采用排序法。A. 起泡排序 B.快速排序 C. 堆排序 D. 基數(shù)排序3.在待排序的元素序列基本有序的前提下，效率最高的排序方法是。A. 插入排序 B.選擇排序 C.快速排序 D. 歸并排序4.一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序方法建立的初始堆為。A. 79，46，56，38，40，80 B. 84，79，56，38，40，46 C. 84，79，56，46，40，38 D. 84，56，79，40，46，385.一組記錄的排序碼為（46，79，56，38，40，84），則利用快速排序方法，以第一個記錄為基準得到的一次劃分結(jié)果為。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84 C. 40，38，46，56，79，84 D. 40，38，46，84，56，