數(shù)據(jù)結(jié)構(gòu)期末考試題總

一、判斷題

1、棧是限定僅在表尾進(jìn)行插入和刪除操作的線性表。（J）

2、引入循環(huán)隊(duì)列的目的是為了克服假溢出時(shí)大量移動(dòng)數(shù)據(jù)元素。（J）

3、區(qū)分循環(huán)隊(duì)列的滿與空，有犧牲一個(gè)存儲(chǔ)單元和設(shè)標(biāo)記兩種方法。（J）

4、若一個(gè)棧的輸入序列為1,2,3,則3,1,2是不可能的棧輸出序列。3

5、表達(dá)式求值是隊(duì)列應(yīng)用的個(gè)典型例子。（X）

6、任何一個(gè)遞歸過程都可以轉(zhuǎn)換成非遞歸過程。（J）

7,循環(huán)隊(duì)列也存在空間溢出問題。（J）

8、棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。（V）

9、KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)變小。3）

10、串是一種數(shù)據(jù)對象和操作都特殊的線性表。（V）

11、對稱矩陣壓縮存儲(chǔ)后不會(huì)失去隨機(jī)存取功能。（J）

12、數(shù)組可看成線性結(jié)構(gòu)的一種推廣，可以對它進(jìn)行插入，刪除等操作。（X）

13、一個(gè)稀疏矩陣AmXn采用三元組形式表示，若把三元組中有關(guān)行下標(biāo)與列卜標(biāo)的值互換，并把m和n

的值互換，則完成了AmXn的轉(zhuǎn)置運(yùn)算。（X）

14、二維以上的數(shù)組其實(shí)是一種特殊的廣義表。

15、廣義表的取表尾運(yùn)算，其結(jié)果通常是個(gè)表，但有時(shí)也可是個(gè)單元素值。（X）

16、若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。（X）

17、廣義表中的元素或者是一個(gè)不可分割的原子，或者是一個(gè)非空的廣義表。（X）

18、所謂取廣義表的表尾就是返回廣義表中最后一個(gè)元素。（X）

19、廣義表的同級元素具有線性關(guān)系。（V）

20、一個(gè)廣義表可以為其它廣義表所共享。（-J）

21、壓縮存儲(chǔ)的三角矩陣和對稱矩陣的存儲(chǔ)空間相同。（）

解答：壓縮存儲(chǔ)的三角矩陣比壓縮存儲(chǔ)的對稱矩陣多一個(gè)存儲(chǔ)空間，用來存儲(chǔ)常量c。

答案：X

22、廣義表中的數(shù)據(jù)元素類型可以不相同。（）

解答：廣義表的不同元素可以有不同的結(jié)構(gòu)，即數(shù)據(jù)元素類型可以不相同。

答案：J

23、廣義表的元素不可以是廣義表。（）

解答：廣義表的元素可以是子表，子表的元素還可以是子表，即廣義表是一個(gè)多層次的結(jié)構(gòu)。

答案：X

24、兩個(gè)稀疏矩陣的和仍為稀疏矩陣。（）

解答：兩個(gè)稀疏矩陣的和不一定是稀疏矩陣。例如，當(dāng)兩個(gè)稀疏矩陣和的非0元個(gè)數(shù)等于這兩個(gè)稀疏矩陣

非0元個(gè)數(shù)之和時(shí)，這兩個(gè)矩陣的和不一定是稀疏矩陣。

答案：X

25、數(shù)組用順序存儲(chǔ)方式存儲(chǔ)時(shí);存取每個(gè)元素的時(shí)間相同。（）

解答：數(shù)組用順序存儲(chǔ)方式存儲(chǔ)時(shí)，只要知道起始結(jié)點(diǎn)的存放地址（即基地址）、維數(shù)和每維的上、下界，

以及每個(gè)數(shù)組元素所占用的字節(jié)數(shù)，就可以將數(shù)組元素的存放地址表示為其下標(biāo)的線性函數(shù)。因此，數(shù)組

中的任一元素可以在相同的時(shí)間內(nèi)存取，即順序存儲(chǔ)的數(shù)組是一個(gè)隨機(jī)存取結(jié)構(gòu)。

答案：V

26、隊(duì)列這種結(jié)構(gòu)是不允許在中間插入和刪除數(shù)據(jù)的。（）

解答：隊(duì)列也是一種特殊的線性表，它只允許在端進(jìn)行插入操作，在另一端進(jìn)行刪除操作，不允許在中

間插入和刪除數(shù)據(jù)。

答案：J

27、循環(huán)隊(duì)列只能用順序表實(shí)現(xiàn)。（）

解答：使用循環(huán)隊(duì)列的目的是解決順序隊(duì)列的假溢出現(xiàn)象，所以循環(huán)隊(duì)列只能用順序表實(shí)現(xiàn)。

答案：，

28、順序棧的“棧滿”與“上溢”是沒區(qū)別的，“棧空”與“下溢”是有區(qū)別的。（）

解答：棧滿時(shí)若有元素入棧，將產(chǎn)生上溢。?？諘r(shí)若進(jìn)行出棧操作，將產(chǎn)生下溢。由此可知，“棧滿”與“上

溢”有區(qū)別的，“棧空”與“下溢”也有區(qū)別。

答案：X

29、順序隊(duì)列的“假溢出”現(xiàn)象是可以解決的。（）

解答：順序隊(duì)列的“假溢出”現(xiàn)象可以利用循環(huán)隊(duì)列或通過移動(dòng)元素的方式解決。

答案：V

30、空串與空格串是一樣的。（）

解答：空串中沒有字符，其長度為0；空格串中含有空格字符，其長度為空格的個(gè)數(shù)。

答案：X

31.單鏈表中指針p所指向結(jié)點(diǎn)存在后繼結(jié)點(diǎn)的條件是p!=NULL.°X

32、雙循環(huán)鏈表從任何結(jié)點(diǎn)出發(fā)可以訪問該結(jié)點(diǎn)的直接前驅(qū)和直接后繼。，

33、隊(duì)列是特殊的線性表，在隊(duì)列的兩端可以進(jìn)行同樣的操作。X

34、雙向循環(huán)鏈表從任意結(jié)點(diǎn)出發(fā)可以訪問鏈表中的任意結(jié)點(diǎn)。4

35、頭指針一定要指向頭結(jié)點(diǎn)。（）

解答：若鏈表有頭結(jié)點(diǎn)，則頭指針指向頭結(jié)點(diǎn)；若鏈表沒有頭結(jié)點(diǎn)，則頭指針指向第一個(gè)結(jié)點(diǎn)（鏈表不空），

或指向空（鏈表為空）。

答案：X

36、鏈表中結(jié)點(diǎn)數(shù)據(jù)域占的存儲(chǔ)空間越多，存儲(chǔ)密度越大。J

37、棧是線性表，線性表的所有操作均適用于棧。x

38、一個(gè)三維數(shù)組可以看作為是數(shù)組元素為二維數(shù)組的線性表。J

39、廣義表中的數(shù)據(jù)元素類型可以不相同。M

40、串是一種數(shù)據(jù)對象和操作都特殊的線性表。V

