2023年数据结构复习题

ZH计0520九州0520

《数据结构》复习

一、填空题：

1、空串的长度是。，空格串的长度是串中包含的容格的个数。

2、队列是一种先进先出表,在队列中允许插入的一端称队尾,允许删除的另一端称队头。

3、两串相等是指两个字符串的长度相等，且各对应位置上的字符相等。

4、组成数据的最小单位是数据项。

5、线性结构中元素之间存在一对一的关系,树形结构中元素之间存在一对多的关系,图形

结构中元素之间存在多对多的关系。

6、向栈中压入元素的操作是：先移动栈顶指针，后存入元素。

7、栈的逻辑结构是线性结构，其特点是后进先出,先进后出,栈中允许插入和删除的一端

称栈顶。

8、在双向链表中，每个结点有两个指针域，一个指向前驱结点,另一个指向后继结点。

9、数据结构通常包括四种基本结构：集合、线性结构、树形结构、图形结构、线性表

10、线性表(ai.a2…an)k,ai称表头元素,an称表尾元素,线性表有两种存储结构：顺

序存储结构和链式存储结构。

11、在一个顺序存储的线性表中，第1个元素的地址是100,每个元素的长度为2,则第5个

元素的地址是108。

12、在线性结构中，第一个结点没有前驱结点,其余每个结点有且只有L个前驱结点；最后

一个结点没有后续结点,其余每个结点有且只有L个后续结点。

二、选择题

1、具有6个顶点的无向图至少应有A条边才能确保是一个连通图。

A、dB.cC.bD.e

2、在初始状态为空的堆栈中依次插入元素f,e,d,c,a,b后，连续进行了三次删除操作，则此时的

栈顶元素是D

A、5B、6C、7D、8

3、后序遍历的顺序是D

A、根结点，左子树，右子树B、左子树，根结点，右子树

C、右子树，根结点，左子树D、左子树，右子树，根结点

4、设结点X有左孩子结点Y,右孩子结点Z,用三种基本遍历方法得到的遍历序列中X(B)

是Y的前驱，X(B)是Z的后继,Y(A)是Z的前驱。

A、一定，B、不一定C、一定不

5、串是指B

A、少于一个字母的序列B、有限个字符的序列C、不少于一个字符的序列D、任意

个字母的序列

6、一个栈的输入序列为1,2,3,4,则下列序列中不可能是栈的输出序列的是C

A、2,3,4,1,5B、2,3,1,4,5C、5,4,1,2,3D、1,5,4,3,2

7、如果结点A有3个兄弟，且B是A的双亲，则B的度是A

A、4B、5C、1D、3

8、通常对数组进行的两种基本操作是C

A、插入和删除B、索引和修改C、查找和修改D、删除和修改

9、一个队列的入队序列是1,2,3,4,则队列的输出序列是B

A、4,3,2,1B、1,2,3,4C、1,4,3,2D、3,2,4,1

10、计算机算法必须具备输入、输出和B等五个基本特性

A、可行性、可移植性、和可扩充性B、可行性、确定性和可穷性C、确定性、可穷必和稳定性

D、易读性、稳定性和安全性

11、树最适合用来表示C

A、有序数据元素B、无序数据元素C、元素之间具有分支层次关系的数据D、元素之间无联系

的数据

12、排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比

较，将其放入已排序的正确位置上的方法，称为：（8_

A、希尔排序B、起泡排序C、插入排序D、选择排序

13、N个顶点的强连通图至少有（A）条边

A、NB、N+lC、N-lD、N（N-1）

14、栈通常采用的两种存储结构是（A）

A、顺序存储结构和链表存储结构B、散列方式和索引方式C、链表存储结构和数组D、线性存

储结构和非线性存储结构

15、深度为4的二叉树至多有（D）个结点

A、8B、16C、7D、15

16、对线性表进行二分查找时，要求线性表必须（C）

A、以顺序方式存储B、以链接方式存储C、以顺序方式，且结点按关键字有序排序D、以链接

方式存储，且结点按关键字有序排序

17、线性表的顺序存储结构是一种（A）的存储结构、

A、随机存取B、顺序存取C、索引存取D、散列存取

18、串是一种特殊的线性表，其特殊性体现在（B）

A、可以顺序存储B、数据元素是一个字符C、可以链接存储D、数据元素可以是多个字符

19、任何一个无向连通图的最小生成树有旦

A、只有一棵B、有一棵或多棵C、一定有多棵D、可能不存在

20、在一棵非空二叉树的中序遍历序列中，根结点的右边A

A、只有右子树上的所有结点B、只有右子树上的部分结点C、只有左子树上的部分

结点D、只有左子树上的所有结点、

三、试分别按先根遍历，中根遍历，后根遍历法写出二叉树的遍历序列

ABDHIEJCFG

HDIBEJAFCG

HIDJEBFGCA

四、画出含有三个结点的二叉树的所有形态。

五、给出图中每个顶点的入度，出度和顶点的度

顶点入度出度度

①213

②224

③134

@303

⑤235

⑥123

六、用Dijkstra算法求图中VI到其余各顶点的最短路径

最短路径长度

VI——►V213

VI——►V38

VI—>V4（经V3）13

VI—>V5（经V3,V4）19

Vl^¥6（经V3,V4,V5）21

VI—>V7（经V2）20

七、已知无向图，试给出：

1.从A出发的“深度优先”遍历序列

2.从A出发的“广度优先”遍历序列

3.该图是连通图吗？

答：①ABDCEGF②ABCDEFG③是

八、对照图未的树回答下列问题

1.树中哪些是叶结点？哪个是根结点？

答：叶结点DMNFJKL；根结点：A

2.结点C的双亲结点是哪一个？A

3.结点C的孩子有哪些？FGH

4.哪些是G的兄弟？F、H

⑤C的深度是多少？3

⑥树的深