数据结构复习题

一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×） 第 1 章

（√）（ 1）数据的逻辑结构与数据元素本身的内容和形式无关。

（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。 （×）（ 3）数据元素是数据的最小单位。 （×）（ 4）数据项是数据的基本单位。

（×）（ 5）数据的逻辑结构和数据的存储结构是相同的。

（√）（ 6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。 （√）（ 7）数据的物理结构是指数据在计算机内实际的存储形式。

（√）（ 8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（ 9）数据的存储结构是数据的逻辑结构的存储映像。 （√）（ 10）算法是对解题方法和步骤的描述。

第 2 章

（×）（ 1）链表的物理存储结构具有同链表一样的顺序。 （×）（ 2）链表的每个结点都恰好包含一个指针域。

（√）（ 3）线性表中的元素可以是各种各样的， 但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。

（×）（ 4）链表的删除算法很简单， 因为当删除链中某个结点后，

计算机会自动地将后续的

各个单元向前移动。

（×）（ 5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （√）（ 6）数组元素的存储位置

是下标 的线性 函数。

（√）（ 7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个 元素。

（×）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价， 一半的元素。

（×）（ 9）顺序存储方式的优点是存储密度大，插入、删除效率高。

（×）（ 10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。

因为平均每次移动仅

第 3 章

（√）（ 1 ）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两 种基本操作。

（×）（ 2）快速排序在

任何情况 下都比 其它排 序方法速

度快。

（√）（ 3）快速排序算法在每一

趟排序 中都能 找到一个 元素放 在其最 终位置上 。

（×）（ 4）如果某种排序算法不稳定，则该排序方法就没有实际应用价值。 （√）（ 5）对 n 个记录的进行快速排序，所需要的平均时间是

O（ nlog 2n）。

（×）（ 6）冒泡排序是不稳定的排序。

（√）（ 7）冒泡排序的时间复杂度是

O（ n2）。

（×）（ 8）堆排序所需的时间与待排序的记录个数无关。

（√）（ 9）对快速排序来说，初始序列为正序或反序都是最坏情况。 （√）（ 10）对于 n 个记录的集合进行归并排序，所需的平均时间为

O (nlog 2n)。

第 4 章

（√）（ 1 ）栈是运算受 的线 性表。 （√）（ 2）在栈空的情

况下，不 能作出 栈操作 ，否则产

生下溢 出。

（×）（ 3）栈一定是顺序存储的线性结构。 （×）（ 4）空栈就是所有元素都为

0 的栈。

（×）（ 5）一个栈的输入序列为： A， B ，C， D，可以得到输出序列： C， A， B， D 。 （√）（ 6）一个栈的输入序列为： A ，B，C，D ，通过入出栈操作可以输出序列： D。

A ，B ，C，

（×）（ 7）在 C 或 C++ 语言中设顺序栈的长度为 （√）（ 8）链栈与顺序

MAXLEN ，则 top=MAXLEN 时表示队满。

栈相比， 其特点 之一是 通常不会 出现栈 满的情 况。

（√）（ 9 ）在栈中插入 或删除一 个元素 应遵守 的“后进 先出” 的原则 。 （√）（ 10 ）进位制的 换 算算法是 栈的应 用。

（√）（ 11 ）队列是限 制 在两 端进 行操作 的线性 表。 （√）（ 12）判断顺序队

列为空的 标准是 头指针 和尾指针 均指向 同一个 结点。

front 指针的值。

（×）（ 13）在链队列做出队操作时，会改变 （√）（ 14）在循环队列中，若尾指针

rear 大于头指针 front ，其元素个数为 rear- front 。

（√）（ 15）队列是一种“先进先出”的线性表。 （×）（ 16）在循环链队列中无上溢出现象。

（×）（ 17）栈和队列都是顺序存储的线性结构。 （√）（ 18）栈和队列都是属于线性结构。

（×）（ 19 ）顺序队和 循 环队的队 满和队 空的判 断条件是 一样的 。

（√）（ 20 ）在队列中 插 入或删除 一个元 素应遵 守的 ”先 进先出 ”的原 则 。

第 5 章

（×）（ 1）串的长度是指串中不同字符的个数。 （×）（ 2）串是 n 个字母的有限序列。

（√）（ 3）空串不等于空格串。

（×）（ 4）如果两个串含有相同的字符，则说明它们相等。

（×）（ 5）如果一个串中所有的字母均在另一个串中出现，则说明前者是后者的子串。

（√）（ 6）串的堆分配存储是一种动态存储结构。

（×）（ 7）“ DT ”是“ DATA ”的子串。

（×）（8）空串与空格串是相同的。

（×）（ 9）串中任意个字符组成的子序列称为该串的子串。

（√）（ 10）子串的定位运算称为模式匹配。

（√）（ 11） n 维的数组可以视为 n-1 维数组元素组成的线性结构。

（√）（ 12）稀疏矩阵中非零元素的个数远小于矩阵元素的总数。

（ㄨ）（ 13）若采用三元组压缩技术存储稀疏矩阵， 只要把每个元素的行下标和列下标互换，

就完成了对该矩阵的转置运算。

（ㄨ）（ 14）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中数据元素的行号、列

号和值。

（ㄨ）（ 15）上三角矩阵主对角线以上（不包括主对角线中的元素）

，均为常数 C。

（√）（ 16）对称矩阵、三角矩阵、稀疏矩阵都可以进行压缩存储。

（ㄨ）（ 17）任何矩阵都可以进行压缩存储。

（√）（ 18）在稀疏矩阵的三元组表表示法中，每个三元组表示矩阵中非零元素的行号、列

号和值。

（√）（ 19）数组元素可以由若干个数据项组成。

