数据结构第二次单元测试题库（串到树）

一、判断题

四．串

1、确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。（ ）

2、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。（ ） 3、一个任意串是其自身的子串。（ ） 1、∨ 2、Χ 3、∨ 五．数组和广义表

1、多维数组是向量的推广。（ ）/*数组和广义表线性表在含义上的扩展*/ 2、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。（ ）/*顶点*/ 3、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。（ ） 4、稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。（ ）/*稀疏矩阵中0元素的分布无规律*/

5. 如果采用如下方式定义一维字符数组：

const int maxSize = 30;/*常变量在程序运行中不能进行修改*/ char a[maxSize];

则这种数组在程序执行过程中不能扩充。 6. 如果采用如下方法定义一维字符数组： int maxSize = 30;

char * a = new char[maxSize]; 则这种数组在程序执行过程中不能扩充。

7. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。/*对于数组一旦规定了它的维数和各维长度，便可

1

为它分配存储空间*/ 8. 多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。 9. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 10. 用字符数组存储长度为n的字符串，数组长度至少为n+1。 1-5ΧΧΧΧ∨ 6-10ΧΧ∨∨∨

11、一个广义表的深度是指该广义表展开后所含括号的层数。（） 12. 一个广义表的表头总是一个广义表。( ) 13. 一个广义表的表尾总是一个表。( )

14. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的长度为3，深度为4。( )

15. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是（ ( (b), c), ( ( (d) ) )）。( 129 ) 11、∨ 12、Χ 13、∨ 14、∨ 15、∨ 六．树

1、一般树和二叉树的结点数目都可以为0。 （ ）

2、在只有度为0和度为k的结点的k叉树中，设度为0的结点有n0个，度为k的结点有nk个，则有n0=nk+1。（ ）

3、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。（ ） 4、哈夫曼树一定是满二叉树。（ ）

5、给定一组权值，可以唯一构造出一棵哈夫曼树。（ ） 6、深度为h的非空二叉树的第i层最多有2i-1 个结点。（ ） 7、满二叉树也是完全二叉树。（ ）

8、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。（ ）

2

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

10、对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。（ ）

11、设与一棵树T所对应的二叉树为BT，则与T中的叶子结点所对应的BT中的结点也一定是叶子结点。（ ）

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

13、由一棵二叉树的前序序列和后序序列可以唯一确定它。（ ） 14、在完全二叉树中,若某结点元左孩子,则它必是叶结点。（ ） 15、树的带权路径长度最小的二叉树中必定没有度为1的结点。（ ） 16、二叉树可以用0≤度≤2的有序树来表示。（ ） 17、一组权值，可以唯一构造出一棵哈夫曼树。( )

18、将一棵树转换成二叉树后，根结点没有左子树；（ ）/*没有右子树*/ 19、用树的前序遍历和中序遍历可以导出树的后序遍历；（ ） 20. 二叉树是一棵无序树。( )

21. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍历，则具有相同的结果。( )

22. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍历，则具有相同的结果。( )

23. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍历，则具有相同的结果。( )

24. 在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和按层遍历，则具有相同的结果。( )

25. 在树的存储中，若使每个结点带有指向双亲结点的指针，这为在算法中寻找双亲结点带来方

3

便。( )

26. 对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。( )

27. 对于一棵具有n个结点，其高度为h的任何二叉树，进行任一种次序遍历的时间复杂度均为O(h)。( )

28. 对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂度为O(log2n)。( )/* log2n下取整+1*/

29. 在一棵具有n个结点的线索二叉树中，每个结点的指针域可能指向子女结点，也可能作为线索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。( )

30. 线索二叉树中的每个结点通常包含有5个数据成员。( ) 1-5∨Χ∨ΧΧ 6-10Χ∨Χ∨Χ 11-15ΧΧΧ∨∨ 16-20ΧΧΧ∨Χ 21-25Χ∨Χ∨∨ 26-30∨ΧΧΧ∨

二、填空题：

四．串

1、一个串的任意个连续的字符组成的子序列称为该串的__子串______，包含该子串的串称为___主串_____。

2、求串T在主串S中首次出现的位置的操作是___Index(S,T,pos)_____________。

3、在初始为空的队列中插入元素A,B,C,D以后，紧接着作了两次删除操作，此时的队尾元素是___D_______。

4、在长度为n的循环队列中，删除其节点为x的时间复杂度为___ O(n)____________。

4

5、已知广义表L为空，其深度为_____1______。

6. 若设串S = “documentHash.doc\\0”，则该字符串S的长度为_____16____。 1、子串，主串 2、Index(S,T,pos) 3、D 4、O(n) 5、1 6. 16 五．数组和广义表

