73 ?对一个满二叉树，m个叶子，n个结点，深度为h，则D A n = h+m B h+m = 2n C m = h-1 D n = 2
h
-1
74.任何一棵二叉树的叶子结点在前序、中序和后序遍历序列中的相对次序 A
A.不发生改变 B ?发生改变 C ?不能确定 D ?以上都不对 75?在线索化树中，每个结点必须设置一个标志来说明它的左、右链指向的是树结构信息，还是线索化信息，若
息，1标识线索，对应叶结点的左右链域，应标识为 __ D _。
A. 00 B ? 01 C ? 10 D ? 11
76. ________________________________ 在下述论述中，正确的是 _D 。 ①只有一个结点的二叉树的度为 0;②二叉树的度为2;③二叉树的左右子树可任意交换；
④深度为K的顺序二叉树的结点个数小于或等于深度相同的满二叉树。
A.①②③ B .②③④ C .②④ D .①④
0标识树结构信
77. ____ 设森林F对应的二叉树为B,它有m个结点，B的根为p，p的右子树的结点个数为 n，森林F中第一棵树的结点的个数是 A 。
A. m-n B . m-n-1 C . n+1 D .不能确定
78.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是 B。
A. 9 B . 11 C . 15 D .不能确定
79 .具有10个叶子结点的二叉树中有 _B ________ 个度为2的结点
A. 8 B . 9 C . 10 D . 11
80 .在一个无向图中，所有顶点的度数之和等于所有边数的 _C_ 倍
A. 1/2 B 1 C 2 D 4
81 .在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 __B_倍 A. 1/2 B 1 C 2 D 4
82 .某二叉树结点的中序序列为 ABCDEF,G后序序列为 BDCAFGE则其左子树中结点数目为:
A. 3 C . 4 D . 5 B . 2
83 .已知一算术表达式的中缀形式为 A+ B *C - D/E，后缀形式为ABC *+DE/ -，其前缀形式为
A. - A+B*C/DE B . - A+B*CD/E C - +*ABC/DE D . - +A*BC/DE
84 .已知一个图，如图所示，若从顶点 a岀发按深度搜索法进行遍历, 序列为 ____ D___;按广度搜索法进行遍历，则可能得到的一种顶点序
f B d ①A. a， b， e， c， d， ? c， f， e， b，
a， C . a， D b ? e， e， b， c， d， d， f， c， f，
a，
f B d ②A. a， b， c， e， d， ? b， c， e， f，
a， ? C . a， e， b， c， f， d， c， f， d， e， D b
a，
85 .采用邻接表存储的图的深度优先遍历算法类似于二叉树的
A.先序遍历
B .中序遍历 C .后序遍历
D
D
A
.按层遍历
86 ?采用邻接表存储的图的广度优先遍历算法类似于二叉树的 D
A先序遍历 B ?中序遍历 C ?后序遍历 D ?按层遍历
87.具有n个结点的连通图至少有 _A _________ 条边
A n-1 B .n C . n(n-1)/2 D
. 2n
88 .广义表( (a)， a )的表头是 C ，表尾是C o A. a B
() C (a) D ((a))
89 .广义表( (a)) 的表头是C A. a B
，表尾是B o
D
((a))
()
C
(a)
90. 顺序查找法适合于存储结构为 _B_的线性表。 A散列存储
B
顺序存储或链式存储 C 压缩存储 D 索引存储
91.
A以顺序方式存储 C以链式方式存储
B D
对线性表进行折半查找时，要求线性表必须 _B 。
以顺序方式存储，且结点按关键字有序排列 以链式方式存储，且结点按关键字有序排列
92.采用折半查找法查找长度为 A O(n 2)
B O(nlog
2
n的线性表时，每个元素的平均查找长度为
D O(log
2
D o
n) C O(n)
n)
93.有一个有序表为｛ 1，3, 9， 12， 32， 41, 45，62, 75，77，82，95，100｝，当折半查找值为 82的结点时，
C
次比较后
查找成功。
A. 11
B 5
C 4
D 8
94. 二叉树为二叉排序
_B
B
树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法
A 正确
错误
95. 下面关于B树和B+树的叙述中，不正确的结论是 A B树和B+树都能有效的支持顺序查找 C B树和B+树都是平衡的多叉树
B B D B
A ______ 。
树和B+树都能有效的支持随机查找 树和B+树都可用于文件索引结构
96. _______________________________ 以下说法错误的是 _B 。 A. 散列法存储的思想是由关键字值决定数据的存储地址 B. 散列表的结点中只包含数据元素自身的信息，不包含指针。 C. 负载因子是散列表的一个重要参数，它反映了散列表的饱满程度。
D. 散列表的查找效率主要取决于散列表构造时选取的散列函数和处理冲突的方法。
97 .查找效率最高的二叉排序树是 _C _________ 。 A. 所有结点的左子树都为空的二叉排序树。 B. 所有结点的右子树都为空的二叉排序树。 C. 平衡二叉树。
D. 没有左子树的二叉排序树。
98?排序方法中，从未排序序列中依次取岀元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称 为C 。 A.希尔排序
B 。冒泡排序
C 插入排序 D
。选择排序
99?在所有的排序方法中，关键字比较的次数与记录的初始排列次序无关的是 A.希尔排序
B ?冒泡排序 C
D
?直接插入排序 D ?直接选择排序
100.堆是一种有用的数据结构。下列关键码序列 A. 94,31,53,23,16,72 C. 16,53,23,94,31,72
B D
D 是一个堆。
.94,53,31,72,16,23 .16,31,23,94,53,72
.堆排序是一种 101 A. 插入 B .选择
B
排序。
C .交换
D .归并
102. D 在链表中进行操作比在顺序表中进行操作效率高。
D .插入
A.顺序查找 B .折半查找 C .分块查找
103.直接选择排序的时间复杂度为 A. O (n) B . O(log 2n)
C
D
（n为元素个数）
O(n2)
.O(nlog 2n) D
二、填空题。
1. 数据逻辑结构包括 2. 数据的逻辑结构分为 3.
线性结构 、 树形结构
集合 、线性结构
和 图状结构 三种类型，树形结构和图状结构合称 、 树形结构 和 图状结构4种。
非线性结构 。
在线性结构中，第一个结点 没有前驱结点，其余每个没有 后续结点，其余
结点有且只有 1 个前驱结点；最后一个结点 每个结点有且只有 1 个后续结点。
4. 线性结构中元素之间存在 一对一关系，树形结构中元素之间存在 一对多关系，图形结构中元素之间存在 多对多 关系
5. 在树形结构中，树根结点没有 前驱结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结 点的后续结点可
以 任意多个 。
6 .数据结构的基本存储方法是
顺序、链式、 索引和 散列存储。
7. 衡量一个算法的优劣主要考虑正确性、可读性、健壮性和 时间复杂度与
空间复杂度。
8.
9 ?算法的5个重要特性是 10. n-i-1 11.
评估一个算法的优劣，通常从
有穷性 、 确定性、 可行性 、输入和输岀。
时间复杂度 和 空间复杂度 两个方面考察。
在一个长度为n的顺序表中删除第i个元素时，需向前移动 个元素。
在单链表中，要删除某一指定的结点，必须找到该结点的 前驱 结
点。
12.
在双链表中，每个结点有两个指针域，一个指向 前驱结点，另一个指向 后继结
点。
13.
在顺序表中插入或删除一个数据元素，需要平均移动 _n_个数据元素，移动数位置有关。
当线性表的元素总数应采用顺序 存 储结
据元素的个数与
14.
基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表的元素是， 构。
15?根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成 16.
_______________ 和 双链表。
下标 表示元素之间的关系的；链式存储结构是通过
顺序存储结构是通过
指针 表示元素之间的关系的。
17. 18. 19.
带头结点的循环链表 L中只有一个元素结点的条件是 L->next->next=L 。
栈是限定仅在表尾进行插入或删除操作的线性表，其运算遵循
后进先岀
的原则。
空串是 零个字符的串 ，其长度等于 零。空白串是由一个或多个空格字符组成的串，其长度等于其包含的空
格个数。
20.
组成串的数据元素只能是 单个字符 。
21. —个字符串中 任意个连续字符构成的部分 称为该串的子串 22.
子串” str ” 在主串” datastructure ” 中的位置是 5 。
23. 二维数组M的每个元素是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要540 个字节；M的第8列和第5行共占108个字节。 24.
稀疏矩阵一般的压缩存储方法有两种，即 三元组表 和 十字链表。
25. 广义表（（a ），（（ b ），c ），（（（ d））））的长度是 _3_，深度是 _4_。 26?在一棵二叉树中，度为零的结点的个数为 n2+1 27.
n0,度为2的结点的个数为n2,则有n0 =
。
在有n个结点的二叉链表中，空链域的个数为 _n+1_。
28. —棵有n个叶子结点的哈夫曼树共有 _2n-1_个结点。 29 ?深度为5的二叉树至多有_3j ________ 个结点。
30.若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点个数为 31 .某二叉树的前序遍历序列是 32. 33. 34. 35.
abdgcefh，中序序列是dgbaechf，其后序序列为 gdbehfca 。
69
。
线索二叉树的左线索指向其 遍历序列中的前驱 ,右线索指向其遍历序列中的后继 。
在各种查找方法中，平均查找长度与结点个数 n无关的查找方法是 散列查找法 。
在分块索引查找方法中，首先查找 索引表 ，然后查找相应的 块表 。
一个无序序列可以通过构造一棵 二叉排序 树而变成一个有序序列，构造树的过程即为对无序序列
进行排序的过程。
36. 37.
具有10个顶点的无向图，边的总数最多为 __45__。
已知图G的邻接表如图所示，其从顶点 v1出发的深度优先搜索序列为 _v1v2v3v6v5v4_，其从
顶点v1出发的广度优先搜索序 列为 _v1v2v5v4v3v6_。
38.
索引是为了加快检索速度而引进的一种数据结构。
个索引隶属于某个数据记录集， 它由若干索引项组成，索引项的结构为 键字和关键字对应记录的地址 。
一
关
39. Prim算法生成一个最小生成树每一步选择都要满足 边的总数不超过n-1 ，
，选中的边加入树中不产生回路
三项原则。
棵
当前选择的边的权值是候选边中最小的
40.
在一棵m阶B树中，除根结点外，每个结点最多有 m 棵子树，最少有 m/2
子树。 三、判断题。
1?在决定选取何种存储结构时，一般不考虑各结点的值如何。 2.
（V）
抽象数据类型（ADT）包括定义和实现ADT的逻辑特性，不必考虑如何在 计算
两方面，其中定义是独立于实现的，定义仅给出一个 机中实现。（V ）
3. 4.
抽象数据类型与计算机内部表示和实现无关。 （V ）
式好。
5.
顺序存储方式插入和删除时效率太低，因此它不如链式存储方（X ）
线性表采用链式存储结构时，结点和结点内部的存储空
间可以是不连续的。
6. 7. 8. 9.
10?线性表就是顺序存储的表。（x ）
11 ?取线性表的第i个元素的时间同i的大小有关。（x ） 12?循环链表不是线性表。（x ）
（X ）
对任何数据结构链式存储结构一定优于顺序存储结构。 （X ）
顺序存储方式只能用于存储线性结构。 （X ）
集合与线性表的区别在于是否按关键字排序。 （X ）
线性表中每个元素都有一个直接前驱和一个直接后继。 （x ）
13?链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序表中效率高。 14?双向链表可随机访问任一结点。 15.
s->next = p->next; （x ）
16?队列是一种插入和删除操作分别在表的两端进行的线性表，是一种先进后出的结构。 17.串是一种特殊的线性表，其特殊性体现在可以顺序存储。 18?长度为1的串等价于一个字符型常量。（x ） 19.空串和空白串是相同的。（x）
20?数组元素的下标值越大，存取时间越长。
（x ）
（V ）
（x ）
在单链表中，给定任一结点的地址 p,则可用下述语句将新结点 s插入结点p的后面：p->next = s;
（x ）
（x ）
21 ?用邻接矩阵法存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中结点个数有关，而与图的边数无
关。（V ）
22?一个广义表的表头总是一个广义表。
23?一个广义表的表尾总是一个广义表。
（x ） （V ）
24?广义表（（（a ）, b）, c ） 的表头是（（a ）, b） ，表尾是（c ） 。（ V ） 25?二叉树的后序遍历序列中，任意一个结点均处在其孩子结点的后面。 26?度为2的有序树是二叉树。（x ）
27.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 28 ?用一维数组存储二叉树时，总是以前序遍历顺序存储结点。
（V ）
（V ）
（x）
（x ）
29?若已知一棵二叉树的前序遍历序列和后序遍历序列，则可以恢复该二叉树。 30?在哈夫曼树中，权值最小的结点离根结点最近。 31 ?强连通图的各顶点间均可达。 （V ）
（x ）
32?对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到该图的每个顶点。 （x ）
33?在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定 排序。（V ） 34?在平衡二叉树中，任意结点左右子树的高度差（绝对值）不超过 1。（V ） 35?拓扑排序是按 AOE网中每个结点事件的最早发生时间对结点进行排序。 36 ?冒泡排序算法关键字比较的次数与记录的初始排列次序无关。
（x ）
（x ）
（x ）
37 ?对线性表进行折半查找时，要求线性表必须以链式方式存储，且结点按关键字有序排列。 38 ?散列法存储的思想是由关键字值决定数据的存储地址。
（V ）
（x ）
39?二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。 40?具有n个结点的二叉排序树有多种，其中树高最小的二叉排序树是最佳的。 41 ?直接选择排序算法在最好情况下的时间复杂度为
O（n）°（ x ）
（V）
大学数据结构期末考试试题(有答案)
