数据结构试题2022(B卷)答案

千里之行，始于足下让知识带有温度。第第2页/共2页精品文档推荐数据结构试题2022(B卷)答案一、填空题（每空1分，共15分）

1.数据的规律结构有四种基本形态，分离是集合、_线性结构_、_树型结构_和

图状结构_。

2.一个算法的效率可分为_时光_效率和_空间_效率。

3.在树型结构中，树根结点没有前趋_结点，其余每个结点的有且惟独_一_个

前趋驱结点；叶子结点没有_后继_结点；其余每个结点的后继结点可以有_多_个。

4.要从一个挨次表删除一个元素时，被删除元素之后的全部元素均需前移一个

位置，移动过程是从_前_向_后_依次移动每一个元素。

5.设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,

push,push后，输出序列是_2，3_。

6.已知广义表A=((a,b,c),(d,e,f))，则运算head((tail(A))=_(d,e,f)_。

7.对于一个有10个结点的二叉树，最小可能高度为_4_，最大可能高度为_10_。

二、挑选题（每题2分，共30分）

1.C

2.A

3.B

4.A

5.A

6.D

7.C

8.D

9.D10.C11.A12.B

13.B14.D15.D

三、推断题（每题1分，共10分）

1.√

2.×

3.×

4.×

5.×

6.√

7.√

8.√

9.×10.×

四、简答题（共15分）

1．简述什么是数据的存储结构？简述存储结构的两种不同的存储方式？（6分）答：数据的存储结构是数据的规律结构在计算机内存中的存储方式，又称物理机构。（2分）

数据的存储结构有挨次和链式两种不同的方式。挨次存储结构的特点是要借助数据元素在存储器中的相应位置来体现数据元素互相间的规律关系；（2分）链式存储结构则通过表示数据元素存储地址的指针来表示数据元素之间的规律关系。（2分）

2．比较对普通线性表、栈和队列三种结构数据举行操作的不同之处？（9分）答：普通线性表可在表的随意位置举行插入和删除操作；（3分）

栈限定仅在表的一端举行插入或删除操作，栈的修改是按“后进先出”的原则举行的；（3分）

队列限定只能在表的一端举行插入，在表的另一端举行删除，是一种“先进先出”的线性表。（3分）

五、分析题（共30分）

1．写出下列树的先序、中序、后序遍历序列。（9分）

答：先序序列：A-B-D-G-H-C-E-F（3分）

中序序列：B-G-D-H-A-E-C-F（3分）

后序序列：G-H-D-B-E-F-C-A（3分）

2.已知一棵树边的集合为{，，，，，，，，，，}，请画出这棵树，并回答下列问题：（12分）

（1）哪个是根结点？a(1分)

（2）哪些是叶子结点？ljkfid(1分)

（3）哪个是结点k的双亲？g(1分)

（4）哪些是结点f的祖先？ac(1分)

（5）哪些是结点g的孩子？jk(1分)

（6）哪些是结点h的兄弟？gf(1分)

（7）结点c的度是多少？3(1分)

（8）结点d的层次号是多少？3(1分)

（9）囫囵树的深度是多少？4(1分)

（10）以结点b为根的子树深度是多少？3(1分)

(2分)

3．画出下图的带权邻接矩阵，并求出从V0到V5的最短路径(写出该路径所

经过的顶点序列以及权值之和)。(9分)

∞

∞

∞

∞

∞

答：带权邻接矩阵如下：????????????????????∞∞∞∞

∞∞∞∞∞∞∞∞

∞∞∞∞∞∞∞∞∞∞∞

∞∞∞

∞∞6020

1050

51003010（3