1、已知一顺序存储的线性表，每个结点占用k个单元，若第一个结点的地址为DA1，则第i个结点的地址为___DA1+(i-1)*k___________。

2、设一行优先顺序存储的数组A[5][6]，A[0][0]的地址为1100，且每个元素占2个存储单元，则A[2][3]的地址为__1130___________。

3、设有二维数组A[9][19]，其每个元素占两个字节，第一个元素的存储地址为100，若按行优先顺序存储，则元素A[6,6]的存储地址为____340__________，按列优顺序存储，元素A[6,6]的存储地址为_____220_________。/*100+(6*9+6)*2*/

4、假设以行为优先存储的三维数组A[5][6][7]，A[0][0][0]的地址为1100，每个元素占两个存储单元，则A[4][3][2]的地址为__1482_____。/*1100+{(4*6+3)*7+2}*2*/

4、设二维数组A[m][n]按列优先存储，每个元素占1个存储单元，元素A00的存储地址loc(A00)，则Aij的存储地址loc(Aij)=_loc(A00)+j*_m+i__________________。 6、稀疏矩阵一般采用_三元组_________方法进行压缩存储。

7、稀疏矩阵可用_三元组________进行压缩存储，存储时需存储非零元的__行号______、____列号____、__值______。

8、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为0，则称为_____对角矩阵_____。

9、若一个n 阶矩阵A中的元素满足：Aij=Aji (0<=I ,j<=n-1)则称A为___对称_________矩阵；若主对角线上方(或下方)的所有元素均为零时，称该矩阵为___（上）下三角矩阵___________。

5

10、对于下三角形和上三角形矩阵，分别以按行存储和按列存储原则进行压缩存储到数组M[k]中，若矩阵中非0元素为Aij，则k对应为__(1+i)*(i-1)/2+j(i>=j)____和_(1+j)*(j-1)/2+i(i<=j)_________(下标从0开始)。

11、设有一下三角形矩阵A[5][5]按行压缩存储到数组B中，B[0]的地址为100，每个元素占2个单元，则A[3][2]地址为_____116_______。/*{3*(3+1)/2+2}*2=16*/

12. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的____下标_____存取的。

13. 在程序运行过程中不能扩充的数组是_静态_________分配的数组。这种数组在声明它时必须指定它的大小。

14. 在程序运行过程中可以扩充的数组是_____动态_____分配的数组。这种数组在声明它时需要使用数组指针。

？15. 二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。

16. 若设一个n?n的矩阵A的开始存储地址LOC(0, 0) 及元素所占存储单元数d已知，按行存储时其任意一个矩阵元素a[i][j]的存储地址为_ LOC(0, 0)+（i*n+ j ）d________。 17. 对称矩阵的行数与列数__相等_______且以主对角线为对称轴，aij = aji，因此只存储它的上三角部分或下三角部分即可。

18. 将一个n阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中，则一维数组需要存储__n*(n+1)/2_______个矩阵元素。

19. 利用三元组表存放稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一个非零元素的行号、列号和___值______。

1、DA1+(i-1)*k 2、1100+（6*2+3）*2=1130 3、100+（19*6+6）*2=340，100+（9*6+??）

6

*2=220 4、1482 5、loc（a00）+(j*m+i)*1 6、三元组 7、三元组，行

9、上（下）三角矩阵 10、i*（i-1）/2+j-1 (i 11、108

号，列号，值 8、对角矩阵

≥j) ，j*(j-1)/2+i-1 (i

12. 下标（或顺序号）13. 静态 14. 动态 15. 两个 16.LOC(0,0)+(i*n+j)*d 17. 相等

18. n(n+1)/2

19. 值

21、广义表（A,(a,b),d,e,((i,j),k)）,则广义表的长度为_____5______，深度为_______3____。 22、已知广义表A=((a,b,c),(d,e,f)),则运算head(head (tail（A）)))=___ _ d _______。 23、已知广义表ls =(a,(b,c,d),e),运用head和tail函数取出ls中的原子b的运算是head(head(tail(s)))_____。

24. 非空广义表的除第一个元素外其他元素组成的表称为广义表的___表尾_____。 25. 广义表A ( (a, b, c), (d, e, f ) ) 的表尾为__25. ( (d, e, f ) ) ______。

26. 广义表是一种递归的数据结构，子表结点则指示下一层广义表的__表头结点______。 27. 广义表的深度定义为广义表括号的____层数____。 21、5，3

22、d 23、head(head(tail(s)))

24. 表尾 25. ( (d, e, f ) )

26. 表头结点 27. 层数 六．树

1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个_____前驱______,且存在一条从根到该结点的_____路径__________。

