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

1、一、緒論選擇題1.數(shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題 計(jì)算機(jī)的以及它們之間的和運(yùn)算等的學(xué)科。1A.數(shù)據(jù)元素 B.計(jì)算方法C.邏輯存儲(chǔ)D.數(shù)據(jù)映像2A.結(jié)構(gòu) B.關(guān)系C.運(yùn)算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.存儲(chǔ)D.關(guān)系3.在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成。A.動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C.線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu) D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)4.線(xiàn)性結(jié)構(gòu)的順序存儲(chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)，線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一種的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取 B.順序存取

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

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

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

5、復(fù)雜度是。s = 0;for( i = 0; i < n; i+) for( j = 0; j < n; j+) s += Bij;sum = s;10.下面程序段的時(shí)間復(fù)雜度是。i = 1;while ( i <= n )i = i * 3;二、線(xiàn)性表單項(xiàng)選擇題1.一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是。A.110 B.108C.100D.1202.一個(gè)棧的入棧序列是a、b、c、d、e，則棧的不可能輸出序列是。A.edcba B.decba C.dceabD.abcde3.若一個(gè)棧的入棧序列是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)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是。A.線(xiàn)性存儲(chǔ)結(jié)構(gòu)和鏈表存儲(chǔ)結(jié)構(gòu) B.散列方式和索引方式C.鏈表存儲(chǔ)結(jié)構(gòu)和數(shù)組 D.線(xiàn)性存儲(chǔ)結(jié)構(gòu)和非線(xiàn)性存儲(chǔ)結(jié)構(gòu)5.判斷一個(gè)棧ST (最多元素為m) 為空的條件是。 A.ST->top!=0 B. ST->top=0 C. ST->top!= m D. ST->top= m6.判斷一個(gè)棧ST (最多元素為m) 為滿(mǎn)棧的條件是。 A.ST->top!=0 B. ST->top=0 C. ST->top!= m-1 D.

7、ST->top= m-17.棧的特點(diǎn)是1，隊(duì)列的特點(diǎn)是2。A.先進(jìn)先出 B.先進(jìn)后出8.一個(gè)隊(duì)列的入隊(duì)序列是1、2、3、4，則隊(duì)列輸出序列是。A.4、3、2、1B.1、2、3、4C.1、4、3、2 D.3、2、4、19.判斷一個(gè)隊(duì)列QU (最多元素為m) 為空的條件是。A. QU->rearQU->front = m B. QU->rearQU->front1 = m C. QU->front = QU->rear D. QU->frontQU->rear + 110.判斷一個(gè)隊(duì)列QU (最多元素為m) 為滿(mǎn)隊(duì)列的條件是。A. QU->

8、;rearQU->front = m B. QU->rearQU->front1 = m C. QU->front = QU->rear D. QU->frontQU->rear + 111.判斷一個(gè)循環(huán)隊(duì)列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.判斷一個(gè)循環(huán)隊(duì)列QU (最多

9、元素為m) 為滿(mǎn)隊(duì)列的條件是。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)隊(duì)列用數(shù)組A0, m-1存放其元素值，已知其頭尾指針?lè)謩e是front和rear，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)是。A.(rearfront + m) %m B. rearfront + 1 C. rearfront1 D. rearfront 14.棧和隊(duì)列的共同點(diǎn)是。A.都是先進(jìn)后出 B.

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

11、43512是。10.一個(gè)棧的輸入序列是12345，則棧的輸出序列12345是。三、鏈表單項(xiàng)選擇題1.不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。A.head=NULLB.head->nxt=NULLC.head->next=headD.head!=NULL2.帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是。A.head=NULLB.head->nxt=NULLC.head->next=headD.head!=NULL3.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿(mǎn)足。A.p->next=NULLB.p=NULLC.p->next=headD.p=head4.在

