一、判斷題

四.串

1、確定串T在串S中初次出現(xiàn)的位置的操作稱為串的模式匹配。（）

2、假如一種串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。（）

3、一種任意串是其自身的子串。（）

KV2、X3、V

五.數(shù)組和廣義表

1、多維數(shù)組是向量的推廣°（）/*數(shù)組和廣義表線性表在含義上的擴展*/

2、用相鄰矩陣表達圖所用的存儲空間大小與圖的邊數(shù)成正比。（）/*頂點*/

3、除插入和刪除操作外，數(shù)組的重要操作尚有存取、修改、檢索和排序等。（）

4、稀疏矩陣中0元素的分布有規(guī)律，因此可以采用三元組措施進行壓縮存儲。（）/*稀疏

矩陣中0元素的分布無規(guī)律*/

5.假如采用如下方式定義一維字符數(shù)組：

constintmaxSize=30;/*常變量在程序運行中不能進行修改*/

chara[maxSize];

則這種數(shù)組在程序執(zhí)行過程中不能擴充。

6.假如采用如下措施定義一維字符數(shù)組：

intmaxSiZP=30;

char*a=newchar.maxSize];

則這種數(shù)組在程序執(zhí)行過程中不能擴充。

7.數(shù)組是一種靜態(tài)的存儲空間分派，就是說，在程序設(shè)計時必須預(yù)先定義數(shù)組的數(shù)據(jù)類型和存

儲空間大小，由編譯程序在編譯時進行分派。/*對「數(shù)組一旦規(guī)定了它的維數(shù)和各維長度，便可

為它分派存儲空間*/

8.多維數(shù)組是一種復(fù)雜的數(shù)據(jù)構(gòu)造，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。

9.使用三元組表達稀疏矩陣中的非零元素能節(jié)省存儲空間。

10.用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。

1-5XXXXV

6-10XXVVV

11、一種廣義表的深度是指該廣義表展開后所含括號的層數(shù)。O

12.一種廣義表的表頭總是一?種廣義表。()

13.一種廣義表的表尾總是一種表。()

14.一種廣義表((a),((b),c),(((d))))的長度為3,深度為4。()

15.一種廣義表((a),((b),c),(((d))))的表尾是:((b),c),(((d))))。(129)

11、V12、X13、V14、V15、V

六.樹

1、一般樹和二叉樹的結(jié)點數(shù)目都可認為0。()

2、在只有度為0和度為k的結(jié)點的k又樹中，設(shè)度為0的結(jié)點有nO個，度為k的結(jié)點有nk個,

則有nO=nk+lo()

3、折半搜索只合用與有序表，包括有序的次序表和有序的鏈表。()

4、哈夫曼樹一定是滿一叉樹。()

5、給定一組權(quán)值，可以唯一構(gòu)造出一棵哈夫曼樹。()

6、深度為h的非空二叉樹的第i層最多有2iT個結(jié)點。()

7、滿二叉樹也是完全二叉樹。()

8、已知一棵二義樹的前序序列和后序序列可以唯一地構(gòu)造出該二叉樹。()

9、非空二叉排序樹的任意一棵子樹也是二叉排序樹。（）

10、對一棵二叉排序樹進行前序遍歷一定可以得到一種按值有序的序列。（）

11、設(shè)與一棵樹T所對應(yīng)的二叉樹為BT,則與T中的葉子結(jié)點所對應(yīng)的BT中的結(jié)點也一定是葉

子結(jié)點。（）

12、哈夫曼樹一定是完全二叉樹。（）

13、由一棵二叉樹的前序序列和后序序列可以唯一確定它。（）

14、在完全二叉樹中，若某結(jié)點元左孩子，則它必是葉結(jié)點。（）

15、樹的帶權(quán)途徑長度最小的二叉樹中必然沒有度為1的結(jié)點。（）

16、二叉樹可以用0W度W2的有序樹來表達。（）

17、一組權(quán)值，可以唯一構(gòu)造出一一棵哈夫曼樹。（）

18、將一棵樹轉(zhuǎn)換成二叉樹后，根結(jié)點沒有左子樹；（）/*沒有右子樹*/

19、用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷：（）

20.二叉樹是一棵無序樹。（）

21.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進行前序遍歷和后序遍

歷，則具有相似的成果。（）

