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

一、判斷題

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

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

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

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

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

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

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

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

9、KMP算法的特點是在模式匹配時指示主串的指針不會變小。3）

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

11、對稱矩陣壓縮存儲后不會失去隨機存取功能。（J）

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

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

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

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

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

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

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

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

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

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

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

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

答案：X

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

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

答案：J

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

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

答案：X

24、兩個稀疏矩陣的和仍為稀疏矩陣。（）

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

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

答案：X

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

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

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

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

答案：V

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

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

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

答案：J

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

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

答案：，

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

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

溢”有區(qū)別的，“?？铡迸c“下溢”也有區(qū)別。

答案：X

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

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

答案：V

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

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

答案：X

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

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

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

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

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

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

或指向空（鏈表為空）。

答案：X

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

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

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

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

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

41、兩個稀疏矩陣的和仍為稀疏矩陣。x

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

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

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

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

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

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

個結(jié)點。V

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

49、二叉樹用鏈式存儲時，空鏈域數(shù)多于非空鏈域數(shù)。M

50、KMP算法的特點是在模式匹配時指示主串的指針不會回溯。＜

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

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

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

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

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

答案：V

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

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

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

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

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

答案：4

56、稀疏矩陣壓縮存儲后，必會失去隨機存取功能。4

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

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

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

答案：V

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

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

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

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

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

答案：X

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

關(guān)系。4

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

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

答案：X

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

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

答案：X

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

64、頭結(jié)點就是鏈表中的第I個結(jié)點。()

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

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

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

答案：X

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

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

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

答案：J

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

二、單選題

1、k=l;

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

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

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

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

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

①除最后一個元素外，每個元素都有后繼。

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

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

④線性表是有限序列。

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

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

4、下面哪一個不是順序表的特點（）。

A）邏輯上相鄰的元素，存儲在計算機中相鄰的存儲空間

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

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

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

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

A）便于插入、刪除運算B）存儲空間動態(tài)分配

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

6、若線性表采用鏈式存儲，則表中各元素的存儲地址

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

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

7、鏈表不具有的特點是（）

①可以隨機訪問任何一個元素②插入和刪除元素不需要移動元素

③不必事先估計存儲空間④所需存儲空間與鏈表長度成正比

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

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

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

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

時間。

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

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

結(jié)點，則執(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、鏈表不具有的特點是（）

A.插入、刪除操作不需要移動元素B.可隨機訪問任一元索

C.不必事先估計存儲空間D.所需空間與線性長度成正比

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

（

A.以順序方式存儲B.以鏈接方式存儲

C.以散列方式存儲D.以索引方式存儲

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

結(jié)點，則執(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、在線性表的卜列存儲結(jié)構(gòu)中，讀取元素花費時間最少的是（）.

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

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

答案：④

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

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

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

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

1.1+1)/?+1

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

〃￡"22

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

答案：②

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

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

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

個數(shù)據(jù)元素時所需移動的數(shù)據(jù)元素的平均次數(shù)為：

金〃〃占n22

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

答案：②

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

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、若進棧序列為1,2,3,4,則不可能得到的出棧序列是

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

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

時，top變化為()

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

20、設(shè)輸入序列為1,2,3,4,借助一個?？梢缘玫降妮敵鲂蛄惺?)。

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

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

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

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

22、棧和隊列都是()。

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

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

23、棧和隊列都是()

①順序存儲的線性表②鏈式存儲的線性表

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

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

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

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

為空的條件是()。

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

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

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

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

27、串是()

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

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

28、若將n階對稱矩陣A的卜三角部分以行序為主序壓縮存儲到一維數(shù)組B中，A的卜?標卜.界為0,B的

下標下界為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]的下標下界為1,每個元素占3個字節(jié)，存儲在起始地址為100的連續(xù)內(nèi)存單元，則元

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

①215②270③262④229

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

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

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

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

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

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

32、對稀疏矩陣進行壓縮存儲的目的是

A)便于進行矩陣運算B)便了輸入和輸出

C)省作儲)舊D)降低運算的時間復(fù)雜度

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

A)廣義點的衣頭怠工一個廣義之B)廣義表的表尾總是一個廣義表

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

34、對廣義表A=(x,((a,b),c,d))做運算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中取出原子項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ù)組進行存儲，則下面說法不正確的是()。

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

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

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

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

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

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

A)最少有31個結(jié)點，最多有64個結(jié)點B)最少有32結(jié)點，最多有64個結(jié)點

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

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

性質(zhì)3

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

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

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

42、n個結(jié)點的二叉樹，若用二叉鏈表作為存儲結(jié)構(gòu)，則非空閑的左、右孩子鏈域為

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

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

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

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

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

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

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

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

①不多于一個結(jié)點的二叉樹

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

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

④其中任意?個結(jié)點的度不為2的

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

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

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

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

132。

答案：D

48、若棧采用順序存儲方式存儲，現(xiàn)兩棧共享空間top[i]代表第i個棧(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]向共享空間的中心延伸，僅當兩棧頂指

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

答案：B

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

的下一個位置。若當前rear和front的值分別為。和3,當從隊列中刪除兩個元素，再加入兩個元素后，rear

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

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

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

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