12、循環(huán)雙鏈表的p所指結(jié)點(diǎn)之后插入s所指結(jié)點(diǎn)的操作是。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.在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s結(jié)點(diǎn)，則執(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.在一個(gè)單鏈表中，已知p所指結(jié)點(diǎn)不是最后結(jié)點(diǎn)，在p之后插入s所指結(jié)點(diǎn)，則執(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.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(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.從一個(gè)具有n個(gè)結(jié)點(diǎn)

15、的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較個(gè)結(jié)點(diǎn)。A. n B. n/2 C. (n-1)/2 D. (n+1)/210.在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)11.給定有n個(gè)元素的向量，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)12.向一個(gè)棧頂指針為HS的鏈棧中插入s所指結(jié)點(diǎn)，則執(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.從一個(gè)棧頂指針為HS的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(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.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，插入s所指結(jié)點(diǎn)，則執(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. 在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)首和隊(duì)尾指針，刪除一個(gè)結(jié)點(diǎn)，則執(zhí)行。A. r = f->next; B. r = r->next;C. f = f->next; D. f = r->next;填空題1.單鏈表是的鏈接存儲(chǔ)表示。2.可以使用表示樹(shù)形結(jié)構(gòu)。3.在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向，另一個(gè)指向。4. 在一個(gè)單鏈表中，p所指結(jié)點(diǎn)之前插入s所指向結(jié)點(diǎn)，可執(zhí)行如下操作：（1）s->next = ；（2

18、）p->next = s；（3）t = p->data；（4）p->data =；（5）s->data =；5.在一單鏈表中，刪除p所指結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：（1）q = p->next；（2）p->data = p->next->data；（3）p->next = ；（4）free (q)；6.帶頭結(jié)點(diǎn)的單鏈表head為空的條件是。7.在一個(gè)單鏈表中，p所指結(jié)點(diǎn)之后插入s所指向結(jié)點(diǎn)，應(yīng)執(zhí)行s->next = 和p->next = 的操作。8.非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向），滿(mǎn)足。9.在棧頂指針為HS的鏈棧中，

19、判定棧空的條件是。10. 在棧頂指針為HS的鏈棧中，計(jì)算該鏈棧中結(jié)點(diǎn)個(gè)數(shù)的函數(shù)是。11.在HQ的鏈隊(duì)中，判定只有一個(gè)結(jié)點(diǎn)的條件是。12.在HQ的鏈隊(duì)中，計(jì)算該棧鏈中結(jié)點(diǎn)個(gè)數(shù)的函數(shù)是。四、串單項(xiàng)選擇題1.空串與空格串是相同的，這種說(shuō)法。A.正確B.不正確2.串是一種特殊的線(xiàn)性表，其特殊性體現(xiàn)在。A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符3.設(shè)兩個(gè)字符串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱(chēng)作。A.連接B.模式匹配C.求子串D.求串長(zhǎng)4.設(shè)串s1=ABCDEFG，s2=PQRST，函數(shù)con (x, y) 返回x與y串的連接串，函數(shù)subs (s, i, j

20、) 返回串s的從序號(hào)i的字符開(kāi)始的j個(gè)字符組成的子串，函數(shù)len (s) 返回串s的長(zhǎng)度，則con (subs (s1, 2, len (s2), subs (s1, len (s2), 2) 的結(jié)果串是。A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF填空題1.串的兩種最基本的存儲(chǔ)方式是。2.兩個(gè)串相等的充分必要條件是。3.空串是，其長(zhǎng)度等于。4.空格串是，其長(zhǎng)度等于。5.設(shè)s = I AM A TEACHER，其長(zhǎng)度是。6.設(shè)s1 = GOOD，s2 = ，s3 = BYE!，則s1、s2和s3連接后的結(jié)果是。五、數(shù)組與稀疏矩陣單項(xiàng)選擇題1.常對(duì)數(shù)組進(jìn)行的兩

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

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

23、8，列下標(biāo)j從1到10，從首地址SA開(kāi)始連續(xù)存放在存儲(chǔ)器內(nèi)，該數(shù)組按列存放時(shí)，元素A58的起始地址為。A. SA+141 B. SA+180 C. SA+222 D. SA+2257.稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即。A. 二維數(shù)組和三維數(shù)組 B. 三元組與散列C. 三元組與十字鏈表 D. 散列和十字鏈表8.若用三元組壓縮技術(shù)存儲(chǔ)稀疏矩陣，只要把每個(gè)元素的行下標(biāo)和列下標(biāo)互換，就完成了對(duì)該矩陣的轉(zhuǎn)置運(yùn)算，這種觀點(diǎn)。A.正確B.不正確9.設(shè)矩陣A是一個(gè)對(duì)稱(chēng)矩陣，為節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一信數(shù)組B1, n(n-1)/2中，對(duì)下三角部分中任一元素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采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是LOC(A00)，則Aij的地址是。2.二維數(shù)組A1020采用列序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占一個(gè)存儲(chǔ)單元，并且A00的存儲(chǔ)地址是200，則A610的地址是。3.二維數(shù)組A10.205.20采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，并且A105的存儲(chǔ)地址是1000，則A189的地址是。4.有一個(gè)10階對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式（以行為主存儲(chǔ)，且LOC(A00

25、)=1），則A85的地址是。5.設(shè)n行n列的下三角矩陣A已壓縮到一維數(shù)組S1.n*(n+1)/2中，若按行序?yàn)橹鞔鎯?chǔ)，則Aij對(duì)應(yīng)的S中的存儲(chǔ)位置是。6.一個(gè)稀疏矩陣如圖所示，則對(duì)應(yīng)的三元數(shù)組表示為。八、樹(shù)形結(jié)構(gòu)單項(xiàng)選擇題1.如圖所示的4棵二叉樹(shù)中，不是完全二叉樹(shù)。3.在線(xiàn)索化二叉樹(shù)中，t所指結(jié)點(diǎn)沒(méi)有左子樹(shù)的充要條件是 。A.t->left = NULL B.t->ltag = 1 C.t->ltag = 1且t->left = NULL D.以上都不對(duì)4.二叉樹(shù)按某種順序線(xiàn)索化后，任一結(jié)點(diǎn)均有指向其前趨和后繼的線(xiàn)索，這種說(shuō)法。A.正確B.錯(cuò)誤 5.二叉樹(shù)的前序遍歷序列

26、中，任意一個(gè)結(jié)點(diǎn)均處在其子女結(jié)點(diǎn)的前面，這種說(shuō)法。A.正確B.錯(cuò)誤 6.由于二叉樹(shù)中每個(gè)結(jié)點(diǎn)的度最大為2，所以二叉樹(shù)是一種特殊的樹(shù)，這種說(shuō)法。A.正確B.錯(cuò)誤 7.設(shè)高度為h的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為。A. 2h B. 2h-1 C. 2h +1 D. h +18.如圖所示二叉樹(shù)的中序遍歷序列是。A. abcdgef B. dfebagc C. dbaefcg D. defbagc9.已知某二叉樹(shù)的后序遍歷序列是dabec，中序遍歷序列是debac，前序遍歷序列是。A. acbed B. decab C. deabc D. cedba10.如果T2是

27、由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的前序就是T2中結(jié)點(diǎn)的。A. 前序 B. 中序C. 后序 D. 層次序11.如果T2是由有序樹(shù)T轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么T中結(jié)點(diǎn)的后序就是T2中結(jié)點(diǎn)的。A. 前序 B. 中序C. 后序 D. 層次序12某二叉樹(shù)的前序遍歷結(jié)點(diǎn)訪問(wèn)順序是abdgcefh，中序遍歷結(jié)點(diǎn)訪問(wèn)順序是dgbaechf，則其后序遍歷結(jié)點(diǎn)訪問(wèn)順序是。A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca13.二叉樹(shù)為二叉排序樹(shù)的充分必要條件是任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值，這種說(shuō)法。A. 正確 B. 錯(cuò)誤14.按照二叉樹(shù)的定義，具

28、有3個(gè)結(jié)點(diǎn)的二叉樹(shù)有種。A. 3 B. 4C. 5 D. 615.如圖所示二叉樹(shù)的中序遍歷序列是。A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh16.樹(shù)的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹(shù)基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這時(shí)，我們把由樹(shù)轉(zhuǎn)化得到的二叉樹(shù)叫做這棵樹(shù)對(duì)應(yīng)的二叉樹(shù)。結(jié)論是正確的。A. 樹(shù)的先根遍歷序列與二叉樹(shù)的先序遍歷序列相同B. 樹(shù)的后根遍歷序列與二叉樹(shù)的后序遍歷序列相同C. 樹(shù)的先根遍歷序列與二叉樹(shù)的中序遍歷序列相同D. 以上都不對(duì)17.深度為5的二叉樹(shù)至多有個(gè)結(jié)點(diǎn)。A. 16 B. 32 C. 31 D.

29、 1018.在一非空二叉樹(shù)的中序遍歷序列中，根結(jié)點(diǎn)的右邊。A. 只有右子樹(shù)上的所有結(jié)點(diǎn) B. 只有右子樹(shù)上的部分結(jié)點(diǎn)C. 只有左子樹(shù)上的所有結(jié)點(diǎn) D. 只有左子樹(shù)上的部分結(jié)點(diǎn)19.樹(shù)最適合用來(lái)表示。A. 有序數(shù)據(jù)元素 B. 無(wú)序數(shù)據(jù)元素 C. 元素之間具有分支層次關(guān)系的數(shù)據(jù) D. 元素之間無(wú)聯(lián)系的數(shù)據(jù)20任何一棵二叉樹(shù)的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序。A. 不發(fā)生改變 B. 發(fā)生改變 C. 不能確定 D. 以上都不對(duì)21.實(shí)現(xiàn)任意二叉樹(shù)的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu)，最佳方案是二叉樹(shù)采用存儲(chǔ)結(jié)構(gòu)。A. 二叉鏈表 B. 廣義表存儲(chǔ)結(jié)構(gòu) C. 三叉鏈表 D. 順序存儲(chǔ)結(jié)構(gòu)22.

30、對(duì)于一個(gè)滿(mǎn)二叉樹(shù)，m個(gè)樹(shù)葉，n個(gè)結(jié)點(diǎn)，深度為h，則。A. n = h + m B. h + m = 2n C. m = h-1 D. n = 2 h -123.如果某二叉樹(shù)的前序?yàn)閟tuwv，中序?yàn)閡wtvs，那么該二叉樹(shù)的后序。A. uwvts B. vwuts C. wuvts D. wutsv25.如圖所示的T2是由有序樹(shù)T1轉(zhuǎn)換而來(lái)的二叉樹(shù)，那么樹(shù)T1有個(gè)葉結(jié)點(diǎn)。A. 4 B. 5 C. 6 D. 7 26.設(shè)n、m為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是。A. n在m右方 B. n是m祖先 C. n在m左方 D. n是m子孫27.線(xiàn)索二叉樹(shù)是一種結(jié)構(gòu)。A. 邏輯 B.

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

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

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

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