22.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進行中序遍歷和后序遍

歷，則具有相似的成果。（）

2工在一棵一叉樹中,假定每個結(jié)點只有左子女，沒有右子女，對它分別進行前序遍歷和中根遍

歷，則具有相似的成果。（）

24.在一棵二叉樹中，假定每個結(jié)點只有左子女，沒有右子女，對它分別進行前序遍歷和按層遍

歷，則具有相似的成果。（）

25.在樹的存儲中，若使每個結(jié)點帶有指向雙親結(jié)點的指針，這為在算法中尋找雙親結(jié)點帶來以

便。()

26.對于一棵具有n個結(jié)點，其高度為h的二叉樹，進行任一種次序遍歷的時間復(fù)雜度為0(n)。

()

27.對于一棵具有n個結(jié)點，其高度為h的任何二叉樹，進行任一種次序遍歷的時間復(fù)雜度均為

0(h)4,()

28.對于一棵具有n個結(jié)點的任何二叉樹，進行前序、中序或后序的任一種次序遍歷的空間復(fù)雜

度為O(logzn)。()/*log2n下取整+1*/

29.在一棵具有n個結(jié)點的線索二叉樹中，每個結(jié)點的指針域也許指向子女結(jié)點，也也許作為線

索，使之指向某一種遍歷次序的前驅(qū)或后繼結(jié)點，所有結(jié)點中作為線索使用的指針域共有n個。

()

30.線索二叉樹中的每個結(jié)點一般包具有5個數(shù)據(jù)組員。()

1-5VXVXX6-10XVXVX

11-15XXXVV16-20XXXVX

21-25XVXVV26-30VXXXV

二、填空題：

四.串

1、一種串的任意個持續(xù)的字符構(gòu)成的子序列稱為該串的—子串，包括該子串的串稱為—

主串,

2、求串T在主串S中初次出現(xiàn)的位置的操作是—Index(S,T,pos)。

3、在初始為空的隊列中插入元素A,B,C,D后來，緊接著作了兩次刪除操作，此時的隊尾元素是

D______e

4、在長度為n的循環(huán)隊列中，刪除其節(jié)點為x的時間愛朵度為_0(n)。

5、已知廣義表L為空，其深度為_____1______<,

6.若設(shè)串S="documentHash.doc'O"，則該字符串S的長度為_____16____。

1、子串，主串2、Index(S,T,pos)3、D4、0(n)5、16.16

五.數(shù)組和廣義表

1、已知一次序存儲的線性表，每個結(jié)點占用k個單元，若第一種結(jié)點的地址為DA1,則第i個

結(jié)點的地址為—DA*k。

2、設(shè)一行優(yōu)先次序存儲的數(shù)組A[5][6],A[0][0]的地址為1100,且每個元素占2個存儲單元，

則A[2][3]的地址為_1130__________o

3、設(shè)有二維數(shù)組A[9][19],其每個元素占兩個字節(jié)，第一種元素的存儲地址為100,若按行優(yōu)

先次序存儲，則元素A[6,6]的存儲地址為-340,按列優(yōu)次序存儲，元素A[6,6]

的存儲地址為220。/*100+(6*9+6)*2*/

4、假設(shè)以行為優(yōu)先存儲的三維數(shù)組A[5][6][7],A[0][0][0]的地址為1100,每個元素占兩個存

儲單元，則A[元[3][2]的地址為_1482o/*1100+{(4*6+3)*7+2}*2*/

4、設(shè)二維數(shù)組按列優(yōu)先存儲，每個元素占1個存儲單元，元素Aoo的存儲地址loc4。)，

則Aij的存儲地址loc(Aij)=_loc(AOT)+j*_m+i。

6、稀疏矩陣一般采用一三元組措施進行壓縮存儲。

7、稀疏矩陣可用_三元組進行壓縮存儲，存儲時需存儲非零元的—行號、—

列號—、_值。

8、若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中，區(qū)域外的值全為0,則稱

為____對角矩陣_____。

9、若一種n階矩陣A中的元素滿足：A『A,i(0<=I,j<=n-l)則稱A為一對稱________矩陣：

若主對角線上方(或下方)的所有元素均為零時，稱該矩陣為一(±)下三角矩陣o

10、對于下三角形和上三角形矩陣，分別以按行存儲和按列存儲原則進行壓縮存儲到數(shù)組M[k]