答案：B

50、用不帶頭結(jié)點的單鏈表存儲隊列時，其隊頭指針指向隊頭結(jié)點，其隊尾指針指向隊尾結(jié)點，則在進行刪除

操作時()。

A.僅修改隊頭指針B.僅修改隊尾指針

C.隊頭、隊尾指針都要修改D.隊頭、隊尾指針都可能要修改

解析：當隊列中有兩個或兩個以上的結(jié)點時，刪除操作只修改隊頭指針，若隊列中只有一個結(jié)點時，刪除

操作既要修改隊頭指針，乂要修改隊尾指針。

答案:D

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

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

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

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

個元素，e2出棧，棧中有1個元素；e3、e4進棧，棧中有3個元素，e4出棧，e3出棧，棧中有1個元素；

e5、e6進棧，棧中有3個元素，e6出棧，e5出棧，棧中有1個元素；el出棧，?？铡Ｓ纱丝芍?，棧中最

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

答案：C

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

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

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

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

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

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

答案：B

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

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

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

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

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

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

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

為(2,1,3).

答案：A

54、設(shè)有一個10階對稱矩陣A,采用壓縮存儲方式，以行序為主序存儲，為第一個元素，其存儲地

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

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

解析：若一個n階對稱矩陣A的卜.標卜界均為0,以行序為主序壓縮存儲，每個元素占用的字節(jié)數(shù)為L,

則元素的地址為：

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

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

都是1,先將下標下界都調(diào)整為0,a[8][5]調(diào)整為a[7][4],然后計算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是一個表頭和表尾都為的空廣義表，即head(L)=(),taiI(L)=(),根據(jù)表頭和表尾的定義可得：L=(())

答案：B

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

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

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

的長度為1,深度為2。

答案：C

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

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、一個nXn階的對稱矩陣采用壓縮存儲時需要的存儲單元數(shù)為()。

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

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

A)邏輯上相鄰的元素，存儲在計算機中相鄰的存儲空間

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

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

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

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

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

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

上面算法的時間復(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ù)項B)數(shù)據(jù)元素C)數(shù)據(jù)對象D)數(shù)據(jù)文件

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

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

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

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

A)dceabB)decbaC)edcbaD)abcde

三、填空題

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

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

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

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

4、有n個結(jié)點的完全二叉樹(空二叉樹的深度為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個字符開始的長度為j的子串。主串的值為"ABCDHIJ”

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

隊尾

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

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

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

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

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

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

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

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

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

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

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ù)的功能是實現(xiàn)將帶頭結(jié)點單鏈表的結(jié)點值按升序排序，請對程序進行填空。

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ù)的功能是實現(xiàn)帶頭結(jié)點的單鏈表逆置，請對程序進行填空。

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采用順序存儲結(jié)構(gòu)。卜.列算法的功能是刪除線性表L中所有值為item的數(shù)

據(jù)元素。

typedefintElemType;

typedefstruct

{ElemType*data;/?存儲空間基地址*/

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

intlistsize;/*當前存儲空間容量（即能存入的元素個數(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é)點的單循環(huán)鏈表中第?個data域值等于x的結(jié)點，請對程序進行填空。

Delete(slink*head,intx)

{slink*p,*q;/*p指向當前處理的結(jié)點,q指向p的前驅(qū)結(jié)點*/

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

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

{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ù)的功能是實現(xiàn)將一個帶頭結(jié)點單鏈表L中所有值為偶數(shù)的結(jié)點放在所有值為奇數(shù)的結(jié)點的前

面，請對程序進行填空。

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ù)的功能是實現(xiàn)將一個帶頭結(jié)點單鏈表L中所有值為x的結(jié)點刪除，請對程序進行填空。

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的運算。

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

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

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

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刀》,任下))的兩種存儲結(jié)構(gòu)圖。

五、算法設(shè)計題

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

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

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

答案：

四、應(yīng)用題

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

2、答：

0c1AA

該廣義表的深度為4。

3、答：

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

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

該廣義表的深度為3。

4、答：該二叉樹如下:

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

5、答：

該二叉樹如下:

6、答：

先序：BELKCJADGFHI

中序：LKECAJBDFGIH

后序：KLAJCEFIHGDB

該二叉樹如下：

7、解析：next的計算方法是：

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è)計題

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é)點。（x）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

二、單選題

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

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

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

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

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

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

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

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

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

A）邏輯B）邏輯和存儲C）物典D）線性

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

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

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

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

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

解析：二又樹是度不大于2的有序樹，選項A錯誤。當結(jié)點個數(shù)n為偶數(shù)時，完全二又樹中有且僅有個

度為1的結(jié)點，當結(jié)點個數(shù)n為奇數(shù)時，完全二叉樹中沒有度為1的結(jié)點，選項B錯誤。具有n個結(jié)點的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

A.先序B.中序

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

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

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

遍歷的順序為：左孩子一右孩子一根結(jié)點?？刹捎煤笮虼涡虻谋闅v實現(xiàn)編號。

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

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

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

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

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

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

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

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

叉樹根結(jié)點的右子樹上的結(jié)點個數(shù)是

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

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

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

16、下列敘述正確的是

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

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

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

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

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

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

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