41、兩個(gè)稀疏矩陣的和仍為稀疏矩陣。x

42、串中任意個(gè)字符組成的子序列稱為該串的子串。x

43、壓縮存儲(chǔ)的三角矩陣和對稱矩陣的存儲(chǔ)空間相同。X

44、如果兩個(gè)串含有相同的字符，則這兩個(gè)串相等。x

45、數(shù)組不適合作為任何二叉樹的存儲(chǔ)結(jié)構(gòu)。x

46、在前序遍歷二叉樹的序列中，任何結(jié)點(diǎn)的子樹的所有結(jié)點(diǎn)都直接跟在該結(jié)點(diǎn)之后、Y

47、若一個(gè)樹葉是某子樹的中序遍歷序列中的最后一個(gè)結(jié)點(diǎn)，則它必是該子樹的前序遍歷序列中的最后一

個(gè)結(jié)點(diǎn)。V

48、已知一棵二叉樹的前序遍歷和后序遍歷序列并不能唯一地確定這棵二叉樹。M

49、二叉樹用鏈?zhǔn)酱鎯?chǔ)時(shí)，空鏈域數(shù)多于非空鏈域數(shù)。M

50、KMP算法的特點(diǎn)是在模式匹配時(shí)指示主串的指針不會(huì)回溯。＜

51、后序遍歷一棵二叉樹等于中序遍歷其對應(yīng)的樹。x

52、滿二叉樹是完全二叉樹。M

53、單循環(huán)鏈表從任何結(jié)點(diǎn)出發(fā)可以訪問鏈表中的任何結(jié)點(diǎn)（）。

解答：將單鏈表中最后一個(gè)結(jié)點(diǎn)的指針域由空改為指向頭結(jié)點(diǎn)，這樣的單鏈表稱為單向循環(huán)鏈表。即單向

循環(huán)鏈表是，個(gè)指向后繼有向環(huán)，從任意結(jié)點(diǎn)出發(fā)可以訪問鏈表中的任意結(jié)點(diǎn)。

答案：V

54、用順序表存儲(chǔ)線性表時(shí)，不需要另外開辟空間保存數(shù)據(jù)元素之間的相互關(guān)系。V

55雙循環(huán)鏈表從任意結(jié)點(diǎn)出發(fā)可以訪問該結(jié)點(diǎn)的直接前驅(qū)和直接后繼()。

解答：將雙鏈表的最后一個(gè)結(jié)點(diǎn)的后繼指針域的值由空改為指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)中的前驅(qū)指針域的值由空

改為指向尾結(jié)點(diǎn)，這樣的雙向鏈表稱為雙向循環(huán)鏈表。即雙向循環(huán)鏈表是兩個(gè)有向環(huán)，?個(gè)是指向后繼有

向環(huán)，另一個(gè)是指向前驅(qū)的有向環(huán)。從任意結(jié)點(diǎn)出發(fā)都可以訪問該結(jié)點(diǎn)的直接前驅(qū)和直接后繼。

答案：4

56、稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。4

57、鏈表中結(jié)點(diǎn)數(shù)據(jù)域占的存儲(chǔ)空間越多，存儲(chǔ)密度越大()。

解答：存儲(chǔ)密度=(結(jié)點(diǎn)數(shù)據(jù)本身所占的存儲(chǔ)量)/(結(jié)點(diǎn)結(jié)構(gòu)所占的存儲(chǔ)總量)

由此可知，鏈表中結(jié)點(diǎn)數(shù)據(jù)域占的存儲(chǔ)空間越多，存儲(chǔ)密度越大。

答案：V

58、順序隊(duì)列和循環(huán)隊(duì)列的隊(duì)滿和隊(duì)空的判斷條件是一樣的。x

59、帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)的單鏈表在查找、刪除、求長度等操作上無區(qū)別()。

解答：頭結(jié)點(diǎn)是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無意義(當(dāng)然有

些情況卜.也可存放鏈表的長度、用做監(jiān)視哨等等)，有頭結(jié)點(diǎn)后，對在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一

結(jié)點(diǎn)，其操作與對其它結(jié)點(diǎn)的操作統(tǒng)一了。而且無論鏈表是否為空，頭指針均不為空。

答案：X

60、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像，不僅要存儲(chǔ)數(shù)據(jù)元素的值，還要存儲(chǔ)元素之間的相互

關(guān)系。4

61、單鏈表中指針p所指向結(jié)點(diǎn)存在后繼結(jié)點(diǎn)的條件是p!=NULL

解答：單鏈表中指針p所指向結(jié)點(diǎn)存在后繼結(jié)點(diǎn)的條件是p->next!=NULLo

答案：X

62、線性表中每個(gè)結(jié)點(diǎn)都有前驅(qū)和后繼()。

解答：線性表中，第一個(gè)結(jié)點(diǎn)沒有前驅(qū)，最后一個(gè)節(jié)點(diǎn)沒有后繼。

答案：X

63、廣義表的元素不可以是廣義表。X

64、頭結(jié)點(diǎn)就是鏈表中的第I個(gè)結(jié)點(diǎn)。()

解答：頭結(jié)點(diǎn)是為了操作的統(tǒng)一、方便而設(shè)立的，放在第一元素結(jié)點(diǎn)之前，其數(shù)據(jù)域一般無意義(當(dāng)然有

些情況卜.也可存放鏈表的長度、用做監(jiān)視哨等等)，有頭結(jié)點(diǎn)后，對在第一元素結(jié)點(diǎn)前插入結(jié)點(diǎn)和刪除第一

結(jié)點(diǎn)，其操作與對其它結(jié)點(diǎn)的操作統(tǒng)一了。首元結(jié)點(diǎn)也就是第一元素結(jié)點(diǎn)，它是頭結(jié)點(diǎn)后邊的第一個(gè)結(jié)點(diǎn)。

答案：X

65、線性表中每個(gè)結(jié)點(diǎn)都有前驅(qū)和后繼。x

66、順序表可能對存儲(chǔ)其中的數(shù)據(jù)進(jìn)行排序操作，鏈表也能進(jìn)行排序操作。()

解答：可以插入和刪除操作對鏈表進(jìn)行排序。

答案：J

67、消除遞歸不一定需要使用棧。X

二、單選題

1、k=l;

fbr(i=0;i〈n;i++)

fbr(j=0;j<n;j++)

上述程序段的時(shí)間復(fù)雜度為()。

A)O(n2)B)O(n)C)O(2n)D)O(l)

2、下面哪一個(gè)不是線性表的特性()

①除最后一個(gè)元素外，每個(gè)元素都有后繼。

②除第一個(gè)元素外，每個(gè)元素都有前驅(qū)。

③線性表的長度為n.n邦。

④線性表是有限序列。

3、與線性表的順序存儲(chǔ)不相符的特性是（）。

A）插入和掰除操作加活B）需要連續(xù)存儲(chǔ)空間C）便于隨機(jī)訪問D）存儲(chǔ)密度大

4、下面哪一個(gè)不是順序表的特點(diǎn)（）。

A）邏輯上相鄰的元素，存儲(chǔ)在計(jì)算機(jī)中相鄰的存儲(chǔ)空間

