一. 绪论
1、程序是用计算机语言表述的算法。 （ ）
2、算法一定要有输入和输出。 （ ）
3、算法分析的目的旨在分析算法的效率以求改进算法。
（
）
4、数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。
（5、程序就是算法，但算法不一定是程序。 （ ） 6、程序越短，程序运行的时间就越少。
（
）
7. 数据元素是数据的最小单位。( )
8. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。 ( )
9. 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。 ( )
10. 数据的逻辑结构与数据元素本身的内容和形式无关。
( )
11. 算法和程序都应具有下面一些特征：有输入，有输出，确定性，有穷性，有效性。 12. 只有用面向对象的计算机语言才能描述数据结构算法。 ( )
13. 插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常被使用。
( )
14. 在使用后缀表示实现计算器类时用到一个栈的实例
, 它的作用是暂存运算器对象。15. 每种数据结构都应具备三种基本运算：插入、删除和搜索。 ( )
16. 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方 面。()
1、∨ 2、Χ 3 、∨ 4、Χ5、∨ 6、Χ7、Χ8、∨ 9、Χ10、∨ 11 、Χ12、
Χ 13 、Χ
14 、∨ 15 、Χ16、∨
）
1
( )
( )
二．线性表
1、线性表的逻辑顺序与物理顺序总是一致的。
( ) ( )
2、线性表的顺序存储表示优于链式存储表示。
3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。 4、二维数组是其数组元素为线性表的线性表。
( )
( )
5、假定有两个用单链有序表表示的集合，则这两个集合的交运算可得到一个新的集合单链表，
其长度小于等于参加运算的任意一个集合单链表的长度。 ( )
6、假定有两个用单链有序表表示的集合，则这两个集合的差运算可得到一个新的集合单链表，
其长度小于参加运算的任意一个集合单链表的长度。 ( )
7、线性表中的每个结点最多只有一个前驱和一个后继。
（ ）
（
）
8、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。
9、单链表从任何一个结点出发，都能访问到所有结点
（ ）
（
）
10、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。
11、用一组地址连续的存储单元存放的元素一定构成线性表。
12、非空线性表中任意一个数据元素都有且仅有一个直接后继元素。
（ ） （
）
13、若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。 14、若线性表采用顺序存储结构，每个数据元素占用 址为 15、则第 1 个数据元素的存储地址是
101 。（
4 个存储单元，第 ）
（ ）
12 个数据元素的存储地
16、若长度为
n 的线性表采用顺序存储结构， 删除表的第 i 个元素之前需要移动表中 n-i+1 个元
素。（
）
p 所指的那个结点的内容。 （
）
）
17、符号 p->next 出现在表达式中表示
18、要将指针 p 移到它所指的结点的下一个结点是执行语句
p=p->next 。（
2
19、线性链表中各个链结点之间的地址不一定要连续。
（ ）
20、线性表只能采用顺序存储结构或者链式存储结构。 （ ）
（
）
21、线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。
22、已知指针 P 指向链表 L 中的某结点，执行语句 P=P-〉 next 不会删除该链表中的结点。
（
）
p 所指的结点后面插入一个由
q 所指的结点的过程是依次执行语句：
23、在非空线性链表中由
q->next=p->next;p->next=q 。（ ）
24、非空双向循环链表中由 q 所指的结点后面插入一个由 p 指的结点的动作依次为： p->prior=q,
p->next=q->next,q->next=p,q->prior->next=p 。（ ）
25 、 删 除 非 空 链 式 存 储 结 构 的 堆 栈 ( 设 栈 顶 指 针 为 top) 的 一 个 元 素 的 过 程 是 依 次 执
行:p=top,top= p->next,free (p) 。 ( )
26. 在顺序表中，逻辑上相邻的元素在物理位置上不一定相邻。 27. 顺序表和一维数组一样，都可以按下标随机（或直接）访问。
( ) ( )
28. 线性表若采用链式存储表示时，其存储结点的地址可连续也可不连续。 29. 线性表若采用链式存储表示 , 在删除时不需要移动元素。 ( )
( )
30. 在对双向循环链表做删除一个结点操作时， 应先将被删除结点的前驱结点和后继结点链接好再执行删除结点操作。 ( )
1-5 Χ Χ ∨∨∨
6-10 ΧΧΧΧ∨ 11-15 ∨ΧΧΧ∨
16-20 Χ Χ ∨∨∨
21-25 ∨∨∨∨∨
3
26-30 Χ ∨∨∨∨
三．栈和队列
１、栈和队列逻辑上都是线性表。 （ ）
２、堆栈在数据中的存储原则是先进先出。 （ ）
3、队列在数据中的存储原则是后进先出。 （ ） （
4、堆栈、队列和数组的逻辑结构都是线性表结构。 ）
5、若某堆栈的输入序列为 1,2,3,4 ，则 4,3,1,2 不可能是堆栈的输出序列之一。 （
（
）
）
6、不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。
7、在链队列中，即使不设置尾指针也能进行入队操作。 8、采用循环链表作为存储结构的队列就是循环队列。 9、堆栈是一种插入和删除操作在表的一端进行的线性表。
（ （
（
） ）
）
10、队列是一种可以在表头和表尾都能进行插入和删除操作的线性表。
（ ）
(
11. 每次从队列中取出的是具有最高优先权的元素 , 这种队列就是优先级队列。 )
12. 链式栈与顺序栈相比 , 一个明显的优点是通常不会出现栈满的情况。
, 队头指针指向队头元素的后一个位置。
( ) ( ) )
13. 在一个顺序存储的循环队列中 14. 栈和队列都是顺序存取的线性表
, 但它们对存取位置的限制不同。 (
15. 在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 16. 若让元素 1,2,3 依次进栈，则出栈次序 1,3,2 是不可能出现的情况。 ( )
( )
?17. 在用单链表表示的链式队列 件为 Q->front == Q->rear
Q中，队头指针为 Q->front ，队尾指针为 Q->rear ，则队空条
。 ( )
1-5 ∨ΧΧ∨∨
6-10 ∨∨ Χ∨Χ
4
11-15 ∨∨ Χ ∨∨
16-17 Χ Χ
递归
18. 递归定义的数据结构通常用递归算法来实现对它的操作。 19. 递归的算法简单、易懂、容易编写，而且执行效率也高。 20. 递归调用算法与相同功能的非递归算法相比，
( ) ( )
主要问题在于重复计算太多， 而且调用本身需
要分配额外的空间和传递数据和控制，所以时间与空间开销通常都比较大。 （ ）
21. 递归方法和递推方法本质上是一回事， 例如求 n! 时既可用递推的方法， 也可用递归的方法。
( )
22. 将 f = 1 + 1/2 + 1/3+ 递归结束条件为
f (1) = 1
, + 1/n 转化为递归函数时，递归部分为 。（
）
f (n) = f (n-1) + 1/n ，
18、∨ 19 、 Χ四．串
20、 ∨ 21 、X 22 、∨
1、确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。
（ ） （
）
2、如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。
3、一个任意串是其自身的子串。
（ ）
1、∨ 2、Χ3、∨
五．数组和广义表
1、多维数组是向量的推广。 （
）
2、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。 （
（
（
） ）
3、除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。 4、稀疏矩阵中 0 元素的分布有规律，因此可以采用三元组方法进行压缩存储。
5
5. 如果采用如下方式定义一维字符数组：
const int maxSize = 30; char a[maxSize];
则这种数组在程序执行过程中不能扩充。
7. 数组是一种静态的存储空间分配，就是说，在程序设计时必须预先定义数组的数据类型和存储空间大小，由编译程序在编译时进行分配。
8. 多维数组是一种复杂的数据结构，数组元素之间的关系既不是线性的也不是树形的。 9. 使用三元组表示稀疏矩阵中的非零元素能节省存储空间。 10. 用字符数组存储长度为 n 的字符串，数组长度至少为n+1。 1-5 ΧΧΧΧ∨
6-10 Χ Χ ∨∨∨
11、一个广义表的深度是指该广义表展开后所含括号的层数。 （）
12. 一个广义表的表头总是一个广义表。( )
13. 一个广义表的表尾总是一个表。( )
14. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的长度为 3，深度为 4。 ( )
15. 一个广义表 ( (a), ( (b), c), ( ( (d) ) ) ) 的表尾是（ ( (b), c), ( ( (d) ) ) ）。( 129 )
11、∨ 12 、 Χ
13 、∨
14 、∨
15 、∨
六．树
1、一般树和二叉树的结点数目都可以为 0。 （ ）
2、在只有度为 0 和度为 k 的结点的 k 叉树中， 设度为 0 的结点有 n0 个，度为 k 的结点有 nk 个，则有 n0=nk+1 。（
）
3、折半搜索只适用与有序表，包括有序的顺序表和有序的链表。
（ ）
6
4、哈夫曼树一定是满二叉树。
（ ）
5、给定一组权值，可以唯一构造出一棵哈夫曼树。 （ ）
6、深度为 h 的非空二叉树的第
i 层最多有 2i-1 个结点。（
）
7、满二叉树也是完全二叉树。 （ ）
8、已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。
（
）
9、非空二叉排序树的任意一棵子树也是二叉排序树。
（ ）
10、对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。
（ ）
11、设与一棵树 T 所对应的二叉树为 BT，则与 T 中的叶子结点所对应的 BT 中的结点也一定是叶子结点。（ ）
12、哈夫曼树一定是完全二叉树。
（
）
13、由一棵二叉树的前序序列和后序序列可以唯一确定它。
（
） 14、在完全二叉树中 , 若某结点元左孩子 , 则它必是叶结点。 （ ）
15、树的带权路径长度最小的二叉树中必定没有度为
1 的结点。（
）
16、二叉树可以用 0≤度≤ 2 的有序树来表示。 （
）
17、一组权值，可以唯一构造出一棵哈夫曼树。
(
)
18、将一棵树转换成二叉树后，根结点没有左子树；
（ ）
19、用树的前序遍历和中序遍历可以导出树的后序遍历； （ ）
20. 二叉树是一棵无序树。 ( )
21. 在一棵二叉树中， 假定每个结点只有左子女， 没有右子女， 对它分别进行前序遍历和后序遍历，则具有相同的结果。 ( )
22. 在一棵二叉树中， 假定每个结点只有左子女， 没有右子女， 对它分别进行中序遍历和后序遍历，则具有相同的结果。 ( )
7
23. 在一棵二叉树中， 假定每个结点只有左子女， 没有右子女， 对它分别进行前序遍历和中根遍历，则具有相同的结果。 ( )
24. 在一棵二叉树中， 假定每个结点只有左子女， 没有右子女， 对它分别进行前序遍历和按层遍历，则具有相同的结果。 ( )
25. 在树的存储中， 若使每个结点带有指向双亲结点的指针， 这为在算法中寻找双亲结点带来方便。( )
26. 对于一棵具有 n 个结点，其高度为
h 的二叉树，进行任一种次序遍历的时间复杂度为 O(n) 。
( )
27. 对于一棵具有 n 个结点， 其高度为 h 的任何二叉树， 进行任一种次序遍历的时间复杂度均为 O(h) 。 ( )
28. 对于一棵具有 n 个结点的任何二叉树， 进行前序、 中序或后序的任一种次序遍历的空间复杂
度为 O(log 2 n) 。 ( )
29. 在一棵具有 n 个结点的线索二叉树中， 每个结点的指针域可能指向子女结点， 也可能作为线
索，使之指向某一种遍历次序的前驱或后继结点，所有结点中作为线索使用的指针域共有 n 个。
( )
30. 线索二叉树中的每个结点通常包含有 5 个数据成员。 ( )
（
31. 已知一棵树的前序遍历和后序遍历序列能唯一地确定这棵树。 1-5 ∨Χ∨ΧΧ 6-10
Χ∨ Χ∨Χ
）
11-15 Χ Χ Χ ∨∨ 16-20 21-25 Χ ∨ Χ ∨∨ 31∨ 七．图
ΧΧΧ∨Χ
26-30 ∨ΧΧΧ∨
8
1、若图 G 的最小生成树不唯一，则
G 的边数一定多于 n-1 ，并且权值最小的边有多条（其中 n
为 G 的顶点数）。（）
2、带权连通图中某一顶点到图中另一定点的最短路径不一定唯一。 （ ）
3、在 n 个结点的无向图中 , 若边数等于 n-1, 则该图必是连通图。 （
）
4、若一个有向图的邻接矩阵中
, 对角线以下元素均为
0, 则该图的拓扑有序序列必定存在。 （）
5、对于有向图，顶点的度分为入度和出度，入度是以该顶点为终点的入边数目；出度是以该顶
点为起点的出边数目，该顶点的度等于其入度和出度之和。
（ ）
6、无向图的邻接矩阵是对称的有向图的邻接矩阵是不对称的。
（
）
7、具有 n 个顶点的连通图的生成树具有 n-1 条边（）
8. 用邻接矩阵存储一个图时，
在不考虑压缩存储的情况下， 所占用的存储空间大小只与图中的顶
点个数有关，而与图的边数无关。 ( )
9. 邻接表只能用于有向图的存储，邻接矩阵对于有向图和无向图的存储都适用。 ( )
10. 邻接矩阵适用于稠密图（边数接近于顶点数的平方）
，邻接表适用于稀疏图（边数远小于顶
点数的平方） 。 ( )
11. 存储无向图的邻接矩阵是对称的，因此可以只存储邻接矩阵的下（上）三角部分。 ( )
12. 强连通分量是有向图中的极大强连通子图。 ( )
13. 对任何用顶点表示活动的网络（ AOV网）进行拓扑排序的结果都是唯一的。 ( )
14. 有回路的有向图不能完成拓扑排序。
( )
15. 在 AOE网络中一定只有一条关键路径。 ( )
16. 用边表示活动的网络（ AOE网）的关键路径是指从源点到终点的路径长度最长的路径。 ( )17. 对于 AOE网络，加速任一关键活动就能使整个工程提前完成。 ()
18. 对于 AOE网络，任一关键活动延迟将导致整个工程延迟完成。
( )
9
19. 在 AOE网络中， 可能同时存在几条关键路径，
称所有关键路径都需通过的有向边为桥。 如果
加速这样的桥上的关键活动就能使整个工程提前完成。
( )
20. 对一个连通图进行一次深度优先搜索可以遍访图中的所有顶点。 ( )
21. 图中各个顶点的编号是人为的，不是它本身固有的，因此可以根据需要进行改变。 ( )
22. 如果无向图中每个顶点的度都大于等于2，则该图中必有回路。 ( ) 23. 如果有向图中各个顶点的度都大于2，则该图中必有回路。 ()
24. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。 25. 图的广度优先搜索算法通常采用非递归算法求解。
( )
( )
26. 对一个有向图进行拓扑排序， 一定可以将图的所有顶点按其关键码大小排列到一个拓扑有序的序列中。 ( )
1、∨ 2 、 ∨ 3 、 Χ∨ 13 、Χ 14
4 、∨5 、∨ 6、Χ 7 、∨ 8 、∨9、Χ10
、∨ 17、Χ 18 、∨ 19 、∨ 20、∨
、∨ 11 21 、∨ 22
、∨ 12 、 、∨ 23 、
、∨ 15、Χ 16
Χ 24 、∨ 25 、∨ 26 、 Χ八．查找
1、散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。
（ ）
2、折半查找方法可以用于按值有序的线性链表的查找。
（ ）
3、哈希的查找无需进行关键字的比较。
（）
4、一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，
以尽可能减少冲突。
（
）
5、在索引顺序表上实现分块查找，在等概率查找情况下，其平均查找长度不与表的个数有关，
而与每一块中的元素个数有关。 （ ）
6. 在顺序表中进行顺序搜索时，若各元素的搜索概率不等，则各元素应按照搜索概率的降序排
10
列存放，则可得到最小的平均搜索长度。
( )
7. 进行折半搜索的表必须是顺序存储的有序表。 8. 能够在链接存储的有序表上进行折半搜索，
( )
其时间复杂度与在顺序存储的有序表上相同。
( )
9. 折半搜索所对应的判定树，既是一棵二叉搜索树，又是一棵理想平衡二叉树。 10. 对于同一组关键码互不相同的记录，
( )
若生成二叉搜索树时插入记录的次序不同则得到不同形
态的二叉搜索树。 ( )
11. 对于同一组记录，生成二叉搜索树的形态与插入记录的次序无关。 12. 对于两棵具有相同记录集合而具有不同形态的二叉搜索树，
( )
按中序遍历得到的结点序列是相
同的。()
13. 在二叉搜索树中， 若各结点的搜索概率不等， 使得搜索概率越大的结点离树根越近， 则得到
的是最优二叉搜索树。 ( )
14. 在二叉搜索树中， 若各结点的搜索概率不等， 使得搜索概率越小的结点离树根越近， 则得到
的是最优二叉搜索树。 ( )
15. 装载因子是散列表的一个重要参数，它反映了散列表的装满程度。 ( )
16. 在用散列表存储关键码集合时，可以用双散列法寻找下一个空位置。在设计再散列函数时， 要求计算出的值与表的大小
m 互质。 ( )
17. 一棵 3 阶 B 树是平衡的 3 路搜索树，反之，一棵平衡的 18. 闭散列法通常比开散列法时间效率更高。
( )
3 路搜索树是 3 阶 B 树。 ( )
?19. 一棵 m 阶 B 树中每个结点最多有 m-1 个关键码，最少有 m/2 -1 个关键码。 ( )
20. 在索引顺序结构上实施分块搜索，在等概率情况下，其平均搜索长度不仅与子表个数有关， 而且与每一个子表中的对象个数有关。( )
21. 在索引顺序结构的搜索中，对索引表既可以采取顺序搜索，也可以采用折半搜索。( )
11
22. 在散列法中采取开散列（链地址）法来解决冲突时 , 其装载因子的取值一定在 (0,1) 之间。
( )
23. AVL 树（平衡二叉搜索树）的所有叶结点不一定在同一层次上，同样，平衡 m路搜索树的叶
结点也不一定在同一层次上。
( )
？ 24. 在一棵 B- 树中，所有叶结点都处在同一层上，所有叶结点中空指针数等于所有关键码的总数加 1。( )
？ 25. 向一棵 B- 树插入关键码的过程中，若最终引起树根结点的分裂，则新树比原树的高度减少1。( )
26. 从一棵 B- 树删除关键码的过程中， 若最终引起树根结点的合并， 则新树比原树的高度增加( )
27. 折半搜索只适用与有序表，包括有序的顺序表和有序的链表。 （ ）
1、∨ 2、Χ3、Χ4、∨ 5、Χ6 、∨ 7 、∨ 8 、Χ 9 、∨
10 、∨ 11 、Χ
∨ 13
、∨ 14 、Χ 15
、∨ 16 、∨ 17 、Χ
18
、Χ
19
、Χ
20 、∨∨22、Χ
23 、∨ 24 、∨ 25 、Χ
26 、Χ
27 、Χ
九．排序
1、删除二叉排序树中一个结点，再重新插入上去，一定能得到原来的二叉排序树。
（ ）2、快速排序是排序算法中最快的一种。
（ ）
3、直接选择排序是一种不稳定的排序方法。
（
）
4、对一个堆按层次遍历，不一定能得到一个有序序列。
（ ）
5、只有在初始数据为逆序时，冒泡排序所执行的比较次数最多。 （ ） 6、希尔排序在效率上较直接插入排序有较大的改进。但是不稳定的。 （ ）
7、在平均情况下，快速排序法最快，堆积排序法最节省空间。
（ ）
1。
、21 、12
12
8、快速排序法是一种稳定性排序法。
（ ）
9、序列初始为逆序时，冒泡排序法所进行的元素之间的比较次数最多。 10、给出不同的输入序列建造二叉排序树，一定得到不同的二叉排序树。
（ （
） ）
11、由于希尔排序的最后一趟与直接插入排序过程相同，因此前者一定比后者花费的时间多。
（
）
12、 101， 88， 46， 70， 34， 39， 45， 58， 66， 10）是堆；（ ）
13、排序是计算机程序设计中的一种重要操作，它的功能是将一个数据元素（或记录） 的任意序
列，重新排列成一个按关键字有序的序列。
（ ）
14. 当向一个最小堆插入一个具有最小值的元素时， 该元素需要逐层向上调整， 直到被调整到堆
顶位置为止。
15. 当从一个最小堆中删除一个元素时，
需要把堆尾元素填补到堆顶位置，
然后再按条件把它逐
层向下调整，直到调整到合适位置为止。
16. 对具有 n 个结点的堆进行插入一个元素运算的时间复杂度为
O(n) 。
17. 直接选择排序是一种稳定的排序方法。
18. 若将一批杂乱无章的数据按堆结构组织起来, 则堆中数据必然按从小到大的顺序线性排列。
19. 当输入序列已经基本有序时，起泡排序需要比较关键码的次数，比快速排序还要少。
20. 在任何情况下，快速排序需要进行关键码比较的次数都是 O(nlog 2n) 。
21. 若用 m 个初始归并段参加 k 路平衡归并排序，则归并趟数应为log 2m 。 22. 堆排序是一种稳定的排序算法。 23. 任何基于排序码比较的算法，
对 n 个数据对象进行排序时， 最坏情况下的时间复杂度都不会
大于 O(nlog 2n) 。
1-5 ΧΧΧ∨∨
13
6-10 ∨∨ Χ ∨∨
11-15 Χ ∨∨∨∨ 16-20 Χ∨Χ∨Χ
21-23 Χ Χ Χ
二、填空题：
一．绪论
1、《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和
______ 运算 ________ 。
2、数据结构算法中， 通常用时间复杂度和
_______ 空间复杂度 ___________ 两种方法衡量其效率。
3、一个算法一该具有 _有穷 _____, 确定 ______,___ 可行 _,__ 输入 ____和 __输出 __ 这五种特性。
4. 数据是 __信息 ______ 的载体，它能够被计算机程序识别、存储和加工处理。 5. 数据结构包括逻辑结构、 ___ 存储结构 _____ 和数据的运算三个方面。
6. 数据结构的逻辑结构包括线性结构和 7. 数据结构的存储结构包括顺序、
_非线性 _______ 结构两大类。
_链接 _____ 、索引和散列等四种。
8. 基本数据类型是计算机已经实现了的 ____ 数据结构 ____。
9. 抽象数据类型的特点是 _数据封装 _______ 、信息隐蔽、使用与实现分离。 10. 算法的一个特性是 __有穷性 ______ ，即算法必须执行有限步就结束。 1. 运算
2
空间复杂度
3
有穷性 确定性 可行性 输入 输出
4
信息 5
存储结构
6 非线性
7. 链接 8. 数据结构 9. 数据封装 10. 有穷性
二．线性表
1、若频繁地对线性表进行插入与删除操作，该线性表应采用
__链表 __________ 存储结构。
2、在非空线性表中除第一个元素外，
集合中每个数据元素只有一个 __直接前驱 _____；除最后一
14
个元素之外，集合中每个数据元素均只有一个
__ 直接后继 _______。
3、线性表中的每个结点最多有 ____1 个直接 ____ 前驱和 _____ 一个直接 _______ 后继。
4、 _循环 _____链表从任何一个结点出发，都能访问到所有结点。
5、链式存储结构中的结点包含 ______数据 ______ 域， _____ 指针 __________ 域。
6、在双向链表中， 每个结点含有两个指针域， 一个指向 _前驱 _____ 结点，另一个指向 __后继 ______
结点。
7 、 某 带 头 结 点 的 单 链 表 的 头 指 针
head ， 判 定 该 单 链 表 非 空 的 条 件
___head->next!=NULL___________ 。
8、在双向链表中， 每个结点含有两个指针域， 一个指向 _前驱 ______结点，另一个指向 _后继 ____ 结点。
9、已知指针 p 指向单链表中某个结点，则语句 结点 _。
p->next=p->next->next的作用 __删除 p 的后继
10、已知在结点个数大于 1 的单循环链表中，指针 p 指向某个结点，则下列程序段结束时， 指针
q 指向 *p 的 ___前驱 __________ 结点。
q=p;
while(q->next!=p)
q=q->next;
11 、 若 要 在 单 链 表 结 点 *P 后 插 入 一 结 点 *S ， 执 行 的 语 句 ___s->next=p->next
p->next=s____________ 。
12、线性表的链式存储结构地址空间可以 连续 ______ 。
__ 不连续 _______ ，而向量存储必须是地址空间 _____
13. 线性表是由 n（ n≥ 0）个 ____数据元素 _____ 组成的有限序列。
15
14. 链表是一种采用 链式 存储结构存储的线性表。
15. 在链表中进行插入和 删除 操作的效率比在顺序存储结构中进行相同操作的效率高。
16. 链表对于数据元素的插入和删除不需要移动结点，只需要改变相应结点的 _____ 指针 _____
的值。
17. 链接存储表示的结点存储空间一般在程序的运行过程中进行动态地分配 18. 单链表中逻辑上相邻的结点而在物理位置上
_不一定 ______相邻。
_______ 和释放。
19. 在单链表中 , 除了表头结点外 , 任意结点的存储位置由其直接 _前驱 ____ 结点的指针域的值所指示。
20. 在单链表设置表头结点的作用是插入和删除表中第一个元素时不必对 ___表头指针 _____ 进
行特殊处理。
21. 若设 L 是指向带表头的单链表 , 语句 L->link=L->link->link
的作用是 ___删除 _____单链
表中的第一个结点。
22. 在双向链表中 , 每个结点除了数据域外 , 还有两个指针域 , 它们分别指向 _____ 前驱结点和后继结点 ____________ 。
23. 线性表的链接存储只能通过 ___链接指针 _____顺序访问。
24. 链表与顺序表、索引表、散列表等都是数据逻辑结构的 ____ 存储 ______表示。
25. 设双向循环链表每个结点结构为 _____p->llink_____
。
(data,llink,rlink),
则结点 *p 的前驱结点的地址为
1、链表 2
6
、直接前驱， 直接后继 、前驱，后继
7
3、1 个直接， 1 个直接
、 head->next!=Null
4、循环 、前驱，后继
5、 重题
指针，数据 8
9、删除 p 的后继结点 10 、后继 12
11 、s->next=p->next;p->next=s 、不连续，连续 13. 数据元素 14.
16
链式（或链接） 15. 删除 16. 指针域 17. 分配
18. 结点
不一定 19. 前驱 20. 表头指针 24.
存储
21. 删除
25. p->llink
22. 前趋结点和后继
23. 链接指针
三．栈和队列
1、栈结构允许进行删除操作的一端为 2、在栈的顺序实现中，栈顶指针
___ 栈顶 __________ 。
top ，栈为空条件 ___top=-1___________ 。
3、对于单链表形式的队列， 其空队列的 F 指针和 R指针都等于 _____头结点的指针 _____________ 。
?4、若数组 s[0..n-1] 为两个栈 s1 和 s2 的共用存储空间，仅当 s[0..n-1] 全满时，各栈才不能
进行栈操作，则为这两个栈分配空间的最佳方案是： s1 和 s2 的栈顶指针的初值分别为
__s[0]s[n-1]_______ 。
5、允许在线性表的一端插入 , 另一端进行删除操作的线性表称为 _队列 ______。插入的一端为 __
队尾 ____, 删除的一端为 __队头 ____。
6、设数组 A[m] 为循环队列
Q的存储空间， font 为头指针， rear 为尾指针，判定 Q 为空队列的
。
条件 ____Q->font==Q->rear________________
7、对于顺序存储的队列，存储空间大小为 则队列中元素的个数为
n，头指针为 F，尾指针为 R。若在逻辑上看一个环，
__(_R-F)%n________ 。
8、已知循环队列的存储空间为数组
data[21] ，且头指针和尾指针分别为 8 和 3，则该队列的当
前长度 ____17______ 。
9. 栈是一种限定在表的一端进行插入和删除的线性表，又被称为
___ 先进后出 ________ 表。
10. 队列是一种限定在表的一端插入，在另一端删除的线性表，它又被称为 __ 先进先出 ______
表。
11. 向一个链式栈插入一个新结点时，
首先把栈顶指针的值赋给新结点的指针域，
然后把新结点
17
的存储位置赋给 __ ______ 。
12. 队列的删除操作在 _______ 进行。
13. 向一个顺序栈插入一个元素时，首先使 _____后移一个位置，然后把待插入元素写入到这个位置上。
14. 若 设 顺 序 栈 的 最 大 容 量 为 MaxSize ， top==-1 _____________ 。
表示栈空，则判断栈满的条件是 __
15. 当用长度为 MaxSize 的数组顺序存储一个栈时，若用 满的条件为 __top==0______ 。
top == MaxSize 表示栈空，则表示栈
16. 向一个循环队列中插入元素时， 元素。
17. 向一个栈顶指针为 top=p 操作。
需要首先移动 __队尾 ______ 指针，然后再向所指位置写入新
top 的链式栈中插入一个新结点 *p 时，应执行 __p->link=top ______ 和
18. 在一个链式队列中，若队头指针与队尾指针的值相同，则表示该队列至多有 __1______ 个结
点。
19. 在一个链式队列中， 若队头指针与队尾指针的值相同， 则表示该队列至多有 ________ 个结点。
1、栈顶 2、 top==-1 3、 头节点的指针 4 、 s[0] ， s[n-1] 8、 17
5、队列，队尾队头 6、 Q->font=Q->rear 7、 (R-F)%n
10. 先进先出
9. 后出先进 11. 栈顶指针 12. 队头（或队首）
13. 栈顶指针 14. top==MaxSize-1 18. 1 19.
一
15. top == 0 16. 队尾 17.
p->link=top
20. 如果一个对象部分地包含自己，或自己定义自己，则称这个对象是 21. 如果一个过程直接或间接地调用自己，则称这个过程是一个
______ 递归 ___的对象。
____ 递归 ____ 的过程。
18
22. 递归工作栈起到两个作用，其一是将递归调用时的实际参数和返回地址传递给下一层递归； 其二是保存本层的形式参数和___局部变量 ______ 。
23. 函数内部的局部变量是在进入函数过程后才分配存储空间，在函数过程执行结束后就 ____
释放 ____ 局部变量所占用的存储空间。
24. 迷宫问题是一个回溯控制的问题，最好使用 20. 递归21. 四．串
_____ 递归 _____ 的方法来解决。
释放24.
递归
递归22. 局部变量23.
1、一个串的任意个连续的字符组成的子序列称为该串的
__子串 ______，包含该子串的串称为 ___
主串 _____ 。
2、求串 T 在主串 S 中首次出现的位置的操作是
___Index(S,T,pos)_____________ 。
3、在初始为空的队列中插入元素
A,B,C,D 以后，紧接着作了两次删除操作，此时的队尾元素是
___D_______。
4、在长度为 n 的循环队列中，删除其节点为
x 的时间复杂度为 ___ O(n) ____________ 。
5、已知广义表 L 为空，其深度为 _____1______ 。 6. 若设串 S = “documentHash.doc
0”，则该字符串
S 的长度为 _____16____ 。
1 、子串，主串 2 、 Index(S,T,pos) 3 、 D 4 、 O(n) 5 、 1 6. 16
五．数组和广义表
1、已知一顺序存储的线性表，每个结点占用 结点的地址为 ___DA1+(i-1)*k___________
。
k 个单元，若第一个结点的地址为 DA1，则第 i 个
2、设一行优先顺序存储的数组
A[5][6] ， A[0][0] 的地址为 1100 ，且每个元素占 2 个存储单元，
则 A[2][3]
的地址为 __1130___________ 。
19
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[4][3][2] 的地址为 __1482_____ 。 /*1100+{(4*6+3)*7+2}*2*/
4、设二维数组 A[m][n] 按列优先存储，每个元素占 1 个存储单元， 元素 A00 的存储地址 loc(A 00 ) ，
ij 00
则 A 的存储地址 loc(A )=_loc(A )+j*_m+i__________________ 。
ij
6、稀疏矩阵一般采用 _三元组 _________方法进行压缩存储。
7、稀疏矩阵可用 _三元组 ________ 进行压缩存储，存储时需存储非零元的 列号 ____ 、 __值 ______。
__ 行号 ______ 、 ____
8、若矩阵中所有非零元素都集中在以主对角线为中心的带状区域中，区域外的值全为 为 _____ 三对角矩阵 _____。
0，则称
9、若一个 n 阶矩阵 A 中的元素满足： Aij =Aji (0<=I ,j<=n-1) 则称 A 为 ___对称 _________ 矩阵；
若主对角线上方 ( 或下方 ) 的所有元素均为零时，称该矩阵为 ___（上）下三角矩阵 ___________ 。
10、对于上三角形和下三角形矩阵，分别以按行存储和按列存储原则进行压缩存储到数组
M[k]
中 ， 若 矩 阵 中 非
0 元 素 为 Aij ， 则 k 对 应 为 __i*(i-1)/2+j-1(i>=j)____ 和
_j*(j-1)/2+i-1(i 个单元，则 A[3][2] 地址为 _____108_______ 。 /*{3*(3-1)/2+2-1}*2=8*/ 12. 一维数组所占用的空间是连续的。但数组元素不一定顺序存取，通常是按元素的 ____ 下标 _____存取的。 13. 在程序运行过程中不能扩充的数组是_静态 _________ 分配的数组。 这种数组在声明它时必须 20 指定它的大小。 14. 在程序运行过程中可以扩充的数组是 _____ 动态 _____ 分配的数组。 这种数组在声明它时需要使用数组指针。 ？15. 二维数组是一种非线性结构，其中的每一个数组元素最多有 _________ 个直接前驱（或直 接后继）。 16. 若设一个 n n 的矩阵 A 的开始存储地址 LOC(0, 0) 及元素所占存储单元数 d 已知，按行存 储时其任意一个矩阵元素 a[i][j]的存储地址为 _ LOC(0, 0)+ （ i*n+ j ）d________ 。 17. 对称矩阵的行数与列数 三角部分或下三角部分即可。 __ 相等 _______且以主对角线为对称轴， aij = aji ，因此只存储它的上 18. 将一个 n 阶对称矩阵的上三角部分或下三角部分压缩存放于一个一维数组中， 要存储 __n*(n+1)/2_______ 个矩阵元素。 则一维数组需 19. 将一个 n 阶对称矩阵 A的上三角部分按行压缩存放于一个一维数组 中 B中，A[0][0] 存放于 B[0] B的___ ， 则A[I][J] 在I≤J 时 将 存 放 于 数 组 ______ 位置。 20. 利用三元组表存放稀疏矩阵中的非零元素， 则在三元组表中每个三元组元素对应一个非零元 素的行号、列号和 ___ 值 ______。 1、 DA1+(i-1)*k 2 、 1100+（ 6*2+3 ）*2=1130 3、100+（ 19*6+6 ）*2=340 ，100+（ 9*6+ ,, ） *2=220 4、 1482 5、 loc （ a00 ） +(j*m+i)*1 6 、三元组 7 、三元组，行 号，列号，值 8、三对角矩阵 9、上（下）三角矩阵 10 、 i* （ i-1 ） /2+j-1 (i ≥ j) ， j*(j-1)/2+i-1 (i 11 、 108 12. 下标（或顺序号） 13. 静态 相等 18. n(n+1)/2 动态 15. 两个 16.LOC(0,0)+(i*n+j)*d 17. 值 19.2n-I-1)*I/2+J 20. 21 21、广义表（ A,(a,b),d,e,((i,j),k) ）, 则广义表的长度为 _____5______ ，深度为 _______3____ 。 22、已知广义表 A=((a,b,c),(d,e,f)), 23、已知广义表 ls =(a,(b,c,d),e), 则运算 head(head (tail 运用 head 和 tail 函数取出 ls （ A） )))=___ _ d _______。 中的原子 b 的运算是 head(head(tail(s))) _____ 。 24. 非空广义表的除第一个元素外其他元素组成的表称为广义表的 25. 广义表 A ( (a, b, c), (d, e, f ) ) ___ 表尾 _____ 。 的表尾为 __25. ( (d, e, f ) ) ______ 。 26. 广义表是一种递归的数据结构，子表结点则指示下一层广义表的 __ 表头结点 ______ 。 27. 广义表的深度定义为广义表括号的 21、 5， 3 22 、 d ____ 层数 ____。 23 、 head(head(tail(s))) 24. 表尾 25. ( (d, e, f ) ) 26. 表头结点 六．树 27. 层数 1、在树结构里， 有且仅有一个结点没有前驱， 称为根。 非根结点有且仅有一个 _____ 前驱 ______, 且存在一条从根到该结点的 _____路径 __________ 。 2、度数为 0 的结点， 即没有子树的结点叫作 ____叶子 ______ 结点或 __终端 _______ 结点。同一个 结点的儿子结点之间互称为 _____兄弟 ______ 结点。 3、假定一棵树的广义表为 A(B(e),C(F(h,i,j),g),D), 则该树的度为 _______3____ ，树的深度为 B，双分支结点个数为 ___1____ ，三分 ___4______ ，终端结点为 __ehijgD____ ，单分支结点为 支结点为 __A_F____， C结点的双亲结点是 __A____，孩子结点是 ___F,g___ 。 4、完全二叉树、满二叉树、线索二叉树和二叉排序树这四个名词术语中，与数据的存储结构有 关系的是 ___线索 __________ 。 5、有三个结点的二叉树，最多有 ____5____ 种形状。 22 6、高度为 k 的二叉树具有的结点数目，最少为 __k___, 最多为 __ 2k -1 ___。 /* 高度？深度？ */ 7、对任何一棵二叉树，若 n0，n1，n2 分别是度为 0，1，2 的结点的个数，则 n0=__ n2+1_____ 。 _50______ 。 8、在含 100 个结点的完全二叉树，叶子结点的个数为 9、将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫 10、若一棵满二叉树含有 121 个结点，则该树的深度为 ____7_____ 。 _排序 ____ 。 11、一个具有 767 个结点的完全二叉树，其叶子结点个数为 __384______ 。 12、深度为 90 的满二叉树，第 11 层有 __1024______ 个结点。 13、有 100 个结点的完全二叉树，深度为 ___7_____ 。 14、设一棵二叉树中度为 ?15、含有 3个 2度结点和 2 的结点 10 个，则该树的叶子个数为 4 个叶结点的二叉树可含 _____11___ 。 /*n0=n2+1*/ __________ 个 1 度结点。 16、一棵具有５层满二叉树中节点总数为 ___31________ 。 17、一棵含有 16 个结点的完全二叉树，对他按层编号，对于编号为 左右结点编号为 ___3___ 、 ___14___ 、 ___15____ 。 7 的结点，他的双亲结点及 18、深度为 k( 设根的层数为 1) 的完全二叉树至少有 _______ 个结点 , 至多有 _______ 个结点。 19、若要对某二叉排序树进行遍历， 保证输出所有结点的值序列按增序排列， 应对该二叉排序树 采用 __ 中序 ______ 遍历法。 20、在序列 (2,5,8,11,15,16,22,24,27,35,50) 要进行 _____4_________ 次元素之间的比较。 中采用折半查找 ( 二分查找 ) 方法查找元素 24 ，需 /*16 、 27、 22、 24*/ 21、设有 10 个值，构成哈夫曼树，则该哈夫曼树共有 ___19___ 个结点。 /*10 个值就是 10 个叶 子结点；没有 1 度的结点 */ 22、从树中一个结点到另一个结点之间的分支构成这两个结点之间的 _____ 路径 _______ 。 23. 对于一棵具有 n 个结点的树，该树中所有结点的度数之和为 _n-1_____ 。 /* 每一个结点对应 23 一个棍就是一度（除根节点外） */ 24. 一棵树的广义表表示为 __2______ 个。 a(b(c,d(e,f),g(h)),i(j,k(x,y))) ，结点 k 的所有祖先的结点数为 25. 一棵树的广义表表示为 假定树根结点的层数为 0。 a(b(c,d(e,f),g(h)),i(j,k(x,y))) ，结点 f 的层数为 _____3____ 。 26. 假定一棵三叉树（即度为 3 的树）的结点个数为 50 ，则它的最小高度为 __4______ 。假定树 根结点的深度为 0。 27. 在一棵高度为 3 的四叉树中，最多含有 ___255_____ 个结点，假定树根结点的高度为0。 28. 在一棵三叉树中，度为 3 的结点数有 2 个，度为 2 的结点数有 1 个，度为 1 的结点数为 2 个，那么度为 0 的结点数有 ____6____ 个。 29. 一棵高度为 5 的完全二叉树中，最多包含有 /*2*2*2*2*2*2-1*/ ____63____ 个结点。假定树根结点的高度为 0。 30. 假定一棵树的广义表表示为 A(B(C,D(E,F,G),H(I,J))) ，则该树的高度为 ___3_____ 。假定 树根结点的高度为 0。 31. 在一棵二叉树中， 假定双分支结点数为 5个，单分支结点数为 6个，则叶子结点数为 ____6____ 个。 /*n0=n2+n1*/ 32. 假定一棵二叉树的结点数为18，则它的最小高度为 ___3_____ 。假定树根结点的高度为0。 1、前驱，路径 2、叶子，终端，兄弟 6、 k ， 2k -1 12、 1024 3、3； 3； e,h,I,j,g ； C； A,F ； A ； F,g 4 、线索 9、排序 10、 7 17、 3， 14， 15 5、 5 11、 384 7、 n1+n2 8 、 、 50 31 13、 7 19、中序 14、11 15 、 1 （ 0 ） 16 20、 4 18 、 2k-1 ， 2k-1 21 、 19 22、路径 23. n-1 24. 2 25. 3 26. 4 27. 85 28. 6 29. 63 24 30. 3 31. 6 32. 4 七．图 1、对于一个图 G，若边集合 E（ G）为无向边的集合，则称该图为 ____ 无向图 ________ 。 2、对于一个图 G，若边集合 E（ G）为有向边的集合，则称该图为 _____ 有向图 _______ 。 3、对于有向图，顶点的度分为入度和出度，以该顶点为终点的边数目叫 __入度 ______；以该顶 点为起点的边数目叫 ___ 岀度 ______。 4、一个无向图采用邻接矩阵存储方法，其邻接矩阵一定是一个 ___对称矩阵 ___________ 。 5、有一个 n 个顶点的有向完全图的弧数____2n_________ 。 6、在无向图中，若从顶点 A 到顶点 B 存在 __ 路径 _______ ，则称 A 与 B 之间是连通的。 7、在一个无向图中，所有顶点的度数之和等于所有边数的 _______2____ 倍。 8、一个连通图的生成树是该图的 _____ 极小 ______连通子图。 若这个连通图有 n 个顶点 , 则它的 生成树有 ___ n* （ n-1 ） ______条边。 9、无向图的邻接矩阵是一个 _______ 对称 ______矩阵。 10、如果从一无向图的任意顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是 _____连通的 _______ 。 11、若采用邻接表的存储结构，则图的广度优先搜索类似于二叉树的 _____ 层次 _______ 遍历。 12、若图的邻接矩阵是对称矩阵，则该图一定是 _______ 无向图 _________ 。 13、从如图所示的临接矩阵可以看出， 该图共有 __3____ 个顶点。如果是有向图， 该图共有 __4____ 条弧；如果是无向图，则共有 _____3___条边。 A B 14、如果从一个顶点出发又回到该顶点，则此路径叫做 _环 / 回路 __________ 。 0 1 B 0 0 15、一个具有个 n 顶点的无向图中，要连通全部顶点至少需要 __n-1______ 条边。 0 1 16. n (n ﹥ 0) 个顶点的连通无向图各顶点的度之和最少为 _2（ _n-1 ） _______ 。 25 C 1 A 1 B0 C 17. 用邻接矩阵存储图，占用的存储空间与图中的 ___ 顶点 _____ 数有关。 0 1 2 3 0 1 0 2 0 3 1 3 18. 设图 G = (V, E) 则从顶点 V0 开始的图 ，V={V ,V ,V , V },E={(V , V ), (V , V ), (V , V ), (V , V )} ， G的不同深度优先序列有 ____4____ 种。 19. 设图 G = (V, E) ， V = {1, 2, 3, 4}, E = {<1, 2>, <1, 3>, <2, 4>, <3, 4>} __2______ 种。 ，从顶点 1 出发，对图 G 进行广度优先搜索的序列有 20. n (n ﹥ 0) 个顶点的无向图中顶点的度的最大值为 21. 在重连通图中每个顶点的度至少为________ 。 __n-1_______ 。 22. n 个顶点的连通无向图的生成树含有 ___n-1______ 条边。 23. 11 个顶点的连通网络 小生成树各边的权值之和为 N 有 10 条边，其中权值为 1, 2, 3, 4, 5 的边各 2 条，则网络 N 的最 ____30_____ 。 /*2* （ 1+2+3+4+5） =30*/ 24. 在使用 Kruskal 算法构造连通网络的最小生成树时， 只有当一条候选边的两个端点不在同一个 ___ 连通分量 _____ 上，才会被加入到生成树中。 25. 一般来说 , 深度优先生成树的高度比广度优先生成树的高度要____ 高 ____。 26. 求解带权连通图最小生成树的Prim 算法使用图的 ___ 邻接矩阵 _____ 作为存储结构。 _ O(n 2 ) _______ 。 7 、 2 ？27. 设图的顶点数为 n，则求解最短路径的 Dijkstra 算法的时间复杂度为 1、无向图 8、极小（ 2、有向图 最小）， n-1 3、入度，出度 4、对称矩阵 5、 n(n-1) 6 、路径 9、对称 10、连通 11、层次 12、无向图 13、 3， 4， 3 14、环/ 回路 15、 n-1 16. 2(n-1) 17. 顶点 18. 4 19. 2 20. n-1 21. 2 22. n-1 23. 30 八．查找 24. 连通分量 25. 高 26. 邻接矩阵 27. O(n 2 ) 1、若待散列的序列为 (18,25,63,50,42,32,9) ，散列函数为 H(key)=key MOD 9 ，与 18 发生冲突 的元素有 ________2_____ 个。 /*18 、 63*/ 26 2、关键字自身作为哈希函数，即 H（ k）=k，也可自身加上一个常数作为哈希函数，即 H(k)=k+C 这种构造哈希函数的方式叫 ___直接定址法 _________ 。 3、折半搜索只适合用于 _____ 有序表 ______________ 。 4、结点关键字转换为该结点存储单元地址的函数 表_____ 。 H 称为 _____ 哈希函数 ________或叫 _____散列 5、在索引查找中，首先查找 ___索引表 _____，然后查找相应的 __子表 _______ ，整个索引查找的 平均查找长度等于查找索引表的平均长度与查找相应子表的平均查找长度的 ___ 和 ____。 6. 链表只适用于 顺序 查找。 7. 在一棵高度为 8. 在一棵高度为 为 0。 h 的理想平衡二叉树中， 最少含有 __2h______ 个结点。假定树根结点的高度为0。 h 的理想平衡二叉树中，最多含有 _2h+1 _-1______ 个结点。假定树根结点的高度 9. 若将一棵树 A(B(C,D,E),F(G(H),I)) 按照左子女 - 右兄弟表示法转换为二叉树， 该二叉树中度 为 2 的结点的个数为 ____2____ 个。 10. 将一棵树按照左子女 - 右兄弟表示法转换成对应的二叉树，则该二叉树中树根结点肯定没有 __右 ______子女。 11. 以顺序搜索方法从长度为 O(n) ______。 n 的顺序表或单链表中搜索一个元素的渐进时间复杂度为 __ ？12. 对长度为 n 的搜索表进行搜索时，假定搜索第 i 个元素的概率为 pi , 搜索长度（即在搜索 过程中依次同有关元素比较的总次数） 为 ci ，则在搜索成功情况下的平均搜索长度的计算公式为 n ___ i 1 pi ci ____。 13. 假定一个顺序表的长度为40，并假定顺序搜索每个元素的概率都相同，则在搜索成功情况 下的平均搜索长度为 __20.5______ 。 /* 等差数列求和 Sn=na1+n(n-1)d/2*/ 27 14. 从有序表 (12,18,30,43,56,78,82,95) 中折半搜索元素 56 时，其搜索长度为 ___3_____ 。 ？ 15. 假定对长度 n=50 的有序表进行折半搜索，则对应的判定树中最底下一层的结点数为 ______ 个。 16. 从一棵二叉搜索树中搜索一个元素时， 若给定值大于根结点的值， 则需要向 _右子树 _______ 继续搜索。 17. 向一棵二叉搜索树中插入一个元素时， 若元素的值小于根结点的值， 则应把它插入到根结点 的 _____ 左子树 ___ 上。 18. 根据 n 个元素建立一棵二叉搜索树的渐进时间复杂度大致为 ____ O(nlog2n) _________ 。 19. 在一棵 AVL 树中，每个结点的左子树高度与右子树高度之差的绝对值不超过 20. 根据一组记录 (56,42,50,64,48) 的结点时需要进行旋转调整。 __1______ 。 依次插入结点生成一棵 AVL 树时，当插入到值为 ___50____ 21. 根据一组记录 (56,74,63,64,48) 依次插入结点生成一棵 AVL 树时，当插入到值为 63 的结点 时需要进行 ______ 先右后左双翻转 __________ 调整。 22. 根据一组记录 (56,42,38,64,48) 依次插入结点生成一棵 AVL 树时，当插入到值为 38 的结点 时需要进行 ___向右单翻转 _________ 调整。 23. 根据一组记录 (56,42,73,50,64,48,22) 依次插入结点生成一棵 AVL 树时，当插入到值为 ___48____ 的结点时才出现不平衡，需要进行旋转调整。 24. 在索引表中， 若一个索引项对应数据对象表中的一个表项， 则称此索引为稠密索引， 若对应 数据对象表中的若干表项，则称此索引为 ___ 稀疏 _____ 索引。 n 25. 假定对长度 n = 100 的线性表进行索引顺序搜索，并假定每个子表的长度均为 索引顺序搜索的时间复杂度为_0(10)______ 。 ，则进行 26. 假定对长度 n=100 的线性表进行索引顺序搜索， 并假定每个子表的长度均为 n ，则进行索 28 引顺序搜索的平均搜索长度为 ________ 。 /*5.5+5.5=11*/ 27. 若对长度 n=10000 的线性表进行二级索引存储，每级索引表中的索引项是下一级 的索引，则一级索引表的长度为 ____500____ 。 20 个表项 29. 假定要对长度 n=100 的线性表进行散列存储，并采用开散列法处理冲突，则对于长度 的散列表，每个散列地址的同义词子表（单链表）的长度平均为 30. 在线性表的散列存储中，装载因子 又称为装载系数，若用 ___5_____ 。 /*100/20*/ m = 20 m表示散列表的长度， n 表示 待散列存储的元素的个数，则 等于 _____n/m___ 。 31. 对于包含 n 个关键码的 m阶 B 树，其最小高度为 ____ log m(n+1) ________ 。 32. 已知一棵 3 阶B树中含有 50 个关键码，则该树的最小高度为 33. 已知一棵 3 阶B树中含有 50 个关键码，则该树的最大高度为 34. 在一棵 m阶 B 树上，每个非根结点的关键码数最少为 35. 在一棵 m阶 B 树上，每个非根结点的子树最少为 ___4_____ 。 ___5_____ 。 ________ 个。 ___ m/2 _____棵。 36. 在一棵 m阶 B 树上，每个非根结点的关键码数最多为 ________ 个。 37. 在对 m阶 B 树插入元素的过程中， 等于 ________ 个，则必须把它分裂为 每向一个结点插入一个关键码后， 2 个结点。 若该结点的关键码个数 38. 在从 m阶 B 树删除关键码的过程中， 当从一个结点中删除掉一个关键码后， 所含关键码个数 等于 m/2 -2 个，并且它的左、右兄弟结点中的关键码个数均等于 ________ ，则必须进行结点合 并。 39. 在一棵具有 n 个结点的 AVL 树上进行插入或删除元素的渐进时间复杂度大致为 1、 2 2 、直接定址法 6. 顺序 n _________ 。 3 7. 2h 、有序表4 、哈希函数，散列函数 9. 2 5 、索引表，子 11. O(n) 表，和 8. 2h+1-1 10. 右 12. i 1 pi ci 13. 20.5 14. 3 15. 19 16. 右 子 树 29 17. 左子树 18. O(nlog2n) 19. 1 20. 50 21. 先 右 后 左 双旋转 22. 右单旋转 23. 64 24. 稀疏 30. n/m 25. O( 31. n) 26. 11 32. 4 27. 500 33. 28. 5 25 34. m/2 -1 29. 5 35. m/2 log (n+1) m 36. m-1 九．排序 37. m 38. m/2 -1 39. O(log 2 n) 1、在进行直接插入排序时 , 其数据比较次数与数据的初始排列 ____ 有 ____关；而在进行直接选 择排序时，其数据比较次数与数据的初始排列 ______ 无 ____关。 2、每一趟排序时从排好序的元素中挑出一个值最小的元素与这些未排小序的元素的第一个元素 ______选择 _______ 排序法。 交换位置，这种排序方法成为 3、给定序列 {100, 86, 48, 73, 35, 39, 42, 57, 66, 21}, 大顶 _____ 堆。 按堆结构的定义 , 则它一定 ____ 4、从未排序序列中选择一个元素，该元素将当前参加排序的那些元素分成前后两个部分，前一 部分中所有元素都小于等于所选元素， 后一部分中所有元素都大于或等于所选元素， 而此时所选 元素处在排序的最终位置。这种排序法称为 ______ 快速 _______排序法。 5. 在一个堆的顺序存储中，若一个元素的下标为 __2i+1____ 。 i(0 ≤ i ≤ n-1) ，则它的左子女元素的下标为 6. 在一个堆的顺序存储中，若一个元素的下标为 i(0 ≤ i ≤ n-1) ，则它的右子女元素的下标为 __2i+2______ 。 7. 在一个最小堆中，堆顶结点的值是所有结点中的 8. 在一个最大堆中，堆顶结点的值是所有结点中的 9. 第 i (i = 1, 2, ,, n __最小的 ______ 。 _最大的 _______ 。 -1) 趟从参加排序的序列中取出第 i 个元素，把它插入到由第 0 个至 30 第 i-1 个元素组成的有序表中适当的位置，此种排序方法叫做 _____ 直接插入 _____ 排序。 10. 第 i (i=0,1,...,n-2) 趟从参加排序的序列中第 i 个至第 n-1 个元素中挑选出一个最小元 素，把它交换到第 i 个位置，此种排序方法叫做 ____ 直接选择 _____ 排序。 11. 每次直接或通过基准元素间接比较两个元素， 方法叫做 ___交换 _______ 排序。 若出现逆序排列就交换它们的位置， 这种排序 12. 每次使两个相邻的有序表合并成一个有序表，这种排序方法叫做 ___ 二路归并 ______排序。 13. 在直接选择排序中，记录比较次数的时间复杂度为 14. 在直接选择排序中，记录移动次数的时间复杂度为 __ O(n 2) ______。 __________ 。 ？15. 在堆排序中，对 n 个记录建立初始堆需要调用 __________ 次调整算法。 16. 在堆排序中， 如果 n 个对象的初始堆已经建好， 用___n-1______ 次调整算法。 那么到排序结束， 还需要从堆顶结点出发调 17. 在堆排序中，对任意一个分支结点进行调整运算的时间复杂度为 18. 对 n 个数据对象进行堆排序，总的时间复杂度为 19. 给定一组数据对象的关键码为 {46,79,56,38,40,84} ____ O(nO(nlog ____ O(log 2n) ________ 。 n)) __________ 。 2 ，则利用堆排序方法建立的初始堆（最 大堆）为 _84,79,56,38,46,40______________ 。 20. 快速排序在平均情况下的时间复杂度为 21. 快速排序在最坏情况下的时间复杂度为 22. 快速排序在平均情况下的空间复杂度为 ___________ 。 ____________ 。 ____________ 。 ?23. 快速排序在最坏情况下的空间复杂度为 ___O(nlog 2n) _________ 。 24 给定一组数据对象的关键码为 {46 ， 79， 56， 38， 40 ， 84} ，对其进行一趟快速排序处理，得到的右子表中有 ___3_____ 个对象。 25. 在对 n 个数据对象的二路归并排序中，每趟归并的时间复杂度为 O(n) ____________ 。 31 26. 在对 n 个数据对象进行的二路归并排序中，整个归并过程的时间复杂度为 __ O(nlog 2 n) _________ 。 27. 在索引表中，每个索引项至少包含有 __ 关键码 ________ 域和地址域这两项。 28. 假定一个线性表为 {12, 23, 74, 55, 63, 40, 82, 36} ，若按 key%3 条件进行划分，使得 同一余数的元素成为一个子表，则包含 29. 假 定 一 74 的子表长度为 ___3_____ 。 个 线 性 表 为 ( ”abcd”, ”baabd”, ”bcef ”, ”cfg ”, ”ahij ”, ”bkwte”, ”ccdt ”, ”aayb”) ， 若按照字 符串的第一个字母进行划分， 使得同一个字母被划分在一个子表中， 则得到的以 a 为第一个字母 的子表长度为 _____3___ 。 1、有，无 大值 9. 2、选择3 、大根堆 4 、快速 直接选择 11. 交换 5. 2i+1 6. 2i+2 12. 7. 最小值 2 8. 最 直接插入 10. 二路归并 3. O(n ) 14. O(n) 20. 15. n/2 O(nlog 2n) 16. 21. O(n n-1 17. O(log 2n) 18. n) O(nlog 2n) 19. 84 ，79，56，38 ，40，46 23. O(n) 24. 3 25. O(n) 2 ) 22. O(log 2 26. O(nlog 2 n) 27. 关键码 28. 2 29. 3 三、选择题： 一．绪论 （ ） 1. 数据结构通常是研究数据的 及它们之间的联系。 A 存储和逻辑结构 B 存储和抽象 C理想和抽象 （ ） 2. 计算机识别、存储和加工处理的对象被统称为 D理想与逻辑 _________ A．数据 C. 数据结构 B. D. 数据元素 数据类型 32 （ ） 3．若需要利用形参直接访问实参，则应把形参变量说明为 ____ 参数。 A. 指针 B. 引用 C.值 D. 变量 （ ） 4. 算法指的是 ________ A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 （ ） 5. 若需要利用形参直接访问实参，则应把形参变量说明为 ________ 参数。 A指针 B 引用 C值 D 常量 （ ） 6．下面算法的时间复杂度为＿＿。 int f （ int n ） { if （ n＝＝ 0） return 1 ； else return n＊ f （ n-1 ）； } A． O(1) B ． O(n) C．O(n2) D ． O(n!) （ ）7. 数据结构是一门研究非数值计算的程序设计问题中计算机的 （ ① ）以及它们之间 的（ ② ）和运算的学科 ① Ａ、操作对象 Ｂ、计算方法 Ｃ、逻辑存储 Ｄ、数据映象 ②Ａ、结构 Ｂ、关系 Ｃ、运算 Ｄ、算法 （ ）8. 数据结构被形式地定义为 (K ，R)，其中 K 是（ ① ）的有限集合， R 是 K 上（ ②的有限集合 ①Ａ、算法 Ｂ、数据元素 Ｃ、数据操作 Ｄ、逻辑结韵 33 ） ②Ａ、操作 Ｂ、映象 Ｃ、存储 Ｄ、关系 （ ） 9. 在数据结构中，从逻辑上可以把数据结构分为 ________ Ａ、动态结构和静态结构 Ｂ、紧凑结构和非紧凑结构 Ｃ、线性结构和非线性结构 Ｄ、内部结构和外部结构 （ ）10. 线性表的顺序存储结构是一种 _________ 的存储结构， 线性表的链式存储结构是一种 ________ 的存储结构 Ａ、随机存取 Ｂ、顺序存取 Ｃ、索引存取 Ｄ、 HASH存取 （ ） 11. 算法分析的目的是（ ① ），算法分析的两个主要方面是（ ② ） ①Ａ、找出数据结构的合理性 Ｃ、分析算法的效率以求改进 Ｂ、研究算法中的输入和输出的关系Ｄ、分析算法的易懂性和文档性 ②Ａ、空间复杂性和时间复杂性 Ｃ、可读性和文档性 Ｂ、正确性和简明性 Ｄ、数据复杂性和程序复杂性 （ ） 12. 计算机算法指的是（ ① ），它必具备输入、输出和（ ② ）等五个特性 ①Ａ、计算方法 Ｂ、排序方法 Ｃ、解决莱一问题的有限运算序列 Ｄ、调度方法 ②Ａ、可执行性、可移植性和可扩充性 Ｃ、确定性、有穷性和稳定性 Ｂ、可执行性、确定性和有穷性 Ｄ、易谩性、稳定性和安全性 （ ） 13. 对于两个函数，若函数名相同，但只是 ____________ 不同则不是重载函数。 A、 参数类型 B 、 参数个数 C、 函数类型 D 、函数变量 （ ） 14. 若需要利用形参直接访问实参，则应把形参变量说明为 ________ 参数 34 A、 指针 B 、 引用 C、 值 D、函数 （ ） 15. 下面程序段的时间复杂度为 ____________ 。 for(int i=0; i A、 O(m2) B 、 O(n2) C、 O(m*n) D 、 O(m+n) （ ） 16. 执行下面程序段时，执行 S 语句的次数为 ____________ 。for(int i=1; i<=n; i++) for(int j=1; j<=i; j++) S; A、 n2 B 、 n2/2 C、 n(n+1) D 、 n(n+1)/2 （ ） 17. 下面算法的时间复杂度为 ____________ 。 int f( unsigned int n ) { if ( n==0 || n==1 ) return 1; else return n*f(n-1); } A、 O(1) B 、 O(n) C、 O(n2) D 、 O(n!) 1-5AA A D A 6-B DA DA C BA 11-CA CB C A C 16-17D B 二．线性表 35 /*n*i*/ （ ） 1. 设单链表中结点的结构为 typedef struct node { file:// 链表结点定义 ElemType data ； file:// 数据 struct node * Link } ListNode ； ； file:// 结点后继指针 已知指针 p 所指结点不是尾结点， 若在 *p 之后插入结点 *s ，则应执行下列哪一个操作 ______。 A. s->link = p ； p->link = s ； B. s->link = p->link D. p->link = s ； p->link = s ； ； C. s->link = p->link ； p = s ； ； s->link = p （ ） 2. 设单链表中结点的结构为 typedef struct node { file:// 链表结点定义 ElemType data ； file:// 数据 struct node * Link ； file:// 结点后继指针 } ListNode ； 非空的循环单链表 first 的尾结点（由 p 所指向）满足： ______ A. p->link == NULL C. p->link == first ； ； B. p == NULL ； D. p == first ； （ ） 3. 在具有 n 个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是 ________ A． O（ 1） C.O(nlogn) B.O （ n） D.O(n2) （ ）4. 在长度为 n 的顺序存储的线性表中，删除第 i 个元素（ 1≤ i ≤ n）时，需要从前向后依 36 次前移 ____ 个元素。 A、 n-i C、 n-i-1 B D 、 n-i+1 、 i （ ）5．在一个单链表 HL 中，若要在指针 q 所指结点的后面插入一个由指针 p 所指向的结点， 则执行 ____ 。 A. q 一>next=p 一 >next ； p 一 >next=q ； C. q 一 >next=p 一 >next ；p 一 >next=q ； B. p 一>next=q 一 >next ； q=p； D. p 一 >next=q 一 >next ； q 一 >next=p ； （ ） 6. 线性表采用链式存储时，结点的存储地址 ________ A. 必须是不连续的 C. 必须是连续的 B. 连续与否均可 D. 和头结点的存储地址相连续 （ ） 7. 将长充为 n 的单链表链接在长度为 m的单链表之后的算法的时间复杂度为 ________ A.O（ 1） C.O（ m） B.O D.O （ n） （ m+n） （ ） 8. 设单链表中结点的结构为（ data, link ）。已知指针 q 所指结点是指针 p 所指结点的 直接前驱，若在 *q 与 *p 之间插入结点 *s ，则应执行下列哪一个操作 ________ A. s->link = p->link; p->link = s; C. p->link = s->link; s->link = p; B. p->link = s; s->link = q; D. q->link = s; s->link = p; （ ） 9. 线性链表不具有的特点是 ________ 。 A. 随机访问 B. 不必事先估计所需存储空间大小 所需空间与线性表长度成正比 C. 插入与删除时不必移动元素 D. （ ） 10. 线性表若采用链表存储结构时，要求内存中可用存储单元的地址 ________ Ａ、必须是连续的 Ｂ、部分地址必须是连续的 37 Ｃ、一定是不连续的 Ｄ、连续不连续都可以 （ ）11．在一个长度为 n 的顺序存储线性表中， 向第 i 个元素 (1 ≤ i ≤ n+1) 之前插入一个新元 素时，需要从后向前依次后移 个元素。 A、 n-i B D 、 n-i+1 C、 n-i-1 、 i （ ）12．在一个长度为 n 的顺序存储线性表中， 删除第 i 个元素 (1 ≤ i ≤ n+1) 时，需要从前向 后依次前移 _____个元素。 A、 n-i B 、 n-i+1 C、 n-i-1 （ D 、 i ）13. 在一个长度为 n 的线性表中顺序查找值为 x 的元素时，查找时的平均查找长度（即 x 同元素的平均比较次数，假定查找每个元素的概率都相等）为 _____ 。 A、 n B D 、 n/2 C、 (n+1)/2 、 (n-1)/2 （ ） 14．在一个单链表 HL 中，若要向表头插入一个由指针 p 指向的结点，则执行 _____ 。 A、 HL = p; p->next = HL; C 、 p->next = HL; p = HL; B、 p->next = HL; HL = p; D 、 p->next = HL->next; HL->next = p; （ ）15．在一个单链表 HL 中，若要在指针 q 所指的结点的后面插入一个由指针 p 所指的结点， 则执行 _____。 A、 q->next = p->next ; p->next = q; C B、 p->next = q->next; q = p; （ D 、 q->next = p->next; p->next = q; 、 p->next = q->next ; q->next = p; ） 16．在一个单链表 HL 中，若要删除由指针 q 所指向结点的后继结点，则执行 _____。 A、 p = q->next ; p->next = q->next; B 、 p = q->next ; q->next = p->next; 38 C、 p = q->next ; q->next = p; D 、 q->next = q->next->next; q->next = q 1-5B C B A D 6-10BC D A D 11-15B A D D D 16B 三．栈和队列 （ ） 1. 在堆栈中存取数据的原则是 。 A 先进先出 B 后进先出 C先进后出 D 随意进出 （ ） 2. 由两个栈共享一个向量空间的好处是 ______ 。 A 减少存取时间 , 降低下溢发生的机率 B 节省存储空间 , 降低上溢发生的机率 C减少存取时间 , 降低上溢发生的机率 D 节省存储空间 , 降低下溢发生的机率 （ ）3. 设长度为 n 的链队列用单循环链表表示， 若只设头指针， 则入队操作的时间复杂度为_______ 。 A. O(1) B. O(log2n) C. O(n) D. O(n2) （ ） 4．队和栈的主要区别是 ________ A. 逻辑结构不同 B. 存储结构不同 C. 所包含的运算个数不同 D. 限定插入和删除的位置不同 （ ） 5．链栈与顺序栈相比，比较明显的优点是 ________ A. 插入操作更加方便 B. 删除操作更加方便 C. 不会出现下溢的情况 D. 不会出现上溢的情况 （ ） 6. 假定一个顺序队列的队首和队尾指针分别为 f 和 r ，则判断队空的条件为 ____ 。 39 A、 f+1==r B 、 r+1==f C、 f==0 （ D 、 f==r ） 7．在一个顺序队列中，队首指针指向队首元素的 ____位置。 A. 前一个 B. D. 后一个 C. 当前 最后一个 （ ） 8. 由两个栈共享一个向量空间的好处是： ________ A. 减少存取时间，降低下溢发生的机率 B. 节省存储空间，降低上溢发生的机率 C. 减少存取时间，降低上溢发生的机率 D. 节省存储空间，降低下溢发生的机率 （ ） 9. 设数组 Data[m] 作为循环队列 SQ的存储空间， front 为队头指针， rear 为队尾指针， 则执行出队操作后其头指针 front 值为 ________ A. front=front+1 C. front=(front-1)%m B. front=(front+1)%(m-1) D. front=(front+1)%m （ ） 10. 链式栈与顺序栈相比，一个比较明显的优点是 ________ 。 A. 插入操作更加方便 C. 不会出现栈空的情况 B. D. 通常不会出现栈满的情况 删除操作更加方便 （ ） 11．若让元素 1,2,3 依次进栈，则出栈次序不可能出现 ________ 种情况。 A.3,2,1 C.3,1,2 B.2,1,3 D.1,3,2 （ ）12. 假定一个顺序队列的队首和队尾指针分别为 front 和 rear ，存放该队列的数组长度 为 N，则判断队空的条件为 ________ 。 A．（ front+1 ） % N == rear C D ． front == 0 B．（ rear+1 ） % N == front ． front == rear 40 （ ） 13．栈的插入和删除操作在＿＿＿进行． (Ａ) ．栈顶 ( Ｃ ) ．任意位置 ( ( Ｂ) ．栈底 Ｄ ). 指定位置 ?（ ） 14. 在一个顺序循环队列中，队首指针指向队首元素的 A. 后两个 B. D. ________ 位置。 后一个 C. 当前 前一个 （ ） 15. 在以下的叙述中，正确的是 __________ Ａ、线性表的线性存储结构优于链表存储结构 Ｃ、栈的操作方式是先进先出 Ｂ、二维数组是它的每个数据元素为一个线性表的线性表Ｄ、 队列的操作方式是先进后出 （ ） 16．栈的插入与删除操作在 _____ 进行。 A、栈顶 C、任意位置 （ B D 、栈底 、指定位置 ）17．当利用大小为 N 的一维数组顺序存储一个栈时， 假定用 top==N 表示栈空， 则向这个 栈插入一个元素时，首先应执行 _____语句修改 top 指针。 A、 top++ B 、 top-- C、 top=0 D 、 top （ ） 18．若让元素 1， 2， 3 依次进栈，则出栈次序不可能出现 _____ 种情况。 A、3，2，1 B 、2，1，3 C、3，1，2 （ D 、1，3，2 ） 19．在一个循环顺序队列中，队首指针指向队首元素的 _____ 位置。 A、前一个 B D 、后一个 C、当前 、后面 41 （ ） 20．当利用大小为 N 的一维数组顺序存储一个循环队列时，该队列的最大长度为 _____ 。 A、 N-2 C、N B D 、 N-1 、N+1 （ ） 21．从一个循环顺序队列删除元素时，首先需要 _____ 。 A、前移一位队首指针 B D 、后移一位队首指针 C、取出队首指针所指位置上的元素 、取出队尾指针所指位置上的元素 （ ）22 ．假定一个循环顺序队列的队首和队尾指针分别为 f 和 r ，则判断队空的条件是 _____ 。 A、 f+1==r B 、 r+1==f C、 f==0 （ D 、 f==r ）23．假定一个链队的队首和队尾指针分别为 front 和 rear ，则判断队空的条件是 _____ 。 A、 front==rear B D —10DABDB 、 front!=NULL C、 rear!=NULL 、 front==NULL 栈和队列 1—5CBCDD6 11 —15CDADB 16 —20ABCAB 21 —23BDA 四．串 （ ） 1．在目标串 T[0 , n-1]= ” xwxxyxy ”中，对模式串 p[0 , m-1]= ” xy ”进行子串定位操 作的结果 _______ A.0 B.2 C.3 D.5 （ ） 2. 如下陈述中正确的是 ________ A. 串是一种特殊的线性表 B. D. 串的长度必须大于零 C. 串中元素只能是字母 空串就是空白串 42 （ ）3. 若目标串的长充为 n，模式串的长度为 [n/3] ，则执行模式匹配算法时，在最坏情况下 的时间复杂度是 ________ A.O（ 1） B.O （ n） C.O（ n2） D.O （ n3 ） 串 1 —3CAB 五．数组和广义表 （ ）1．二维数组 A 按行顺序存储，其中每个元素占 1 个存储单元。若 A[1][1] 的存储地址为 420， A[3][3] 的存储地址为 446 ，则 A[5][5] A.470 C.472 B.471 D.473 的存储地址为 _______ （ ） 2．在稀疏矩阵的十字链接存储中，每个列单链表中的结点都具有相同的 _____ 。 Ａ．行号 Ｂ．列号 Ｃ．元素值 Ｄ．地址 （ ） 3. 一个数组元素 A[i] 与 ________ 的表示等价。 A、 *(A+i) B D 、 A+i C、 *A+i 、 &A+i （ ） 4. 在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的 ________ 。 A、 行号 C、 元素值 B D 、 列号 、 地址 43 数组 1—4CAAA 广义表 （ ） 1．已知广义表的表头为 A，表尾为 (B,C) ，则此广义表为 ________ A. （ A,(B,C) ） C.(A,B,C) （ B. （ A,B,C ） D.(( A,B,C)) n，则求广义表深度算法的时间复杂度为 ） 2. 设一个广义表中结点的个数为 ____ 。 A、 O(1) C、 O(n2) B D 、 O(n) 、 O(log 2 n) （ ） 3. 一个非空广义表的表头 ________ A. 不可能是子表 C. 只能是原子 B. 只能是子表 D. 可以是子表或原子 0 ）4. 设一个广义表中结点的个数为 n，则求广义表深度算法的时 2 3 3 5 （ 间复杂度为 _______ 。 A、 O(1) C、 O(n2) B D 、 O(n) 、 O(log2n) 广义表 1—4BDDB 六．树 （ ） 1. 将一棵有 100 个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点 的编号为 1，则编号为 49 的结点的左孩子的编号为 ______ 。 A.98 C.50 ( )2. B.99 D.48 ( ) 对于如图所示二叉树采用中根遍历，正确的遍历序列应为 44 A.ABCDEF B.ABECDF C.CDFBEA D.CBDAEF （ ） 3. 某二叉树的前序和后序序列正好相反，则该二叉树一定是 _____ 的二叉树 A 空或者只有一个结点 C任一结点无左孩子 B 高度等于其结点数 D任一结点无右孩子 （ ） 4．二叉树中第 5 层上的结点个数最多为 ________ A.8 C.16 B.15 D.32 （ ） 5. 由权值分别为 3,8,6,2,5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为 ________ 。 A、 24 C、 72 B D 、 48 、 55 A （ ） 6. 一棵度为 3 的树中，度为 3 的结点个数为 2，度为 2 的结点个数为 1，则度为 0 的结 B E 点个数为 ________ A.4 C.6 B.5 D.7 C D F 树 1 —6ADBCDC 七．图 （ ） 1. 在含有 n 个项点有 e 条边的无向图的邻接矩阵中，零元素的个数为 ________ 。 A.e C.n2-e B.2e D.n2-2e （ ） 2. 图的深度优先遍历类似于二叉树的 _______ 。 45 A. 先序遍历 B. 中序遍历 C. 后序遍历 （ D. 层次遍历 ） 3. 一个无向连连通图的生成树是含有该连通图的全部项点的 _______ 。 A. 极小连通子图 B. D. 极小子图 C. 极大连通子图 极大子图 （ ） 4．如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是 _______ A. 有向完全图 B. 连通图 C. 强连通图 D. 有向无环图 （ ） 5．下面关于图的存储的叙述中，哪一个是正确的。 ________ A．用相邻矩阵法存储图 , 占用的存储空间数只与图中结点个数有关 , 而与边数无关 , 而与结点个数无关 B．用相邻矩阵法存储图 , 占用的存储空间数只与图中边数有关 C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关 D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关 （ ） 6. 输入序列为（ A,B,C,D ），不可能得到的输出序列是 ______. A. (A,B,C,D) C.(A, C,D,B) B.(D,C,B,A) D.(C,A,B,D) 图 1--5DAADA 6D 八．查找 （ ） 1. 设有 100 个元素，用折半查找法进行查找时，最大比较次数是 _____ 。 A.25 C.10 B.50 D.7 （ ）2. 设散列表长 m=14, 散列函数 H（ K）=K％ 11，已知表中已有 r(38)=5; 4 个结点： r(15)=4; 46 r(61)=6;r(84)=7 ，其他地址为空，如用二次探测再散列处理冲突，关键字为 49 的结点地址是 ________ 。 A8 B3 C5 D9 （ ） 3．对于哈希函数 H(key)=key%13 ，被称为同义词的关键字是 _______ A．35 和 41 B.23 和 39 C.15 和 44 D.25 和 51 （ ） 4．对包含 N 个元素的散列表进行检索，平均检索长度 ________ A、为 o(log2N) B 、为 o(N) C、不直接依赖于 ND 、上述三者都不是 （ ） 5．向二叉搜索树中插入一个元素时，其时间复杂度大致力 ____ 。 A O（1） B O （ 1og2n） C O （ n） D O （ nlog2n ） （ ） 6. 从二叉搜索树中查找一个元素时，其时间复杂度大致为 ________ 。 A、 O(n) B 、 O(1) C、 O(log2n) D 、 O(n2) （ ） 7. 根据 n 个元素建立一棵二叉搜索树时，其时间复杂度大致为 ________ 。 A、 O(n) B 、 O(log2n ) C、 O(n2) D 、 O(nlog2n) （ ） 8. 适于对动态查找表进行高效率查找的组织结构是 ________ A. 有序表 B. 分块有序表 C. 二叉排序树 D. 线性链表 47 查找 1—5DDDCB6 —8CDC 九．排序 （ ） 1. 快速排序在 _____情况下最易发挥其长处。 A. 被排序数据中含有多个相同排序码 B. 被排序数据已基本有序 C. 被排序数据完全无序 D. 被排序数据中最大值和最小值相差悬殊 （ ） 2. 堆的形状是一棵 _______ 。 A. 二叉排序树 B. 满二叉树 C. 完全二叉树 D. 平衡二叉树 （ ） 3. 一个序列中有 10000 个元素，若只想得到其中前 10 个最小元素，最好采用 _______方法 A. 快速排序 B. 堆排序 C. 插入排序 D. 二路归并排序 （ ） 4．对 n 个关键字的序列进行快速排序，平均情况下的空间复杂度为 _______ A.O（ 1） B.O （ logn ） C.O（ n） D.O （ nlogn ） （ ） 5. 向堆中插入一个元素的时间复杂度为 ________ 。 A、 O(log2n) B 、 O(n) C、 O(1) D 、 O(nlog2n) （ ） 6. 从堆中删除一个元素的时间复杂以为 ____。 A、 O(1) B 、 O(log 2 n) C、 O(n) D 、 O(nlog 2 n) （ ） 7. 从堆中删除一个元素的时间复杂度为 ________ 。 48 A、 O(1) B 、 O(n) C、 O(log2n) （ D 、 O(nlog2n) ）8. 用某种排序方法对关键字序列（ 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 则所采用的排序方法是 ________ A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 排序 1—5CCBDA6—8BCD 应用题： 1、栈和队列都是特殊线性表，其特殊性是什么？ 2、设有一顺序队列 sq，容量为 5，初始状态 sq.front=sq.rear=0 其头尾指针变化状态，若不能入队，简述理由后停止。 1） d,e,b 入队。 2） d,e 出队。 3） i,j 入队。 4） b 出队。 5） n,o,p 入队。 3、设有一个顺序栈 S，元素 s1, s2, s3, s4, s5, s6 依次进栈，如果s3, s4, s6, s5, s1 ，则顺序栈的容量至少应为多少？ ，划出作完下列操作的队列及 6 个元素的出栈顺序为 s2, 49 4、将两个栈存入数组 V[1..m] 中应如何安排最好 ?这时栈空、栈满的条件是什么 ? 5、已知稀疏矩阵如下： 请写出该稀疏矩阵三元组表示。 6、广义表 A=（ a,b,(c,d),(e,(f,g)) ） , 求其长度，及深度。 7、请画出下面广义表相应的加入表头结点的单链表表示， D(A(x,y,L(a,b)) ， B(z,A(x,y,L(a,b)))) 。 8、一棵具有 n 个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层 有若干结点） 有多少层？若设根结点在第 0 层，则树的高度 h 如何用 n 来表示（注意 n 可能为 0）？ 9、设二叉树后根遍历为 BAC，画出所有可能的二叉树。 10、假设一棵二叉树的层序序列是 ABCDEFGHIJ和中序序列是 DBGEHJACIF,请画出该树。 请指出结点 P 的父结点， 左子 11、有一个完全二叉树按层次顺序存放在一维数组中，如下所示： 女，右子女。 12、给出下列二叉树的先序序列。 50 13、已知某非空二叉树采用顺序存储结构， 树中结点的数据信息依次存放在一个一维数组中， 即 ABC□DFE□□ G□□ H□□，该二叉树的中序遍历序列为： 14、设一棵二叉树的前序序列为 1,2,3,4,5,6,7,8,9, 其中序序列为 2,3,1,5,4,7,8,6,9, 试画出 该二叉树。 15、已知一组元素为（ 46， 25 ， 78， 62， 12， 37， 70， 29），试画出按元素排列次序插入生成的 一棵二叉树。 16、由于元素插入的次序不同， 所构成的二叉排序树也有不同的状态， 4 的二叉排序树。 请画出一棵含有 1，2，3， 4， 5， 6 六个结点且以 1 为根，深度为 17、什么是线索二叉树？为什么要线索化？ 18、有 n 个顶点的有向连通图最多有多少条边 ?最少有多少条边？ 19、下图中给出由 7 个顶点组成的无向图。从顶点 1 出发， 对它进行深度优先遍历得到的顶点序列是： 进行广度优先遍历得到的顶点序列是： 20、什么是连通图的生成树？ 21、什么是哈夫曼（ Huffman ）树？ 22、已知结点 a,b,c,d 及其权值写出哈夫曼树的构造过程。 a b c d 51 7 5 2 4 23、已知图 G={V , E} V={ a, b, c, d, e } E={(a, b),(b, d),(c, d),(d, e),(e, a),(a, c)} 画出图 G，画出图 G 的邻接表。 24、考虑下图： 1）从顶点 A 出发，求它的深度优先生成树。 2）从顶点 E 出发，求它的广度优先生成树。 3）根据普里姆（ Prim ）算法，求它的最小生成树。 25、设有关键码序列（ Q， H， C， Y， Q， A， M， S， R， D， F， X），要按照关键码值递增的次序进行排序。 若采用初始步长为 4 的 Shell 排序法，则一趟扫描的结果是： 若采用以第一个元素为分界元素的快速排序法，则一趟扫描的结果是： 26、一个对象序列的排序码为 {46 ，79，56，38，40， 84} ，采用快速排序以位于最左位置的对象 为基准而得到的第一次划分结果为： 27、用二分法对一个长度为 10 的有序表进行查找，填写查找每个元素需要的比较次数。 下标： 0 1 2 3 4 5 6 7 8 9 52 比较次数： 28、若对序列 (49,38,27,13,97,76,50,65) 采用泡排序法 ( 按照值的大小从小到大 ) 进行排序，请 分别在下表中写出每一趟排序的结果。 原始序列 49 38 27 13 97 76 50 65 第 1 趟的结果 第 2 趟的结果 第 3 趟的结果 第 4 趟的结果 29、给出一组关键字： 29，18 ，25， 47，58 ，12，51，10，分别写出按下列各种排序方法进行排 序时的变化过程： 1）归并排序 每归并一次书写一个次序。 2）快速排序 每划分一次书写一个次序。 3）堆排序 先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。 30、给出一组关键字 T=（ 12， 2， 16， 30，8， 28，4， 10，20， 6，18 ）。写出用下列算法从小到 大排序时第一趟结束时的序列： 1）希尔排序（第一趟排序的增量为 5） 2）快速排序 ( 选第一个记录为枢轴 ( 分隔 )) 3）链式基数排序（基数为 10） 31、若杂凑表的地址范围为 [0:9] ，杂凑函数为 H(key)=(key2+2)MOD 9，并且采用链地址方法处53 理冲突，请画出元素 7,4,5,3,6,2,8,9,1 依次插入该杂凑表以后，该杂凑表的状态。 32、已知二叉树采用二叉链表存储结构，链结点的构造为 lchild | data | rchild ，根结点的 指针为 T。下面是利用中序遍历的方法统计二叉树中度为 1 的结点的个数的算法，算法中设 置了一顺序存储结构的堆栈 STACK [1:M] ，栈顶指针为 top ，请在算法的空缺处填入适当内 容，使之能正常工作。 33、设有一个顺序栈 S，元素 s1, s2, s3, s4, s5, s6 依次进栈，如果 6 个元素的出栈顺序为 s2, s3, s4, s6, s5, s1 ，则顺序栈的容量至少应为多少？ 34、设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07} , (1) 从空树开始构造平衡二叉搜索树 , 画出每加入一个新结点时二叉树的形态。若发 生不平衡 , 指明需做的平衡旋转的类型及平衡旋转的结果。 (2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度。 35、关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 } 排序树两种的情况下等概率下查找成功的平均查找长度。 请计算在二分法查找、二叉 36、 37、 广义表 A=（ a,b,(c,d),(e,(f,g)) ）, 计算下面式子的值 Head(Tail(Head(Tail(Tail(A))))) 下图是用邻接表存储的图，画出此图，并写出从 的结果。 C 点开始按深度优先、广度优先遍历该图 38、 用序列（ 46， 88，45，39，70，58， 54 101， 10， 66， 34）建立一个排序二叉树，画出该树，并求在等概率情况下查找成功的平均查找 长度。 39、 判断下列序列是否为堆，如果不是请调整为堆，如果是请判断是什么类型的堆（ 101， 88， 46， 70， 34， 39， 45， 58， 66， 10） 40、 假设一棵二叉树的层序序列是 ABCDEFGHIJ和中序序列是 DBGEHJACIF,请画出该树。 41、 找出所有满足下列条件的二叉树 a) 它们在先序遍历和中序遍历时, 得到的结点访问序列相同； b) 它们在后序遍历和中序遍历时, 得到的结点访问序列相同； c) 它们在先序遍历和后序遍历时, 得到的结点访问序列相同。 42、 已知 L 是无表头结点的单链表 , 其中 P 结点既不是首元结点 a) 在 P 结点后插入 S 结点的语句序列是 ______ b) 在 P 结点前插入 S 结点的语句序列是 ______ c) 在表首插入 S 结点的语句序列是 ______ d) 在表尾插入 S 结点的语句序列是 ______ (1) P->next=S; (2) P->next=P->next->.next; (3) P->next=S->next; (4) S->next=P->next; (5) S->next=L; (6) S->next=NIL; (7) Q=P; (8) WHILE P->next<>Q , 也不是尾元结点。 55 P=P->next; (9) WHILE P->next!=NULL P=P->next; (10) P=Q; (11) P=L; (12) L=S; (13) L=P; 43、 已知树 T 的先序遍历序列为 ABCDEFGHIJKL，后序遍历序列为 CBEFDJIKLHGA，请画出树 T。 44、 对关键字序列（ 72，87 ，61 ，23，94，16 ，5，58 ）进行堆排序、快速排序、直接选择排序， 使之关键字递增有序，请写出每个排序的前三趟结果。 45、 46、 47、 请画出广义表 D 的图形表示 D=(D,(a,b),((a,b),c),( )) 若一二叉树有 2 度结点 100 个，则其叶结点有多少个？该二叉树可以有多少个 对于单链表、单循环链表和双向链表，如果仅仅知道一个指向链表中某结点的指针 否将 p 所指结点的数据元素与其确实存在的直接前驱交换 1 度顶点？ p ，能 ? 请对每一种链表作出判断，若可 以，写出程序段；否则说明理由。 单链表和单循环链表的结点结构为 data next 双向链表的结点结构为 prior data next (1) 单链表 (2) 单循环链表 (3) 双向链表 56 48、已知散列函数为 H(key)=key%7 ，散列表长度为 7( 散列地址空间为 0..6) ，待散列序列为： (25 ， 48， 32， 50， 68) 。要求： (1) 根据以上条件构造一散列表，并用线性探测法解决有关地址冲突； (2) 若要用该散列表查找元素68，给出所需的比较次数。 49、已知一组键值序列为 (38 ， 64，73，52，40， 37 ，56，43) ，试采用快速排序法对该组序列作 升序排序，并给出每一趟的排序结果。 50、已知某二叉树的顺序存储结构如图所示，试画出该二叉树。 A B C D E F 51、设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 } (1) 从空树开始构造平衡二叉搜索树 , 画出每加入一个新结点时二叉树 的形态。 若发生不平衡 , 指明需做的平衡旋转的类型及平衡旋转的结果。 (2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长 度。 52、求下列广义表运算的结果： 1) HEAD(p,h,w); 2) TAIL (b,k,p,h); 3) HEAD ((a,b),(c,d)); 4) TAIL (a,b),(c,d); 5) HEAD（ TAIL （（ (a,b),(c,d) ））） 6) TAIL （ HEAD((a,b),(c,d)) ） 53、画出下列广义表的图形表示： 57 1) D（ A（））， B（ e）， C（ a,L(b,c,d) ） 2) J1(J2,(J1,a,J3(J1)),J3(J1)) 54、完成下列要求： 1） 请画出下列广义表的存储结构 （(((a),b)),(((),(d)),(e,f)) ） 2）请写出下面链表表示的广义表 55、一棵二叉树如图： 1) 写出对此树进行中序、先序、后续遍历时得到的结点序列。 2) 画出树的后序线索二叉树。 58 56、将下列森林转化为二叉树。 57、已知一个图如下所示， 写出其临接矩阵， 并从顶点 a 出发按深度优先搜索、 按广度优先搜索， 则可以得到所有顶点序列为什么？ 58、试问在直接插入排序、希尔排序、快速排序、归并排序、二分法排序、直接选择排序中，哪 些排序是稳定的？哪些是不稳定的， 哪个排序平均比较次数最少？哪个排序要求内存容量最 多？ 59、哈希表中使用哈希函数 H（ key ）=3 * key % 11, 并采用开放定址法处理冲突，随机探测再 散列的下一地址公式为： d1=H (key ) di=( di-1 +7 * key ) % 11 （ I=2,3 , .. ） 59 试在 0 到 10 的散列地址空间中对关键字序列（ 22， 41， 53， 46， 30 ， 13， 01， 67）画出 Hash 表示意图，并求在等概率情况下查找成功的平均查找长度。 60、什么是内部排序？什么是排序方法的稳定性？说出你所学过的三个稳定算法， 一个不稳定算 法。 61、何为队列上溢？一般用什么方法解决，简述之。 62、载入下图所示的有权图 G，回答下列问题： 1） 给出从结点 v1 出发按深度优先搜索遍历图所得的结点序列； 2） 3） 给出图的拓扑序列； 给出从结点 v1 到结点 v8 的最短路径和关键路径。 63、对于下图，请给出 1） 2） 对应的邻接矩阵，并给出 A,B,C 三个顶点的入度和出度； 邻接表表示和逆邻接表表示； 60 3） 求其连同分量； 64、对于下图的树，分别用孩子链表和孩子兄弟链表法画出存储结构。 65、对于下图的树，请分别用中序、先序的方法写出其遍历结果。 66、已知一个表 {jan,feb,mar,apr,may,june,july,aug,sep} 1) 使按表中元素的次序依次插入一棵初始为空的二叉排序树，画出表中元素构成的二叉 排序树。 2) 求初等概率情况下查找 67、数组 a[1..10,-2..6,2..8] july 的查找长度。 以行优先的顺序存储，设第一个元素的首地址为 100，每个元素 占 3 个存储长度的存储空间，则元素 A[5,1,8] 的存储地址为多少？ 68、设有一组关键字（ 17，13，153 ，29，35，21）需插入到表长为 12 的表中，请回答下列问题： 1） 2） 自己设计一个合理的散列函数 用自己设计的函数将上述关键字插入到散列表中， 画出其结构； 并指出用线性探测法解 61 决冲突构造散列表的装填因子为多少？ 71、请画出下列二叉树的中序线索化前趋链树，后序线索化后继链树。 72、将下列结点按输入顺序构造一棵二叉平衡树。 {As ， Bx， Ca， Dww， Ae， Cf ， Edd， Fap， Goi ， Fab， Hre} 73、试在如图所示线索化的二叉树中，查找指定结点 E 的后继结点、 C 的前驱结点，并说明找到 结果的原因。 A aBC D EG B FH C E F D G H 74、什么是数据结构？ 75、试比较线性表的顺序存储结构和链式存储结构的优缺点。 76、有一组关键字 {14 ， 15， 30， 28， 5， 10} ，分别画出冒泡排序、快速排序过程的图示。 77、具有 3 个节点的树和具有 3 个节点的二叉树它们的所有不同形态有哪些？ 78、内存中一片连续空间（不妨假设地址从 1 到 m），提供给两个栈 S1 和 S2 使用，怎样分配这 部分存储空间，使得对任一个栈，仅当这部分空间全满时才发生上溢。 79、给出数组 int A[3 , 8， 2, 6] ；当它在内存中按行存放和按列存放时，分别写出数组元素 62 A[i,j] 的地址计算公式（设每个元素占两个存储单元） 。 80、已知一组键值序列为 (38 ， 64，73，52，40， 37 ，56，43) ，试采用快速排序法对该组序列作 升序排序，并给出每一趟的排序结果。 81、如图所示的二叉树完成中序遍历、后续遍历、先序遍历，并画出后序线索化的二叉树。 A B E C D F 82、将下图转换为二叉树，对转换后的二叉树进行先根、中根、后根遍历。 A B C D E F G J 83、有一组数值 14、 21、 32、 15、 28，画出哈夫曼树的生成过程及最后结果。 84、有 n 个顶点的有向连通图最多有多少条边 ?最少有多少条边？ 85、对关键字序列（ 72， 87，61， 23 ，94， 16，5， 58 ）进行堆排序、快速排序、直接选择排序， 63 使之关键字递增有序，请写出每个排序的前三趟结果。 86、已知图 G={V , E} V={ a, b, c, d, e } E={(a, b),(b, d),(c, d),(d, e),(e, a),(a, c)} 画出图 G，画出图 G 的邻接表。 87、设一个有向图为 G=(V,E), 其中 V={v1,v2,v3,v4} ， 88、请给出下图的邻接矩阵和邻接表。 a c e f b d 89、请画出下图中的极大连通子图。 1 2 3 4 5 6 E={ 画出相应的邻接矩阵、 邻接表和逆邻 64 90、对于如下图请画出其用 prim 和 kruskal 两种 3 1 3 12 2 10 6 不同算法生成最小生成树的各条边的并入顺序。 画 3 出最小生成树。 并写出广度优先和深度优先的结点 20 4 5 4 5 8 6 7 遍历顺序。 91、什么是静态查找，什么是动态查找，什么叫平均查找长度。 92、用序列（ 46， 88 ， 45， 39 ， 70， 58， 101， 10， 66， 34）建立一个二叉排序树，画出该树， 并求在等概率情况下查找成功的平均查找长度。 93、已知一个线性表（ 38，25，74，63 ，52， 48），假定采用 h(k)=k%7 计算散列地址进行散列存 储，若引用线性探测的开放地址法解决冲突，则在该散列表上进行检索的平均检索长度为多少， 若利用连地址法处理冲突，则在该散列表上进行检索的平均查找长度为多少？设地址空间为 9。 请画出算列表。 94、已知长度为 12 的表：（ Jan , Fed , Mar , Apr , May , Jun , Aug , Sep , Oct , Nov , Dec ） 按表中元素的顺序， 依次插入一棵初始为空的二叉排序树， 画出插完之后的二叉排序树， 并求其 在等概率情况下，查找成功的平均查找长度。 95、有散列函数为 h(k)=k%11, 如果用二次探测在散列的方式解决冲突， 49 应放入哪？ 65 15 38 61 84 0 1 2 3 4 596、用增量序列 {8 、 4、{56 、 37、 59、 41、 98、6 7 8 9 10 11 12 13 、 1} 对下列关键字进行希尔排序，用图表示排序过程。 、 94、 50、 63、 52、 42、 54、 60、 72、 86、 90}66 2 47 五、程序题 1、已知二叉树用下面的顺序结构存储，写出中序遍历该二叉树的算法。 left data right 2、下列算法为删除单链表中值为 X 的算法，将程序填完整 void del(struct node *head) { q=head; p=q->next; while(( )&&( )) { q=p; _________;} if(p= = null) printf( “ error ” ); else{______________; free(p);printf( “ success! ” );}} 3 、以下函数中， h 是带头结点的双向循环链表的头指针， 1） 写出下列程序的功能。 2） 当链表中结点数分别为 1 和 6（不包括头结点） 次数。 Int fox(struct node *h) { struct node p,q; int j=1; p=h- >next; q=h- >prior; while 循环体的执行 67 （（时，请写出程序中 while(p!=q && p->prior!=q) { if (p->data= = q->data) {p=p->next; q=q->prior; j++;} else j=0; } return(j); } 4、写出按后序序列遍历中序线索树的算法 . 5、写出计算树深度的算法。 6、写出计算树叶子结点的算法。 7、写出计算字符串长度的算法。 8、试写出以带头结点单链表为存储结构实现简单选择排序的算法9、阅读下列算法，并回答下列问题： 1） 该算法完成什么功能？ 2） 算法中 R[n+1] 的作用是什么？ void sort (elemtype r[],int n) {int k,i; for(k=n-1;k>=1;k- -) if(r[k]>r[k+1]) { r[n+1]=r[k]; 68 （ （ for(i=k+1;r[i] } 10、试编写一算法，以完成在带头结点单链表 11. 二叉树是由所有度数不大于 L 中第 i 个位置前插入元素 X 的操作。 2 的结点构成的一种特定树，若某结点度为 2，则该结点有左右 两个孩子，请编写算法计算一二叉树所有度数为 2 的结点个数。 12、试设计一个算法在中序线索化的树中， 求指定结点 P 在后序遍历序列中的前驱结点， 要求用 非递归算法。 13、若 X 和 Y 是两个单链表存储的串，设计一个算法，找出 X 中第一个不在 Y 中出现的字符。 14、试设计一个算法在中序线索化的树中， 求指定结点 P 在后序遍历序列中的前驱结点， 要求用 非递归算法。 15、设计一个算法，删去串中第 I 个字符开始的 J 个字符， 说明算法所用的存储结构， 并估计算 法的执行时间。 16、设有单链表中存放着 N 个字符，试设计算法判断字符串是否中心对称关系，例如： X Y Z Z Y X ， X Y Z Y X 都算是中心对称的字符串。要求用尽可能少的时间完成判断 ( 提示： 将一半字符先依次进栈 ) 。 提示 : 我们设 H为指向链表头结点的指针 , 单链表每个结点包括两个域 : 分别是 date,next 分别代 表数据域和指针域 ,s 为定义的栈。 17、设计一个算法将任意输入的 N 个数，按输入的顺序 ( 或逆序 ) 链接成一个单链表。 69 18、试设计一个算法，求单链表中数据值为 X0 的元素的地址。 19、试编一个程序，将两个字符串 s1 和 s2 进行比较，若 s1>s2 则输出一个正数；若 s1=s2，则 输出 0；若 s1 *p 的右子树中插入一个结点 *s 的算法。 21、给定一棵用链表表示的二叉树， 其根指针为 t ，试写出从根开始， 按层次遍历二叉树的算法， 同层的节点按从左到有的次序访问。 22、完成在二叉排序树中查找结点的程序 Bitreptr *bstsearch(t,k) Bitreptr *k; Keytype k; { if(t= =null) return null; else while(t !=null) {if (t->key= =k)_________; if(t- >key>k)______________; else____________________; } } 23、编写一个算法交换单链表中 P 所指向的位置和其后续位置上的两个结点， HEAD指向该链表 的表头， P 指向该链表中的某一结点。 70 24、已知两个链表 A 和 B，其元素值递增排列。写出编程将 A 和 B 合并成一个递减有序（相同值 只保留一个）的链表 C 的思想，并要求利用原表结点。（ * ） 25、下列算法完成在一个带头单链表中第 i 个结点前插入一个结点算法，请将空余处填上。 Void inserti (struct node *head) { p =head ->next;k=0; while(p!=null)&&(k<_______) {________; k++;} if p!=null {printf( “ please input to x ” ); scanf( “ %d” ,&x); q=(struct node *)malloc(sizeof(struct q->data=x; node)); _________; _________; } else printf( “ not found ith node ” );} 26 、写出下列算法的功能： void weizhi( struct node *head) head p q { p= head->next head->next =null; ； s y while (p!=null) 71 { q=p->next; p->next=head->next; head->next=p; p=q; } } 27、建立一个带头结点、有 10 个结点的单链表，请将下列算法填完整。void creat( ) { struct node *head,*p,*s; int i,x; head = ( struct node *)malloc( sizeof( struct node)); head->next=null; p=head; for ( i =1;i<=10 ; i ++) { s=(struct node *)malloc(sizeof(struct node)); printf( “请输入数据值” ) ； scanf( “%d”,&x); s ->data= x; s ->next=p->next; _______; _______;}} void searchbinary( elemtype a[ ],int n ,int k) {int low=0,high=n-1,mid, find=0; while(find= = 0)&&(low<=high) 72 { mid=______________; if(k= = a[mid]) {find=1; printf( “find k! ”);} else {if ( k else _____________;} } if (find= =0) printf( “not find k!oid insstr(char string1,char string2,int i) {int n,m, j; n=strlen(string1); m=strlen(string2); if ( i<0|| i>n – 1) printf( “error! ”); else { for(j=n;j>=i-1;j - -) string1[j+m]=string1[j]; for(j=0,j void delstr(char string, int i, int j) {if ( i> strlen(string)) printf( “error! ”); else{ k= i-1; ”); }73 while(string[k+j] ! = ‘ o’) { ____________; k++;} string[k]= ‘ 0’; }} Void delete( int a[n],int i) {if (i<0)||(i>=n) printf( “error ”); else{for (j=i-1;j n=n-1;} } 在有头结点 head 单链表 p 指针结点后插入值为 x 的结点，请将下列算法填完整；void insert( struct node *head, elemtype x) { struct node *s,*p*q; q = head->next ; while (q!=p) q=q->next; if q= =null printf( “not find ”); else { s=(struct node *)malloc( sizeof(struct node) ) ; s->data=x; _______________ ； _______________ ； }} void weizhi (linkqueue *q) {struct queuenode *p; if q.front = = q.rear 74 printf( “the queue is empty ”); else{ p=q->front->next; q->front->next=p->next return(p->data); free(p); }} 41、写出在二叉排序树中插入一指定结点一个结点的算法。42、完成计算二叉树叶子结点的算法。 void midtravel(struct treenode *bt) {struct treenode *p,*a[n]; int top= - 1,true =1, j =0; while(true) { p=bt; while(p != null) { top + +; a[top]=p; p=________} if (top != -1) { p=a[top]; top -- ; printf( “%c”,p ->data); if (p->left = = null )&&__________ ______________; p=p->right;} 75 else true = 0; } printf( “ %d” ,j)} 43、完成二叉树按层遍历的算法。 void leveltravel ( struct treenode *bt) { struct treenode *p,*a[n]; int rear=front = -1; p=bt; rear =__________; a[rear]=p; while (rear != front) { front = ___________; p=a[front]; printf( “%c”,p ->data); if ( p->left !=null) { rear =(rear +1)% n a[rear]= _________; } if (p->right!= null) {rear = (rear +1)%n ; a[rear]=_________; } } } 44、给定一棵用链表表示的二叉树， 其根指针为t ，试写出从根开始，按层次遍历二叉树的算法，76 同层的节点按从左到有的次序访问。 45、写出在中序线索二叉树中结点 *p 的右子树中插入一个结点 *s 的算法。 46、试设计一个算法在中序线索化的树中，求指定结点 P 的前驱结点，要求用非递归算法。 47、完成下列程序 , 并说出该算法所完成的功能。 void weizhisort(struct node r[ n],int n) { int low,high,mid,j,i; for(i=2;i<=n;i++) { r[0]=r[i]; low=__________; high=_________; while(low<=high) { mid=(low+high)/2; if(r[0].key }} 48、完成程序，并说出程序的功能 Bitreptr *bstsearch(t,k) Bitreptr *k; 77 Keytype k; {if(t= =null) return null; else while(t !=null) {if (t->key= =k)_________; if(t->key>k)______________; else____________________; } } 49、完成下列程序，并说出该算法的功能。 void weizhitravel ( struct treenode *bt) { struct treenode *p,*a[n]; int true = 1,top =-1; while (true) { while (p!= null) // 只要 p 不空全部压栈 // { printf(“%c”,p ->data); ______________; a[top] =p ; _________;} if ( top != - 1) {p=a[top]; 78 p=p->right; top - -;} else true =0; } } 50、写出在二叉排序树中查找值为 x 的算法。 51、试写出以带头结点单链表为存储结构实现简单选择排序的算法。52、阅读下列算法，并回答下列问题： 该算法完成什么功能？算法中 R[n+1] 的作用是什么？ void sort (elemtype r[],int n) {int k,i; for(k=n-1;k>=1;k- -) if(r[k]>r[k+1]) { r[n+1]=r[k]; for(i=k+1;r[i] } 53、说出下列算法的运行结果 : struct node { elemtype data; struct node *next;} 79 void weizhi (struct node *head,struct node *q) {struct node *p, *r; p=head->next while(p->next!=q)&&(p->next != null) p=p->next; if (p->next !=null) { r=p->next; q->next=r; p->next=r->next; r->next=p;} } 算法完成的结果是 : _______________________ 54、设编写一计算字符串长度的算法。 55、写一算法将一单链表逆置。要求操作在原链表上进行。 56、编写算法在一个非减有序线性表中， 插入一个值 x 的元素，使插入的线性表仍为非减有序表。80 因篇幅问题不能全部显示，请点此查看更多更全内容