2025年综合能力测试树状图结构与串行数据解析挑战

一、判断题

四.串

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

2、假如一种串中的所有字符均在另一串中出现，则说前者是后者的子串。（）

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

KV2、X3、V

五.数组和广义表

1、多维数组是向量的推广°（）/*数组和广义表线性表在含义上的扩展*/

2、用相邻矩阵表达图所用的存储空间大小与图的边数成正比。（）/*顶点*/

3、除插入和删除操作外，数组的重要操作尚有存取、修改、检索和排序等。（）

4、稀疏矩阵中0元素的分布有规律，因此可以采用三元组措施进行压缩存储。（）/*稀疏

矩阵中0元素的分布无规律*/

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

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

chara[maxSize];

则这种数组在程序执行过程中不能扩充。

6.假如采用如下措施定义一维字符数组：

intmaxSiZP=30;

char*a=newchar.maxSize];

则这种数组在程序执行过程中不能扩充。

7.数组是一种静态的存储空间分派，就是说，在程序设计时必须预先定义数组的数据类型和存

储空间大小，由编译程序在编译时进行分派。/*对「数组一旦规定了它的维数和各维长度，便可

为它分派存储空间*/

8.多维数组是一种复杂的数据构造，数组元素之间的关系既不是线性的也不是树形的。

9.使用三元组表达稀疏矩阵中的非零元素能节省存储空间。

10.用字符数组存储长度为n的字符串，数组长度至少为n+1。

1-5XXXXV

6-10XXVVV

11、一种广义表的深度是指该广义表展开后所含括号的层数。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、一般树和二叉树的结点数目都可认为0。()

2、在只有度为0和度为k的结点的k又树中，设度为0的结点有nO个，度为k的结点有nk个,

则有nO=nk+lo()

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

4、哈夫曼树一定是满一叉树。()

5、给定一组权值，可以唯一构造出一棵哈夫曼树。()

6、深度为h的非空二叉树的第i层最多有2iT个结点。()

7、满二叉树也是完全二叉树。()

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

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

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

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

子结点。（）

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

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

14、在完全二叉树中，若某结点元左孩子，则它必是叶结点。（）

15、树的带权途径长度最小的二叉树中必然没有度为1的结点。（）

16、二叉树可以用0W度W2的有序树来表达。（）

17、一组权值，可以唯一构造出一一棵哈夫曼树。（）

18、将一棵树转换成二叉树后，根结点没有左子树；（）/*没有右子树*/

19、用树的前序遍历和中序遍历可以导出树的后序遍历：（）

20.二叉树是一棵无序树。（）

21.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和后序遍

历，则具有相似的成果。（）

22.在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行中序遍历和后序遍

历，则具有相似的成果。（）

2工在一棵一叉树中,假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中根遍

历，则具有相似的成果。（）

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

历，则具有相似的成果。（）

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

便。()

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

()

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

0(h)4,()

28.对于一棵具有n个结点的任何二叉树，进行前序、中序或后序的任一种次序遍历的空间复杂

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

29.在一棵具有n个结点的线索二叉树中，每个结点的指针域也许指向子女结点，也也许作为线

索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有n个。

()

30.线索二叉树中的每个结点一般包具有5个数据组员。()

1-5VXVXX6-10XVXVX

11-15XXXVV16-20XXXVX

21-25XVXVV26-30VXXXV

二、填空题：

四.串

1、一种串的任意个持续的字符构成的子序列称为该串的—子串，包括该子串的串称为—

主串,

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

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

D______e

4、在长度为n的循环队列中，删除其节点为x的时间爱朵度为_0(n)。

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

6.若设串S="documentHash.doc'O"，则该字符串S的长度为_____16____。

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

五.数组和广义表

1、已知一次序存储的线性表，每个结点占用k个单元，若第一种结点的地址为DA1,则第i个

结点的地址为—DA*k。

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

则A[2][3]的地址为_1130__________o

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[元[3][2]的地址为_1482o/*1100+{(4*6+3)*7+2}*2*/

4、设二维数组按列优先存储，每个元素占1个存储单元，元素Aoo的存储地址loc4。)，

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

6、稀疏矩阵一般采用一三元组措施进行压缩存储。

7、稀疏矩阵可用_三元组进行压缩存储，存储时需存储非零元的—行号、—

列号—、_值。

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

为____对角矩阵_____。

9、若一种n阶矩阵A中的元素满足：A『A,i(0<=I,j<=n-l)则称A为一对称________矩阵：

若主对角线上方(或下方)的所有元素均为零时，称该矩阵为一(±)下三角矩阵o

10、对于下三角形和上三角形矩阵，分别以按行存储和按列存储原则进行压缩存储到数组M[k]

中，若矩阵中非0元素为Au,则k对应为l)/2+j(i>=j)—和