B）在順序表中查找一個(gè)元素與表中元素的分布沒有關(guān)系

C）用動(dòng)態(tài)一維數(shù)組存儲(chǔ)順序表最合適

D）插入一個(gè)元素，平均要移動(dòng)表長一半的數(shù)據(jù)元素

5、與線性表的鏈接存儲(chǔ)不相符合的特性是（）。

A）便于插入、刪除運(yùn)算B）存儲(chǔ)空間動(dòng)態(tài)分配

C）'“此主也的存儲(chǔ)空間D）只能順序查找

6、若線性表采用鏈?zhǔn)酱鎯?chǔ)，則表中各元素的存儲(chǔ)地址

A）必須是連續(xù)的B）部分地址必須是連續(xù)的

C）一定不是連續(xù)的D）可以連城也可以不連續(xù)

7、鏈表不具有的特點(diǎn)是（）

①可以隨機(jī)訪問任何一個(gè)元素②插入和刪除元素不需要移動(dòng)元素

③不必事先估計(jì)存儲(chǔ)空間④所需存儲(chǔ)空間與鏈表長度成正比

8、某線性表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用以下哪種存儲(chǔ)

方式最節(jié)省操作時(shí)間（）。

A）單鏈表B）僅有頭指針的單循環(huán)鏈表C）雙鏈表D）僅彳j頭指針的雙?/<

9,若某鏈表中最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除最后一個(gè)元素，則采用（）最節(jié)省

時(shí)間。

A）單鏈表B）雙鏈表C）帶頭—勺雙循環(huán)鏈表D）單循環(huán)鏈表

10、在一個(gè)單鏈表中，已知q所指向的結(jié)點(diǎn)是p所指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s所指向的

結(jié)點(diǎn)，則執(zhí)行（）

?s->next=p->next;p->next=s;?p->next=s->next;s->next=p;

（3）q->next=s;s->next=p;④p->next=s;s->next=q

11、鏈表不具有的特點(diǎn)是（）

A.插入、刪除操作不需要移動(dòng)元素B.可隨機(jī)訪問任一元索

C.不必事先估計(jì)存儲(chǔ)空間D.所需空間與線性長度成正比

12、對于一個(gè)線性表，若要求既能夠進(jìn)行較快地插入和刪除，又能夠反映出數(shù)據(jù)元素之間的關(guān)系，則應(yīng)該

（

A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)

C.以散列方式存儲(chǔ)D.以索引方式存儲(chǔ)

13、在一個(gè)單鏈表中，已知q所指向的結(jié)點(diǎn)是p所指向結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入s所指向的

結(jié)點(diǎn)，則執(zhí)行（）。

①s->next=p->next;p->next=s;②p->next=s->next;s->next=p;

③q->next=s;s->next=p;④p->next=s;s->next=q

14、在線性表的卜列存儲(chǔ)結(jié)構(gòu)中，讀取元素花費(fèi)時(shí)間最少的是（）.

①單鏈表②雙鏈表③循環(huán)鏈表④順序表

解答：順序表是隨機(jī)存取，時(shí)間復(fù)雜度為0（1）,鏈表是順序存取，時(shí)間復(fù)雜度為0（n）。

答案：④

15、在單鏈表上插入一個(gè)數(shù)據(jù)結(jié)點(diǎn)的平均時(shí)間復(fù)雜性為()o

①0⑴②0(n)③0(logm)?0(n2)

解答：在單鏈表上插入?個(gè)數(shù)據(jù)結(jié)點(diǎn)，時(shí)間耗費(fèi)主要是在杳找插入位置上。在長度為n的單鏈表的第/個(gè)

結(jié)點(diǎn)后插入一個(gè)數(shù)據(jù)元素時(shí)，平均查找次數(shù)為：

1.1+1)/?+1

—>，=—x----------=-------

〃￡"22

時(shí)間復(fù)雜度為0(n)。

答案：②

16、在順序表上刪除一個(gè)數(shù)據(jù)結(jié)點(diǎn)的平均時(shí)間復(fù)雜性為().

①0⑴②(n)③。(logs)@0(n2)

解答：在順序表上刪除一個(gè)數(shù)據(jù)結(jié)點(diǎn)，時(shí)間耗費(fèi)主要是在數(shù)據(jù)移動(dòng)操作匕在長度為n的順序表中刪除一

個(gè)數(shù)據(jù)元素時(shí)所需移動(dòng)的數(shù)據(jù)元素的平均次數(shù)為：

金〃〃占n22

平均時(shí)間復(fù)雜度為0(n)。

答案：②

17、非空雙循環(huán)鏈表中，在q所指向的結(jié)點(diǎn)前插入一個(gè)由p所指向結(jié)點(diǎn)的過程依次為()。

A)p->next=q;p->prior=q->prior;q->prior=p;q->next=p;

B)p->next=q;p->prior=q->prior;q->prior=p;q->prior->next=p;

C)p->ncxt=q;p->prior=q->prior;q->prior=p;p->prior->ncxt=p;

D)p->next=q;p->prior=q->prior;q->prior=p;p->next->prior=p;

18、若進(jìn)棧序列為1,2,3,4,則不可能得到的出棧序列是

A)3,2,l,4B)3,2,4,lC)4,2,3.1D)2,3,4,l

19、在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端作為棧底，以top作為棧頂指針，則當(dāng)作退棧處理

時(shí)，top變化為()

?top不變②top+=n③top—@top++

20、設(shè)輸入序列為1,2,3,4,借助一個(gè)棧可以得到的輸出序列是()。

①1,3,4,2②3,1,4,2

③4,3,1,2?4,1,2,3

21、若進(jìn)隊(duì)序列為1,2,3,則出隊(duì)序列是()。

A)3,2,lB)l,2,3C)1,3,2D)3,2,l

22、棧和隊(duì)列都是()。

A)順序存儲(chǔ)的線性結(jié)構(gòu)B)限制存取小的線忤結(jié)構(gòu)

C)鏈接存儲(chǔ)的線性結(jié)構(gòu)D)限制存取點(diǎn)的非線性結(jié)構(gòu)

23、棧和隊(duì)列都是()

①順序存儲(chǔ)的線性表②鏈?zhǔn)酱鎯?chǔ)的線性表

③限制插入、刪除位置的線性表④限制插入、刪除操作位置的非線性結(jié)構(gòu)

24、若循環(huán)隊(duì)列的隊(duì)頭指針為front,隊(duì)尾指針為rear,則隊(duì)長的計(jì)算公式為()。(rcar+M-front)%M

A)rear-frontB)front-rearC)rear-front+lD)都不i[:確

25、在具有n個(gè)單元的順序存儲(chǔ)的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)列

為空的條件是()。

A)front==rear+lB)front+1==rearC)front:-rearD)front==0

26、在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則進(jìn)行插入s所指向結(jié)點(diǎn)的操作是()

?front->next=s;front=s;②rear->next=s;rear=s;

?front=front->next;@front=rear->next;

27、串是()

①一些符號構(gòu)成的序列②一些字母構(gòu)成的序列

③一個(gè)以上的字符構(gòu)成的序列④任意有限個(gè)字符構(gòu)成的序列