中，若矩陣中非0元素為Au,則k對應(yīng)為l)/2+j(i>=j)—和

_(l+j)*(j-D/2+i(i<=j)(下標從0開始)。

11、設(shè)有一下三角形矩陣A[5][5]按行壓縮存儲到數(shù)組B中，B[0]的地址為100,每個元素占2

個單元,則A[3][2]地址為116。/*{3*(3+1)/2+2)*2=16*/

12.一維數(shù)組所占用的空間是持續(xù)的。但數(shù)組元素不一定次序存取，一般是按元素的下標

存取的。

13.在程序運行過程中不能擴充的數(shù)組是一靜態(tài)_______分派的數(shù)組。這種數(shù)組在申明它時必須

指定它的大小。

14.在程序運行過程中可以擴充的數(shù)組是動態(tài)分派的數(shù)組。這種數(shù)組在申明它時需要

使用數(shù)組指針。

?15.二維數(shù)組是一種非線性構(gòu)造，其中的每一種數(shù)組元素最多有個直接前驅(qū)(或直

接后繼)。

16.若設(shè)一種nxn的矩陣A的開始存儲地址L0C(0,0)及元素所占存儲單元數(shù)d已知，按行存

儲時其任意一種矩陣元素的存儲地址為_L0C(0,0)+(i*n+j)d。

17.對稱矩陣的行數(shù)與列數(shù)—相等且以主對角線為對稱軸，=因此只存儲它的上

三角部分或下三角部分即可。

1R.將一種n階對稱矩陣的上三角部分或下三角部分壓縮寄存于一種一維數(shù)組中，則一維數(shù)組需

要存儲_n*(n+1)/2個矩陣元素。

19.運用三元組表寄存稀疏矩陣中的非零元素，則在三元組表中每個三元組元素對應(yīng)一種非零元

素的行號、列號和—值_____。

1、DAl+(i-l)*k2、1100+(6*2+3)*2=11303、100+(19*6+6)*2=340,100+(9*6+??????)

*2=2204、14825、loc(aOO)+(j*m+i)*l6、三元組7、三元組，行

號，列號，值8、對角矩陣9、上(下)三角矩陣10、(i

2j)，j*(j-l)/2+i-l(i<j)Ik108

12.下標(或次序號)13.靜態(tài)14.動態(tài)15.兩個16.LOC(O,O)+(i*n+j)*d17.

相等18.n(n+l)/219.值

21、廣義表(A,(a,b),d,e,((i,j),k)),則廣義表的長度為5,深度為_______3_°

22、已知廣義表A=((a,b,c),(d,c,f)),則運算hcad(hcad(tail(A))))=_____d________。

23、已知廣義表Is=(a,(b,c,d),e),運用head和tail函數(shù)取出Is中的原子b的運算是

head(head(tail(s)))。

24.非空廣義表的除第一種元素外其他元素構(gòu)成的表稱為廣義表的—表尾o

25.廣義表A((a,b,c),(d,e,f))的表尾為_25.((d,e,f))

26.廣義表是一種遞歸的數(shù)據(jù)構(gòu)造，子表結(jié)點則指示下一層廣義表的—表頭結(jié)點。

27.廣義表的深度定義為廣義表括號的一層數(shù)—o

21、5,322、d23、head(head(tai1(s)))24.表尾25.((d,e,f))

26.表頭結(jié)點27.層數(shù)

六.樹

1、在樹構(gòu)造里，有且僅有一種結(jié)點沒有前驅(qū)，稱為根，非根結(jié)點有且僅有一種____前驅(qū),

且存在一條從根到該結(jié)點的途徑。

2、度數(shù)為0的結(jié)點，即沒有子樹的結(jié)點叫作—葉子_____結(jié)點或_終端結(jié)點。同一種

結(jié)點的兒子結(jié)點之間互稱為____兄弟結(jié)點。

3、假定一棵樹的廣義表為A(B(e),C(F(h,i,j),g),D),則該樹的度為______3—,樹的深度為

_4______,終端結(jié)點為_ehi」gD—,單分支結(jié)點為B，雙分支結(jié)點個數(shù)為_1一,三分

支結(jié)點為_A_F___,C結(jié)點的雙親結(jié)點是_A,孩子結(jié)點是—F,g—。

