李春葆數(shù)據(jù)結(jié)構(gòu)習(xí)題與解析

1、一、緒論選擇題1.數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題 計算機(jī)的以及它們之間的和運算等的學(xué)科。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是的有限集，R是K上的有限集。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é)構(gòu)的順序存儲結(jié)構(gòu)是一種的存儲結(jié)構(gòu)，線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)是一種的存儲結(jié)構(gòu)。A.隨機(jī)存取 B.順序存取

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

3、正確8線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時，要求內(nèi)存中可用存儲單元的地址。A.必須連續(xù)的 B.部分地址必須連續(xù)的C.一定是不續(xù)的D連續(xù)不連續(xù)都可以9.以下的敘述中，正確的是。A.線性表的存儲結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯Y(jié)構(gòu) B.二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C.棧的操作方式是先進(jìn)先出 D.隊列的操作方式是先進(jìn)后出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é)點，其余每個結(jié)點有且只有個前驅(qū)結(jié)點；最后一個結(jié)點后續(xù)結(jié)點，其余每個結(jié)點有且只有個后續(xù)結(jié)點。3.在樹形結(jié)構(gòu)中，樹

4、根結(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 = i +1*/ s += i; /* s = s + i*/9.下面程序段的時間

5、復(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 <= n )i = i * 3;二、線性表單項選擇題1.一個向量第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是。A.110 B.108C.100D.1202.一個棧的入棧序列是a、b、c、d、e，則棧的不可能輸出序列是。A.edcba B.decba C.dceabD.abcde3.若一個棧的入棧序列是1、2、3、 、n，其輸出序列為p1、p2

6、、p3、 、pn，若p1=n，則pi為。A. i B. n = i C. n - i +1 D.不確定4.棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是。A.線性存儲結(jié)構(gòu)和鏈表存儲結(jié)構(gòu) B.散列方式和索引方式C.鏈表存儲結(jié)構(gòu)和數(shù)組 D.線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)5.判斷一個棧ST (最多元素為m) 為空的條件是。 A.ST->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.

7、ST->top= m-17.棧的特點是1，隊列的特點是2。A.先進(jìn)先出 B.先進(jìn)后出8.一個隊列的入隊序列是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->

8、;rearQU->front = m B. QU->rearQU->front1 = m C. QU->front = QU->rear D. QU->frontQU->rear + 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 (最多

9、元素為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存放其元素值，已知其頭尾指針分別是front和rear，則當(dāng)前隊列中的元素個數(shù)是。A.(rearfront + m) %m B. rearfront + 1 C. rearfront1 D. rearfront 14.棧和隊列的共同點是。A.都是先進(jìn)后出 B.

10、都是先進(jìn)先出C.只允許在端點處插入、刪除元素 D.沒有共同點填空題1.向量、棧和隊列都是結(jié)構(gòu)，可以在向量的 位置插入和刪除元素；對于棧只能在 插入和刪除元素；對于隊列只能在 插入元素和刪除元素。2.在一個長度為n的向量中的第i個元素(1in)之前插入一個元素時，需向后移動個元素。3.在一個長度為n的向量中的刪除第i個元素(1in)時，需要向前移動個元素。4.向棧中壓入元素的操作是。5.對棧進(jìn)行退棧時的操作是。6.在一個循環(huán)隊列中，隊首指針指向隊首元素的。7.從循環(huán)隊列中刪除一個元素時，其操作是。8.在具有n個單元的循環(huán)隊列中，隊滿時共有個元素的。9.一個棧的輸入序列是12345，則棧的輸出序列

11、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=NULLC.head->next=headD.head!=NULL3.非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向）滿足。A.p->next=NULLB.p=NULLC.p->next=headD.p=head4.在

12、循環(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->right=p->right; p-&

13、gt;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->n

14、ext=s; B. s->next = p->next; p->next = s;C. s->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é)點

15、的單鏈表中查找其值等于x結(jié)點時，在查找成功的情況下，需平均比較個結(jié)點。A. n B. n/2 C. (n-1)/2 D. (n+1)/210.在一個具有n個結(jié)點的有序單鏈表中插入一個新結(jié)點并仍然有序的時間復(fù)雜度是。A. O(1) 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->nex

16、t = 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 = 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.

17、 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.單鏈表是的鏈接存儲表示。2.可以使用表示樹形結(jié)構(gòu)。3.在雙鏈表中，每個結(jié)點有兩個指針域，一個指向，另一個指向。4. 在一個單鏈表中，p所指結(jié)點之前插入s所指向結(jié)點，可執(zhí)行如下操作：（1）s->next = ；（2

18、）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->next = 的操作。8.非空的循環(huán)單鏈表head的尾結(jié)點（由p所指向），滿足。9.在棧頂指針為HS的鏈棧中，

19、判定?？盏臈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=ABCDEFG，s2=PQRST，函數(shù)con (x, y) 返回x與y串的連接串，函數(shù)subs (s, i, j

20、) 返回串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 = ，s3 = BYE!，則s1、s2和s3連接后的結(jié)果是。五、數(shù)組與稀疏矩陣單項選擇題1.常對數(shù)組進(jìn)行的兩

21、種基本操作是。A.建立與刪除B.索引和修改C.查找和修改D.查找與索引2.二維數(shù)組M的成員是6個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)i的范圍從0到8，列下標(biāo)j的范圍從1到10，則存放M至少需要 1 個字節(jié)；M的第8列和第5行共占2 個字節(jié)；若M按行優(yōu)先方式存儲，元素M85的起始地址與當(dāng)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ù)組M的成員是4個字符（每個字符占一個存儲單元）組成的串，行下標(biāo)i的范圍從0到4，列下標(biāo)j的范圍從0到5，M

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