28、若將n階對稱矩陣A的卜三角部分以行序?yàn)橹餍驂嚎s存儲(chǔ)到一維數(shù)組B中，A的卜?標(biāo)卜.界為0,B的

下標(biāo)下界為1。那么，A中的任一下三角元素aij在矩陣B中的位置為

A)i(i+l)/2+jA)i(i+l)/2+j-lC)i(iH)/2+j?1D)j(j+l)/2+i

29、數(shù)組A[10][10]的下標(biāo)下界為1,每個(gè)元素占3個(gè)字節(jié)，存儲(chǔ)在起始地址為100的連續(xù)內(nèi)存單元，則元

素A[5][4]的地址為().=100+(4*10+3)*3=229

①215②270③262④229

30、將8階對稱矩陣A的卜三角部分逐行地存儲(chǔ)到起始地址為1()0的內(nèi)存單元中，已知每個(gè)元素占4個(gè)字

節(jié)，下標(biāo)下界都為0,則A[7][4]的地址為i>=j,i*(i+l)/2+j=32地址=100+32*4=228

A)35B)36C)340D)228

31、將一個(gè)100階的對稱矩陣A按行優(yōu)先壓縮存入一維數(shù)組B中,下標(biāo)的下界都為0,則A中的元素A[65][64]

在數(shù)組B中的位置為()。

A)2194B)2195C)2209D)2197

32、對稀疏矩陣進(jìn)行壓縮存儲(chǔ)的目的是

A)便于進(jìn)行矩陣運(yùn)算B)便了輸入和輸出

C)省作儲(chǔ))舊D)降低運(yùn)算的時(shí)間復(fù)雜度

33、下面說法不正確的是()。

A)廣義點(diǎn)的衣頭怠工一個(gè)廣義之B)廣義表的表尾總是一個(gè)廣義表

C)廣義表難以用順序存儲(chǔ)結(jié)構(gòu)D)廣義表可以是?個(gè)多層次的結(jié)構(gòu)

34、對廣義表A=(x,((a,b),c,d))做運(yùn)算head(head(tail(A)))后的結(jié)果為().

A)xB)(a.b)C)aD)c

35、廣義表((),())的深度為()。

A)0B)1C)2D)3

36、L!知廣義表L=((x,y,z),a,(u,t,w)),則從L中取出原子項(xiàng)t的操作是()。

ihcad(tail(hcad(tail(tail(L)))))②head(head(tail(tail(tail(L)))))

③head(tail(tail(tail(taiI(L)))))④head(lail(tail(head(tail(L)))))

37、在樹的雙親表示法中對樹按層次編號，用數(shù)組進(jìn)行存儲(chǔ)，則下面說法不正確的是()。

A)兄結(jié)點(diǎn)的下標(biāo)值小于弟結(jié)點(diǎn)的下標(biāo)值B)所有結(jié)點(diǎn)的雙親均可以找到

。任意結(jié)點(diǎn)的孩子信息可以找到D)下標(biāo)值為i和i+l的結(jié)點(diǎn)的關(guān)系足孩廣和雙親

38、有100個(gè)結(jié)點(diǎn)的完全二叉樹由根開始從上到下從左到右對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)的編號為1,編號為

43的結(jié)點(diǎn)的左孩子的編號為性質(zhì)5

A)50B)48C)98D)86

39、在深度為6的完全二叉樹中()。最少211+1,最多211

A)最少有31個(gè)結(jié)點(diǎn)，最多有64個(gè)結(jié)點(diǎn)B)最少有32結(jié)點(diǎn)，最多有64個(gè)結(jié)點(diǎn)

C)最少有31個(gè)結(jié)點(diǎn)，最多有63結(jié)點(diǎn)D)最少/32m，最多仃63”,也

40、假定在一棵二叉樹中，度為2的結(jié)點(diǎn)數(shù)為15,度為1的結(jié)點(diǎn)數(shù)為32,則葉子結(jié)點(diǎn)個(gè)數(shù)為()。n0=n2+l

性質(zhì)3

A)15B)16C)17D)18

41、已知完全二叉樹有80個(gè)結(jié)點(diǎn)，則整個(gè)二叉樹有()個(gè)度為1的結(jié)點(diǎn)。性質(zhì)6

A)0B)lC)2D)不確定

42、n個(gè)結(jié)點(diǎn)的二叉樹，若用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，則非空閑的左、右孩子鏈域?yàn)?/p>

A)nB)2nC)n-1D)n+1

43、假定在一棵二叉樹中，度為2的結(jié)點(diǎn)數(shù)為15個(gè)，度為1的結(jié)點(diǎn)數(shù)為32個(gè)，則葉子結(jié)點(diǎn)個(gè)數(shù)為()。

A)18B)17C)16D)15

44、對一棵有n個(gè)結(jié)點(diǎn)的樹，則該樹中的度之和為()

?n②n-l③n+1④不確定

45、在二叉樹的先序遍歷中，任意一個(gè)結(jié)點(diǎn)均處在其子孫前面()。根左右

A)小:確B)不正確C)有時(shí)正確D)不定

46、若二叉樹的先序遍歷序列和后序遍歷序列正好相同，則一定是一棵()二叉樹

①不多于一個(gè)結(jié)點(diǎn)的二叉樹

②結(jié)點(diǎn)個(gè)數(shù)可能大于1且各結(jié)點(diǎn)均無左孩子

③結(jié)點(diǎn)個(gè)數(shù)可能大于1且各結(jié)點(diǎn)均無右孩子

④其中任意?個(gè)結(jié)點(diǎn)的度不為2的

47、若一個(gè)棧的輸出序列的第一個(gè)元素是i,則第j個(gè)輸出元素是()。

A.i-j+1B.i-jC.j-i+1D.不確定的

解析：對輸入序列為1,2,3,…,n,若第一個(gè)輸出的元素是n,即i==n,則第j個(gè)輸出的元素是n-j+1,否則不

能確定其他元素的輸出順序。例如：輸入序列為123,若第一輸出元素是1,則可能的輸出序列有123和

132。

答案：D

48、若棧采用順序存儲(chǔ)方式存儲(chǔ)，現(xiàn)兩棧共享空間top[i]代表第i個(gè)棧(i=l,2)棧頂，棧1的底在

v[0],棧2的底在則棧滿的條件是().

A.|top[2]-top[l]|=0B.top[l]+l=top[2]

C.top[l]+top[2]=mD.top[l]=top[2]

解析：棧1和棧2共享內(nèi)存中一片連續(xù)空間，兩棧頂top[l]和top[2]向共享空間的中心延伸，僅當(dāng)兩棧頂指

針值之差的絕對值等于1時(shí)，判為棧滿。

答案：B

49、若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，隊(duì)頭指針fkont指向隊(duì)頭元素，隊(duì)尾指針rear指向隊(duì)尾元素

的下一個(gè)位置。若當(dāng)前rear和front的值分別為。和3,當(dāng)從隊(duì)列中刪除兩個(gè)元素，再加入兩個(gè)元素后，rear

和front的值分別為多少？()。

A.I和5B.2和5C.4和2D.5和1