4、完全二叉樹、滿二叉樹、線索二叉樹和二叉排序樹這四個名詞術(shù)語中，與數(shù)據(jù)的存儲構(gòu)造有

關(guān)系的是—線索.

5、有三個結(jié)點的二叉樹，最多有____5種形狀。

6、高度為k的二叉樹具有的結(jié)點數(shù)目，至少為_k_,最多為_2k-l—o/*高度？深度？*/

7、對任何一棵二叉樹，若nO,nl,n2分別是度為0,1,2的結(jié)點的個數(shù)，則n0=_n2+l。

8、在含100個結(jié)點的完全二叉樹，葉子結(jié)點的個數(shù)為_50o

9、將一種數(shù)據(jù)元素(或記錄)的任意序列，重新排列成一種按關(guān)鍵字有序的序列叫一排序—。

10、若一棵滿二叉樹具有121個結(jié)點，則該樹的深度為—7____。

11、一種具有767個結(jié)點的完全二叉樹，其葉子結(jié)點個數(shù)為_384_____。

12、深度為90的滿二叉樹，第11層有_1024______個結(jié)點。

13、有100個結(jié)點的完全二叉樹，深度為7_____。

14、設(shè)一棵二叉樹中度為2的結(jié)點10個，則該樹的葉子個數(shù)為ll_o/*n0=n2+l*/

?15、具有3個2度結(jié)點和4個葉結(jié)點的二叉樹可含_________個1度結(jié)點。

16、一棵具有5層滿二叉樹中節(jié)點總數(shù)為_31。

17、一棵具有16個結(jié)點的完全一叉樹，對他按層編號,對于編號為7的結(jié)點，他的雙親結(jié)點及

左右結(jié)點編號為—3―、—14—、-15。

18、深度為k(設(shè)根的層數(shù)為1)的完全二叉樹至少有______個結(jié)點，至多有_______個結(jié)點。

19、若要對某二又排序樹進行遍歷，保證輸出所有結(jié)點的值序列按增序排列，應(yīng)對該二義排序樹

采用—中序_____遍歷法。

20、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)措施查找元素24,需

要進行_____4________次元素之間的比較。/*16、27、22、24*/

21、設(shè)有10個值，構(gòu)成哈夫曼樹，則該哈夫曼樹共有—19—個結(jié)點。/*10個值就是10個葉

子結(jié)點；沒有1度的結(jié)點*/

22、從樹中一種結(jié)點到另一種結(jié)點之間的分支構(gòu)成這兩個結(jié)點之間的____途徑。

23.對于一棵具有n個結(jié)點的樹，該樹中所有結(jié)點的度數(shù)之和為一n-1___。/*每一種結(jié)點對應(yīng)

一種根就是一度(除根節(jié)點外)*/

24.一棵樹的廣義表表達為a(b(c,d(e,f),g(h)),i(j,k(x,y))),結(jié)點k的所有祖先的結(jié)點數(shù)為

_2______個。

25.一棵樹的廣義表表達為a(b(c,d(e,f),g(h)),i(j,k(x,y))),結(jié)點f的層數(shù)為3。

假定樹根結(jié)點的層數(shù)為0。

26.假定一棵三叉樹(即度為3的樹)的結(jié)點個數(shù)為50,則它的最小高度為_4____o假定樹

根結(jié)點的深度為0。

27.在一棵高度為3的四叉樹中，最多具有255個結(jié)點，假定樹根結(jié)點的高度為0。

28.在一棵三叉樹中，度為3的結(jié)點數(shù)有2個，度為2的結(jié)點數(shù)有1個，度為1的結(jié)點數(shù)為2

個，那么度為0的結(jié)點數(shù)有—6—個。

29.一棵高度為5的完全二叉樹中，最多包具有—63—個結(jié)點。假定樹根結(jié)點的高度為0。

30.假定一棵樹的廣義表表達為A(B(C,D(E,F,G),H(LJ)))，則該樹的高度為—3。假定

樹根結(jié)點的高度為0。

31.在一棵二又樹中,假定雙分支結(jié)點數(shù)為5個，單分支結(jié)點數(shù)為6個，則葉子結(jié)點數(shù)為—6

個。/*n0=n2+nl*/

32.假定一棵二叉樹的結(jié)點數(shù)為18,則它的最小高度為_3。假定樹根結(jié)點的高度為0。