2、度数为0的结点，即没有子树的结点叫作____叶子______结点或__终端_______结点。同一个结点的儿子结点之间互称为_____兄弟______结点。

7

3、假定一棵树的广义表为A(B(e),C(F(h,i,j),g),D),则该树的度为_______3____，树的深度为___4______，终端结点为__ehijgD____，单分支结点为B，双分支结点个数为 ___1____，三分支结点为__A_F____，C结点的双亲结点是__A____，孩子结点是___F,g___。

4、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有关系的是___线索__________。

5、有三个结点的二叉树，最多有____5____种形状。

6、高度为k的二叉树具有的结点数目，最少为__k___,最多为__2-1___。/*高度？深度？*/ 7、对任何一棵二叉树，若n0，n1，n2分别是度为0，1，2的结点的个数，则n0=__ n2+1_____。 8、在含100个结点的完全二叉树，叶子结点的个数为_50______。

9、将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫_排序____。 10、若一棵满二叉树含有121个结点，则该树的深度为____7_____。 11、一个具有767个结点的完全二叉树，其叶子结点个数为__384______。 12、深度为90的满二叉树，第11层有__1024______个结点。 13、有100个结点的完全二叉树，深度为___7_____。

14、设一棵二叉树中度为2的结点10个，则该树的叶子个数为_____11___。/*n0=n2+1*/ ?15、含有3个2度结点和4个叶结点的二叉树可含__________个1度结点。 16、一棵具有５层满二叉树中节点总数为___31________。

17、一棵含有16个结点的完全二叉树，对他按层编号，对于编号为7的结点，他的双亲结点及左右结点编号为___3___、___14___、___15____。

18、深度为k(设根的层数为1)的完全二叉树至少有_______个结点, 至多有_______个结点。 19、若要对某二叉排序树进行遍历，保证输出所有结点的值序列按增序排列，应对该二叉排序树采用__中序______遍历法。

k

8

20、在序列(2,5,8,11,15,16,22,24,27,35,50)中采用折半查找(二分查找)方法查找元素24，需要进行_____4_________次元素之间的比较。/*16、27、22、24*/

21、设有10个值，构成哈夫曼树，则该哈夫曼树共有___19___个结点。/*10个值就是10个叶子结点；没有1度的结点*/

22、从树中一个结点到另一个结点之间的分支构成这两个结点之间的_____路径_______。 23. 对于一棵具有n个结点的树，该树中所有结点的度数之和为_n-1_____。/*每一个结点对应一个棍就是一度（除根节点外）*/

24. 一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点k的所有祖先的结点数为__2______个。

25. 一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y)))，结点f的层数为_____3____。假定树根结点的层数为0。

26. 假定一棵三叉树（即度为3的树）的结点个数为50，则它的最小高度为__4______。假定树根结点的深度为0。

27. 在一棵高度为3的四叉树中，最多含有___255_____个结点，假定树根结点的高度为0。 28. 在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有____6____个。

29. 一棵高度为5的完全二叉树中，最多包含有____63____个结点。假定树根结点的高度为0。/*2*2*2*2*2*2-1*/

30. 假定一棵树的广义表表示为A(B(C,D(E,F,G),H(I,J)))，则该树的高度为___3_____。假定树根结点的高度为0。

31. 在一棵二叉树中，假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为____6____个。/*n0=n2+n1*/

9

32. 假定一棵二叉树的结点数为18，则它的最小高度为___3_____。假定树根结点的高度为0。 1、前驱，路径

4、线索

2、叶子，终端，兄弟 5、5

k

3、3；3；e,h,I,j,g；C； A,F ； A；F,g

7、n1+n2

8

、、

50 31

6、k，2-1

9、排序 10、7 11、384 17、3，14，15

k-1

k

12、1024 13、7 14、11 15、1（0） 16

19、中序

18、2，2-1 20、4 21、19 22、路径

23. n-1 24. 2 25. 3 26. 4 27. 85 28. 6 29. 63

31. 6 32. 4

30. 3

三、选择题：

四．串

（ ）1．在目标串T[0?n-1]=”xwxxyxy”中，对模式串p[0?m-1]=”xy”进行子串定位操

作的结果_______ A.0 C.3

B.2

D.5

（ ）2.如下陈述中正确的是________

A. 串是一种特殊的线性表 B. 串的长度必须大于零 C. 串中元素只能是字母 D. 空串就是空白串

（ ）3.若目标串的长充为n，模式串的长度为[n/3]，则执行模式匹配算法时，在最坏情况下

的时间复杂度是________ A.O（1） C.O（n2）

串 1—3 C A B

B.O（n） D.O（n3）

10

五．数组和广义表

（ ）1．二维数组A按行顺序存储，其中每个元素占1个存储单元。若A[1][1]的存储地址为