解析：元素出隊(duì)時(shí)，front的公式計(jì)算為：front=(front+l)%6,出隊(duì)兩個(gè)元素，front的值為5。元素入隊(duì)時(shí)，

rear的公式計(jì)算為：rear=(rear+l)%6,出隊(duì)兩個(gè)元素，rear的值為2。

答案：B

50、用不帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)隊(duì)列時(shí)，其隊(duì)頭指針指向隊(duì)頭結(jié)點(diǎn)，其隊(duì)尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行刪除

操作時(shí)()。

A.僅修改隊(duì)頭指針B.僅修改隊(duì)尾指針

C.隊(duì)頭、隊(duì)尾指針都要修改D.隊(duì)頭、隊(duì)尾指針都可能要修改

解析：當(dāng)隊(duì)列中有兩個(gè)或兩個(gè)以上的結(jié)點(diǎn)時(shí)，刪除操作只修改隊(duì)頭指針，若隊(duì)列中只有一個(gè)結(jié)點(diǎn)時(shí)，刪除

操作既要修改隊(duì)頭指針，乂要修改隊(duì)尾指針。

答案:D

51、設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素cl,c2,c3,c4,c5和c6依次通過棧S,?個(gè)元素出棧后即進(jìn)

隊(duì)列Q,若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,el,則棧S的容量至少應(yīng)該是()。

A.6B.4C.3D.2

解析：出隊(duì)序列就是出棧序列，得到出棧序列e2,e4,e3,e6,e5,el的過程是：el,e2進(jìn)棧，棧中有2

個(gè)元素，e2出棧，棧中有1個(gè)元素；e3、e4進(jìn)棧，棧中有3個(gè)元素，e4出棧，e3出棧，棧中有1個(gè)元素；

e5、e6進(jìn)棧，棧中有3個(gè)元素，e6出棧，e5出棧，棧中有1個(gè)元素；el出棧，?？?。由此可知，棧中最

多有3個(gè)元素，所以棧S的容量至少應(yīng)該3。

答案：C

52、若串S="structure”，其子串的數(shù)目是().

A.9B.46C.45D.10

解析：子串是串中任意個(gè)連續(xù)的字符組成的子序列，并規(guī)定空串是任意串的子串，任意串是其自身的子串。

若字符串長度為n(n>0),長度為n的子串有1個(gè)，長為n-l的子串有2個(gè)，長為n-2的子串有3個(gè)，，

長為1的子串有n個(gè)。由此可知，長度為n的字符串的子串?dāng)?shù)為n(n+l)/2+1o所以本題的答案為：

9*(9+1)/2+1=46.

答案：B

53、已知個(gè)稀疏矩陣的三元組表如下：

(1,2,3),(1,6,1),(3,1,5),(3,2,-1),(4,5,4),(5,1,-3)

則其轉(zhuǎn)置矩陣的三元組表中第3個(gè)三元組為()。

A.(2,1,3)B,(3,1,5)C,(3,2,-1)D.(2,3,-1)

解析：采用三元組存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)稀疏矩陣轉(zhuǎn)詡的方法是：對給定的三元組表，按列標(biāo)值升序排序，若列

表值相同，再按行標(biāo)值升序排序；交換行標(biāo)和列標(biāo)值。本題中，按此方法得到轉(zhuǎn)置矩陣的三元組表為：(1,

3,5),(I,5,-3),(2,1,3),(2,3,-1),(5,4,4),(6,1,1)?轉(zhuǎn)置矩陣的三元組表中第3個(gè)三元組

為(2,1,3).

答案：A

54、設(shè)有一個(gè)10階對稱矩陣A,采用壓縮存儲(chǔ)方式，以行序?yàn)橹餍虼鎯?chǔ)，為第一個(gè)元素，其存儲(chǔ)地

址為1,每個(gè)元素占一個(gè)字節(jié)，則a[8][5]的地址為

A.13B.33C.18D.40

解析：若一個(gè)n階對稱矩陣A的卜.標(biāo)卜界均為0,以行序?yàn)橹餍驂嚎s存儲(chǔ)，每個(gè)元素占用的字節(jié)數(shù)為L,

則元素的地址為：

LOC(a[i][iJ)=WC(a[0][0])+(/(/+1)/2+j)*L

若下標(biāo)下界不為o,先將下標(biāo)下界調(diào)整為o,然后根據(jù)上面公式計(jì)算相應(yīng)元素地址即可。本題中，下標(biāo)下界

都是1,先將下標(biāo)下界都調(diào)整為0,a[8][5]調(diào)整為a[7][4],然后計(jì)算a[7][4]的地址即可。

LOC(a[7][4])=1+(7*(7+1)/2+4)*1=1+32=33

答案:B

55、廣義表((a,b,c,d))的表頭是().

A.aB.()C.(a,b,c,d)D.(b,c,d)

解析：根據(jù)表頭的定義，廣義表《a,b,c,d))的表頭為(a,b,c,d)。

答案：C

56、廣義表(a(b,c),d,e)的表尾是()。

A.((b,c),d,e)B.a,(b,c)C.(a,(b,c))D.(a)

解析：根據(jù)表尾的定義，廣義表(a,(b?,d,e)的表尾為((b,c),d,e)。

答案:A

57、表頭和表尾均為空表的廣義表是()。

A.()B.(())C.((()))D.(();())

解析：設(shè)L是一個(gè)表頭和表尾都為的空廣義表，即head(L)=(),taiI(L)=(),根據(jù)表頭和表尾的定義可得：L=(())

答案：B

58、設(shè)廣義表1=((a,b,c)),則L的長度和深度分別為()。

A.1和1B.1和3C.1和2D.2和3

解析：廣義表的長度是廣義表中元素的個(gè)數(shù)，廣義表的深度是廣義表中括號嵌套的最大數(shù)。依據(jù)定義，L

的長度為1,深度為2。

答案：C

59、已知廣義表L=((x,y,z),a,(u>t,w)),從L表中取出原子項(xiàng)t的運(yùn)算是()。

A.head(tail(tail(L)))B.tail(head(head(tail(L))))

C.head(tail(head(tail(L))))D.head(tail(head(tail(tail(L)))))

解析：(1)在L的表尾,取出L的表尾:Ll=tail(L)=(a,(u,t,w))

(2)t在LI的表尾，取出L1的表尾:L2=tail(Ll)=((u,t,w))

(3)t在L2的表頭,取出L2的表頭:L3=head(L2)=(叩,w)

(4)t在L3的表尾，取出L3的表尾:L4=tail(L3尸(t,w)

(5)t是L4的表頭,取出L4的表頭：head(L4)=t

由止匕可知：

t=head(L4)=head(tail(L3))=head(tail(head(L2)))

=head(tail(head(tail(L1))))=head(tail(head(tail(tail(L)))))

答案：D

60、廣義表((),())的深度為()o

A)0B)1C)2D)3

61、一個(gè)nXn階的對稱矩陣采用壓縮存儲(chǔ)時(shí)需要的存儲(chǔ)單元數(shù)為()。

A)n2B)2nC)n*(n+l)/2D)n*(n+1)

62、下面()不是順序表的特點(diǎn)。