_(l+j)*(j-D/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.若设一种nxn的矩阵A的开始存储地址L0C(0,0)及元素所占存储单元数d已知，按行存

储时其任意一种矩阵元素的存储地址为_L0C(0,0)+(i*n+j)d。

17.对称矩阵的行数与列数—相等且以主对角线为对称轴，=因此只存储它的上

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

1R.将一种n阶对称矩阵的上三角部分或下三角部分压缩寄存于一种一维数组中，则一维数组需

要存储_n*(n+1)/2个矩阵元素。

19.运用三元组表寄存稀疏矩阵中的非零元素，则在三元组表中每个三元组元素对应一种非零元

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

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.静态14.动态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函数取出Is中的原子b的运算是

head(head(tail(s)))。

24.非空广义表的除第一种元素外其他元素构成的表称为广义表的—表尾o

25.广义表A((a,b,c),(d,e,f))的表尾为_25.((d,e,f))

26.广义表是一种递归的数据构造，子表结点则指示下一层广义表的—表头结点。

27.广义表的深度定义为广义表括号的一层数—o

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

26.表头结点27.层数

六.树

1、在树构造里，有且仅有一种结点没有前驱，称为根，非根结点有且仅有一种____前驱,

且存在一条从根到该结点的途径。

2、度数为0的结点，即没有子树的结点叫作—叶子_____结点或_终端结点。同一种

结点的儿子结点之间互称为____兄弟结点。

3、假定一棵树的广义表为A(B(e),C(F(h,i,j),g),D),则该树的度为______3—,树的深度为

_4______,终端结点为_ehi」gD—,单分支结点为B，双分支结点个数为_1一,三分

支结点为_A_F___,C结点的双亲结点是_A,孩子结点是—F,g—。

4、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储构造有

关系的是—线索.

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

6、高度为k的二叉树具有的结点数目，至少为_k_,最多为_2k-l—o/*高度？深度？*/

7、对任何一棵二叉树，若nO,nl,n2分别是度为0,1,2的结点的个数，则n0=_n2+l。

8、在含100个结点的完全二叉树，叶子结点的个数为_50o

9、将一种数据元素(或记录)的任意序列，重新排列成一种按关键字有序的序列叫一排序—。

10、若一棵满二叉树具有121个结点，则该树的深度为—7____。

11、一种具有767个结点的完全二叉树，其叶子结点个数为_384_____。

12、深度为90的满二叉树，第11层有_1024______个结点。

13、有100个结点的完全二叉树，深度为7_____。

14、设一棵二叉树中度为2的结点10个，则该树的叶子个数为ll_o/*n0=n2+l*/

?15、具有3个2度结点和4个叶结点的二叉树可含_________个1度结点。

16、一棵具有5层满二叉树中节点总数为_31。

17、一棵具有16个结点的完全一叉树，对他按层编号,对于编号为7的结点，他的双亲结点及

左右结点编号为—3―、—14—、-15。

18、深度为k(设根的层数为1)的完全二叉树至少有______个结点，至多有_______个结点。

19、若要对某二又排序树进行遍历，保证输出所有结点的值序列按增序排列，应对该二义排序树

采用—中序_____遍历法。

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____o假定树

根结点的深度为0。

27.在一棵高度为3的四叉树中，最多具有255个结点，假定树根结点的高度为0。

28.在一棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2

个，那么度为0的结点数有—6—个。

29.一棵高度为5的完全二叉树中，最多包具有—63—个结点。假定树根结点的高度为0。

30.假定一棵树的广义表表达为A(B(C,D(E,F,G),H(LJ)))，则该树的高度为—3。假定

树根结点的高度为0。

31.在一棵二又树中,假定双分支结点数为5个，单分支结点数为6个，则叶子结点数为—6

个。/*n0=n2+nl*/

32.假定一棵二叉树的结点数为18,则它的最小高度为_3。假定树根结点的高度为0。

1、前驱，途径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],则执行模式匹配算法时，在最坏状况下

的时间复杂度是

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

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

串1一3CAB

五.数组和广义表

()1.二维数组A按行次序存储，其中每个元素占1个存储单元。若AUH1]的存储地址为

420,A[3]⑶的存储地址为446,则A⑸⑸的存储地址为

A.470B.471

C.472D.473

()2.在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相似的____o

A.行号B.列号

C.元素值D.地址

()3.一种数组元素Mi]与的表达等价。

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

C、*A+iD,&A+i

()4.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相似的

A、行号B,列号

C、元素值D.地址

数组1—4CAAA

广义表

()1.已知广义表的表头为A,表尾为(R,C),则此广义表为

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

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

()2.设一种广义表中结点的个数为n,则求广义表深度算法的时间复杂度为__。

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

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

（）3.一种非空广义表的表头—

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

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

02335

（）4.设一种广义表中结点的个数为n,则求广义表深度算法的时

间复杂度为。

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

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

广义表1—4BDDB

六.树

（）1.将一棵有100个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点

的编号为1,则编号为49的结点的左孩子的编号为.

A.98B.99

C.50D.48

（）2.对于如图所示二叉树采用中根遍历，对的的遍历序列应为（）

A.ABCDEFB.ABECDF

C.CDFBEAD.CBDAEF

（）工一叉树中第5泉上的结点个数最多为

A.8B.15

C.16D.32

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

A、24B、48

C、72D、55

()5.一棵度为3的树中，度为3的结点个数为2,

点个数为________

A.4B.5

C.6D.7

树1—5ADCDC

四、应用题：

1、己知稀疏矩阵如下:

10002

00300

A-45000

00000

■00060

请写出该稀疏矩阵三元组表达，和十字链表表达方式。

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的父结点，左子

女，右子女。123456789101112

HkACDPFJXBQZ

c

o

A口

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