（√）(20）稀疏矩阵压缩存储就是为矩阵中非零元素分配一个存储空间。

第 6 章

（√）（ 1 ）树结构中每 个结点最 多只有 一个直 接前驱。

（×）（ 2）完全二叉树

一定是满 二查树 。

（√）（ 3）由树转换成二叉树，其根结点的右子树一定为空。

（√）（4）在前序遍历二叉树的序列中， 任何结点的子树的所有结点都是直接跟在该结点之 后。

（×）（ 5）用一维数组来存储二叉树时，总是以前序遍历存储结点。

（×）（6）已知二叉树的前序遍历和后序遍历并不能唯一确定这棵二叉树，

因为不知道根结

点是哪一个。

（√）（ 7）二叉树的前序遍历中，任意一个结点均处于其子女结点的前面。

（√）（ 8）由二叉树的前序遍历序列和中序遍历序列，可以推导出后序遍历的序列。 （√）（ 9）不使用递归，也可以实现二叉树的前序、中序和后序遍历。

（√）（ 10）在完全二叉树中，若一个结点没有左孩子，则它必然是叶子结点。

第 7 章

（√）（ 1）图可以没有边，但不能没有顶点。

（×）（ 2）在无向图中， （ V1， V 2）与（ V 2 ，V 1）是两条不同的边。 （×）（ 3）邻接表只能用于有向图的存储。

（√）（ 4）用邻接矩阵法存储一个图时， 在不考虑压缩存储的情况下，

所占用的存储空间大

小只与图中顶点个数有关，而与图的边数无关。

（√）（ 5）一个图的邻接矩阵表示是唯一的。

（×）（ 6）有向图不能进行广度优先遍历。

（√）（ 7）一个图的最小生成树是该图所有生成树中权最小的生成树。

（√）（ 8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）

部分就可以了。

（×）（ 9）有向图的邻接矩阵一定是对称的。

（×）（ 10）一个图的深度优先遍历的序列是唯一的。

第 8 章

（√）（ 1）二分查找法要求待查表的关键字值必须有序。

（√）（ 2）哈希法是一种将关键字转换为存储地址的存储方法。

（×）（ 3）在二叉排序树中，根结点的值都小于孩子结点的值。

（×）（ 4）对有序表而言采用二分查找总比采用顺序查找法速度快。

（√）（ 5）二叉排序树是一种特殊的线性表。

（√）（ 6）散列存储法的基本思想是由关键字的值决定数据的存储地址。

（√）（ 7）哈希法的查找效率主要取决于哈希表构造时选取的哈希函数和处理冲突的方法。

（√）（ 8）一般说来用哈希函数得到的地址，冲突不可能避免，只能尽可能减少。

（×）（ 9）选择好的哈希函数就可以避免冲突的发生。

（×）（ 10）在二叉排序树上删除一个结点时，不必移动其它结点，只要将该结点的父结点的相应的指针域置空即可。

二．填空题 第 1 章

1．数据结构是一门研究非数值计算程序设计中计算机的操作对象以及它们之间的关系和运算的学科。

2．数据的存储结构形式包括：顺序存储、链式存储、散列存储、索引存储。

3．数据结构按逻辑结构可分为两大类，它们分别是：线性结构和非线性结构。

4．一个算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模

n 的函

数。

5．数据结构有逻辑结构和存储结构两种结构。

6．数据的存储结构形式包括：顺序存储、链式存储、散列存储、索引存储。

7．一个算法的效率可分为

时间 效率和空间效率。

8．数据元素是数据的基本单位。

9．数据结构主要研究数据的逻辑结构、存储结构和算法。

11．数据的逻辑结构是于计算机的。

12．数据结构被定义为 (D ，R)，其中 D 是数据的有限集合，

R 是 D 上的关系的有限集合。

13．树形结构结构中的元素之间存在一对多的关系。 14．若一个算法中的语句频度之和为

T（ n）=125n+3nlog 2n，则算法的时间复杂度为

O（ nlog 2n）。

15．数据结构主要研究数据的逻辑结构、存储结构和算法。

第 2 章

1．顺序表中逻辑上相邻的元素在物理位置上必须相连。

2．在单链表中要在已知结点 其查找的时间复杂度为

*P 之前插入一个新结点，需找到 O(n)

。

*P 的直接前趋结点的地址，

3．线性表是 n 个结点的有限集合。

4．链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。 5．链表相对于顺序表的优点有插入、删除方便；缺点是存储密度小。 6．顺序表相对于链表的优点是：节省存储和随机存取。

7．对于一个具有 n 个结点的单链表， 在已知 p 所指结点后插入一个新结点的时间复杂度是 （1）。

O

8．在链表中逻辑上相邻的元素的物理位置不必相连。 9．线性表中第一个结点没有直接前趋，称为开始结点。 10．在顺序表中访问任意一个结点的时间复杂度均为 11．在 n 个结点的单链表中要删除已知结点

O(1) 。

O (1)

*P ，其时间复杂度为

。

12．在单链表中需知道头指针才能遍历整个链表。

13．在一个单链表中，在指针p 所指向的结点之后插入指针 s->next=p->next 和 p->next=s 操作。

s 所指向的结点时，应执行

14．在一个长度为 n 的顺序表中， 如果要在第 i 个元素前插入一个元素， 要后移 n- i +1 元素。

个

15．在双向链表中， 每个结点都有两个指针域，它们一个指向其前趋结点， 继结点。

另一个指向其后

第 3 章

1．根据被处理的数据在计算机中使用不同的存储设备，排序可分为：内排序和外排序。

2．评价排序算法优劣的主要标准是时间复杂性和算法所需的附加空间。 3．插入排序、堆排序、归并排序中，排序是不稳定的有：堆排序。

4．在对一组记录（ ， 38，96， 23，15， 72，60， 45， 83）进行直接插入排序时，当把第

7 个记录 60 插入到有序表时，为寻找插入位置需比较

3 次。

5．对 n 个关键字进行冒泡排序，其可能的最小比较次数为： 6．内排序是指整个排序过程，全部在计算机的内存中进行。

n-1 次。

7．大多数排序算法都有两个基本的操作：比较和移动。

8．在插入排序和选择排序中，若初始数据基本正序，则选用

插入排序 较好。

9．在排序前，关键字值相等的不同记录，排序后相对位置变化的排序方法，称为不稳定的排序方法。

10．若原始数据接近无序，则选用

快速排序 最好。

11．对于 n 个记录的集合进行归并排序，所需要的平均时间为： 12．在插入排序、归并排序、快速排序中，排序是不稳定的有：

O（ log 2n）。

快速排序

。

13．对一组记录（ ，35，96，21，12，72，60，44，80）进行直接选择排序时，第四次选 择和交换后，未排序记录是

2

， 72， 60， 96， 80 。

14．对于 n 个记录的集合进行，若对其进行快速排序，在最坏的情况下所需要的时间是

O(n )

。

i 趟直接插入排序中，要进行

i-1

次关键字的比较。

15．在最坏情况下，在第

第 4 章

1．在栈 中存取 数据遵 从的原则 是： 后 进先出 。

2．在有 n个元素 的栈中 ，进栈操 作的时 间复杂 度为 O （ 1 ） 。

3．后进 先出的 线性表 称为 栈。

4．在顺 序栈中 ，当 top =MAXLEN-1时，表 示栈满 。

5. 栈 是输入 、输出 受 的 线 性表。

6．在有 n个元素 的栈中 ，出栈操 作的时 间复杂 度为 O （ 1 ） 。 7．在栈 结构中 ，允许 插入、删 除的一 端称为 栈顶。

8 ． 顺 序 栈 S存 在 数 组 S->data[0..MAXLEN-1]

中 ， 出 栈 操 作 时 要 执 行 的 语 句 有 ：

S-> top -- 。

9．在顺 序栈中 ，当栈 顶指针 top =-1 时，表示 栈空

。

10 ．向一个栈顶指针为

top 的链栈插入一个新结点 * p 时，应执行 p->next=top ；和 top=p ；

操作。

11 ．同一栈的各元素的类型相同。

12．栈只能在栈顶插入和删除元素。

13．已知顺序栈 S，在对 S 进行出栈操作之前首先要判断栈是否空。

14．若进栈的次序是

A 、 B、 C、 D、 E，执行三次出栈操作以后，栈顶元素为

B 。

15．从一个栈删除元素时，首先取出栈顶元素，然后再移动栈顶指针。 16 ．在队列中存取数据应遵从的原则是

先进先出

。

17 ．设长度为 n 的链队列用单循环链表表示，若只设头指针，则入队操作的时间复

杂度为 O（ n）。

18 ．在队列中，允许插入的一端称为

队尾。

19 ．设长度为 n 的链队列用单循环链表表示，若只设头指针，则出队操作的时间复 杂度为

0（ 1）。

20 ．设循环队列的头指针 空闲元素，队列的最大空间为

front 指向队头元素，尾指针

rear 指向队尾元素后的一个 front==rear 空

。

MAXLEN，则队空的标志为

。

21 ．队列在进行出队操作时，首先要判断队列是否为 22 ．设循环队列的头指针

front

指向队头元素，尾指针

rear 指向队尾元素后的一个

MAXLEN 。

空闲元素， 队列的最大空间为 MAXLEN，则队满标志为 front==(rear+1)%

front ，队尾指针为

。

23 ．在一个链队列中，若队头指针为 一个结点的条件为：

rear ，则判断该队列只有

front==rear&&front<>NULL

可变的

。

24 ．队列结构的元素个数是

25 ．设长度为 n 的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复 杂度为

0（1） 。

26 ．设长度为 n 的链队列用单循环链表表示，若只设尾指针，则入队操作的时间复

杂度为

0（1）。

27 ．链队列为空时，LQ->front->next= NULL 28 ．设循环队列的头指针 空闲元素， 队列的最大空间为

。

rear 指向队尾元素后的一个 时，队列长度是 MAXLEN-front 。

front 指向队头元素，尾指针

MAXLEN，当 rear29 ．向一个循环队列中插入元素时，首先要移动队尾指针，然后再向指针所指位置 写入新的元素。

30．队列 Q经过 InitQueue ( Q)； InQueue ( Q， a) ； InQueue ( Q，b) ； GetHead ( Q， x) 后，的值是

a

。

第 5 章

1．长度为零的字符串称为 空 串 。

2 ． 在 串 的 运 算 中， EqualStr(aaa ， aabb) 的 值 为 < 0 。

3．串的顺序存储结构简称为 顺序串 。 4．串的链式存储结构简称为

链式串 。

5 ．求 子 串 函 数 SubStr(\"Today is 30 July,2005\

的结果是：

July 。

6．设 S=\"A:/document/mary.doc\"

，则 len(s)=_ 20 。

7．由零个或多个字符组成的有限序列称为

字 符串

（或串）。 8．字符串按存储方式可以分为：顺序存储、链接存储和

堆分配存储

。

9．设 S=“A:/mydocument/text1.doc ，” 则 strlen(S)=23 。 10．在空串和空格串中，长度不为 0 的是空格串。

11．串 顺序存储紧凑格式的优点是： 空间利用率高

,对串的字符处理效率

低 。

12 ．两个串相等是指两个串相长度等， 且对应位置的 字符都相同 。

13．串 顺序存储紧凑格式的缺点是对串的字符处理

效率低。 14 ．模式匹配成功的起始位置称为：

有效位移 。

15 ．所有模式匹配不成功的起始位置称为：

无效位移 。

16. 数组的顺序存储方式有行优先顺序存储和 列优先顺序存储两种。

17. 同一数组中各元素的长度

相等

。

18. 在数组中，数据元素的存放地址可以直接通过地址计算公式算出，所以 数组是一种

随机

存取结构。

19. 在 n维数组中的每一个元素最多可以有 n个直接前驱。

20. 输 出 二 维 数 组 A[m][n] 中 所 有 元素 值 的 时 间 复 杂 度 为O(m*n)。 数 组 元 素 a[0..2][0..3]

的 实 际 地址 上 2000 ， 元素 长 度 是 4 ， 则 Loc[1,2]=

2024

。

21. 数组的三元组存储是对 稀疏矩阵 的压缩存储

x

22. 稀疏矩阵的三元组有 3列 。

23. 稀疏矩阵的三元组中第1列存储的是数组中非零元素所在的

行 数 。 个存储单元。

24. n阶对称矩阵，如果只存储下三角元素，只需要 n（n-1） /2

25. 稀疏矩阵A如下图所示，其非零元素存于三元组表中，三元组（4，1，5）按

行优先顺序存储在三元组表的第

8 0 0 0 0

6项 。

0 11 0 3 5 0

0 0 0 0 0 0

0 0 0

A=

0 0 0 6 0 0

0 0 0

7 0 9

0 0 0

0

稀疏矩阵 A

26. 稀疏疏矩阵的压缩存储方法通常有三元组表和

十字链表 两种。

n（ n-1）

27． n阶下 三 角 矩 阵 ，因 为 对角 线 的 上 方 是同 一 个 常 数 ，需要 /2+1 个

存储单元。

28 ． 稀 疏 矩 阵 中有 n 个 非 零 元 素 ，则 三 元 组 有 n

行。

列数

非零元素

。

。

29. 稀疏矩阵的三元组中第 2 列存储的是数组中非零元素所在的

30. 稀疏矩阵的三元组中，第3列存储的是稀疏数组中的

第 6 章

1．在树中，一个结点所拥有的子树数称为该结点的度。

2．一棵含有 n 个结点的完全二叉树，它的高度是 3．度为零的结点为叶子结点（或叶结点） 。 4．一棵深度为 h 的完全二叉树上的结点总数最少为 5．树内各结点度的最大值称为树的度。

6．一棵深度为 h 的完全二叉树上的结点总数最多为

| log2n |+1 。（下取整）

2

h-1

个。

2 -1 个。

。

h

7．树中结点的最大层次称为树的深度（或高度） 8．三个结点可以组成

2

种不同形态的树。

9．由树转换成二叉树时，其根结点没有右子树。

10．有 20 个结点的完全二叉树，编号为

10 的结点的左儿子结点的编号是 20 。

11．在树中，一个结点的直接子结点的个数称为该结点的度。 12．由二叉树的后序和中序遍历序列，可以唯一确定一棵二叉树。

13．给定如下图所示的二叉树，其前序遍历序列为：

A B E

H

F

C

G

ABEFHCG 。

14．给定如下图所示的二叉树，其层次遍历序列为：

A B E

H

F

C

G

ABCEFGH 。

15．将一棵完全二叉树按层次编号， 对于任意一个编号为

i 的结点，该结点右孩子的编号为：

2*i+1 。

第 7 章

1．图有： _邻接矩阵 _和邻接表等存储结构。

2．n 个顶点 e 条边的图若采用邻接矩阵存储，

深度优先遍历算法的时间复杂度为：

O（ n2） 。

3．图的遍历有：深度优先搜和

_广度优先搜 __ 等方法。

_ O（ n2） __。

4． n 个顶点 e 条边的图若采用邻接矩阵存储，则空间复杂度为： 5．图有：邻接矩阵和 6．若图

邻接表 等存储结构。

G中每条边_无方向，则 G为无向图。

都

n-1 7．在具有 n 个顶点的图的生成树中，含有 8．有向图的边也称为

条边。

_弧 ___。

9．图的邻接矩阵表示法是表示 __顶点 ____ 之间相邻关系的矩阵。

10．有向图 G用邻接矩阵存储，其i 行的所有元素之和等于顶点

第

11．图的深度优先遍历序列 ___不是 _____唯一的。

i 的 __出度 ____。

12．设有一稀疏图 G，则 G采用 _邻接表 ____存储比较节省空间。

13．从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为

图的遍历（或遍历） 。

14．遍历图的两种基本方法是：深度优先遍历和广度优先遍历。

15．有向图的邻接表表示适于求顶点的出度。

第 8 章

1．顺序查找法，表中元素可以任意存放。

2．散列表查找法的平均查找长度与元素个数 3．快速排序是对冒泡

n 无关。

排序的一种改进。

4．在哈希函数 H(key)=key % P 中， P 一般应取质数。

5．二分查找的存储结构仅适用于顺序存储结构，而且关键字有序的。

6．在分块查找方法中，首先查找索引，然后再查找相应的块。

7．二分查找法，表中元素必须按关键字有序存放。

8．在分块查找方法中，表中元素每块内的元素可以任意存放，块与块之间必须有序存放。

9．顺序查找、二分查找、分块查找都属于静态查找。

10．顺序查找法，其平均查找长度为：

(n+1)/2 。

O（ 1）。

11．理想情况下，在散列表中查找一个元素的时间复杂度为：

12．散列表的查找效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。 13．二叉排序树是一种动态查找表。

14．处理冲突的两类主要方法是开放定址法和拉链法（或链地址法）

。 次。

15．设有 100 个元素，用二分查找时，最少的比较次数是 1

三．选择题

第 1 章

1．数据结构通常是研究数据的（

A. 存储结构和逻辑结构

A ）及它们之间的相互联系。

B. 存储和抽象 C. 联系和抽象 D. 联系与逻辑

2．执行下列语句的时间复杂度为： （ B）。

s=0;

for (i=1;i<=n; i++)

s=s+i;

A. O（ 1） B. O（ n） C. O（ n）

（ C）。

2

D.

O（ n）

3

3．数据结构中，在逻辑上可以把数据结构分成：

A. 动态结构和静态结构

B. 紧凑结构和非紧凑结构

D. 内部结构和外部结构

2

C. 线性结构和非线性结构

4．某程序的时间复杂度为（

2

3n+log 2n+n+15 ）其数量级表示为（ B ）

A. O（ n） B. O（ n） C. O（ log2n）D. O（ nlog 2n） 5．非线性结构的数据元素之间存在（

B ）。

A. 一对多关系

B. 多对多关系 C. 多对一关系 D. 一对一关系

D

）

2

6．下列时间复杂度中最坏的是（

A. O（ 1）B. O（ n）C. O（ log 2n） D. O（ n）

7．以下任何两个结点之间都没有逻辑关系的是（

D ）

A. 图型结构 B. 线性结构 C. 树型结构 D.

A ）。

集合

8．链接存储的存储结构所占存储空间（

A ．分两部分，一部分存放结点的值，另一部分存放表示结点间关系的指针

B．只有一部分，存放结点值

C．只有一部分，存储表示结点间关系的指针

D．分两部分，一部分存放结点值，另一部分存放结点所占单元素

9．一个存储结点存放一个（

B ）

A.

数据项 B. 数据元素 C. 数据结构 D. 数据类型

A ）

O（ log 2n） D. O（ n2）

A. O（ 1）

B. O（ n）C.

10．下列时间复杂度中最好的是（

11．每一个存储结点不仅含有一个数据元素，还包含一组指针，该存储方式是（

B ）存

储方式

A. 顺序 B.

链式

C. 索引 D.

D ）

散列

12．下列算法的实际复杂度是（

for (i=0;ifor (j=0;ic[i][j]=i+j;

2

A. O（ 1）B. O（ n） C. O（log 2n）D. O（ n ） 13．数据元素是数据的基本单位，其内（

B ）数据项。

A.

只能包括一个 B. 可以包括多个

C. 不包括 D. 可以包括也可以不包括

14. 数据结构中，与所使用的计算机无关的是数据的（

A. 存储

C ）结构；

B. 物理

C. 逻辑 D. 物理和存储

15．数据的逻辑结构是（

A ）关系的整体

数据项之间逻辑

A. 数据元素之间逻辑 C. 数据类型之间 D.

B.

存储结构之间

第 2 章

1．用单链表方式存储的线性表， 存储每个结点需要两个域， 一个数据域， 另一个是（ B

）。

A ．当前结点所在地址域

B ．指针域 C．空指针域

A

D．空闲域

O（ n）。

2．在具有 n 个结点的单链表中，实现（

A ．遍历链表和求链表的第

）的操作，其算法的时间复杂度都是

i 个结点 B．在地址为 P 的结点之后插入一个结点 D．删除地址为 P 的结点的后继结点

B

）。

C．删除开始结点

3．设 a， b，c 为三个结点， p ， 10 ， 20，代表地址，则如下存储结构称为（

P

a 10

b 20

c ^

A ． 循环链表

B．单链表 C．双向循环链表 D ．双向链表

4．已知一个顺序存储的线性表，设每个结点需占 则第 i 个结点的地址为（

A ． B+(i-1)*m

m 个存储单元，若第一个结点的地址

B ，

A

）。

B． B+i*m

）。

C．B-i*m

D． B+(i+1)*m

5．单链表的存储密度（

A ．大于 1

C

B ．等于 1

C．小于 1

D．不能确定

O(1) 的操作是（

6．在 n 个结点的顺序表中，算法的时间复杂度是

A ）。

A ．访问第 i 个结点 (1<=i<-n) 和求第 i 个结点的直接前驱 (2<=i<=n)

B．在第 i 个结点之后插入一个新结点 C．删除第 i 个结点 (1<=i<=n)

(1<=i<=n)

D．将 n 个结点从小到大排序

7．在线性表中（ B）只有一个直接前驱和一个直接后继。

A ．首元素 B ．中间元素 C ．尾元素

D ．所有元素

8．指针 P 指向循环链表 L 的首元素的条件是（

D ）。

A ．P= = L

B． L->next= = P

C． P->next= = NULL

D． P->next= = L

9．一维数组和线性表的区别是（

A

）。

A ．前者长度固定，后者长度可变

B．后者长度固定，前者长度可变

C．两者长度都固定

D ．两者长度都可变

10．指针 P 所指的元素是双循环链表 L 的尾元素的条件是（ D）。

A ．P= = L B． P->prori= = L 11．一C．P= = NULL

D．P->next= =L

个向量第一个元素的存储地址是

100，每个元素的长度为

2，则第 5 个元素的地址是（

B ）

A． 110

B

．108 C ． 100

D

． 120

12．两个指针

P 和 Q，分别指向单链表的两个元素， P 所指元素是 Q 所指元素前驱的条件

是（）。

A． P->next= =Q->nextB ．P->next= = Q

C． Q->next= = P

D． P= = Q

13．向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动

（ B ）个元素。

A．8B．63.5C．63D．7 14．用链表存储的线性表，其优点是（

C）。

A ．便于随机存取 B．花费的存储空间比顺序表少

C．便于插入和删除

D ．数据元素的物理顺序与逻辑顺序相同

15．单链表的示意图如下：

L

A

B

C

D Λ

P

Q

R

指向链表 Q 结点的后继的指针是（

D ）

A． L

B． P

C． QD ．R

第 3 章

1．每次从无序表中取出一个元素， 把它插入到有序表中的适当位置， 这种排序方法叫 （ C

A ．选择 B．交换 C．插入 D．归并

2．快速排序方法在（ C）情况下最不利于发挥其长处。

A ．要排序的数据量太大 B ．要排序的数据中含有多个相同值

）。

C.

要排序的数据已基本有序 D. 要排序的数据个数为奇数

3．排序方法中，从无序序列中选择关键字最小的记录，将其与无序区（初始为空）的第一个记录交换的排序方法，称为 : ( D ) 。

A．希尔排序

B ．归并排序 C ．插入排序 D. 选择排序 A）。

4．在待排序的元素序列基本有序的前提下，效率最高的排序方法是：（

A．直接插入

B ．冒泡排序 C ．希尔排序 D ．选择排序

5．每次把待排序方的区间划分为左、右两个区间，其中左区间中元素的值不大于基准元素 的值，右区间中元素的值不小于基准元素的值，此种排序方法叫做（

C）。

A．冒泡排序

B A

．堆排序 C ．快速排序 D. 归并排序

6．排序是根据（

）的大小重新安排各元素的顺序。

A ．关键字 B．数组 7．堆的形状是一棵（ D）。

C ．元素件 D ．结点

A．二叉排序树 B ．满二叉树 C ．不是二叉树 D. 完全二叉树

8．稳定的排序方法是指在排序前后， 关键字值相等的不同记录间的前后相对位置

A ．保持相反 B．保持不变

（ B

）。

C ．不定 D ．无关

D）。

9．下述几种排序方法中，要求内存量最大的是：（

A ．插入排序

B ．选择排序

B

C ．快速排序 D. 归并排序

10．直接插入排序的方法是（

）的排序方法。

A ．不稳定 B．稳定 C ．外部 D．选择 11．直接插入排序的方法要求被排序的数据（

B ）存储。

A ．必须链表

B ．必须顺序 C ．顺序或链表 D ．可以任意

12．设有 1000 个无序元素， 希望用最快的速度挑选出其中前 排序法。

10 个最大的元素， 最好选用（B）

A．冒泡排序

B ．堆排序 C ．快速排序 D. 归并排序

A）

13．用快速排序法对 n 个元素进行排序时，最坏情况下的执行时间为（

A． O（n）

2

B

． O（log 2n） C． O（nlog 2n） D. O （ n）

14．一个数据序列的关键字为：（ 46，79，56，38，40， 84），采用快速排序，并以第一个

C

）

B．（ 40， 38，46， 79，56， 84） D

．（ 40， 38， 46， 56， 79， 84）

数为基准得到第一次划分的结果为：（

A． （ 38，40， 46， 56， 79，84）

C ．（ 40， 38， 46， 56，79， 84） 15．用某种排序方法对关键字序列（ 序列的变化情况如下：

25， 84， 21， 47， 15， 27， 68， 35， 20）进行排序时，

20 ，15， 21，25， 47，27， 68， 35， 84

15 ， 20， 21， 25， 35， 27，47， 68，84 15 ， 20， 21， 25， 27， 35，47， 68，84 则所采用的排序方法是（

D）。

．希尔排序

C

．归并排序

D.

快速排序

A ．选择排序

B

第 4 章

1．顺序 栈判空 的条件是（C）

A ． top==0 2．设有编号为 能的出站顺序为

A ． 1234

B． top==1

C ． top==-1 D． top==m

1， 2， 3， 4 的四辆列车，顺序进入一个栈式结构的站台，下列不可 ( D ) B ． 1243

C ． 1324 D． 1423

3．插入 和删除 只能在 一端进行 的线性 表，称 为 ( C A ．队列

) 。

B．循环 队列 C． 栈 D． 循环栈

4．链栈 与顺序 栈相比 ，有一个 比较明 显的优 点是（

A．插入 操作根 加方便 C．不会 出现栈 空的情 况

B ）。

栈满的 情况。

B．通常 不会出现

D． 删 除操作根 加方便 A

5．在栈 中，出 栈操作 的时间复 杂度为 (

A ．O(1) B

． O(log 2n)

C． 0(n)

) 。

2

D ． O(n )

6．带头 结点的 链栈 LS 的示意图 如下， 栈顶元 素是（ A

LS

H A ． A

A B． B

B C ． C

）

C D ． D

D Λ

7．元素 A,B,C,D 依次进 栈以后， 栈顶元 素是（ D ）

A ． A

B． B

C． C D ． D

8．顺序 栈存储 空间的 实现使用 （B ）存储 栈元素。 A ．链表 B．数组

9．在 C或 C++语 言中， 一个顺序

C．循环 链表 D． 变量

栈一旦 被声明 ，其占用 空间的 大小（ A

）。

A ． 已固定 B．不固 定 C．可 以改变 D．动态 变化

10 ． 当 栈 中 的 元 素 为 n 个 ， 做 进 栈 运 算 时 发 生 上 溢 ， 则 说 明 该 栈 的 最 大 容 量 为

（ C

） 。

A ． n-1B ． n+1C ． nD． n/2 11 ．栈与 一般线 性表的 区别在于

( B ) 。

A ． 数据元 素的类 型不同 B． 运算是 否受限 制 C．数据 元素的 个数不 同 D．逻 辑结构 不同

12 ．设有 一个顺 序栈 S，元素 A,B,C,D,E,F,

依次 进栈，如 果六个 元素出 栈的顺序 是

。

B，D，C，F，E，A，则栈的容量

至少应 是 ( A )

A ． 3B． 4C． 5D． 6

13 ．在栈 顶一端 可进行 （

D ） 操作。

A ．插入 B．删除 C．进栈 D．插入和

删除

14 ． 从 一 个 栈顶 指 针 为 top 的 链 栈 中 删 除 一 个结 点 时 ， 用 x 保 存被 删除 的结 点 ， 应

执行下列

(D) 命令。

． top=top->next;x=top->data;

A ． x=top;top=top->next; B

C． x=top->data;D

． x=top->data;top=top->next;

15．在一个栈顶指针为HS的链栈中，将一个S指针所指的结点入栈，应执行下列

( B )

命令。

A ． HS->next=S; B． S->next=HS->next;HS->next=S; ． S->next=HS;HS=HS->next;

A ) 。 C．先 进后出

C． S->next=HS->next;HS=S;D

16 ．在队 列中存 取数据 应遵循的 原则是 ( A ．先进 先出

B． 后进先出

D．随 意进 出

17 ．设长 度为 n 的链队 列 用单循环 链表表 示，若 只设头指 杂度为 ( A ． O(1)

C ) 。

针，则 人队操 作的时间 复

B ． O(log 2 n) C ． O(n)

D． O(n 2)

18 ．一个 循环队 列一旦 说明，其 占用空 间的大 小（ A） 。 A ．已固 定

B．可以变 动

C ． 不能固定

D．动态变化

19 ．当利用大小为n的数组顺序存储一个队列时，该队列的最后一个元素的下标为 （ B

）。

A ． n-2 B． n-1 C ． n D ． n+1

20 ．设长 度为 n 的链队 列 用单循环 链表表 示，若 只设尾指 杂度为 ( A ． O(1)

A ) 。

2

针，则 出队操 作的时间 复

B ． O (log n) C ． O(n)

D． O(n 2)

21 ．队列 是限定 在（ D）进行操 A ．中间

B．队头

作的线 性表。

C． 队尾 D．端 点 ）。

22 ．若进队的序列为：A， B， C， D，则出队的序列是（ A ．B，C，D，A C．A，B，C，D

C

B．A，C，B，D

D．C，B，D，A

23 ．从一个顺序循环队列删除一个元素时，首先需要做的操作是（ A ．队头 指针减 1

B ）。

B ．取 出队头指

尾指针 所指的 元素

针所指 的元素

C ．队头 指针加 1 D ．取出队

24. 在一个顺序存储的循环队列中，队头指针指向队头元素的（ A ．前一 个 25 ．四个元素按： 元素是（ A ． A

A

D ．当前

）位置。

B．后一个

C ．后面

A， B， C， D顺序连续进队 Q，执行一次 OutQueue(Q) 操作后，队头 ）。

B

B． BC． C

B ) 。

D． D

26 ．队列 中的元 素个数 是( A ．不变 的

27 ．设链栈中结点的结构： 想在链栈的栈顶插入一个由指针

B．可变 的

data 为数据域，

C．任意 的 next 为指针域，且

D． 0

top 是栈顶指针。若 A

s 所指的结点，则应执行下列（

B． top->next=s D． s->next=top

）操作。

A ． s->next=top->next； top->next=s C． s->next=top

； top=top->next

； top=s

28 ．若用一个大小为 6的数组来实现循环队列，且当前 front 和rear 的值分别为 3和 0，当从

B

)。

队列中删 除一个 元素， 再加入两 个元素 后， front 和 rear 的值分别为 (

A

．5和1 B．4和2

( D )

。

C ．2和4

D．1和5

29．以下属于队列的操作有 A ．在队 首插入 元素 C ．按元 素的大 小排 序

B．删除 值最小 的元素

D．判断 是否还 有元素

30. 带头结点的 链队列 LQ示意图如 下， LQ为空时 （ A ） LQ->front

H

A B C D

Λ

LQ->rear

A． LQ->front== LQ->rear

B． LQ->rear==NULL

C． LQ->front!= LQ->rear D． LQ->front==null

第 5章

1．串是一种特殊的线性表，其特殊性体现在（B）。

A.可以顺序存储B．数据元素是一个字符

C.可以链接存储D．数据元素可以是多个字符

2．设 目 标 串 T=\"AABBCCDDEEFF\" ，P=\"CCD\" ，则 该 模 式 匹 配 的 有 效 位 移 为 (

C ) 。

A．2 B．3 C．4D.5

3 ． 设 有 两 个 串 p 和 q， 求 q 在 p 中 首 次 出 现 的 位 置的 运 算 称 作 ( B

A.连接B．模式匹配

。

)

C.求子串

D．求串长

， S2=\"SDUDENT\" ， 执 行串 比 较 函 数 EqualStr(S1,S2)

后的结果

4. S1=\"sdudent\"

C ) 。 为 (

A． 0 B．小于0 D

）。

C．大于0

D．不确定

5．串的模式匹配是指（

A．判断两个串是否相等 B．对两个串比较大小

C．找某字符在主串中第一次出现的位置

D．找某子串在主串中第一次出现的第一个字符位置

6．朴素模式匹配算法在最坏情况下的时间复杂度是

A

( D )

。

． O（ m）

B

． O（ n）

C ． 0 （ m+n） D． 0 （ m*n）

7．以下论断正确的是

A

( A )

。

B． \"BEIJING\" 是 \"BEI JING\" 的子串

． \"\" 是空串， \"\" 空格串 ． \"something\"<\"Somethig\"

， S2=\"30July2005\"

C

D． \"BIT\"=\"BITE\"

8. S1=\"Todayis\" 果为(

A

)。

，执 行 串 连 接 函 数 ConcatStr(S1,S2)

后 的 结

A． \"Today is 30 July2005\"

B． \"30 July2005\"

C． \"Today is\" D． \"30 July2005 Today is\"

9．某串的长度小于一个常数，则采用（

A ．链式 B

B ）存储方式最节省空间。

．顺序

C．堆结构 D．无法确定

10. S=\"Today is 30 July2005\" ， LenStr(S)=( D ) 。

A． 18 B． 19 C． 20D． 21

) 。

11 ． 设 有 两 个 串 S1和 S2， 则 EqualStr(S1,S2) 运 算 称 作 ( D

A. 串连接

B．模式匹配 D．串比较

， S2=\"morning\"

， 执 行 串 连 接 函 数 ConcatStr(S1,S2)

C. 求子串

12. S1=\"good\"

后的结果为

(

A ) 。

B． \"good morning\"

A． \"goodmorning\" C． \"GOODMORNING\"

D． \"GOOD MORNING\"

13．在实际应用中，要输入多个字符串，且长度无法预定，则应该采用（ 式比较合适。

A

C ）存储方

．链式

B ．顺序 C．堆结构

D

．无法确定

14.

设 串 S1=\"I AM\" ， S2=\"A SDUDENT\ 则 ConcatStr(S1,S2)=(

B． \"I AM A SDUDENT\"

D. \"A SDUDENT\"

B ) 。

A． \"I AM\"

C． \"IAMASDUDENT\"

15. 以下论述正确的是（ C ）。 B． \"tel\"

是 \"Teleptone\"

的 子 串

A． 空 串 与 空 格 串是 相 同 的

C．空串是零个字符的串

D. 空串的长度等于1

） 恰 好 有 m个 直 接前 驱 和 m个 直接 界 后 继 。

16. 在 一 个 m维 数 组 中， （ D

A.开始结点B．总终端结点

C.边界结点D．内部结点

17. 数组的体积与（ A）无关。 A ．数组的基地址 C．各维的上下界

B ．维数

D．结点的大小

18. 对下述矩阵进行压缩存储后，失去随机存取功能是（

A ．对称矩阵

B

D ）。

．三角矩阵 D．稀疏矩阵

C．三对角矩阵

19. 在按行优先顺序存储的三元组表中，下述陈述错误的是（

D ）。

A． 同 一行的非零元，是按列号递增次序存储的

B． 同 一列的非零元，是按行号递增次序存储的

C． 三 元组表中三元组行号递增的

D． 三 元组表中三元组列号递增的

20. 以下（ C ）是稀疏矩阵的压缩存储方法。 A ．一维数组

C．三元组表

B

．二维数组

D．广义表

）。

21. 对稀疏矩阵进行压缩存储是为了（

B

A ．降低运算时间

B．节约存储空间

D．便于输入和输出

C．便于矩阵运算

22. 若数组 A[0..m[0..n] 按列优先顺序存储，则 A ． LOC(a 00 )+[j*m+i] C． LOC(a 00 )+[(j-1)*n+i-1]

aij的地址为（ A

）。

B． LOC(a 00 )+[j*n+i]

D． LOC(a 00 )+[(j-1)*m+i-1]

23. 下列矩阵是一个（

B ）

A ．对称矩阵

B ．三角矩阵

D．带状矩阵

C．稀疏矩阵

24.在稀疏矩阵的三元组表示法中，每个三元组表示（

A． 矩 阵中非零元素的值

B． 矩 阵中数据元素的行号和列号

D

）。

C． 矩 阵中数据元素的行号、列号和值

D． 矩 阵中非零数据元素的行号、列号和值

25. 已知二维数组 A[6][10] ，每个数组元素占 4个存储单元，若按行优先顺序存放数组元素

a[3][5] 的存储地址是 1000，则 a[0][0] 的存储地址是（

A． 872

B． 860

C． 868

B

）。

D． 8

26. 已知二维数组 A[8][10] 中， a12的地址为 1000，则 a00的地址为（

A． 972

B． 979

C． 980

C

）。

C

）。

D． 982

27. 数组与一般线性表的区别主要在（ A ．不能进行插入操作 C．逻辑结构方面

B．不能进行删除操作 D．存储方面

28. 数组是一个（

B

）线性表结构。

A ．非 C．加了的

29. 数组 A[0:1,0:1,0:1]

B．推广了的

D．不加的

共有（ B． 5

D ）元素。 C． 6

A． 4 D． 8

30. 二维数组 a[4][4] ，数组的元素起始地址 Loc[0][0]=1000 ，元素长度为 2，则 Loc[0][0] 为 （D）。

A． 1000

B． 1008

C． 1010

D． 1020

第 6 章

1．树最适合用来表示（

D

）。

A ．有序数据元素

B

D

．无序数据元素

．元素之间有分支层次的关系

）。

C ．元素之间无联系的数据

2．对于一棵满二叉树， m个树叶， n 个结点，深度为 h，则（ D

A ． n=h+m

B ．h+m=2n

C C

C ． m： h-1 D

． n=2h-1

3．结点前序为 ABC的不同二叉树有（

A ．3

）形态。

B ．4 ．5 D．6

4．下列 4 棵树中，（ B

A ．

）不是完全二叉树。

B ． C ． D ．

A B

C

B

A A A

C

B

F

D

E

C

B

D

C

D

E

F

G D E

5．根据二叉树的定义，具有

3 个结点的二叉树有（ B． 4

C C． 5

）种树型。

A ． 3 D． 6

6．如右图所示的二叉树，先序遍历的序列是（

A ． A、 B、C、D、E、 F、G 、 H、I

B ）

A

B

C

B． A、 B、D、H、I 、 E、C、F、G

D E F G

C． H、 D、I 、B、E、 A、F、C、G

H I

D． H、 I 、D、E、B、 F、G、C、A

7．下列存储形式中，哪一个不是树的存储形式（

D

）。

A ．数组存储法

B ．双亲表示法

C ．孩子链表表示法 D ．孩子兄弟表示法 8．具有 35 个结点的完全二叉树的深度为（

A ． 5

K

B

） C． 7

K-1

B． 6 K 层至多有（

K

D．8

K-1

9．对于二叉树来说，第

C ）个结点。 C

A ． 2

B．2 -1 A ）。

．2

D．2 -1

10．线索二叉树是一种（

A ．物理

B

．逻辑 C．逻辑和存储 D．线性

11．一棵 n 个结点的二叉树，其空指针域的个数为（

A ． n

B

B ）。

． n-1

C ）

．n+1 C

D

．不确定

12．如右图所示的二叉树，中序遍历的序列是（

A

B

C

E

F

D G

A． A、B、C、D、E、F、 G 、H、I

B． A 、B、D、H、I、E、C、F、G

C． H、D、I、B、E、A 、F、C、G

D． H、I、 D、E、B、F、G、C、A

13．二叉树按某种顺序线索化后， 任一结点均有指向其前驱和后继的线索，

这种说法（ B

A ．正确

B

．错误

C．不确定

D

．都有可能

14．深度为 K 的二叉树至多有（ B

）个结点。

A ． 2 K B． 2K-1 C ． 2K-1

D．2K-1 -1 15． A， B 为一棵二叉树上的两个结点，在中序遍历时， A 在 B 前的条件是（ C ）。

A ．A在 B右方 B．A 是 B 祖先 C．A在 B左方 D．A 是 B 子孙

第 7 章

1． 在一个图中，所有顶点的度数之和等于图的边数的(

C )

倍。

A ． 1/2

B. 1

C. 2

D. 4

2．生成树的构造方法只有（

B ）。

A ．深度优先

B

．深度优先和广度优先 C ．无前驱的顶点优先

D

．无后继的顶点优先

3． 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的

( B )

倍。

A ． 1/2

B. 1

C. 2 D. 4

4．下面的各种图中，（

C

）的邻接矩阵一定是对称的。

A ． AOE图

B． AOV图

C．无向图 D

．有向图

5．无向图顶点 v 的度是关联于该顶点（ B

）的数目。

A ．顶点

B．边 C．序号

D．下标

6．有 n 个顶点的有向图的邻接矩阵是用（ B ）数组存储。

A ．一维

B． n 行 n 列 C．任意行 n 列

D

． n 行任意列

7．有 n 个条边的无向图的邻接矩阵（表）存储法中，链表中结点的个数是（

C ）个。A ． n/2

B． n C． 2n

D． n*n

8．在图的表示法中，表示形式唯一的是（

A

）。

A ．邻接矩阵表示法

B．邻接表表示法

C ．逆邻接表表示法

D．邻接表和逆邻接表表示法

9．最小生成树的构造可使用（ A ）算法。

A． prim 算法 B．卡尔算法 C．哈夫曼算法 D．迪杰斯特拉算法

10．在下列图中，度为

3 的结点是（ B

）。

1

2

3

）。

4 5

A ．V1B.V 2C. V 3D.V4

11．具有 4 个顶点的无向完全图有（

A ）条边。

A ． 6

B． 12 C． 16

D． 20

12 按广度优先进行遍历，则可能得到的一种顶点序列为（

B ）。

A． a， b， e， c， d， f

a

B． a， b， e， c， f ， d C. a ， e，b， c， f ， d b

c

D. a ， e，d， f ， c， b

e

13．连通分量是（

C

）的极大连通子图。 d f

A ．树

B．图 C．无向图

D．有向图

14．强连通分量是（

D

）的极大强连通子图。

A ．树

B．图 C．无向图 D．有向图

15．任何一个连通图的生成树( C )

。

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

第 8 章

1．顺序查找法适合于存储结构为（

B）的线性表。

A ．散列存储 B．顺序存储或链接存储 C ．压缩存储

D．索引存储

2．采用二分查找方法查找长度为

n 的线性表时，每个元素的平均查找长度为（

A． O(n

2)

B ． O(nlog 2n)

C. O(n)

D

． O(log 2 n)

3．对线性表进行二分查找时，要求线性表必须（

D ）。

A ．以顺序方式存储

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

D．以顺序方式存储，且结点按关键字有序排序

4．采用顺序查找方法查找长度为

n 的线性表时，每个元素的平均查找长度为（

A ． n

B． n／2

C

． (n+1) ／ 2

D

． (n-1) ／ 2

5．如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用（ 方法。

A．分块 B．顺序 C．二分 D．散列

6．设哈希表长 m=14 ，哈希函数 H(key)=key ％11。表中已有 4 个结点：

addr(15)=4

addr(38)=5

D ）。

C）。

A ）查找

addr(61)=6

addr(84)=7

其余地址为空。如用二次探测再散列处理冲突，关键字为

A．8

B

．3

C

49 的结点的地址是（ D

．9

D ）。

．5

7．有一个长度为 12 的有序表， 按二分查找法对该表进行查找，

查找成功所需的平均比较次数为（

A． 35／ 12

在表内各元素等概率情况下

B）。

B ． 37／12 C ． 39／12

D ）。

D ． 43／ 12

8．平衡二叉树的各结点左右子树深度之差不能为（

A ．-1B．0 9．下列（

C

C

．1D．2

）不是利用查找表中数据元素的关系进行查找的方法。

A．平衡二叉树 B．有序表的查找 C. 散列查找 D．二叉排序树的查找

10． 100 个元素采用二分查找时，最大的比较次数是（

C）。

A．25 B

．50

C

）。

C

．7

D

． 10

11．冲突指的是（

A．两个元素具有相同序号

C．不同键值对应相同的存储地址

B. 两个元素的键值不同

D

．两个元素的键值相同

12．线性表必须是（ B ），才能进行二分查找方法查找。

A．顺序存储的线性表 C. 链表存储的线性表

B．顺序存储的有序表 D．链表存储的有序表

13．不可能生成下图所示二叉排序树的关键字序列是（

A ）。

4

A． 45312 B． 42531 C． 45231

2

5

1

3

D． 42315

14．动态查找包括（ B）查找。

A．顺序表 B. 二叉排序树 C．有序表 D．索引顺序表

15．在查找过程中，不做增加、删除、修改工作，这种查找称为（

A．静态查找 B. 内创造 C．动态查找 D．外查找

A）。

四．应用题

1．根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。

A= （ D， R），其中：

D={1 ， 2， 3，4， 5， 6} ，

R={ （ 1,2） ,（ 1,6）,（ 2,3） ,（ 2,4） , （ 3,4） ,（ 3,5） ,（ 3,6） ,（4,5） ,（ 5,6） }

解：

1

2

6

3

4

5

属于图结构

2.根据二元组关系画出逻辑图形，并指出它们属于何种数据结构。

B=（ D， R），其中：

D={40 ，30， 20，60， 50， 80， 70，10} ， R={<30,20>,<30,60>,<20,40>,<60,50>,

<60,70>,<60,80>,<70,10>}

解：

30

20

60

40

50

70

80

10

属于树结构

3. 求下列表达式： 3+4/(25-(6+15))*8 的后缀表达式（要求写出过程） 解： 3 4 25 6 15 + - / 8 * +

4. 求下列表达式： A*(B+C)*D-E 的后缀表达式（要求写出过程） 解： ABC+*D*E –

5 设有一个栈，元素进栈的次序为：

A， B， C， D， E，用 I 表示进栈操作，栈操作，写出下列出栈的操作序列。 （ 1）C，B，A，D，E （ 2）A，C，B，E，D解：（ 1 ） IIIOOOIOIO

（ 2） IOIIOOIIOO

6. 序列 1， 2， 3 顺序入栈，试写出所有可能的出栈序列。 解：

1，2，3 1，3，2

2，1，3 2，3，1 3，2，1

7 按二叉树前序遍历的结果为： ABC ，试画出所有不同的二叉树。

解：

O

表示出

A

B

B

A

A A

B

A

B

B C

C

C

C

C

8. 二叉树按中序遍历的结果为：解：

ABC，试画出所有不同形态的二叉树。

C

C

B

B

A

A

C

A

B

9. 把下列一般树转换为二叉树

1

2

3 4

5

6

7

8

解：

10 把下列森林转换为二叉树

AF

H

B

C D

G

I J

E

K

解：

A B

F

C

G H

E D I

A

A

B

C

CB

1 2 3

4

5 6

8

7

11. 将下列二叉树转换为森林。

A

B

C

D

F

H

I

E

G

解：

A

E

G

B C D F H I

12.将下列二叉树转换为森林。

A B

C

E

F

G

D

H I J

K

解：

A

C

B

E

G

F

D

J K

I

H

13. 某二叉树的结点数据采用顺序存储，其结构如下： 1

2 3 4 5

6 7

8

9 10

11 12 13 14 E A

F

D

H

C

G （ 1）画出该二叉树（ 2 分）

（ 2）写出结点值为 D 的父结点及左、右子树（ 3 分）解： （ 1）

E

A

F

DH

C

G

I

B

（2） D 的父结点为

A

D 的左子树为 C D 的右子树为空

14 给定如图所示二叉树

T ，请画出与其对应的中序线索二叉树。

28

25

33

4008

60

55

0

解：

（1）中序遍历序列： 55 40 25 60 28 08 33

（2） 中序线索二叉树：

28

25

33

NULL

NULL

40

60 08

550

15

16

17 18 19 20

I

B

2000 计算机研究生考题】

3

【

15 已知一棵二叉树结点的中序遍历序列为：

DEBAFCHG ，后序遍历序列： EDBFHGCA ，

试恢复该二叉树，并写出它的先序遍历的序列。

解：恢复的二叉树

A

B C

D

F

E

G

H

先序遍历序列为： ABDECFGH

16. 画出表达式： -A+B-C+D 的标识符树，并求它们的后缀表达式。 解：

+

ˉ

D C

+

ˉ

B A

–D +

0

后缀表达式： 0 A–B + C

17.画出表达式：（ A+B/C-D ） *（ E* （ F+G））的标识符树，并求它们的后缀表达式。

解：

*

ˉ

*

D

E

F

C

+

G

+

A

B

/

后缀表达式： ABC/+D –EFG+**

后缀表达式： ABCD/*+E*FG*+

18 假设用于通信的电文仅由 A 、B 、 C、 D 、E、 F、 G 8 个字母组成，字母在电文中出现的频率分别为 7， 19，2， 6， 32，3， 21， 10。试为这 8 个字母设计哈夫曼编码。

解：以权值： 2、 3、6、 7、 10、19、 21、32 构造哈夫曼树：

100

0

1

字母编号

1

对应编码 1010

00 10000 1001

11 10001

01 1011

出现频率

40

1

0

60

0

A B C D E

1

D E F

7 19 2 6 32 3 21 10

19

21

28

0

32

1 17

0

11

1 0

0

5

1

2

3

6 7

10

19.

已知某图 G的邻接矩阵如图，

0 1 0 1 1 0 1 0 0 1 0 1 1 0 1 0

解： （1）

（ 1）画出相应的图； （ 3 分）

（ 2）要使此图为完全图需要增加几条边。 （ 2 分）

1 2 1 2

4 3 4 3

（2）完全无向图应具有的边数为：

右图）。

n* （ n-1） 1/2=4* （ 4-1）/2=6，所以还要增加

2 条边（如

20. 根据如下有向图，画出邻接矩阵和邻接表。

①

②

③

④

⑤

解

（ 1）邻接矩阵

12345

10 20 30 41 50

1 1 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0

（ 2）邻接表 1 2 3 4

2 4 5 1 4

3

∧ ∧ ∧ ∧

5∧

5

21. 已知一个无向图有 6 个结点， 9 条边，这 9 条边依次为（ 0，1），（ 0，2），（ 0，4），（0， 5），（ 1，2），（ 2， 3），（ 2， 4），（ 3，4），（ 4， 5）。试画出该无向图，并从顶点 0 出发，分别写出按深度优先搜索和广度优先搜索进行遍历的结点序列。

解：

0

1 2 4 5

3

从顶点 0 出发的深度优先搜索遍历的结点序列： 从顶点 0 出发的广度优先搜索遍历的结点序列：

0 1 2 0 1 2

3 4

4 5 （不唯一）。 5 3 （不唯一）。

22.已知一个无向图的顶点集为： {a ，b， c， d，e} ，其邻接矩阵如下：

0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1

（ 1） 画出该图的图形；

（ 2） 写出从顶点 a 出发按深度优先搜索进行遍历的结点序 列。

1 0 1 1 0

解：

（1）（ 2）深度优先搜索：

a

a b d c e （或 a b d

e

e c）

b c d

23.图 G 的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。

0 8

8 0

10 11 0 3 0 4 0

0 13 4 0 7

0 7 0

10 3 11 0

0 13

解：

11

最小生成树：

8

1

10

2

3 3 5

4

7

84

1

13

2

3

3 4

4

5

7

24. 已知如图所示的有向图，请给出该图的 :

（ 1） 每个顶点的入 / 出度； （ 2） 邻接表。

解： （1）

（ 2）

顶点 入度 出度

1 3 0

2 2 2

3 1 2

4 1 3

5 2 1

6 2 3

25 对于给定结点的关键字集合 4， 8， 2， 10} ，

K={5 ，7，3，1，9，6，

（1）试构造一棵二叉排序树；

（2）求等概率情况下的平均查找长度 解：（ 1）构造二叉排序树：（

ASL 。

2） ASL=(1*1+2*2+3*4+4*3)/10=2.9

5

3 1

2

7

4

6

9

8 10

26 对于给定结点的关键字集合 （ 1）试构造一棵二叉排序树；

1

K={1 ， 12， 5， 8， 3， 10， 7，13， 9} ，

12

5

3

7

9

13

8

10

（ 2）在二叉树排序 BT 中删除“ 12”后的树结构：

1

1

10

13

5

或

3

8

3

7

9

10

5

13

8

7

9

27 给定结点的关键字序列为： 19， 14，23， 1，68， 20，84， 27，55， 11， 10， 79。

设散列表的长度为 13，散列函数为： H（ K ） =K % 13 。

试画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。解：（ 1） 线性探测再散列解决冲突时所构造的散列表：

0

1 14

2 1

3 68

4 27

5 55 ①①

6 19

7 20

8 84

9 79

10 23 ①③

11 11

12 10

①②①④③

（2）平均查找长度

③⑨①

ASL= （ 1*6+2*1+3*3+4*1+9*1 ） /12=30/3=3

28 给定结点的关键字序列为： 19， 14，23， 1，68， 20，84， 27，55， 11， 10， 79。

设散列表的长度为 13，散列函数为： H（ K ） =K % 13 。

试画出链地址法解决冲突时所构造的哈希表，并求出其平均查找长度。解：（ 1）链地址法解决冲突时所构造的哈希表。

0

∧

14

∧

1

27

79

∧

1

2

3

68

∧ ∧

19 20 ∧

∧ ∧

23 11 ∧

∧

55 ∧

4 5 6 7

84 ∧

8 9 10 11

10 ∧

12

（2）平均查找长度 ASL= （ 1*6+2*4+3*1+4*1 ） /12 = 21/12 =7/4 ( 或 1.75)

29 解：

已知数据序列 {17 ， 18，60， 40，7， 32， 73， 65， 85}

17 18 60

40 7 32 73 65 85

请写出采用冒泡排序法对该序列作升序排序时每一趟的结果。 第一趟排序结果： 第二趟排序结果： 第三趟排序结果： 第四趟排序结果：

17 18 40 7 32 60 65 73 85 17 18 7 32 40 60 65 73 17 7 7

7 18 32 40 60 65 17 18 32 40 60 17 18 32 40

第五趟排序结果：

第五趟排序过程中已无记录交换，排序结束。

30 已知数据序列 {10 ，8， 18， 15，7， 16} ，写出采用直接插入算法排序时，每一趟排序的结果。 解：

10 8 18

15 7 16

7

第一趟结束时结果： 第二趟结束时结果： 第三趟结束时结果： 第四趟结束时结果： 第五趟结束时结果：

[810] 1815 [810 18]15 [8

16

7 16

16 18]

10 15 18] 7 16

15 16

[7 8 10 15 18] [7 8 10

31 已知数据序列 {10 ， 1， 15， 18， 7，15} ，试画出采用快速排序法，第一趟排序的结果。

解

1011518715 low

交换

high

7

1 15 18 [10] 15 low

high

7 1 [10] 18

low high

15 15

交换

第一趟排序结果：

32 已知数据序列 {10 ， 18，4， 3， 6，12， 9，15} ，写出二路归并排序的每一趟排序结果。

[10] [18] [4] [3] [6] [12] [9] [15] [10

18] [3

4] [6 12] [9 15] 18] [6

9 12 15]

第一趟排序结果 第二趟排序结果 第三趟排序结果

[3 4 10

[3 4 6 9 10 12 15 18]

33 已知数据序列 {40 ，63， 11，84，35，93，58， 39，15} ，写出采用简单选择排序的每一趟排序结果。 解：

[40 63 11 84 35 93 58 39 15] （ 11）

[63

40 84 [40 84

[84 39）

35 93 58 39 15] 35 93 58 39 63] 40 93 58 39 63] [40 93 58 84 63]

[93

58 84 63] [93 84 63]

[84 93] 84） 84

[93] 93）

（ 11 15） （ 11 15 35 （ 11 15 35 （ 11 15 35 （ 11 15 35 （ 11 15 35 （ 11 15 35

（ 11 15 35）

39 40）

39 40 58） 39 40 58 63 39 40 58 63

39 40 58 63）

五．程序填空题（填上适当的表达式、运算符或语句，每空

1 分，共 5 分）

1．已知线性表中的元素是无序的，并以带表头结点的单链表作存储。试写一算法，删除表中所有大于 min ，小于 max 的元素。

Void delete (lklist head; datatype min, max)

{ q=head->next; while (p!=NULL)

{ if ((p->data<=min ) {q=p; p=

p->next

| | ( p->data>=max

; }

)

else

{ q->next=

p->next

;

;

;

delete (p)

p= q->next }

}

}

2． 在带头结点的 head 单链表的结点 a 之后插入新元素 x，试完成下列填空。

struct node

{ elemtype data; node };

void lkinsert (node *head, elemtype x) { node * s, * p;

s= new node ;

* next;

s->data=__x _;

p=head->next;

while (p!=NULL) &&( p->data!=a )

_____p=p->next_________;

if (p==NULL)

cout<< \" 不存在结点 a!

\" ;

else {_____s->next=p->next______;

___ p->next=s__________;

}

}

3．在顺序存储的线性表第

i 个位置插入新结点 x，

typedef struct

{ datatype data[MAXLEN]; int last;

// 将 data 和 last 封装在一个结构体

}SeqList;

int InsList(SeqList *L,int i,datatype x) { int j;

// 插入结点函数

if (L->last= =MAXLEN-1)

{ cout<< \"顺序表已满！ \"; return(-1);}

if( i<1 || i>L->last+2 ) { cout<< \"

位置出错！ \"; return(0);}

// 检查插入位置的正确性

for (j=L->last; j>=i-1 ; j--)

L->data[j+1]=L->data[j] ; L->Lata[i-1]= x ; L->last ++

// 结点移动

// 新结点插入

;

（或 L->last= L->last +1

）

return(1);

}

4．试完成显示队列中所有元素的程序填空。

typedef struct queuenode // { int data;

struct queuenode *next; }queuenode; typedef struct }linkqueue;

void ShowQueue(linkqueue *q) { queuenode * p=q->front;

if(p==NULL)

cout<<\" 队列为空 ! \";

定义队列的存储结构

// 定义队头、队尾指针

{queuenode *front,*rear;

//

显示队列函数

else

{

cout<<\" 队列为： \";

while(p!=NULL) {cout<data;

p=p->next;

}

} }

5．下面程序是把两个串 typedef Struct { }St {int i;

char vec[MAXLEN]; int len; ;

r1 和 r2 首尾的程序，即：

//

// len

//

r1=r1+r2 ，试完成程序填空。

定义合并后串的最大长度

为串的长度

字符串连接函数

void ConcatStr(Str *r1,Str *r2)

cout<< r1->vec <vec; if(r1->len+r2->len> MAXLEN )

cout<< \" 两个串太长，溢出！ \";

else

{

for(i=0;i< r2->len ;i++) //

r1->vec[ r1->len+i ]=r2->vec[i]; r1->vec[r1->len+i]= '\\0' ; //

把 r2 连接到 r1

添上字符串结束标记

r1->len= r1->len+r2->len ;

//

修改新串长度

}

}

6. 在按行优先顺序存储的三元组表中，

求某列非零元素之和的算法如下， 填空以完成算法。

( 补结构体声明 )

if f2(TablSum *a,col)

{

// 求第 col 列非零元素之和

int k,sun=0;

if (

① a->t<=0 )

printf(

if (

“ a=0”); ② n<0 || n>=a->n

)

printf( “列错！” );

for ( ③ col=0 ; ④ kt ;

if (a->tada[k].j==n)

⑤ k++ )

sum=

⑥ a->data[k].v ;

return sum;

}

7．二叉树先序优先遍历

typedef struct BT

{ datatype data;

BT *lchild; BT *rchild; }BT;

void Preorder(BT *T)

{ i f( T )

{

cout<<

( T->data

;

或 T!=NULL )

// 定义结点

// 先序遍历

Preorder( T->lchild );

Preorder( T->rchild ); } }

8．二叉树中序优先遍历

typedef struct BT

{ datatype data;

BT *lchild; BT *rchild; }BT;

void Inorder(BT *T)

{ i f ( T )

{Inorder( T-> lchild );

cout<< T->data ; Inorder( T-> rchild );

} }

9．二叉树后序优先遍历

typedef struct BT

{ datatype data;

// 定义结点

（或 T！ =NULL）

// 定义结点

// 中序遍历

BT *lchild;

BT *rchild;

}BT;

void Postorder(BT *T)

//

{ i f ( T )

（或 T!=NULL）

后序遍历

{ Postorder( T->lchild );

Postorder( T->rchild ); cout<< T->data ; } }

10．二叉树按层次遍历

typedef struct BT { datatype data;

BT *lchild; BT *rchild; }BT;

void Levelorder(BT *T) { i nt i,j;

BT *q[100],*p; p=T;

if ( p!=NULL ) { i=1;q[i]=p;j=2; } while (i!=j)

{p=q[i]; cout<< p->data ; if ( p->lchild!=NULL )

{q[j]= p->lchild ;j++;} if (p->rchild!=NULL)

{ q[j]= p->rchild ;j++; } i++;

} }

11．以二叉链表为存储结构，试完成求二叉树深度的程序填空

//

定义结点

//

层次遍历

typedef struct BT

{ datatype data;

//

定义结点

BT *lchild;

BT *rchild;

}BT;

int TreeDepth(BT *T)

//

求树深度

{ i nt ldep,rdep; if( T==NULL )

return 0;

else

{ldep= TreeDepth(T->lchild) ;

rdep= TreeDepth(T->rchild) ;

if(ldep>rdep)

return ldep+1 ;

else

return rdep+1 ;

}

}

12．以二叉链表为存储结构，试完成求二叉树中叶结点数的程序填空。

typedef struct BT

{ datatype data;

//

定义结点

BT *lchild;

BT *rchild;

}BT;

void Leafnum(BT *T)

//

（或 T！=NULL）

求叶结点数

{ if( T )

count++ ;

Leafnum( T->lchild ); Leafnum( T->rchild ); } }

{ i f(T->lchild==NULL&&T->rchild==NULL)

// count

初值为 0

13． 设表的长度为 L，试填空完成直接插入排序程序。

voidinsertsort(int R[ ] )//

按递增序对 R[1] ~R[ n ] 进行直接插入排序

{ int i, j;

for (i=2; i <=L;i++ )

{R[0]=R[i ];

// 设定 R[0] 为监视哨

j=i-1

；

while (R[ 0 ]< R[ j ] ) { R[j+1]=R[j] ;

j- - ;

}

R[ j+1 ]= R[0];

//

插入第 i 个记录

}

}

14．直接选择排序 void selectsort ( ) //

按递增序对

R[1] ~

R[n] 进行直接选择排序

{ int i, j, k ;

for (i=1; i<= n ; i++)

{k=i ;

for (j= i+1; j<=n; j++)//

选择选择关键字最小的记录

if (R[ j ] < R[ k ] )

k=j;

if

（ ! k=j

）

{ R[ 0 ]=R[ i ]; //

交换关键字

R[ i ] = R[ k ] ;

R[ k ]=R[ 0 ]; }

}

}

15．填空完成交换二叉树中每个结点的左、右孩子的算法

typedef struct BT

{ datatype data;

//

BT *lchild;

BT *rchild;

}BT;

void Exchange(BT *T) //

{BT*P if( T )

(

或 T!=NULL )

{ Exchange(T->lchild);

Exchange(T->rlchild); if ( T->lchild || T->rchild ) { p= T->lchild ;

T->lchild= T->rchild ; T->lchild= p ;

} }

}

六．按题目要求，写出运行下列程序的结果

1． A[n] 为 int 类型的数组， A[n]=1 ， 45， 16， 28，3，80，法后的输出结果。

void findmax ( A[n] ) { int

max, i;

max=A[ 0 ]; i= 1 ;

while ( i { if

( A[i] > max )

max=A[i];

定义结点

交换每个结点的左、右孩子

36，18，77， 66，写出运行下列算

i ++ ;

}

cout<< max ; }

答： 80

2． 写出运行下列程序段的输出结果（栈的元素类型为

void main()

{Stack S;

Char x,y; InitStack(S); x= \"c \"; y= \"k \";

Push(S,x); Push(S, Push(S,y);Pop(S,x); Push(S, \"t \" ); Push(S,x); Pop(S,x); Push(S,

\"s \");

while(!StackEmpty(S))

{ Pop(S,y);cout<答： \"stack \"

\"a \");

char）。

3． 写出运行下列程序段的输出结果（队列中的元素类型为

void main()

{ Queue Q; InitQueue (Q);

Char x= \" e \"; y= \"c \";

InQueue (Q, \"h \"); InQueue (Q,

OutQueue (Q,x); InQueue (Q,x);

char）。

\"r \"); InQueue (Q, y);

OutQueue (Q,x); InQueue (Q,

\"a \");

while(!QueueEmpty(Q))

{ OutQueue (Q,y);cout<答： \"char \" 4.

设栈和队列的元素类型均为char，且队列 Q 中的元素为 ASDFGH，试写出运行下列算法 void algo(Queue &Q) {Stack S;

char d;

InitStack(S);

while(!QueueEmpty(Q)) { OutQueue(Q,d); Push(S,d); };

while(!StackEmpty(S))

后队列 Q的元素。

{ Pop(S,d);

InQueue(Q,d); } }

答： HGFDSA

（将队列中的数据元素进行逆置）

5．以二叉链表为存储结构的二叉树，试写出运行下列算法后，

typedef struct BT

{ datatype data;

BT *lchild; BT *rchild; }BT;

void Nodenum(BT *T) {

if （ T!=NULL） {

count++ ;

Nodenum( T->lchild ); Nodenum( T->rchild ); }

// count //

count 是求二叉树的。

定义结点

为全局变量

}

解：总结点数（或“结点总数” ，或“结点数” ）

6．二叉树的结构如图所示，试写出执行下列算法后的输出结果：

typedef struct BT

{ datatype data; BT *lchild; BT *rchild;

。

（用大写的英文字母表示， 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号）

A

B

F

E

D

G

}BT;

void Preorder(BT *T) { i f (T!=NULL)

{

cout<<

T->data;

Preorder(T->lchild); Preorder(T->rchild);

C

} }

解： ABCEDFG

先序遍历

7．二叉树的结构如图所示，试写出执行下列算法后的输出结果：

typedef struct BT { datatype data;

。

（用大写的英文字母表示， 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号）

A

BT *lchild; BT *rchild;

B

C

E

D

F

G

}BT;

void Inorder(BT *T) { i f (T!=NULL) {Inorder(T->lchild);

cout<data; Inorder(T->rchild);

} }

解： CEBAFDG

中序遍历

8．二叉树的结构如图所示，试写出执行下列算法后的输出结果：

typedef struct BT

{ datatype data; BT *lchild; BT *rchild;

。

（用大写的英文字母表示， 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号）

A

B

F

E

D

G

}BT;

void Postorder(BT *T) { i f (T!=NULL ）

{ Postorder(T->lchild);

Postorder(T->rchild); cout<data; } }

解： ECBFGDA

C

后序遍历

9．二叉树的结构如图所示，试写出执行下列算法后的输出结果：

typedef struct BT { datatype data; //

BT *lchild; BT *rchild; }BT;

。

（用大写的英文字母表示， 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号）

定义结点

A

B

D

void Levelorder(BT *T) { i nt i,j;

BT *q[100],*p; p=T;

if (p!=NULL)

{ i=1;q[i]=p;j=2; } while (i!=j)

{p=q[i]; cout<data ;

if (p->lchild!=NULL) {q[j]=p->lchild; j++;} if (p->rchild!=NULL)

C

F

G

E

{ q[j]=p->rchild; j++; }

i++;

} }

解： ABDCFGE

层次遍历

10．二叉树的结构如图所示，试写出执行下列算法后的输出结果：

typedef struct BT { datatype data;

BT *lchild; BT *rchild; }BT;

int BTD(BT *T) C

{ i nt ldep,rdep; if(T==NULL)

return 0;

else

{ldep= BTD (T->lchild) ;

rdep= BTD (T->rchild) ; if(ldep>rdep)

return ldep+1;

else

return rdep+1;

}

//

定义结点

。

A

B

F

E

D

G

}

解： 4

求二叉树深度

11．二叉树的结构如图所示，试写出执行下列算法后的输出结果：

。

typedef struct BT { datatype data; //

BT *lchild; BT *rchild; }BT;

void Leafnum(BT *T) { if(T!=NULL

）

// count

{ i f(T->lchild==NULL && T->rchild==NULL)

count++;

Leafnum(T->lchild); Leafnum(T->rchild); } }

解： 3

求叶结点数

定义结点

A

B

C

E

F

D

G

为全局变量，且初值为 0

12． 读下列算法，并回答下列问题：

（ 1）采用算法进行排序？ （ 2）算法中 R[0] 的作用是什么？

voidinsertsort(int R[ ] ) { int i, j;

for (i=2; i<=n;i++ ) {R[0]=R[i ];

j=i-1;

while (R[ 0 ]< R[ j ])

{ R[j+1]=R[j]; j- -;} R[ j+1 ]=R[0];

}

}

解：

（ 1）直接插入法

（ 2）监视哨 （或哨兵）

13． 已知 11 个元素的有序表为 {05 13 19 21 37 56 75 80 88 92}, 88，执行下列查找算法，要经过次比较才能找到 解： {

若查找

88。

int BS(SSTable ST,int key,int low,int high)

//

折半查找的递归算法

if (low>high) return 0; mid= (low+high)/2;

if (ST.elem[mid].key==key)

return mid;

else

//

查找不到时返回 0

if (ST.elem[mid].key>key) return BS(ST,key,low,mid-1);

二叉树的二叉链表描述如下： typedefstruct BT {datatypedata;

BT *lchild; BT *rchild; }BT;

C算法如下：

void Preorder(BT *T) {if (T==NULL) return;

else

return BS(ST,key,mid+1,high);

} 解： 3

（二分查找）

14．如下图所示的二叉树，其存储结构为二叉链表。其中 lchild ， rchild

分别为指向左右孩子的指针， data

为数

据域，试回答下列问题： （1）对下列二叉树，执行算法

Preorder() ，试指出其输

{cout<data; Preorder(T->lchild);

Preorder(T->rchild); } }

出结果是：；

（用大写的英文字母表示， 字母之间不要任何间隔符号， 最后一个字母后面也不要间隔符号） （2）设二叉树共有 n 个结点，试分析算法

A

B

C

E

Preorder() 的时间复杂度是： 。

D

F

G

解：

（ 1） ABCEDFG （ 2） O（ n）或 O(n)

15．如下图所示的二叉树， 其存储结构为二叉链表。 其中 lchild ， rchild 分别为指向左右孩子的指针， 试回答下列问题： 结果；

（用大写的英文字母表示，

二叉树的二叉链表描述如下： typedefstruct BT {datatypedata;

BT *lchild;

data 为数据域，

（1）对下列二叉树，执行算法

traversal()

，试指出其输出

BT *rchild;

字母之间不要任何间隔符号，

最后 }BT;

一个字母后面也不要间隔符号） C算法如下：

（2）对 n 个结点的二叉树，试写出算法 复杂度。

traversal()

的时间

void traversal(BT *T) {if (T!=NULL) {cout<data; traversal(T->lchild); cout<data;

traversal(T->rchild); } }

A

B

D

C

F

G

E

答：

（1） ABCCEEBADFFDGG （ 2）时间复杂度为 O(n)

（先根再左再根再右）

* 每个结点都被打印两次， 其规律是： 凡是有左子树的结点， 必间隔左子树的全部结点后再 重复出现；如 A ，B ，D 等结点。反之马上就会重复出现。如

C， E， F， G 等结点。

七．程序设计题

1．一个带头指针的单链表，写出在值为

void insertm ( lklist {p=head->next;

while ( p!=NULL )

p=p->next;

q=p->next;

&&

( p->data!=x )

X 的结点之后插入 m 个结点的算法。

head; int m )

for ( i=0;

ii ++ )

{ s=new ( node );

cin<// 输入待插入的值

s->data=a; p->next=s; p=s; }

p->next=q;

}

2. 在线性链表的第 i 个位置，插入值为 x 的结点，试写出该算法。

typedef struct linknode

{char data; struct linknode *next; }node; node *head; int n=0;

// 线性表长度

void InsList(int i,char x)

// 插入结点函数

{ node *s,*p;

int j;

s=new node; n++; s->data=x; if(i==0)

{ s->next=head;head=s;} else

{ p=head;j=1;

while (p!=NULL && jnext; } if(p!=NULL)

{s->next=p->next;

p->next=s;}

else

cout<<\" 未找到！ \"; }

}

3．有两个循环单链表，链头指针分别为

head1 和 head2，试编写一个函数将链表 接到链表 head2，链接后的链表仍然是循环链表。

（提示：先找到两链表的尾指针，将第一个链表的尾指针与第二个链表的头结点链接起来）解： node *link(head1,head2)

node *head1, *head2;

{node *p, *q;

链

head1

p=head1;

while(p->next!=head1)

p=p->next;

q=head2;

while(q->next!=head2)

q=q->next;

p->next=head2;

q->next=head1;

return(head1);

}

4．链栈的存储结构和栈顶指针定义如下：

#define MAXLEN 100 typedef struct stacknode {int data;

// 定义栈的存储结构

struct stacknode*next; }stacknode;

typedef struct

{ stacknode *top; }linkstack;

// 定义栈顶的指针

试写出把十进数转换为二进制数的程序。

解： void Conversion(int n)

{ linkstack s;

int x;

s.top=NULL; do

{x=n%2; //

n=n/2;

取余数

// 栈的应用：二—十进制转换

// 置栈空

// 取新的商

stacknode*p=new stacknode; p->next=s.top; // 修改栈顶指针 s.top=p;

s.top->data=x; // 余数入栈

}

while(n);

cout<< \" 转换后的二进制数值为： while(s.top) // 出栈处理

{cout<data;

stacknode*p=s.top;

// 申请新结点

\";

s.top=s.top->next;

deletep;// 出栈一个余数，收回一个结

}

}

5. 设计一个算法，要求判别一个算术表达式（存在字符数组 a[ ]中）的圆括号配对是否正

确？

（允许使用

InitStack(s) ，产生一个堆栈

S 来帮助判断）

解：

int correct(char a[ ]) {

stack s ;

InitStack(s);

// 调用初始化栈函数

for(i=0; iif (a[i]= = ’(’) Push (s,’(’);

else if (a[i]= = ’)’)

{

if StackEmpty(s)

return 0;

// 若栈空返回 0

；否则出栈

else

Pop (s);

}

if (StackEmpty (s) )

cout<< “配对正确！ ”;

//

若栈空，说明配对正确

else

cout<< “配对错误！ ”;

}

6．试写一个算法判别读入的一个以‘ #’为结束符的字符序列是否是“回文” 。

（允许直接使用建栈、建队、判栈空、判队空等函数）

解：

int PalindromeTest() //

判别输入的字符串是否回文序列

, 是则返回返回 0 {

InitStack(S);InitQueue(Q); while((c=getchar())!='#') {

Push(S,c);InQueue(Q,c);

//

同时使用栈和队列两种结构

}

while(!StackEmpty(S)) {

Pop (S,a);OutQueue (Q,b));

if (a!=b) return ERROR;

}

return OK;

}

否则

1,

7．试编写判别给定二叉树是否为完全二叉树的算法。

答： int IsFullBitree(Bitree T) // 判断二叉树是否完全二叉树 , 是则返回 1, 否则返回 0

{ InitQueue(Q); flag=0; InQueue (Q,T);

while (!QueueEmpty(Q)) { OutQueue (Q,p);

if (!p)

flag=1; else

if (flag) return 0;

else

{ InQueue(Q,p->lchild); InQueue(Q,p->rchild); } //

}

return 1; }

不管孩子是否为空，都入队列

分析： 该问题可以通过层次遍历的方法来解决，

不管当前结点是否有左右孩子都入队列。 这

样当树为完全二叉树时， 遍历时得到的是一个连续的不包含空指针的序列。 会含有空指针。

反之，则序列中

8．试写一个判别给定二叉树是否为二叉排序树的算法， 且树中结点的关键字均不同。 解：

bool BisortTree(BiTree T, BiTree&PRE) int last=0, flag=1;

趋大就行。

// last

设此二叉树以二叉链表作存储结构。

// PRE 为指向当前访问结点的前驱的指针。

是全局变量，用来记录前驱结点值，只要每个结点都比前

int IsBSTree (Bitree T)

// 判断二叉树 T 是否二叉排序树，是则返回 1，否则返回 0

{

if (T->lchild && flag)

IsBSTree(T->lchild);

if (T->data立即返回

// 与其中序前驱相比较 , flag=0

表示当前结点比直接前驱小，则

last=T->data; if (T->rchild && flag)

IsBSTree (T->rchild);

return flag; }

9．从键盘输入若干个整数， 以回车为间隔， 以-1 为结束符号， 建立一个顺序存储的线性表， 然后按提示输入一个待查找的数进行查找。若找到，则显示找到的数据在线性表中的位置；否则显示“找不到” 。

void SeqSearch() {int a[n],i,x,y;

cout<<\" 建立整数的顺序表 ( 以回车为间隔，以 -1 结束 ) ： \"; for (i=1;i<=MAXLEN;i++) {cin>>a[i]; if (a[i]==-1)

{ y=i; break; } }

cout<<\" 请输入要查找的数据： \";

cin>>x;

i=y-1;

while (i>=0&&a[i]!=x)

i--; if (i==0)

cout<<\" 没有找到 \";

else

cout<<\" 已找到，在第 \"<10.

对有序表 R[0] 至 R[n-1] 进行二分查找， 查找成功时返回记录在表中的位置；时显示：“没有找到！ ”，试编写此程序。

void BinSearch()

{ int R[MAXLEN],i,low,high,mid,n,x; char ch;

cout<< \" 请输入要查找的数据 : \"; cin>> x ;

low=0; high=n-1; while(low<=high)

{mid=(low+high)/2;

if(R[mid]>x)

high=mid-1; else

if(R[mid]low=mid+1;

else

break;

}

if(low>high)

{cout<< \"

没有找到！ \";

if(R[mid]查找失败

mid++;

cout<< \"

可将此数插入到 \" << mid+1<< \" 的位置上。 \";

}

else

cout<< \"

要找的数据 \" << x <<\" 在第 \"<< mid+1<<\" 的位置上 \";

}

11．设计一个函数修改冒泡排序过程以实现双向冒泡排序

关键字进行比较，产生最小和最大的元素）

（每一趟排序，

。

解： void dbubble(SeqList r)

{int i,j,t,b; while(b) { b=0;

for(j=n-i+1;j>=i+1;j--) //

由底向上

if (r[j].keyr[j-1]=t;

}

for(j=i+1;j由上向底

if(r[j].key>r[j+1].key)

{b=1; t=r[j]; r[j]=r[j+1]; r[j+1]=t; } i++; } }

12．以单链表为存储结构，写一个直接选择排序算法。

解： void selectsort(pointer h)

{ pointer p,q,r,s,t; t=NULL; while(h)

{p=h; q=NULL; s=h; r=NULL; while(p)

{ if(p->keykey)

{ s=p; p=q; }

if(s==h)

通过每两个相邻的

h=h->link; else h=s;

s->link=t; t=s;

} h=t; }

13．以单链表作为存储结构实现直接插入排序算法。 解： void InsertList (List head)

{Lnode *p, * pprev if(!head) return;

pprev=head; p=head->next; while(p)

{q=head; qprev=NULL; while(q->keykey)// {qprev=q; q=q->next;} if(q==p) //p else

{ current=p; p=p->next; pprev->next=p; current->next=q; if(q==head) // head=current; else //

} }

插在中间某个位置上

插在表头

最大，无须插入

查找插入位置

, q,*qprev, *current;

{pprev=p; p=p->next;}

qprev->next=current;

}

14.