A)邏輯上相鄰的元素，存儲(chǔ)在計(jì)算機(jī)中相鄰的存儲(chǔ)空間

B)在順序表中查找一個(gè)元素與表中元索的分布沒有關(guān)系

C)用動(dòng)態(tài)-維數(shù)組存儲(chǔ)順序表最合適

D)插入一個(gè)元素，平均要移動(dòng)表長一半的數(shù)據(jù)元素

63、fbr(i=0;i<m;i++)

fbrO=0;j<n;j-H-)

A[i][j]=i*j；

上面算法的時(shí)間復(fù)雜度為()。

A)O(m2)B)O(n2)C)O(mXn)D)O(m+n)

64、在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的基本單位是()。

A)數(shù)據(jù)項(xiàng)B)數(shù)據(jù)元素C)數(shù)據(jù)對象D)數(shù)據(jù)文件

65、設(shè)單鏈表中指針p指向結(jié)點(diǎn)A,要?jiǎng)h除A之后的結(jié)點(diǎn)(若存在)，則修改指針的操作為()。

A)p->ncxt=p->ncxt->ncxtB)p=p->ncxt

C)p=p->next->nextD)p->next=p

66、一個(gè)棧的入棧序列是a、b、c、d、e,則棧的輸出序列不可能是()。

A)dceabB)decbaC)edcbaD)abcde

三、填空題

1、稀疏矩陣一一般的壓縮存儲(chǔ)方法有三元組表和()。十字鏈表

2、為了避免造成假溢出現(xiàn)象，經(jīng)常將順序隊(duì)列改造成。

解答：為了避免造成假溢出現(xiàn)象，經(jīng)常將順序隊(duì)列改造成循環(huán)隊(duì)列。

3、二叉樹的第i層(根結(jié)點(diǎn)為第1層)上，最多有()個(gè)結(jié)點(diǎn)。2」

4、有n個(gè)結(jié)點(diǎn)的完全二叉樹(空二叉樹的深度為0),其深度h=()oriog2nj+1

5、廣義表L=(5,(3,2,(14,9,3),(),4),2,(6,3,10))的深度為().3

6、執(zhí)行delete("ABCDEFGHIJ",5,3)后，主串的值為。

解答：delete(s,ij)的功能是在串s中刪除從第i個(gè)字符開始的長度為j的子串。主串的值為"ABCDHIJ”

7、將插入限定在表的一端，而刪除限定在表的另一端進(jìn)行的線性表稱為隊(duì)列，允許插入的一端稱為

隊(duì)尾

8、所有插入和刪除都在表的一端進(jìn)行的線性表稱為()。棧

9、()可以作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的?種數(shù)據(jù)結(jié)構(gòu)。棧

10、串是一種特殊的線性表，串常見的存儲(chǔ)結(jié)構(gòu)有順序存儲(chǔ)和()兩種方式。族式仃小

11、通常把隊(duì)列中允許插入的一端稱為()。隊(duì)尾

12、設(shè)順序表有19個(gè)元素，第一個(gè)元素的地址為200,且每個(gè)元素占3個(gè)字節(jié)，則第14個(gè)元素的存儲(chǔ)地

址為(239)。第14個(gè)元素的卜.標(biāo)為13,所以第14個(gè)元素的存儲(chǔ)地址為：200+3*13=239

13、已知h是一個(gè)帶頭結(jié)點(diǎn)的雙鏈表，每個(gè)結(jié)點(diǎn)有四個(gè)成員：指向前驅(qū)結(jié)點(diǎn)的指針prior、指向后繼結(jié)點(diǎn)的

指針next、存放數(shù)據(jù)的成員data和訪問頻度freq。所有結(jié)點(diǎn)的freq初始值為0。每當(dāng)在雙鏈表上進(jìn)行一次

locate(h,x)操作時(shí)，令元素值為x的結(jié)點(diǎn)的freq的值增1,并使此鏈表中結(jié)點(diǎn)保持按訪問頻度遞減的順序排

列，以便使訪問頻度高的結(jié)點(diǎn)總是靠近表頭。

locate(dlink*h,ElemTypex)

{dlink*p=h->next,*q;

while(p!=NULL&&)p=p->next;p-data!x

if(p==NULL)return0;

else

{p->freq++；q=p->prior;

whilc(q!=h&&)q->frcq-p-freq

{p->prior=q->prior;p->prior->next=p;q->next=p->next;

if()q->next->prior=q;q->ncxt!NULL

p->next=q;

q->prior=p;

;q=p->prior

)

)

return1;

)

14、下列函數(shù)的功能是實(shí)現(xiàn)將帶頭結(jié)點(diǎn)單鏈表的結(jié)點(diǎn)值按升序排序，請對程序進(jìn)行填空。

voidsort2(slink*11)