35、所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可得到頂點(diǎn)序列為1；按寬度搜索法進(jìn)行遍歷，則可得到頂點(diǎn)序列為2。1 A. abecdf B. acfebd C. aebcfd D. aedfcb2 A. abcedf B. abcefd C. aebcfd D. acfdeb10.已知一有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示（1）根據(jù)有向圖的深度優(yōu)先遍歷算法，從v1頂點(diǎn)出發(fā)，所得到的頂點(diǎn)序列是1。（2）根據(jù)有向圖的寬度優(yōu)先遍歷算法，從v1頂點(diǎn)出發(fā)，所得到的頂點(diǎn)序列是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.采用鄰接表存儲(chǔ)的圖的深度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷12.采用鄰接表存儲(chǔ)的圖的寬度優(yōu)先遍歷算法類(lèi)似于二叉樹(shù)的。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 按層遍歷13.判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用。A. 求關(guān)鍵路徑方法 B. 求最短路徑的Dijkstra方法C. 寬度優(yōu)先遍歷算法 D. 深度優(yōu)先遍歷算法填空題1.n個(gè)頂點(diǎn)的連通圖至

37、少條邊。2.在無(wú)權(quán)圖G的鄰接矩陣中，若 (vi, vj) 或 <vi, vj> 屬于圖G的邊集，則對(duì)應(yīng)元素Aij 等于，否則等于。3.在無(wú)權(quán)圖G的鄰接矩陣中，若Aij等于1，則等于Aji = 。4. 已知圖G的鄰接表如圖所示，其從v1頂點(diǎn)出發(fā)的深度優(yōu)先搜索序列為，其從v1頂點(diǎn)出發(fā)的寬度優(yōu)先搜索序列為。5.已知一圖的鄰接矩陣表示，計(jì)算第i個(gè)結(jié)點(diǎn)的入度的方法是 。6.已知一圖的鄰接矩陣表示，刪除所有從第i個(gè)結(jié)點(diǎn)出發(fā)的邊的方法是 。十、查找單項(xiàng)選擇題1.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為的線(xiàn)性表。A. 散列存儲(chǔ) B. 順序存儲(chǔ)或鏈接存儲(chǔ)C. 壓縮存儲(chǔ) D. 索引存儲(chǔ)2.對(duì)線(xiàn)性表進(jìn)行二分查找時(shí)，要