1、前驅(qū)，途徑2、葉子，終端，兄弟3、3；3；e,h,I,j,g；C；A,F；A；F,g

4、線索5、56、k,2-17、nl+n2

9、排序10、711、38412、102413、714、1115、1(0)16、31

17、3,14,1518、2kl,2k-l19、中序21、1922、途徑

23.n-124.225.326.427.8528.629.63

30.331.632.4

三、選擇題：

四.串

()1.在目的串T[0…="xwxxyxy”中，對模式串p[0…mT]="xy”進行子串定位操

作的成果

A.0B.2

C.3D.5

()2.如下陳說中對的的是________

A.串是一種特殊的線性表B.串的長度必須不小于零

C.串中元素只能是字母D.空串就是空白串

()3.若目的串的長充為n,模式串的長度為[n/3],則執(zhí)行模式匹配算法時，在最壞狀況下

的時間復(fù)雜度是

A.0(1)B.O(n)

C.O(n2)D.O(n3)

串1一3CAB

五.數(shù)組和廣義表

()1.二維數(shù)組A按行次序存儲，其中每個元素占1個存儲單元。若AUH1]的存儲地址為

420,A[3]⑶的存儲地址為446,則A⑸⑸的存儲地址為

A.470B.471

C.472D.473

()2.在稀疏矩陣的十字鏈接存儲中，每個列單鏈表中的結(jié)點都具有相似的____o

A.行號B.列號

C.元素值D.地址

()3.一種數(shù)組元素Mi]與的表達等價。

A、*(A+i)B,A+i

C、*A+iD,&A+i

()4.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點都具有相似的

A、行號B,列號

C、元素值D.地址

數(shù)組1—4CAAA

廣義表

()1.已知廣義表的表頭為A,表尾為(R,C),則此廣義表為

A.(A,(B,C))B.(A,B,C)

C.(A,B,C)D.((A,B,0)

()2.設(shè)一種廣義表中結(jié)點的個數(shù)為n,則求廣義表深度算法的時間復(fù)雜度為__。

A、0(1)B、0(n)

C、0(n2)D^O(log2n)

（）3.一種非空廣義表的表頭—

A.不也許是子表B.只能是子表

C.只能是原子D.可以是子表或原子——~~——

02335

（）4.設(shè)一種廣義表中結(jié)點的個數(shù)為n,則求廣義表深度算法的時

間復(fù)雜度為。

A、0（1）B、0（n）

C、0（n2）D、0（log2n）

廣義表1—4BDDB

六.樹

（）1.將一棵有100個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點進行編號，根結(jié)點

的編號為1,則編號為49的結(jié)點的左孩子的編號為.

A.98B.99

C.50D.48

（）2.對于如圖所示二叉樹采用中根遍歷，對的的遍歷序列應(yīng)為（）

A.ABCDEFB.ABECDF

C.CDFBEAD.CBDAEF

（）工一叉樹中第5泉上的結(jié)點個數(shù)最多為

A.8B.15

C.16D.32

（）4.由權(quán)值分別為3,8,6,2,5的葉子結(jié)點生成一棵哈夫曼樹，它的帶權(quán)途徑長度為

A、24B、48

C、72D、55

()5.一棵度為3的樹中，度為3的結(jié)點個數(shù)為2,

點個數(shù)為________

A.4B.5

C.6D.7

樹1—5ADCDC

四、應(yīng)用題：

1、己知稀疏矩陣如下:

10002

00300

A-45000

00000

■00060

請寫出該稀疏矩陣三元組表達，和十字鏈表表達方式。

2、廣義表A=(a,b,(c,d),(e,(f,g)))，求其長度,及深度。

3、請畫出下面廣義表對應(yīng)的加入表頭結(jié)點的單鏈表表達，

D(A(x,y,L(a,b)),B(z,A(x,y,L(a,b))))?

4、設(shè)二叉樹后根遍歷為BAC,畫出所有也許的二叉樹。

5、假設(shè)一棵二叉樹的層序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,請畫出該樹。

6、有一種完全二叉樹按層次次序寄存在一-維數(shù)組中，如下所示：請指出結(jié)點P的父結(jié)點，左子

女，右子女。123456789101112

HkACDPFJXBQZ

c

o

A口

7、給出下列二叉樹的先序序