{slink*p,*q,*r,*s;

P=H;

whilc(p->next!=NULL)

{q=p->next;r=p;

whilc()q->ncxt!NULL

{if(q->next->data<r->next->data)r=q;

;}q^q->ncxt

iR)「!=P

{s=r->next;r->next=s->next;s->next=p->next;p->next=s;}

;p=p->next

15、下列函數(shù)的功能是實(shí)現(xiàn)帶頭結(jié)點(diǎn)的單鏈表逆置，請對程序進(jìn)行填空。

voidtum(slink*L)

{slink*p,*q;

p=;L->nexl

L->next=NULL;

while()p->next!=NL'LL

{q=p;

p=;p->next

q->next=L->next;

L->next=;q

16、已知氏度為len的線性表L采用順序存儲(chǔ)結(jié)構(gòu)。卜.列算法的功能是刪除線性表L中所有值為item的數(shù)

據(jù)元素。

typedefintElemType;

typedefstruct

{ElemType*data;/?存儲(chǔ)空間基地址*/

intlength;/*順序表長度（即已存入的元素個(gè)數(shù)）*/

intlistsize;/*當(dāng)前存儲(chǔ)空間容量（即能存入的元素個(gè)數(shù)）*/

Jsqlist;

voiddelnode(sqlist*L,ElemTypeitem)

{intk=0,i=0;

while(i<L->length)

{if(L->data[i]=itcm)

;k++

else

L->data[i-k]=L->data[i];

L->lcngth=L->lcngth-k;

)

17、下面程序段為刪除帶頭結(jié)點(diǎn)的單循環(huán)鏈表中第?個(gè)data域值等于x的結(jié)點(diǎn)，請對程序進(jìn)行填空。

Delete(slink*head,intx)

{slink*p,*q;/*p指向當(dāng)前處理的結(jié)點(diǎn),q指向p的前驅(qū)結(jié)點(diǎn)*/

if(!head)retumO;/*鏈表為空*/

ifl[hcad->next=hcad)/*鏈表只有?個(gè)結(jié)點(diǎn)*/

{if^head->data=x)

{frcc(hcad);hcad=NULL;returnx;}

return0;

p=head;q=head;

while(q->next!=head)q=;q->next

while(p->next!=head)

{if(p->data==x)

{;q->next=p->next

if(p==head)head=;p->next

free(p);retumx;

)

else{q=p;;}p=p->next

}

return0;

)

18、卜.列函數(shù)的功能是實(shí)現(xiàn)將一個(gè)帶頭結(jié)點(diǎn)單鏈表L中所有值為偶數(shù)的結(jié)點(diǎn)放在所有值為奇數(shù)的結(jié)點(diǎn)的前

面，請對程序進(jìn)行填空。

voidChangeList(slink*L)/*借助于頭插法思想*/

{slink*p,*q；

p=L;/*p為q的前驅(qū)*/

q=L->next;/*用q從頭至尾掃描單鏈表L*/

while()q!=NULL

if(q->data%2=0)

{p->next=q->next;

q->ncxt=;L->ncxt

L->next=q;

q=;p->ncxt

)

else

{;p=q

q=q->ncxt;

}

)

19、下列函數(shù)的功能是實(shí)現(xiàn)將一個(gè)帶頭結(jié)點(diǎn)單鏈表L中所有值為x的結(jié)點(diǎn)刪除，請對程序進(jìn)行填空。

voidDclListX(slink*L,ElcmTypcx)

{slink*p,*q,*t;

p=L;/*p為q的前驅(qū)*/

q=；/*用q從頭至尾掃描單鏈表L*/L->next

while(q!=NULL)

{iR)q->data=x

{p->next=q->ncxt;

free(q);

;q=p->ncxt

}

else

{;p=q

q=q->next;

四、應(yīng)用題

1、已知廣義表L=((a,b,c),(d,e,f,g)),給出用取表頭(head)和取表尾(tail)函數(shù)取出原子e的運(yùn)算。

2、畫出廣義表(a,(b,(c,())),(d,e))的存儲(chǔ)圖，并計(jì)算其深度。孩子兄弟鏈表

3、已知廣義表(a,(b,(a,b)),((a,b),(a,b))),試完成下列操作：任選一種結(jié)點(diǎn)結(jié)構(gòu)，畫出該廣義表的存儲(chǔ)結(jié)構(gòu)圖：

計(jì)算該廣義表的表頭和表尾。計(jì)算該廣義表的深度。孩子兄弟鏈表

4、已知一棵二叉樹的后序遍歷序列和中序遍歷序列分別為：

中序：CBEDAFIGH

后序：CEDBIFHGA

試畫出這棵：叉樹，并寫出其先序遍歷序列.

5、已知一棵二叉樹的先序遍歷序列和中序遍歷序列分別為：

先序：ABCDEFG

中序：CBEDAFG

試畫出這棵二叉樹。并寫出其后序遍歷序列。

6、已知一棵二叉樹的先序、中序和后序遍歷序列分別為：

先序：BExKCJADG'HI

中序：LKxCAJxxFGIH

后序：KLXJCEFXXGDB

其中有些字母已丟失，清添寫完整，并畫出此二義樹。

7、設(shè)字符串S="aabaabaabaac",P="aabaac”

(1)給出S和P的next值；

(2)若S作主串，P作模式串，試給出利用Brute-Force算法和KMP算法的匹配過程。

8、畫出下列廣義表(0人,(13,9刀》,任下))的兩種存儲(chǔ)結(jié)構(gòu)圖。

五、算法設(shè)計(jì)題

1、編寫算法，按矩陣格式輸出按行序壓縮存儲(chǔ)的n階上三角矩陣。

2^已知鏈串類型名為linkstr,編寫算法voidfirstupr(linkstr*s),實(shí)現(xiàn)將鏈串中存放的■個(gè)英文句子的各單

詞的首字母變?yōu)榇髮憽?/p>

答案：

四、應(yīng)用題

1、答：hcad(tail(head(tail(L))))

2、答：

0c1AA

該廣義表的深度為4。

3、答：

該廣義表的一種存儲(chǔ)結(jié)構(gòu)如下:

該廣義表的表頭為a,表尾為((b,(a,b)),((a,b),(a,b)))。

該廣義表的深度為3。

4、答：該二叉樹如下:

該二叉樹的先序序列為:ABCDEGFIHo

5、答：

該二叉樹如下:

6、答：

先序：BELKCJADGFHI

中序：LKECAJBDFGIH

后序：KLAJCEFIHGDB

該二叉樹如下：

7、解析：next的計(jì)算方法是：

voidgetnext(string*t,intnext[])/*由模式串t求出next值*/

{intj,k;

j=O;k=-l;next[0]=-l;

while(j<t->length)

if(k==-l||t->ch[j]==t->ch[k])

{j++；k++;next[j]=k;}

elsek=next[k];

(1)

S的next值如下:

j01234567891011

S串a(chǎn)abaabaabaac

next[j]-101012345678

T的next值如下：

J012345

p串a(chǎn)abaac

next[j]-101012

(2)利用BF算法的匹配過程:利用KMP算法的匹配過程：

第一趟匹配：aabaabaabaac第一趟匹配：aabaabaabaac

aabaac(i=6,j=6)aabaac(i=6,j=6)

第二趟匹配：aabaabaabaac第二趟匹配：aabaabaabaac

aa(i=3,j=2)(aa)baac

第三趟匹配：aabaabaabaac第三趟匹配：aabaabaabaac

a(i=3,j=l)(成功)(aa)baac

第四趟匹配：aabaabaabaac

aabaac(i=9,j=6)

第五趟匹配：aabaabaabaac

aa(i=6,j=2)

第六趟匹配：aabaabaabaac

a(i=6,j=l)

第七趟匹配：aabaabaabaac

(成功)aabaac(i=13,j=7)

8、答：

(1)廣義表(()人,出,((3旦)),出下))的頭尾表示法如圖1所示。

圖1廣義表(()人,出,((3丁)),田F))頭尾表示法

(2)廣義表(()/,(8,((：,。)),也1))的孩子兄弟表示法如圖2所示。

圖2廣義表(()人,(8,?,口)),也下))孩子兄弟表示法

五、算法設(shè)計(jì)題

1>print(inta[],intn)

(

intij;

fbr(i=O;i<n;i-H-)

{fbr(j=O;jvn;j++)

if(i<=j)printf(,'%4d,|,a[i*(2*n-i+l)/2+j-i]);

elseprintf(,,%4d,,,a[n*(n+l)/2]);

printR%")；

2、voidfirstupr(linkstr*s)

{intword=0;linkstr*p;

p=s->next;

whilc(p!=NULL)

{if{p->ch—1)word=0;

elseif(word==0)

{if(p->ch>=,a,&&p->ch<-z,)

p->ch-=32;

word=l;

p=p->next;}}

一、判斷題

1、度為2的樹就是二叉樹。（x）

2、完全二叉樹一定存在度為1的結(jié)點(diǎn)。（x）

3、由樹轉(zhuǎn)換成二叉樹，其根結(jié)點(diǎn)的左子樹總是空的。x

4、完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必是葉子結(jié)點(diǎn)。（Y）

5、二叉樹只能用二叉鏈表表示。（x）

6、給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。（Y）

7,一棵樹中的葉子數(shù)一定等于與其對應(yīng)的二叉樹的葉子數(shù)。（x）

8、霍夫曼樹無左右子樹之分。x

9、給定權(quán)值的霍夫曼樹是唯一的。x

10、線索二叉樹的優(yōu)點(diǎn)是便于在中序下查找前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。（4）

11、二叉樹中序線索化后，不存在空指針域。（x）

12、霍夫曼樹的結(jié)點(diǎn)個(gè)數(shù)不能是偶數(shù)。（4）

13、由樹的前序和中序遍歷序列可以導(dǎo)出樹的后序遍歷序列。（x）

14、霍夫曼樹是帶權(quán)路徑長度最短的樹，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。＜

15、線索二叉樹的指針域中，指向前驅(qū)或后繼的個(gè)數(shù)多于指向孩子的個(gè)數(shù)。J

16、在二叉排序樹上插入新結(jié)點(diǎn)時(shí)，不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某葉子結(jié)點(diǎn)指針。J

二、單選題

1、樹轉(zhuǎn)換成二叉樹后，二叉樹的根結(jié)點(diǎn)（）。

A）無左孩子B）無右孩子C）既有左孩子也有右孩子D）左孩子和右孩子不確定

2、引入線索二叉樹的目的是（）。

A）加快杳找結(jié)點(diǎn)的前馱或后繼的速度B）為了能在二叉樹中方便地進(jìn)行插入與刪除

C）為了能方便地找到雙親D）使二叉樹的遍歷結(jié)果唯一

3、下列關(guān)于二叉樹度的說法中正確的是（）。

A.二叉樹的度為2B.一棵二叉樹的度可以小于2

C.二叉樹中至少有?個(gè)結(jié)點(diǎn)的度為2D.二義樹中任何一個(gè)結(jié)點(diǎn)的度都為2

4、線索二叉樹是一種（）結(jié)構(gòu)。

A）邏輯B）邏輯和存儲(chǔ)C）物典D）線性

5、下列敘述正確的是（）。

A.二叉樹是度為2的有序樹。

B.完全二叉樹一定存在度為1的結(jié)點(diǎn)。

C.對于有N個(gè)結(jié)點(diǎn)的二又樹，其高度為LlogznJ+l。

D.深度為K的二叉樹中結(jié)點(diǎn)總數(shù)￡2口。

解析：二又樹是度不大于2的有序樹，選項(xiàng)A錯(cuò)誤。當(dāng)結(jié)點(diǎn)個(gè)數(shù)n為偶數(shù)時(shí)，完全二又樹中有且僅有個(gè)

度為1的結(jié)點(diǎn)，當(dāng)結(jié)點(diǎn)個(gè)數(shù)n為奇數(shù)時(shí)，完全二叉樹中沒有度為1的結(jié)點(diǎn)，選項(xiàng)B錯(cuò)誤。具有n個(gè)結(jié)點(diǎn)的

完全二叉樹的深度為Llog2n」+1,選項(xiàng)C錯(cuò)誤。深度為k（Ql）的二叉樹上至多有2七1個(gè)結(jié)點(diǎn)，選項(xiàng)D正確。

6、霍夫曼樹中度為1的結(jié)點(diǎn)個(gè)數(shù)為（）。

A）OB）1C）2D）不確定

7、若一棵二叉樹有10個(gè)度為2的結(jié)點(diǎn)，5個(gè)度為1的結(jié)點(diǎn)，則度為0的結(jié)點(diǎn)個(gè)數(shù)是

A.9B.IIC.15D.不確定

8、若X是二叉中序線索樹中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則x的前驅(qū)為（）。

A.X的雙親B.X的右子樹中最左的結(jié)點(diǎn)

C.X的左子樹中最右結(jié)點(diǎn)D.X的左子樹中最右葉結(jié)點(diǎn)

9、一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹，其高度最小為（）。

A.10B.IIC.12D.不確定

10、高度為K的二叉樹的最大結(jié)點(diǎn)數(shù)為（）。

A.2KB.2K_|C.2K-1D.2K''-1

11、在有n個(gè)葉子結(jié)點(diǎn)的霍夫曼樹中，其結(jié)點(diǎn)總數(shù)為（）。

A）nB）2n-1C）2n+1D）2n

12、對二叉樹的結(jié)點(diǎn)從1開始進(jìn)行連續(xù)編號，要求每個(gè)結(jié)點(diǎn)的編號大于其左、右孩子的編號，同一結(jié)點(diǎn)的

左右孩子中，其左孩子的編號小于其右孩子的編號，可采用（）次序的遍歷實(shí)現(xiàn)編號。

A.先序B.中序

C.后序D.從根開始按層次遍歷

解析：由于每個(gè)結(jié)點(diǎn)的編號大于其左、右孩子的編號，所以先遍歷該結(jié)點(diǎn)的孩子，再遍歷該結(jié)點(diǎn)。在一結(jié)

點(diǎn)的左、右孩子中，其左孩子的編號小于其右孩子的編號，所以先遍歷左孩子再遍歷右孩子。由此可知，

遍歷的順序?yàn)椋鹤蠛⒆右挥液⒆右桓Y(jié)點(diǎn)?？刹捎煤笮虼涡虻谋闅v實(shí)現(xiàn)編號。

13、若一個(gè)：叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。

A.空或只有一個(gè)結(jié)點(diǎn)B.任一結(jié)點(diǎn)無左子樹

C.高度等于其結(jié)點(diǎn)數(shù)D.任一結(jié)點(diǎn)無右子樹

解析：若二叉樹的高度等于其結(jié)點(diǎn)數(shù)，則每層只有一個(gè)結(jié)點(diǎn)，其前序序列和后序序列正好相反。A、B和D

都是二叉樹的高度等于其結(jié)點(diǎn)數(shù)的特殊情況，選擇A、B或D都不夠全面。

14、利用二叉鏈表存儲(chǔ)樹，則根結(jié)點(diǎn)的右指針是（）。

A.指向最左孩子B.指向最右孩子C.空D.非空

15、設(shè)森林F中有三棵樹，第一、第二、第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為Ml、M2和M3。與森林F對應(yīng)的二

叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是

A.MlB.M1+M2C.M3D.M2+M3

解析：根據(jù)森林（樹）與二叉樹的轉(zhuǎn)換規(guī)則，與森林對應(yīng)的二叉樹的根結(jié)點(diǎn)的右子樹的結(jié)點(diǎn)數(shù)就是第二顆

和第三棵樹的結(jié)點(diǎn)數(shù)之和。

16、下列敘述正確的是

A.樹的后根遍歷序列等同于該樹對應(yīng)的二叉樹的后序序列。

B.給定一棵樹，可以找到唯一的一棵二叉樹與之對應(yīng)。

C.已知棵樹的前序遍歷序列和中序遍歷序列，可以得到該樹的后序遍歷序列。

D.必須把樹轉(zhuǎn)換成二叉樹后才能進(jìn)行存儲(chǔ)。

解析：樹的遍歷有先根序遍歷和后根序遍歷兩種方法。其中，先根序遍歷序列等同于對應(yīng)的二叉樹的先序

序列，后根序遍歷序列等同于對應(yīng)的二叉樹的中序序列。選項(xiàng)A和C錯(cuò)誤。樹的存儲(chǔ)有雙親表示法、孩子

鏈表示法、孩子雙親表示法和孩子兄弟表示法等多種方法。