38、求線(xiàn)性表必須。A. 以順序方式存儲(chǔ) B. 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C. 以鏈接方式存儲(chǔ) D. 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列3.采用順序查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為。A. n B. n/2 C. (n+1)/2 D. (n-1)/24.采用二分查找方法查找長(zhǎng)度為n的線(xiàn)性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為。A. O(n2) B. O(nlog2n) C. O(n) D. O (log2n)5.二分查找和二叉排序樹(shù)的時(shí)間性能。A. 相同 B. 不相同6.有一個(gè)有序表為1，3，9，12，32，41，45，62，75，77，82，95，100，當(dāng)二分查找值

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

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

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

42、是。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序2.設(shè)有1000個(gè)無(wú)序的元素，希望有最快的速度挑選出其中前10個(gè)最大的元素，最好采用排序法。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），則利用快速排序方法，以第一個(gè)記錄為基準(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個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(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.排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱(chēng)為。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序8.排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱(chēng)為。A. 希爾排序 B. 歸并排序 C. 插入排序 D. 選擇排序9.用某種排序方法對(duì)線(xiàn)性表（25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，元素序列的變化情況如下：（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.下列幾種排序方法中，平均查找長(zhǎng)度最小的是。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序11.下列幾種排序方法中，要求內(nèi)存量最大的是。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序12.快速排序方法在情況下最不利于發(fā)揮其長(zhǎng)處。A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)

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