420，A[3][3]的存储地址为446，则A[5][5]的存储地址为_______ A.470 C.472

B.471 D.473

（ ）2．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的_____。

Ａ．行号 Ｂ．列号 Ｃ．元素值 Ｄ．地址

（ ）3. 一个数组元素A[i]与________的表示等价。

A、 *(A+i) B、 A+i C、 *A+i D、 &A+i

（ ）4. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的________。

A、 行号 B、 列号 C、 元素值 D、 地址

数组 1—4 C A A A 广义表

（ ）1．已知广义表的表头为A，表尾为(B,C)，则此广义表为________

A.（A,(B,C)） C.(A,B,C)

B.（A,B,C）

D.(( A,B,C))

（ ）2.设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为____。

A、O(1) B、O(n)

11

C、O(n2) D、O(log 2 n)

（ ）3.一个非空广义表的表头________

A.不可能是子表 C.只能是原子

B.只能是子表

D.可以是子表或原子

0 2 （ ）4. 设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为_______。

A、 O(1) B、 O(n) C、 O(n2) D、 O(log2n)

广义表1—4 B D D B 六．树

3 3 5 （ ）1.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子的编号为______。

A.98 C.50

B.99 D.48

( )2.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )

A.ABCDEF B.ABECDF C.CDFBEA D.CBDAEF

（ ）3．二叉树中第5层上的结点个数最多为________

A.8

B.15

C.16 D.32

（ ）4. 由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为________。

12

A、 24 B、 48 C、 72 D、 55

A（ ）5.一棵度为3的树中，度为3的结点个数为2，度为2的结点个数为1，则度为0的结B E 点个数为________

A.4 B.5

C D C.6

D.7

树 1—5 A D C D C 四、应用题：

1、已知稀疏矩阵如下：

请写出该稀疏矩阵三元组表示，和十字链表表示方式。 2、广义表A=（a,b,(c,d),(e,(f,g))）,求其长度，及深度。 3、请画出下面广义表相应的加入表头结点的单链表表示，

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

4、设二叉树后根遍历为BAC，画出所有可能的二叉树。

5、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。 6、有一个完全二叉树按层次顺序存放在一维数组中，如下所示：请指出结点P的父结点，左子女，右子女。

13

F

7、给出下列二叉树的先序序列。

8、已知某非空二叉树采用顺序存储结构，树中结点的数据信息

依次存放在一个一维数组中，即

ABC□DFE□□G□□H□□，该二叉树的中序遍历序列为：

9、设一棵二叉树的前序序列为1,2,3,4,5,6,7,8,9,其中序序列为2,3,1,5,4,7,8,6,9,试画出该

二叉树。

10、什么是线索二叉树？为什么要线索化？ 11、什么是哈夫曼（Huffman）树？

12、已知结点a,b,c,d及其权值写出哈夫曼树的构造过程。 a b c d 7 5 2 4

13、已知树T的先序遍历序列为ABCDEFGHIJKL，后序遍历序列为CBEFDJIKLHGA，请画出树T。 14、求下列广义表运算的结果： HEAD(p,h,w); TAIL (b,k,p,h); HEAD ((a,b),(c,d)); TAIL (a,b),(c,d);

HEAD（TAIL（（(a,b),(c,d)））） TAIL（HEAD((a,b),(c,d))）

14

15、将下列森林转化为二叉树。

16、如图所示的二叉树完成中序遍历、后续遍历、先序遍历，并画出后序线索化的二叉树。A

B E

C D F

17、将下图转换为二叉树，对转换后的二叉树进行先根、中根、后根遍历。 A

B C D E F G J 15

五、程序题（参看课件，至少会用文字描述）

1、写出二叉树结构存储（二叉链表），写出中序遍历该二叉树的算法。（**）

left 2、写出计算树深度的算法。 3、写出计算树叶子结点的算法。 4、写出计算字符串长度的算法。

5、试设计算法判断字符串是否中心对称关系，例如：

X Y Z Z Y X ，X Y Z Y X 都算是中心对称的字符串。要求用尽可能少的时间完成判断(提示：

将一半字符先依次进栈)。

*6、完成计算二叉树叶子结点的算法。（参看课件） void midtravel(struct treenode *bt) {struct treenode *p,*a[n]; int top= - 1,true =1, j =0; while(true) { p=bt;

while(p != null) { top + +; a[top]=p;

p=________} if (top != -1) { p=a[top]; top -- ;

printf(“%c”,p->data);

data right 16

if (p->left = = null )&&__________ ______________;

p=p->right;}

else true = 0; } printf(“%d”,j)}

17

本文来源：https://www.bwwdw.com/article/uvxp.html