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

本文格式为Word版，下载可任意编辑——数据结构其次次单元测试题库（串到树）一、判断题

四．串

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

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

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

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

constintmaxSize=30;/*常变量在程序运行中不能进行修改*/chara[maxSize];

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

char*a=newchar[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、D4、O(n)5、16.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(010、对于下三角形和上三角形矩阵，分别以按行存储和按列存储原则进行压缩存储到数组M[k]中，若矩阵中非0元素为Aij，则k对应为__(1+i)*(i-1)/2+j(i>=j)____和_(1+j)*(j-1)/2+i(i五．数组和广义表

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

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

B.471D.473

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

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

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

A、*(A+i)B、A+iC、*A+iD、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

BE

CDF

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

BCDEFGJ15

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

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

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

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

XYZZYX，XYZYX都算是中心对称的字符串。要求用完可能少的时间完成判断(提醒：

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

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

while(p!=null)