23、8，列下標(biāo)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ù)存儲稀疏矩陣，只要把每個元素的行下標(biāo)和列下標(biāo)互換，就完成了對該矩陣的轉(zhuǎn)置運算，這種觀點。A.正確B.不正確9.設(shè)矩陣A是一個對稱矩陣，為節(jié)省存儲，將其下三角部分按行序存放在一信數(shù)組B1, n(n-1)/2中，對下三角部分中任一元素aij (ij)，在一組數(shù)組B的下標(biāo)位

24、置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的存儲地址是1000，則A189的地址是。4.有一個10階對稱矩陣A，采用壓縮存儲方式（以行為主存儲，且LOC(A00

25、)=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é)點均有指向其前趨和后繼的線索，這種說法。A.正確B.錯誤 5.二叉樹的前序遍歷序列

26、中，任意一個結(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. acbed B. decab C. deabc D. cedba10.如果T2是

27、由有序樹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é)點的值均大于其左孩子的值、小于其右孩子的值，這種說法。A. 正確 B. 錯誤14.按照二叉樹的定義，具

28、有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. 以上都不對17.深度為5的二叉樹至多有個結(jié)點。A. 16 B. 32 C. 31 D.

29、 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. 二叉鏈表 B. 廣義表存儲結(jié)構(gòu) C. 三叉鏈表 D. 順序存儲結(jié)構(gòu)22.

30、對于一個滿二叉樹，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. n在m左方 D. n是m子孫27.線索二叉樹是一種結(jié)構(gòu)。A. 邏輯 B.

31、 邏輯和存儲 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 17 18 19 20 21eafdgcjihb5.深度為k的完全二叉樹至

32、少有個結(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.由如圖所示的二叉樹，回答以下問題：（1）其中序遍歷序列；（2）其前序遍歷序列；（3）其后序遍歷序列

33、；（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)/2 D. 2n4.具有4個頂點的無向完全圖有條邊。A. 6 B. 12

34、 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+e2 A. e/2 B. e C. 2e D. n+e9.已知一個圖如圖

35、所示，若從頂點a出發(fā)按深度搜索法進(jìn)行遍歷，則可得到頂點序列為1；按寬度搜索法進(jìn)行遍歷，則可得到頂點序列為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,v4,v5 C. v1,v3,v4,v5,v2 D. v1,v4,v3,v

36、5,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.判定一個有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用。A. 求關(guān)鍵路徑方法 B. 求最短路徑的Dijkstra方法C. 寬度優(yōu)先遍歷算法 D. 深度優(yōu)先遍歷算法填空題1.n個頂點的連通圖至

37、少條邊。2.在無權(quán)圖G的鄰接矩陣中，若 (vi, vj) 或 <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. 壓縮存儲 D. 索引存儲2.對線性表進(jìn)行二分查找時，要

38、求線性表必須。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，75，77，82，95，100，當(dāng)二分查找值

39、為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的有序表，按二分查找法對該表進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為。A. 35/12 B. 37/12 C. 39/12 D. 43/129.采用分塊查找時，若線性表中共有625個元素，查找每個元素的概率相同，假設(shè)采用順序

40、查找來確定結(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.在分塊查找方法中，首先查找，然后再查找相應(yīng)的。5.長度為25

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

42、是。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.

43、一組記錄的排序碼為（46，79，56，38，40，84），則利用快速排序方法，以第一個記錄為基準(zhǔn)得到的一次劃分結(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，796.一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72），其中含有5個長度為2的有序表，按歸并排序的方法對該序列進(jìn)行一趟歸并后的結(jié)果為。A. 16 25 35 48 23 40 79 82 36 72 B. 16 25 35 48 79 82 23 36 40 72C. 16 25 48

44、 35 79 82 23 36 40 72 D. 16 25 35 48 79 23 36 40 72 827.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序8.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時為空）的一端的方法，稱為。A. 希爾排序 B. 歸并排序 C. 插入排序 D. 選擇排序9.用某種排序方法對線性表（25，84，21，47，15，27，68，35，20）進(jìn)行排序時，元素序列的變化情況如下：（1）25，84，21

45、，47，15，27，68，35，20（2）20，15，21，25，47，27，68，35，84（3）15，20，21，25，35，27，47，68，84（4）15，20，21，25，27，35，47，68，84則采用的排序方法是。A. 選擇排序 B. 希爾排序 C. 歸并排序 D. 快速排序10.下列幾種排序方法中，平均查找長度最小的是。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序11.下列幾種排序方法中，要求內(nèi)存量最大的是。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序12.快速排序方法在情況下最不利于發(fā)揮其長處。A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)

46、中含有多個值C. 要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個數(shù)為奇數(shù)填空題1.在對一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時，當(dāng)把第七個記錄60插入到有序表時，為尋找插入位置需比較次。2.在利用快速排序方法對（54，38，96，23，15，72，60，45，83）進(jìn)行快速排序時，遞歸調(diào)用而使用的棧的所能達(dá)到的最大深度為，共需遞歸調(diào)用的次數(shù)為，其中第二次遞歸調(diào)用是對一組記錄進(jìn)行快速排序。3.在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則應(yīng)首先選取方法，其次選取方法，最后選取方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取方法；若只從平均情況下排序最快考慮，則應(yīng)選取方法；若從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取方法。4.在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有。5.在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是，需要內(nèi)存量最多的是。6.在堆排序和快速排序中，若原始記錄接近正序或反序，則選用，若原始記錄無序，則選用。7. 在插入排序和選擇排序中，若初始數(shù)據(jù)基本正序，則選用，若初始數(shù)據(jù)基本反序，則選用，8.對n個元素的序列進(jìn)行起泡排序時，最少的比較次數(shù)是。答案一、 緒論選擇題：1.A.B。2.B.D。3.C。