若一个图的独立顶点集集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有__3_____个连通分量。
点击联系发帖人
时间：2017-09-18 09:22
拒绝访问 | www. | 百度云加速
请打开cookies.
此网站 (www.) 的管理员禁止了您的访问。原因是您的访问包含了非浏览器特征(3a6a-ua98).
重新安装浏览器，或使用别的浏览器A.nB.n(n-1)C.n(n-1)/2D.n；5.在一个具有n个顶点的有向完全图中，所含的边数；A.nB.n(n-1)C.n(n-1)/2D.n；6.在一个无向图中，若两顶点之间的路径长度为k，；A.kB.k+1C.k+2D.2k；7.对于一个具有n个顶点的无向连通图，它包含的连；A.0B.1C.nD.n+1；8.若一个图中包含有k个连通分量，若要按照深
C. n(n-1)/2
D. n(n+1)/2
5. 在一个具有n个顶点的有向完全图中，所含的边数为(
C. n(n-1)/2
D. n(n+1)/2
6. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为(
7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为(7. B)。
8. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则
必须调用(8. A )次深度优先搜索遍历的算法。
9. 若要把n个顶点连接为一个连通图，则至少需要(9. C )条边。
10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为
有效元素）的个数为(
11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为
12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为(12. D )。
13. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向
量的大小至少为(13. A )。
14. 在一个无权图的邻接表表示中，每个边结点至少包含(14. B )域。
15. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链
表中的边结点数为(15. B )。
16. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单
链表中的边结点数为(16. C )。
17. 对于一个无向图，下面(17. A )种说法是正确的。
A. 每个顶点的入度等于出度
B. 每个顶点的度等于其入度与出度之和
C. 每个顶点的入度为0
D. 每个顶点的出度为0
18. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的(18. A)。
D. 度数减1
19. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进
行深度优先搜索，得到的顶点序列可能为(
A. A,B,C,F,D,E
B. A,C,F,D,E,B
C. A,B,D,C,F,E
D. A,B,D,F,E,C
20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进
行广度优先搜索，得到的顶点序列可能为(20. D )。
A. A,B,C,D,E,F
B. A,B,C,F,D,E
C. A,B,D,C,E,F
D. A,C,B,F,D,E
21. 若一个图的边集为{&1,2&,&1,4&,&2,5&,&3,1&,&3,5&,&4,3&}，则从顶点1开始对该图
进行深度优先搜索，得到的顶点序列可能为(21. A
A. 1,2,5,4,3
B. 1,2,3,4,5
C. 1,2,5,3,4
D. 1,4,3,2,5
22. 若一个图的边集为{&1,2&,&1,4&,&2,5&,&3,1&,&3,5&,&4,3&}，则从顶点1开始对该图
进行广度优先搜索，得到的顶点序列可能为(
A. 1,2,3,4,5
B. 1,2,4,3,5
C. 1,2,4,5,3
D. 1,4,2,5,3
23. 由一个具有n个顶点的连通图生成的最小生成树中，具有(23. B )条边。
24. 已知一个有向图的边集为{&a,b&,&a,c&,&a,d&,&b,d&,&b,e&,&d,e&}，则由该图产生的一
种可能的拓扑序列为(24. A
A. a,b,c,d,e
B. a,b,d,e,b
C. a,c,b,e,d
D. a,c,d,b,e
二、填空题
1. 在一个图中，所有顶点的度数之和等于所有边数的________倍。1. 2
2. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点
的有向完全图中，包含有________条边。
2. n(n-1)/2，n(n-1)
3. 假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{&a,c&, &a,e&, &c,f&, &d,c&, &e,b&,
&e,d&}，则出度为0的顶点个数为________，入度为1的顶点个数为________。3. 2，4
4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。4. n-1
5. 表示图的两种存储结构为__________和__________。5. 邻接矩阵，邻接表
6. 在一个连通图中存在着________个连通分量。6. 1
7. 图中的一条路径长度为k，该路径所含的顶点数为________。7. k+1
8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________
个连通分量。
9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为
________?________。9.
10. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结
点的个数分别为________和________。10. 2e，e
11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有
________和________结点。11. 出边，入边
12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，
求任一顶点度数的时间复杂度分别为________和________。
12. O（n），O（e/n）
13. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空
2间复杂度分别为________和________。13.O（n），O（n+e）
14. 一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得
到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为
____________。
14. acdeb，acedb （答案不唯一）
15. 一个图的边集为{&a,c&,&a,e&,&c,f&,&d,c&,&e,b&,&e,d&}，从顶点a出发进行深度优先
搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点
序列为____________。15. acfebd，acefbd （答案不唯一）
16. 图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法
需要使用队列。 16. 深度，广度
17. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为
________和________。17. n，n-1
18. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/
不唯一）的。 18. 唯一
19. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是__（唯一/不唯一）的。
20. 假定一个有向图的边集为{&a,c&,&a,e&,&c,f&,&d,c&,&e,b&,&e,d&}，对该图进行拓扑排序得
到的顶点序列为________。
20. aebdcf（答案不唯一）
三、应用题
1. 对于一个无向图6-11(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度
优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
注：每一种序列都是唯一的，因为都是在存储结构上得到的。
1. 深度优先搜索序列：0,1,2,8,3,4,5,6,7,9
广度优先搜索序列：0,1,4,2,7,3,8,6,5,9
2. 对于一个有向图6-11(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结
点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍
历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
注：每一种序列都是唯一的，因为都是在存储结构上得到的。
2. 深度优先搜索序列：0,4,7,5,8,3,6,1,2
广度优先搜索序列：0,4,3,1,7,5,6,2,8
3. 已知一个无向图的邻接矩阵如图6-12(a)所示，试写出从顶点0出发分别进行深度优
先和广度优先搜索遍历得到的顶点序列。
3. 深度优先搜索序列：0,2,3,5,6,1,4
广度优先搜索序列：0,2,3,5,6,1,4
4. 已知一个无向图的邻接表如图6-12(b)所示，试写出从顶点0出发分别进行深度优先
和广度优先搜索遍历得到的顶点序列。
4. 深度优先搜索序列：0,3,6,4,1,5,2
广度优先搜索序列：0,3,2,6,5,4,1
5. 已知图6-13所示的一个网，按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。
5. 过程如图6-16所示
6. 已知图6-13所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。
6. 求解过程如图6-17所示。
(b) (c) (e) (f) 图6-17
图6-14所示为一个有向网图及其带权邻接矩阵，要求对有向图采用
Dijkstra算法，求从
V0 到其余各顶点的最短路径。
有向带权图
图6-14 有向带权图及其邻接矩阵
7. 求解过程如下表所示。
三亿文库包含各类专业文献、应用写作文书、生活休闲娱乐、专业论文、各类资格考试、外语学习资料、文学作品欣赏、79图结构习题答案等内容。
1. 图结构习题 1.对于下列所示的图,给出从顶点 1 开始的 BFS 树。 2.对于题 1 中的图,给出从顶点 4 出发,使用 Dijkstra 最短路径算法产生的最短 路径... 平面力偶系习题答案_工学_高等教育_教育专区。建筑力学第三单元 平面力偶系 3-...3-4 在图3-4a 所示结构中,各构件的自重略去不计,在构件BC 上作用1 力偶... 第6章图练习题答案_信息与通信_工程科技_专业资料。第 6 章图练习题答案一、填空题 1. 图有 邻接矩阵 、 邻接表 等存储结构,遍历图有 深度优先遍历 、 广度... D 1 E 2 C A B 习题 2-7 图 习题 2-7 解答图 解:将题中的折杆用直杆代替,如图(b)所示。杆 CD 和链杆 1 由铰 D 联结构成二元 体可以去掉;同... q C B A D 八.(本大题 15 分) 用力法作图结构的 M 图.EI=常数. EI 2q EI EI 2EI l l EI 2q l 结构力学试卷答案三.是非题 1 . (X) ;2.... 结构力学课后习题答案_工学_高等教育_教育专区。习 题 7-1 试确定图示结构的...Z 1 ? 7 ql 4 348 EI 作出最终 M 图 85 2 ql 348 5 ql 2 768 41... 第6章 图习题参考答案_IT认证_资格考试/认证_教育专区。习题六参考答案一、选择...无向图采用邻接表存储结构,编写算法输出图中各连通分量的顶点序列。 参考答案: ... 数据结构图习题_理学_高等教育_教育专区。数据结构习题和答案 第7章 图 一、选择题 1.对于一个具有 n 个顶点和 e 条边的有向图,在用邻接表表示图时,拓扑... 建筑施工图自测练习题――答案 1.工业建筑;农业建筑;民用建筑 2.设计总说明;建筑施工图;结构施工图;设备施工图。 3.建筑设计总说明;总平面图;建筑平面图;建筑...您所在位置： &
 &  & 
图答案.doc 4页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：200 &&
你可能关注的文档：
··········
··········
单项选择题
在一个具有n个顶点的有向图中，若所有顶点的出度数之和是s，则所有顶点的入度数之和为（）
A．ｓ B．ｓ－１ C．ｓ＋１ D． ｎ
２．在一个具有n个顶点的有向图中，若所有顶点的出度数之和是s，则所有顶点的度数之和为（）
A．ｓ B．ｓ－１ C．ｓ＋１ D． ２ｓ
３．在一个具有ｎ个顶点的无向图中，若具有ｅ条边，则所有顶点的度数之和为（）
A．ｎ B．ｅ C．ｎ＋ｅ D． ２ｅ
４．在一个具有ｎ个顶点的无向完全图中，所含的边数为（）
A．ｎ B．ｎ（ｎ－１） C．ｎ（ｎ－１）/２ D．ｎ（ｎ－１）/２
５．在一个具有ｎ个顶点的有向完全图中，所含的边数为（）
A．ｎ B．ｎ（ｎ－１） C．ｎ（ｎ－１）/２ D．ｎ（ｎ－１）/２
６．在一个无权图中，若两顶点之间的路径长度为ｋ，则该路径上的顶点数为（）
Ａ．ｋ Ｂ．ｋ＋１ Ｃ．ｋ＋２ Ｄ．２ｋ
７．对于一个具有ｎ个顶点的无向连通图，它包含的连通分量的个数为（）
Ａ．０ Ｂ．１ Ｃ．ｎ Ｄ．ｎ＋１
８．若一个图中包含有ｋ个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须用（）次深度优先搜索遍历的算法。
Ａ．ｋ Ｂ．１ Ｃ．ｋ－１ Ｄ．ｋ＋１
９．若要把ｎ个顶点连接为一个连通图，则至少需要（）条边。
Ａ．ｎ Ｂ．ｎ＋１ Ｃ．ｎ－１ Ｄ．２ｎ
１０．在一个具有ｎ个顶点和ｅ条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。
Ａ．ｎ Ｂ．ｎ×ｅ Ｃ．ｅ Ｄ．２×ｅ
１１．在一个具有ｎ个顶点和ｅ条边的有向图的邻接矩阵中，表示边存在的元素的个数为（）。
Ａ．ｎ Ｂ．ｎ×ｅ Ｃ．ｅ Ｄ．２×ｅ
１２．在一个具有ｎ个顶点和ｅ条边的有无向图的邻接表中，边结点的个数为（）。
Ａ．ｎ Ｂ．ｎ×ｅ Ｃ．ｅ Ｄ．２×ｅ
１３．在一个具有ｎ个顶点和ｅ条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（）。
Ａ．ｎ Ｂ．２ｎ Ｃ．ｅ Ｄ．２×ｅ
１４．在一个无权图的邻接表表示中，每个边结点至少包含（）域。
Ａ．１ Ｂ．２ Ｃ．３ Ｄ．４
１５．对于一个有向图，若一个顶点的入度为ｋ１，出度为ｋ２，则对应邻接表中该顶点单链表中的边结点数为（）。
Ａ．Ｋ１ Ｂ．Ｋ２ Ｃ．Ｋ１－Ｋ２ Ｄ．Ｋ１＋Ｋ２
１６．对于一个有向图，若一个顶点的入度为ｋ１，出度为ｋ２，则对应逆邻接表中该顶点单链表中的边结点数为（）。
Ａ．Ｋ１ Ｂ．Ｋ２ Ｃ．Ｋ１－Ｋ２ Ｄ．Ｋ１＋Ｋ２
１７．对于一个无向图，下面（）说法是正确的。
Ａ．每个顶点的入度等于出度 Ｂ．每个顶点的度等于其入度与出度之和 Ｃ．每个顶点的入度为０ Ｄ．每个顶点的出度为０
１８．在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）。
Ａ．出边数 Ｂ．入边数 Ｃ．度数 Ｄ．度数减１
１９．若一个图边集为｛（Ａ，Ｂ），（Ａ，Ｃ），（Ｂ，Ｄ），（Ｃ，Ｆ），（Ｄ，Ｅ），（Ｄ，Ｆ）｝，则从顶点Ａ开始对该图进行深度优先搜索，得到的顶点序列可能为（）。
Ａ．A,B,C,F,D,E Ｂ．A,C,F,D,E,B Ｃ．A,B,D,C,F,E Ｄ．A,B,D,F,E,C
２０．若一个图边集为｛（Ａ，Ｂ），（Ａ，Ｃ），（Ｂ，Ｄ），（Ｃ，Ｆ），（Ｄ，Ｅ），（Ｄ，Ｆ）｝，则从顶点Ａ开始对该图进行广度优先搜索，得到的顶点序列可能为（）。
Ａ．Ａ,B,C,D,E,F Ｂ．A,B,C,F,D,E Ｃ．A,B,D,C,E,F Ｄ．A,C,B,F,D,E
２１．若一个图边集为｛ 1,2 , 1,4 , 2,5 , 3,1 , 3,5 , 4,3 ｝,则从顶点１开始对该图进行深度优先搜索，得到的顶点序列可能为（）。
Ａ．1,2,5,4,3 Ｂ．1,2,3,4,5 Ｃ．1,2,5,3,4 Ｄ．1,4,3,2,5
２２．若一个图边集为｛ 1,2 , 1,4 , 2,5 , 3,1 , 3,5 , 4,3 ｝,则从顶点１开始对该图进行广度优先搜索，得到的顶点序列可能为（）。
Ａ．1,2,3,4,5 Ｂ．1,2,4,3,5 Ｃ．1,2,4,5,3 Ｄ．1,4,2,5,3
２３．由一个具有ｎ个顶点的连通图生成的最小生成树中，具有（）条边。
Ａ．ｎ Ｂ．ｎ－１ Ｃ．ｎ＋１ Ｄ．２＊ｎ
２４．已知一个无向图的边集为｛（０,1）3,（0,2）5,（0,3）6,（1,4）10,（2,3）2,（2,4）9,（3,4）8｝,则该图的最小生成树的权为（）。
Ａ．４３ Ｂ．１６ Ｃ．１８ Ｄ．２３
２５．已知一个无向图的边集为｛（０,1）3,（0,2）5,（0,3）6,（1,4）10,（2,3）2,（2,4）9,（3,4）8｝,则该图的最小生成树的边集为（）。
Ａ．｛（０,1
正在加载中，请稍后...南开13秋 数据结构-海文库
全站搜索：
您现在的位置：&>&&>&理学
南开13秋 数据结构
13秋学期《数据结构》在线作业
一、单选题1.
若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为（）A. iB. n=iC. n-i+1D. 不确定正确答案：C
堆的形状是一棵()A. 二叉排序树B. 满二叉树C. 完全二叉树D. 平衡二叉树正确答案：C
设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个A. n-1B. nC. n+1D. n+2正确答案：C
在表长为ｎ的链表中进行线性查找，它的平均查找长度为（
）A. ＡＳＬ＝ｎB. ＡＳＬ＝（ｎ＋１）／２C.D.正确答案：B
把一棵树转换为二叉树后，这棵二叉树的形态是（）A. 唯一的B. 有多种C. 有多种，但根结点都没有左孩子D. 有多种，但根结点都没有右孩子正确答案：A
在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B. 在第i个结点后插入一个新结点（1≤i≤n）C. 删除第i个结点（1≤i≤n）D. 将n个结点从小到大排序正确答案：A
判定一个队列QU（最多元素为m0）为满队列的条件是（）A.
QU-&rear － QU-&front = = m0B. QU-&rear － QU-&front －1= = m0C.
QU-&front = = QU-&rearD. QU-&front = = QU-&rear+1正确答案：A
若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为A. 38,40,46,56,79,84B. 40,38,46,79,56,84C. 40,38，46,56,79,84D. 40,38,46,84,56,79正确答案：C
在一个图中，所有顶点的度数之和等于图的边数的（）倍A. 1/2B. 1C. 2D. 4正确答案：C
用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的A. 栈B. 队列C. 树D. 图正确答案：B
设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）A. 循环链表B. 单链表C.
双向循环链表D. 双向链表正确答案：B
链表是一种采用
存储结构存储的线性表A. 顺序B. 链式C. 星式D. 网状正确答案：B
不含任何结点的空树（）A. 是一棵树B. 是一棵二叉树C. 是一棵树也是一棵二叉树D. 既不是树也不是二叉树正确答案：C
数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为A. r－fB. （n＋f－r）% nC. n＋r－fD. （n＋r－f）% n正确答案：D
若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()A. 79,46,56,38,40,84B. 84,79,56,38,40,46C. 84,79,56,46,40,38D. 84,56,79,40,46,38正确答案：B
从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()A. 希尔排序B. 归并排序C. 插入排序D. 选择排序正确答案：D
任何一个无向连通图的最小生成树()A. 只有一棵B. 一棵或多棵C. 一定有多棵D. 可能不存在正确答案：A
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A. 1/2B. 1C. 2D. 4正确答案：B
下述几种排序方法中，要求内存最大的是()A. 插入排序B. 快速排序C. 归并排序D. 选择排序正确答案：C
线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以正确答案：D
二、判断题1.
顺序存储方式的优点是存储密度大，且插入、删除运算效率高。A. 错误B. 正确正确答案：A
队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。A. 错误B. 正确正确答案：A
栈和队列的存储方式既可是顺序方式，也可是链接方式。A. 错误B. 正确正确答案：B
用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。A. 错误B. 正确正确答案：B
栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。A. 错误B. 正确正确答案：B
栈和队列是一种非线性数据结构。A. 错误B. 正确正确答案：A
对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表A. 错误B. 正确正确答案：B
二叉树中所有结点个数是2k-1-1，其中k是树的深度。A. 错误B. 正确正确答案：A
栈和链表是两种不同的数据结构。A. 错误B. 正确正确答案：A
在表结构中最常用的是线性表，栈和队列不太常用。A. 错误B. 正确正确答案：A
二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。A. 错误B. 正确正确答案：A
二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。A. 错误B. 正确正确答案：A
两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。A. 错误B. 正确正确答案：B
线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。A. 错误B. 正确正确答案：A
对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i―1个结点。A. 错误B. 正确正确答案：A
顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。A. 错误B. 正确正确答案：A
顺序存储方式只能用于存储线性结构。A. 错误B. 正确正确答案：A
二叉树中每个结点有两棵非空子树或有两棵空子树。A. 错误B. 正确正确答案：A
线性表在物理存储空间中也一定是连续的。A. 错误B. 正确正确答案：A
若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n―1个非空指针域。A. 错误B. 正确正确答案：B
链表的物理存储结构具有同链表一样的顺序。A. 错误B. 正确正确答案：A
一个栈的输入序列是12345，则栈的输出序列不可能是12345。A. 错误B. 正确正确答案：A
链表的每个结点中都恰好包含一个指针。A. 错误B. 正确正确答案：A
二叉树中每个结点的两棵子树的高度差等于1。A. 错误B. 正确正确答案：A
线性表的逻辑顺序与存储顺序总是一致的。A. 错误B. 正确正确答案：A
具有12个结点的完全二叉树有5个度为2的结点。A. 错误B. 正确正确答案：B
线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。A. 错误B. 正确正确答案：A
线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。A. 错误B. 正确正确答案：A
二叉树中每个结点的两棵子树是有序的。A. 错误B. 正确正确答案：B
链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。A. 错误B. 正确正确答案：A
一、（共 10 道试题，共 60 分。）1.表达式a*(b+c)-d的后缀表达式是（ ）。A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd-----------------选择：B2.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。A. (rear+1) MOD n=frontB. rear=frontC. rear+1=frontD. (rear-l) MOD n=front-----------------选择：B3.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（ ）。A. (n+1)/2B. n/2C. nD. n+1-----------------选择：C4.在一个单链表中，删除*p结点之后的一个结点的操作是（ ）。A. p-&next=p;B. p-&next-&next=p-&C. p-&next-&next=p;D. p-&next=p-&next-&-----------------选择：D5.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ ）。A. cB. b，cC. （b，c）D. （（b，c））-----------------选择：D6.在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动（ ）个数据元素。A. (n-1)/2B. n/2C. n-1D. n-----------------选择：B7.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）。A. head==NULLB. head→next==NULLC. head→next==headD. head!=NULL-----------------选择：B8.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（ ）个指针域的值。A. 1B. 2C. 3D. 4-----------------选择：B9.一个顺序栈S，元素a，b，c，d，e依次进栈，如果5个元素的出栈顺序为b，e，d，c，a，则顺序栈的容量至少应为（ ）。A. 2B. 3C. 4D. 5-----------------选择：C10.广义表((e))的表头是（ ）。A. eB. (e)C. ()D. (())-----------------选择：B
大工13春《数据结构》在线作业1
二、判断题（共 10 道试题，共 40 分。）1.顺序表中存取每一个元素的时间相同。（ ）A. 错误B. 正确-----------------选择：B2.算法分析的两个主要方面空间复杂度和时间复杂度。（ ）A. 错误B. 正确-----------------选择：B3.4个元素按a,b,c,d顺序连续进入队列，队头的元素是a。（ ）A. 错误B. 正确-----------------选择：B4.插入和删除只能在表的一端进行的线性表，称为队列。（ ）A. 错误B. 正确-----------------选择：A5.栈是限定只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。（ ）A. 错误B. 正确-----------------选择：A6.中缀表达式A-(B+C/D)*E的后缀形式是ABCD/+E*-。（ ）A. 错误B. 正确-----------------选择：B7.若n阶方阵的对角线右上方的元素均等于零，称为下三角矩阵。（ ）A. 错误B. 正确-----------------选择：B8.在栈中，出栈操作的时间复杂度为O(n)。（ ）A. 错误B. 正确-----------------选择：A9.栈和队列的共同特点是先进先出。（ ）A. 错误B. 正确-----------------选择：A10.顺序表的长度是表中的数据元素个数。（ ）A. 错误B. 正确-----------------选择：B
《数据结构》复习大纲――知识点剖析第一章：绪论一、基础知识概念和术语(黑体字部分)。另外，注意：1、数据元素是数据的基本单位。P42、数据项是数据不可分割的最小单位。P53、数据结构及其形式定义。P5四种基本结构：①集合②线性结构③树形结构④图（网）状结构4、数据结构的逻辑结构（抽象的，与实现无关）物理结构（存储结构）
顺序映像（顺序存储结构）位置“相邻”非顺序映像（链式存储结构）指针表示关系P65、数据类型
P7抽象数据类型（ADT）P7ADT=（数据对象，数据关系，基本操作）ADT细分为原子类型，固定聚合，可变聚合类型。P86、算法的概念
P137、算法的五个特征①有穷性 ②确定性 ③可行性 ④输入（0个或多个） ⑤输出（1个或多个）8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量
其中正确性的四个层次（通常要求达到C层）。9、算法的时间复杂度
常见有： O(1)，O(n)，O(n)，O(log2n)，O(n log2n)，O(2)语句频度，用归纳法计算。10、算法的空间复杂度
P17二、算法起泡排序。P16另一种形式void BubbleSort ( DataType a[], int n ){for ( i=0; i&n-1; i++ )for ( j=0; j&n-i-1; j++ )if ( a[j]&a[j+1] )a[j]&―&a[j+1];}或void BubbleSort ( DataType a[], int n ){for ( i=1; i&n; i++ )for ( j=0; j&n-i; j++ )if( a[j]&a[j+1] )a[j]&―&a[j+1];}或void BubbleSort ( DataType a[], int n ){for ( i=0; i&n-1; i++ ) {change =for ( j=0; j&n-i-1; j++ )if ( a[j]&a[j+1] ) {a[j]&―&a[j+1];change =}if ( !change )}} 1 分析算法的时间复杂度时，log2n常简单记作log n。
说明：a) 考试中要求写算法时，可用类C，也可用C程序。 b) 尽量书写算法说明，言简意赅。c) 技巧：用“边界值验证法”检查下标越界错误。如上第一个： 第二个循环条件若写作j&n-i，则当i=0时 a[j+1]会越界。2d) 时间复杂度为O(n)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。 第二章、线性表 一、基础知识和算法 1、线性表及其特点线性表是n个数据元素的有限序列。2线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。 2、顺序表―线性表的顺序存储结构（1）特点：a) 逻辑上相邻的元素在物理位置上相邻。b) 随机访问。 （2）类型定义3简而言之，“数组+长度”。const int MAXSIZE = 线性表最大长度; typedef struct{DataType elem[MAXSIZE]; } SqL注：a) SqList为类型名，可换用其他写法。b) DataType是数据元素的类型，根据需要确定。
c) MAXSIZE根据需要确定。如
const int MAXSIZE=64;d) 课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以e) 课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L.length==L.listsize时，用realloc (L.elem, L.listsize+增量) 重新分配内存，而realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。（3）基本形态 a) 顺序表空条件
L.length==0 不允许删除操作b) 顺序表满条件
L.length==MAXSIZE 不允许插入操作0 1 ... MAXSIZE-1
L.length==0
L.length==MAXSIZ0&L.length&MAXSI23这里太简炼了，只是为了便于记忆。不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。
c) 不空也不满可以插入，删除（4）基本算法――遍历d) 顺序访问所有元素for ( i=0; i&L. i++ )
visit ( L.elem[i] );
5 查找元素xfor ( i=0; i&L. i++ )if ( L.elem[i]==x )if ( i&L.length )找到;else未找到;2. 插入算法 ListInsert(&L,i,x)a) 前提：表不满b) 合理的插入范围：1≤i≤L.length+1注：位序i在C/C++中对应于下标i-1。c) 步骤第i至最后所有元素后移一个元素在第i个位置插入元素x表长增1d) 算法4bool ListInsert ( SqList& L, int i, DataType x ){if ( L.length==MAXSIZE || i&1 || i&L.length+1 ) // 失败// 元素后移for ( j=L.length-1; j&=i-1; j-- )
// 这里j为下标，从L.length-1到i-1L.elem[j+1] = L.elem[j];
若作为位序，有如何修改？// 插入xL.elem[i-1] =// 表长增1L.length++;
// 插入成功}3. 删除算法 ListDelete(&L,i,&x)a) 前提：表非空b) 合理的删除范围：1≤i≤L.lengthc) 步骤取出第i个元素第i个元素之后的元素向前移动一个位置 4 这里返回true表示正确插入，返回false表示插入失败。以下常用来区分操作是否正确执行。表长减1d) 算法bool ListDelete ( SqList& L, int i, DataType& x ){if ( L.length==0 || i&1 || i&L.length ) // 失败
x = L.elem[i-1];for ( j=i; j&L. j++ )L.elem[j-1] = L.elem[j];L.length--;
// 删除成功}
4. 算法分析表 错误！文档中没有指定样式的文字。.1 顺序表插入和删除算法的分析基本操作平均移动次数时间复杂度尾端操作 插入 移动元素 1n?1n(n?i?1)? ?i?1?删除 移动元素 1n?1?i(n?i)?n?1 O(n) O(n) 插入第n+1个元素，不移动 删除第n个元素，不移动 插入、删除需移动大量元素O(n)；但在尾端插入、删除效率高O(1)。5. 其他算法a) InitList (&L), ClearList (&L)L.length = 0;b) ListEmpty (L)return L.length == 0;c) ListLength (L)return L.d) GetElem (L, i, &e)e = L.elem[i-1];单链表――线性表的链式存储结构之一6. 概念线性链表，单链表，结点；数据域，指针域；头指针，头结点。7. 特点用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）。8. 类型定义5简而言之，“数据 + 指针”。typedef struct LNode {DataTstruct LNode *} LNode, *LinkL9. 基本形态带头结点的单链表的基本形态有：a) 单链表空条件： L-&next == 0b) 单链表不空条件：L-&next != 0
10. 基本算法
a) 顺序访问所有元素借助指针，“顺藤摸瓜”(沿着链表访问结点)。 ．．．．p = L-&
// 注意起始位置的考虑while ( p!=NULL ) {
// 判表尾，另外 (p!=0)或(p)均可
visit( p-&data );
// 访问:可以换成各种操作
// 指针沿着链表向后移动 }
例：打印单链表中的数据。void PrintLinkList ( LinkList L ){p = L-&while ( p!=NULL ) {print ( p-&data );
// 访问：打印数据域p = p-&}}b) 查找元素x// 在单链表L中查找元素x// 若找到，返回指向该结点的指针；否则返回空指针LinkList Find ( LinkList L, DataType x ){p = L-&while ( p!=NULL ) {if ( p-&data == x )
// 找到xp = p-&} 5 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
return NULL;
// 未找到}
// 在单链表L中查找元素x// 若找到，返回该元素的位序；否则返回0 int Find ( LinkList L, DataType x ){p = L-&
j = 1;while ( p!=NULL ) {if ( p-&data == x )
// 计数器随指针改变
}return 0;
// 未找到}
前一个算法的另一种写法：p = L-&while ( p && p-&data!=x )p = p-&if ( p && p-&data==x )else
或者p = L-&while ( p && p-&data!=x )
// 为什么c) 查找第i个元素LinkList Get ( LinkList L, int i ){p = L-&
j = 1;while ( p && j&i ) {p = p-&
j++;}if ( p && j==i )else
return 0;}d) 查找第i-1个元素p = L;
j = 0;while ( p && j&i-1 ) {p = p-&
j++;}if ( p && j==i-1 )else
return 0;11. 插入算法 ListInsert(&L,i,x)技巧：画图辅助分析。思路：先查找第i-1个元素若找到，在其后插入新结点
6bool ListInsert ( LinkList &L, int i, DataType x ){// 查找第i-1个元素pp = L;
j = 0;while ( p && j&i-1 ) {插入前
j++;}// 若找到，在p后插入x
if ( p && j==i-1 ) {执行①之后
s = (LinkList) malloc(sizeof(LNode));s-&data =s-&next = p-&
// ②执行②之后
// 插入成功}else
// 插入失败}
注意：a) 要让p指向第i-1个而不是第i个元素（否则，不容易找到前驱以便插入）。b) 能够插入的条件： p && j==i-1 。即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素。c) 新建结点时需要动态分配内存。s = (LinkList) malloc(sizeof(LNode));若检查是否分配成功，可用if ( s==NULL )
// 分配失败则终止程序d) 完成插入的步骤：①②。技巧：先修改新结点的指针域。
12. 删除算法 ListDelete(&L,i,&x)思路：先查找第i-1个元素若找到且其后存在第i个元素，则用x返回数据，并删删除前
除之bool ListDelete ( LinkList &L, int i, int &x )执行①之后 { 6 这里返回true表示正确插入，返回false表示插入失败。
// 查找第i-1个元素pp = L;
j = 0;while ( p && j&i-1 ) {p = p-&
j++;}//若存在第i个元素，则用x返回数据，并删除之if ( p && j==i-1 && p-&next ) { // 可以删除s = p-&
// ①p-&next = s-&
// ②x = s-&free (s);}else}
注意：a) 要求p找到第i-1个而非第i个元素。为什么？b) 能够进行删除的条件： p && j==i-1 && p-&next 。条件中的p-&next就是要保证第i个元素存在，否则无法删除。若写成p-&next && j==i-1也不妥，因为此时(循环结束时)可能有p==NULL，所以必须先确定p不空。技巧：将条件中的“大前提”放在前面。该条件也不可以写成p-&next && p && j==i-1，因为先有p!=0才有p-&next，上式颠倒了这一关系。c) 释放结点的方法。 free(s);d) 完成删除的步骤：①②。
13. 建立链表的两种方法思路：建立空表（头结点）；依次插入数据结点（每次插入表尾得(a1,a2,?,an)，每次插入表头得(an,?,a2,a1)）。 a) 顺序建表void CreateLinkList ( LinkList &L, int n){// 建立空表L = (LinkList) malloc(sizeof(LNode));L-&next = NULL;
// 空表p = L;
// 用p指向表尾// 插入元素for ( i=0; i&n; i++ ) {scanf ( x );s = (LinkList) malloc(sizeof(LNode));s-&data =// 插入表尾s-&next = p-&p-&next =p =
// 新的表尾}}b) 逆序建表void CreateLinkList ( LinkList &L, int n){// 建立空表L = (LinkList) malloc(sizeof(LNode));L-&next = NULL;
// 空表// 插入元素for ( i=0; i&n; i++ ) {scanf ( x );s = (LinkList) malloc(sizeof(LNode));s-&data =// 插入表头s-&next = L-&L-&next =}}循环链表14. 特点最后一个结点的指针指向头结点。15. 类型定义同单链表。16. 基本形态空表：L-&next == L。非空表。
17. 与单链表的联系判断表尾的方法不同：单链表用p==NULL；循环链表用p==L。其余操作相同。双向循环链表18. 特点一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链表。19. 类型定义typedef struct DuLNode {DataTstruct DuLNode *prior, *
// 两个 指针 } DuLNode, *DuLinkL20. 基本形态空表：用后向指针判断L-&next == L，或者用前向指针判断L-&prior == L。非空表。
21. 与单链表和循环链表的联系最大不同：前驱容易求得，可以向前遍历。 判断表尾的方法与循环链表相同：p==L。 插入和删除时需要修改两个方向的指针。 22. 插入和删除需要修改两个方向的指针。例如：(见下表)表 错误！文档中没有指定样式的文字。.2 双向循环链表的插入和删除
顺序表与单链表的比较
第三章、栈和队列 栈栈，栈顶，栈底，空栈，后进先出(LIFO)，入栈(Push)，出栈(Pop)。 顺序栈：栈的顺序存储结构；链栈：栈的链式存储结构。 链栈存储结构用不带头结点的单链表实现。 类型定义 同单链表。 基本形态 a) 栈空条件: S == NULLSS S/\b) 栈非空c) 栈满（一般不出现）基本算法d) 入栈 Push (&s, x)bool Push ( LinkList &s, DataType x ) {// 新建结点p = (LinkList) malloc (sizeof(LNode));
if ( !p ) // 失败
p-&data =// 插入栈顶p-&next =s =}e) 出栈 Pop (&s, &x)前提：栈非空。bool Pop ( LinkList &s, DataType &x ) {if ( s==NULL )
// 删除栈顶元素p =s = s-&x = p-&free ( p );}f) 栈顶元素前提：栈非空。bool Top ( LinkList &s, DataType &x ) {if ( s==NULL )
x = s-&}顺序栈存储结构类似于顺序表，插入和删除操作固定于表尾。 类型定义7简单说，“数组 + 长度”。 7 不准确的说法，只为便于理解和记忆，不要在正式场合引用。const int MAXSIZE = 栈的最大容量；typedef struct {DataType elem[MAXSIZE];} SqS基本形态g) 栈空条件
s.top == 0;h) 栈满条件
s.top == MAXSIZEi) 栈不空、不满
基本算法j) 入栈
Push (&s, x)前提：栈不满bool Push ( SqStack& s, DataType x ){if ( s.top == MAXSIZE )
s.elem[top] =
// 或者s.elem[top++] =
代替这两行}k) 出栈
Pop (&s, &x)前提：栈非空bool Pop ( SqStack &s, DataType &x ){if ( s.top==0 )top--;
// 可用x=s.elem[--top];
x = s.elem[top];
代替这两行}l) 栈顶元素前提：栈非空s.elem[top-1] 即是。队列队列，队头，队尾，空队列，先进先出(FIFO)。链队列：队列的链式存储结构。循环队列：队列的顺序存储结构之一。链队列存储结构简而言之，“单链表 + 尾指针”。类型定义课本P61。typedef struct {LinkLLinkL} LinkQ基本形态队列空：Q.front==Q.rear。非空队列。基本算法m) 入队列课本P62。插入队尾，注意保持Q.rear指向队尾。n) 出队列课本P62。删除队头元素，特别注意：如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。循环队列存储结构9简单说，“数组 + 头、尾位置”。类型定义const int MAXSIZE = 队列最大容量;typedef struct {DataType elem[MAXSIZE];int front,
// 队头、队尾位置} SqQ基本形态通常少用一个元素区分队列空和队列满，也可以加一标志。约定front指向队头元素的位置，rear指向队尾的下一个位置，队列内容为 [front, rear)。o) 队列空条件：Q.front == Q.rear。不能出队列。p) 队列满条件：(Q.rear+1)%MAXSIZE == Q.front （少用一个元素时）。不能入队列。 8Q.front Q.rear Q.front Q.rear 89 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
不准确的说法，只为便于理解和记忆，不要在正式场合引用。
q) 队列不空也不满
tag:1r) 加一标志区分队列空和队列满的情况可以用满所有空间。队列空和队列满时都有Q.front==Q.rear，再用标志区分。队列空：Q.front==Q.rear and Q.tag==0；队列满：Q.front==Q.rear and Q.tag==1。 基本算法s) 入队列前提：队列不满。bool EnQueue ( SqQueue &Q, DataType x ){if ( (Q.rear+1)%MAXSIZE==Q.front )
// 队列满// 入队列Q.elem [Q.rear] =Q.rear = (Q.rear+1)%MAXSIZE;}t) 出队列前提：队列非空。bool DeQueue ( SqQueue &Q, DataType &x ){if ( Q.front==Q.rear )
// 队列空// 出队列x = Q.elem [Q.front];Q.front = (Q.front+1)%MAXSIZE;}u) 队列中元素个数结论：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。注：Q.rear-Q.front可能小于0，需要加上MAXSIZE。int QueueLength ( SqQueue Q ){return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;}v) 用标志区分队列空和满用标志区分队列空和满时，队列初始化、入队列、出队列和队列长度的算法如下： void InitQueue ( SqQueue &Q ) {
Q.front = Q.rear = 0;
Q.tag = 0;}bool EnQueue ( SqQueue &Q, DataType x ) {if ( Q.front==Q.rear and Q.tag==1 )Q.elem[ Q.rear ] =Q.rear = (Q.rear+1)%MAXSIZE;if ( Q.tag==0 )
Q.tag = 1;
// 队列非空}bool DeQueue ( SqQueue &Q, DataType &x ) {if ( Q.front==Q.rear and Q.tag==0 )x = Q.elem[ Q.front ];Q.front = (Q.front+1)%MAXSIZE;if ( Q.front==Q.rear )
Q.tag = 0;
// 队列空}int QueueLength ( SqQueue Q ){if ( Q.front==Q.rear and Q.tag==1 )return MAXSIZE;
// 队列满elsereturn (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
// 队列不满(包含队列空的情况) }栈和队列比较都是线形结构，栈的操作LIFO（后进先出），队列操作FIFO（先进先出）。简化的栈和队列结构在算法中使用栈和队列时可以采用简化的形式。表 错误！文档中没有指定样式的文字。.4 简化的栈和队列结构
栈和队列的应用w) 表达式求值参见课本P53。x) 括号匹配例：检查表达式中的括号是否正确匹配。如{ ( ) [ ] }正确，( [ ) ] }则错误。 分析：每个左括号都“期待”对应的右括号，匹配成功则可以消去。思路：遇到左括号则入栈，遇到右括号则与栈顶括号相比较，如果匹配则消去，否则匹配失败。当然，如果栈中没有括号可以匹配，或者最后栈中还有未匹配的左括号，也都是匹配错误。// 检查输入的表达式中括号是否匹配bool MatchBrackets (){const int MAXSIZE = 1024;
// 栈的最大容量char s [MAXSIZE];
// 简化的栈结构
// 栈顶// 栈初始化top = 0;// 检查括号是否匹配ch = getchar();while ( ch!=EOF ) {switch ( ch ) {case ‘(‘, ‘[’, ‘{’:s [top++] =
// 所有左括号入栈case ‘)’:if ( top==0 or s [--top]!=’(’ )
// 栈空或右括号与栈顶左括号失配case ‘]’:if ( top==0 or s [--top]!=’[’ )case ‘}’:if ( top==0 or s [--top]!=’{’ )}ch = getchar();
// 取下一个字符}if ( top==0 )
// 正好匹配
// 栈中尚有未匹配的左括号}y) 递归程序的非递归化将递归程序转化为非递归程序时常使用栈来实现。z) 作业排队如操作系统中的作业调度中的作业排队，打印机的打印作业也排成队列。aa) 按层次遍历二叉树void LevelOrder ( BinTree bt, VisitFunc visit ){const int MAXSIZE = 1024;
// 队列容量(足够大即可)BinTree q [MAXSIZE];
// 简化的队列结构int front,
队头、队尾
if ( ! bt )// 初始化队列，根结点入队列front = rear = 0;q [rear] =rear = (rear+1)%MAXSIZE;// 队列不空，则取出队头访问并将其左右孩子入队列while ( front!=rear ) {p = q [front];front = (front+1)%MAXSIZE;if ( p ) {visit ( p-&data );
// 访问结点q [rear] = p-&rear = (rear+1)%MAXSIZE;q [rear] = p-&rear = (rear+1)%MAXSIZE;}}}第四章串基础知识和算法概念串，空串，空格串，串的长度；子串，子串在主串中的位置，主串；串相等。 串的基本操作 表 错误！文档中没有指定样式的文字。.5 串的基本操作Assign (s, t), Create(s, cs)Equal (s, t), Length(s)Concat (s, t)Substr (s, pos, len)Index (s, t)Replace (s, t, v)Delete (s, pos, len) Assign(s,t)将变量t赋值给s，Create(s,cs)根据字串创建变量s。 判断串相等，求串长度。如Length(“”)=0。 串连接。如Concat(“ab”,”cd”)=”abcd”。 取子串，pos为开始位置，len为子串长度。 求子串t在主串s中的位置。如Index(“abc”,”ab”)=1，Index(“a bc”,”bc”)=3。 把串s中的字串t替换成v。如Replace(“aaa”,”aa”,”a”)=”aa”。 删除串s的一部分。注：完成习题集4.1~4.6。串的存储结构表 错误！文档中没有指定样式的文字。.6 串的存储结构定长顺序串堆分配存储表示块链存储表示基础知识和算法树及有关概念 最大长度固定，超过最大长度则作截断处理 串的长度几乎没有限制 块内存储空间连续，块间不连续 树和二叉树树，根，子树；结点，结点的度，叶子（终端结点），分支结点（非终端结点），内部结点，树的度；孩子，双亲，兄弟，祖先，子孙，堂兄弟；层次（根所在层为第1层），深度，高度；有序树，无序树，二叉树是有序树；森林。二叉树二叉树（二叉树与度为2的树不同，二叉树的度可能是0，1，2）；左孩子，右孩子。 二叉树的五种基本形态。二叉树的性质10i-1bb) 二叉树的第i层上至多有2个结点。kcc) 深度为k的二叉树至多有2-1个结点。k
满二叉树：深度为k，有2-1个结点。完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。dd) 叶子结点n0，度为2的结点为n2，则n0 = n2+1。考虑结点个数：n = n0 + n1 + n2考虑分支个数：n-1 = 2n2 + n1可得n0 = n2+1例：1) 二叉树有n个叶子，没有度为1的结点，共有
个结点。 2) 完全二叉树的第3层有2个叶子，则共有
个结点。分析：1) 度为2的结点有n-1个，所以共2n-1个结点。 2) 注意考虑到符合条件的二叉树的深度可能是3或4，所以有5、10或11个结点。ee)ff) n个结点的完全二叉树深度为?logn??1。 n个结点的完全二叉树，结点按层次编号有：
i的双亲是?n/2?，如果i = 1时为根（无双亲）；i的左孩子是2i，如果2i&n，则无左孩子；i的右孩子是2i + 1，如果2i + 1&n则无右孩子。二叉树的存储结构gg) 顺序存储结构用数组、编号i的结点存放在[i-1]处。适合于存储完全二叉树。hh) 链式存储结构二叉链表：typedef struct BTNode {DataTstruct BTNode *lchild, *} BTNode, *BinT三叉链表：typedef struct BTNode {DataTstruct BTNode *lchild, *rchild, *} BTNode, *BinT 10 本书中约定根结点在第1层，也有约定根在第0层的，则计算公式会有所不同。
例：用二叉链表存储n个结点的二叉树(n&0)，共有(_a_)个空指针域；采用三叉链表存储，11共有(_b_)个空指针域。二叉树的五种基本形态① ②①空树：bt==NULL
②左右子树均空：bt-&lchild==NULL and bt-&rchild==NULL ③右子树为空：bt-&rchild==NULL
④左子树为空：bt-&lchild==NULL⑤左右子树均非空。前两种常作为递归结束条件，后三者常需要递归。遍历二叉树ii) 常见有四种遍历方式按层次遍历，先序遍历，中序遍历，后序遍历。 按层次遍历：“从上至下，从左至右”，利用队列。
先序遍历：DLR；中序遍历：LDR；后序遍历LRD。
例：写出a+b*(c-d)-e/f的前缀、中缀和后缀表达式。 画出二叉树，分别进行前序、中序、后序遍历即可得到。前缀表达式：- + a * b - c d / e f中缀表达式：a + b * c - d - e / f后缀表达式：a b c d - * + e f / -
jj) 先序遍历算法void Preorder ( BinTree bt ){if ( bt ) {visit ( bt-&data );Preorder ( bt-&lchild );Preorder ( bt-&rchild );}}kk) 中序遍历算法void Inorder ( BinTree bt ){if ( bt ) {Inorder ( bt-&lchild );visit ( bt-&data );Inorder ( bt-&rchild );11 答案：(a) n+1 (b) n+2。提示：只有根结点没有双亲。}}ll) 后序遍历void Postorder ( BinTree bt ){if ( bt ) {Postorder ( bt-&lchild );Postorder ( bt-&rchild );visit ( bt-&data );}}mm) 按层次遍历思路：利用一个队列，首先将根（头指针）入队列，以后若队列不空则取队头元素p，如果p不空，则访问之，然后将其左右子树入队列，如此循环直到队列为空。void LevelOrder ( BinTree bt ){// 队列初始化为空InitQueue ( Q );// 根入队列EnQueue ( Q, bt );// 队列不空则继续遍历while ( ! QueueEmpty(Q) ) {DeQueue ( Q, p );if ( p!=NULL ) {visit ( p-&data );// 左、右子树入队列EnQueue ( Q, p-&lchild );EnQueue ( Q, p-&rchild );}}}
若队列表示为“数组q[] + 头尾 front, rear”有：void LevelOrder ( BinTree bt ){const int MAXSIZE = 1024;BinTree q[MAXSIZE];int front,// 队列初始化为空front = rear = 0;// 根入队列q[rear] =
rear = ( rear+1 ) % MAXSIZE;// 队列不空则循环while ( front != rear ) {p = q[front];
front = ( front+1 ) % MAXSIZE;if ( p ) {visit ( p-&data );// 左、右子树入队列q[rear] = p-&
rear = ( rear+1 ) % MAXSIZE;q[rear] = p-&
rear = ( rear+1 ) % MAXSIZE;}}}nn) 非递归遍历二叉树一般借助栈实现。设想一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。 (a) 中序非递归遍历指针p从根开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访问结点，然后移动到右子树上去。void InOrder ( BinTree bt, VisitFunc visit ){InitStack ( S );p =while ( p || ! StackEmpty(S) ) {if ( p ) {Push ( S, p );p = p-&} else {Pop ( S, p );visit ( p );
// 中序访问结点的位置p = p-&}}}(b) 先序非递归遍历按照中序遍历的顺序，将访问结点的位置放在第一次指向该结点时。void Preorder ( BinTree bt, VisitFunc visit ){InitStack ( S );p =while ( p || ! StackEmpty(S) ) {if ( p ) {visit ( p );
// 先序访问结点的位置Push ( S, p );p = p-&} else {Pop ( S, p );p = p-&}}}或者，由于访问过的结点便可以弃之不用，只要能访问其左右子树即可，写出如下算法。 void Preorder ( BinTree bt, VisitFunc visit ){InitStack ( S );Push ( S, bt );while ( ! StackEmpty(S) ) {Pop ( S, p );if ( p ) {visit ( p );Push ( S, p-&rchild );
// 先进栈，后访问，所以Push ( S, p-&lchild );
这里先让右子树进栈}}}(c) 后序非递归遍历后序遍历时，分别从左子树和右子树共两次返回根结点，只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。void PostOrder ( BinTree bt, VisitFunc visit ){InitStack ( S ),
InitStack ( tag );p =while ( p || ! StackEmpty(S) ) {if ( p ) {Push ( S, p ),
Push ( tag, 1);
// 第一次入栈p = p-&} else {Pop ( S, p ),
Pop ( tag, f );if ( f==1 ) {// 从左子树返回，二次入栈，然后p转右子树Push ( S, p ),
Push ( tag, 2 );p = p-&} else {// 从右子树返回(二次出栈)，访问根结点，p转上层visit ( p );p = NULL;
// 必须的，使下一步继续退栈}}}}注：后序非递归遍历的过程中，栈中保留的是当前结点的所有祖先。这是和先序及中序遍历不同的。在某些和祖先有关的算法中，此算法很有价值。oo) 三叉链表的遍历算法下面以中序遍历为例。// 中序遍历三叉链表存储的二叉树void Inorder ( BinTree bt, VisitFunc visit ){if ( bt==NULL )
// 空树，以下考虑非空树// 找到遍历的起点p =
// Note: p!=null herewhile ( p-&lchild )
p = p-&// 开始遍历while ( p ) {// 访问结点visit ( p );// p转下一个结点if ( p-&rchild ) {
// 右子树不空，下一个在右子树p = p-&while ( p-&lchild )
转右子树的最左下结点
// 右子树为空，下一个在上层f = p-&while ( p == f-&rchild ) {
若p是右子树则一直上溯p =
f = f-&}}}}遍历二叉树的应用 pp) 写出遍历序列（前、中、后序）qq) 根据遍历序列画出二叉树(a) 已知前序和中序序列，唯一确定二叉树。 例：前序：ABDEGCFH，中序：DBGEAFHC，画出二叉树。分析：前序序列的第一个是根，这是解题的突破口。步骤：①前序序列的第一个是根 ②在中序序列中标出根，分成左右子树 ③在前序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的前序和中序序列重复以上步骤直至完成。(b) 已知后序和中序序列，唯一确定二叉树。例：后序：DGEBHFCA，中序：DBGEAFHC，画出二叉树。分析：后序序列的最后一个是根，这是解题的突破口。步骤：①后序序列的最后一个是根 ②在中序序列中标出根，分成左右子树 ③在后序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的后序和中序序列重复以上步骤直至完成。(c) 已知前序和后序序列，不存在度为1的结点时能唯一确定二叉树。例：前序：ABDEC，后序：DEBCA，画出二叉树。又前序AB，后序BA则不能唯一确定二叉树。
注：对于不存在度为1的结点的二叉树，首先确定根结点，然后总可以将其余结点序列划分成左右子树，以此类推即可确定二叉树。
说明：画出二叉树后可以进行遍历以便验证。rr) 编写算法思路：按五种形态(①--⑤)分析，适度简化。例：求二叉树结点的个数。分析：① 0; ② 1; ③ L+1; ④ 1+R; ⑤ 1+L+R。简化：② 1+L=0+R=0 ③ 1+L+R=0 ④ 1+L=0+R ⑤ 1+L+R 可合并成⑤一种情况。int NodeCount ( BinTree bt ){if ( bt==0 )
return 0;else
return 1 + NodeCount(bt-&lchild) + NodeCount(bt-&rchild);}
例：求二叉树叶子结点的个数。分析：① 0; ② 1; ③ L; ④ R; ⑤ L+R。简化：③④⑤可合并成⑤。int LeafCount ( BinTree bt ){if ( bt==0 )
return 0;else if ( bt-&lchild==0 and bt-&rchild==0 )
return 1;else
return LeafCount(bt-&lchild) + LeafCount(bt-&rchild);}
例：求二叉树的深度。分析：① 0; ② 1; ③ 1+L; ④ 1+R; ⑤ 1+max(L,R)。简化：②③④⑤可合并成⑤。 int Depth ( BinTree bt ){if ( bt==0 )
return 0;else
return 1 + max(Depth(bt-&lchild), Depth(bt-&rchild));}线索二叉树ss) 线索n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。
lchild 有左子树，则指向左子树，标志ltag == 0；没有左子树，可作为前驱线索，标志ltag == 1。rchild 有右子树，则指向右子树，标志rtag == 0；没有右子树，可作为后继线索，标志rtag == 1。tt) 线索化二叉树利用空指针作为线索指向前驱或后继。左边空指针可以作为前驱线索，右边空指针可以作为后继线索，可以全线索化或部分线索化。表 错误！文档中没有指定样式的文字。.7 线索化二叉树的类型中序线索化 前序线索化 后序线索化uu) 画出线索二叉树思路：先写出遍历序列，再画线索。 步骤： 标出必要的空指针（前驱?左指针；后继?右指针，要点：“不要多标，也不要少标”）。
写出对应的遍历序列（前序，中序或后序）。
对照遍历结果画线索。例：画出图中二叉树的后序后继线索。步骤：先标出所有空的右指针(DGCH)；写出后序遍历结果：DGEBHFCA；标出后继线索：D?G, G?E,C?A, H?F。如图。
vv) 遍历线索二叉树反复利用孩子和线索进行遍历，可以避免递归。 树和森林ww) 树的存储结构双亲表示法，孩子表示法，孩子兄弟表示法。特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。 xx) 树与二叉树的转换表 错误！文档中没有指定样式的文字。.8 树和二叉树的对应关系
前驱、后继线索 中序全线索 前序全线索 后序全线索前驱线索 中序前驱线索 前序前驱线索 后序前驱线索后继线索 中序后继线索 前序后继线索 后序后继线索特点：由树转化成的二叉树，根结点没有右孩子 例：树转换成二叉树。
yy) 森林与二叉树的转换森林中第1棵树的根作为对应的二叉树的根；其他的树看作第1棵树的兄弟；森林中的树转换成对应的二叉树。则森林转换成对应的二叉树。 例：将森林转换成对应的二叉树。参见课本P138。 zz) 树的遍历树的结构：①根，②根的子树。先根遍历：①②。例：ABCDEFGHIJK。 后根遍历：②①。例：CEDFBHGJKIA。 aaa) 遍历森林森林的结构：①第一棵树的根，②第一棵树的根的子树森林，③ 其余树(除第一棵外)组成的森林。先序遍历：①②③。例：ABCDEFGHIJ。 中序遍历：②①③。例：BDCEAGFIJH。 注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。树的结构划森林的结构划分
bbb) 遍历树、森林与遍历二叉树的关系表 错误！文档中没有指定样式的文字。.9 遍历树、森林和二叉树的关系树 先根遍历 后根遍历森林 先序遍历 中序遍历二叉树 先序遍历 中序遍历
赫夫曼树及其应用ccc) 最优二叉树(赫夫曼树，哈夫曼树)树的带权路径长度：所有叶子结点的带权路径长度之和。WPL??wklkk?1n路径长度lk按分支数目计算。带权路径长度最小的二叉树称为最优二叉树，或赫夫曼树(哈夫曼树)。 ddd) 构造赫夫曼树 算法：参见课本P145。12简单说，“每次取两个最小的树组成二叉树”。 eee) 赫夫曼编码(前缀码)向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。例：字符及其权值如下：A(6), B(7), C(1), D(5), E(2), F(8)，构造哈夫曼树和哈夫曼编码，计算带权路径长度。12不准确的说法，只为便于理解和记忆，不要在正式场合引用。
哈夫曼编码： A:00 B:01 C:1110 D:110 E:1111WPL = (6+7+8)*2+5*3+(1+2)*4 = 69或采用课本上的算法计算，如下。
说明：同样的一组权值可能构造出不同的哈夫曼树，结果不一定唯一，但带权路径长度都是最小的。 技巧：要使前一种方法构造出的赫夫曼树和课本上算法产生的一样，只要把每次合并产生的二叉树放在树的集合的末尾，并且总是用两个最小树的前者作为左子树后者作为右子树。图基础知识和算法图的有关概念图，顶点，弧，弧头，弧尾；有向图（顶点集+弧集），0≤e≤n(n-1)，无向图（顶点集+边集），0≤e≤n(n-1)/2；稀疏图（e&nlogn），稠密图；完全图e=n(n-1)/2，有向完全图e=n(n-1)；网，有向网，无向网。子图，邻接点，顶点的度，入度，出度；路径，路径长度（经过边或弧的数目），简单路径，回路（环），简单回路（简单环）；连通图，连通分量，强连通分量。例：有6个顶点组成的无向图构成连通图，最少需要(_a_)条边；当边的数目大于(_b_)时，该图必定连通。分析：a. 5。最少有n-1条边就可以构成连通图。 b. 10。考虑将n个顶点分成两组，一组有n-1个顶点，另一组只有1个顶点。首先在第一组中添加边，直到n-1个顶点构成全连通子图，共(n-1)(n-2)/2条边，此后若再在图中任意添加一条边将必定连通两组顶点，从而构成连通图。思考：对有向图有何结论。图的存储结构图的存储结构常见图的存储结构有：邻接矩阵，邻接表，逆邻接表，十字链表，邻接多重表。 邻接多重表只适用于存储无向图，其他存储结构可以存储无向图和有向图。
例：画出图的邻接矩阵、邻接表、逆邻接表和十字链表。邻接矩阵 13简言之，“数组(顶点)+二维数组(弧)+个数”。const int MAX_VERTEX = 最大顶点个数;typedef struct Graph {
// 图VertexType
vexs[MAX_VERTEX]; // 顶点向量
arcs[MAX_VERTEX] [MAX_VERTEX];
// 邻接矩阵int
vexnum, // 顶点和弧的个数} G
图：有边(弧)为1；否则为0。网：有边(弧)为权值；否则为∞。2存储空间个数为n，与边的数目无关。无向图的邻接矩阵是对称的。ABCDE
邻接表13 不准确的说法，只为便于理解和记忆，不要在正式场合引用。简言之，“数组(弧尾顶点)+链表(邻接点)+个数”。typedef struct ArcNode {
// 弧结点 // 邻接点struct ArcNode * // 下一个邻接点} ArcN
typedef struct VexNode {
// 顶点结点VertexT // 顶点信息ArcNode * // 第一个邻接点} VexN
const int MAX_VERTEX = 最大顶点个数;typedef struct Graph {
// 图VexNode
vexs[MAX_VERTEX]; // 顶点向量int
vexnum, // 顶点和弧的个数} G
边(弧)多则需要存储空间多。14
逆邻接表15简言之，“数组(弧头顶点)+链表(逆邻结点)+个数”。类型定义类似邻接表。
十字链表16简言之，“数组(顶点)+弧结点(含头和尾)+个数”。边可以看作两条弧。typedef struct ArcNode {
// 弧结点int
vtail, // 弧尾和弧头顶点编号struct ArcNode
*nexttail, * // 指向同弧尾和同弧头的弧结点 } ArcN
141516 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
不准确的说法，只为便于理解和记忆，不要在正式场合引用。
不准确的说法，只为便于理解和记忆，不要在正式场合引用。typedef struct VexNode {
// 顶点结点VertexT // 顶点信息ArcNode
*firstin, * // 指向第一条入弧和第一条出弧 } VexN
const int MAX_VERTEX = 最大顶点个数;typedef struct Graph {
// 图VexNode
vexs[MAX_VERTEX]; // 顶点向量int
vexnum, // 顶点和弧的个数} G
弧结点中包含两个指针分别指向同一弧头的下一个弧和同一个弧尾的下一个弧。顶点结点则指向第一个同弧头和弧尾的弧。十字链表相当于邻接表和逆邻接表的结合。
技巧：把弧结点按行排整齐，然后画链表。同弧尾的弧组成链表，同弧头的弧组成链表。 邻接多重表17简言之，“数组(顶点)+边结点”。typedef struct EdgeNode {
// 边结点int
vexi,struct EdgeNode
*nexti, *} EdgeN
typedef struct VexNode {
// 顶点结点VertexTypeEdgeNode
const int MAX_VERTEX = 最大顶点个数;typedef struct Graph {
// 图VexNode
vexs[MAX_VERTEX];int
vexnum,} G
只适合存储无向图，不能存储有向图。17// 边的两个顶点 // 两个顶点所依附的下一条边 // 顶点信息 // 指向第一条边 // 顶点向量 // 顶点和边的个数
不准确的说法，只为便于理解和记忆，不要在正式场合引用。
技巧：把边结点按列排整齐，然后画链表。相同顶点组成链表，这里没有起点和终点的区别。 图的遍历深度优先搜索遍历方法从图中某个顶点出发，访问此顶点，然后依次从其未被访问的邻接点出发深度优先遍历图；若图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问为止。分析方法方法：画一棵“深度优先搜索树”。
例：下图从A出发深度优先搜索的结果是：ABEDC。分析：画“深度优先搜索树”。从A出发，访问A(画圈作标记)，A的邻接点有B和C(作为A的孩子)，B未访问，访问B(画圈)，B的邻接点有E(作B的孩子)，...，以此类推，画出搜索树。深度优先搜索的过程就是沿着该搜索树先根遍历的过程。技巧：顶点的邻接点是无所谓次序的，所以同一个图的深度优先遍历序列可能不同，但在遍历时(除非邻接点的次序有明确规定)一般按照编号顺序安排邻接点的次序。
算法课本上的算法稍加改动：void DFSTraverse ( Graph G ){visited [0 .. G.vexnum-1] =
// 初始化访问标志为未访问(false)
for ( v=0; v&G. v++ )if ( ! visited[v] )
DFS ( G, v );
// 从未被访问的顶点开始DFS }
void DFS ( Graph G, int v ){visit ( v );
visited [v] =
// 访问顶点v并作标记for ( w=FirstAdjVex(G,v); w&=0; w=NextAdjVex(G,v,w) )if ( ! visited[w] )
DFS ( G, w );
// 分别从每个未访问的邻接点开始DFS }其中的FirstAdjVex(G,v)表示图G中顶点v的第一个邻接点，NextAdjVex(G,v,w)表示图G中顶点v的邻接点w之后v的下一个邻接点。深度优先搜索算法有广泛的应用，以上算法是这些应用的基础。广度优先搜索遍历方法从图中某顶点出发，访问此顶点之后依次访问其各个未被访问的邻接点，然后从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问，直至所有已被访问的顶点的邻接点都被访问。若图中尚有顶点未被访问，则另选图中未被访问的顶点作为起始点，重复以上过程，直到图中所有顶点都被访问为止。 广度优先搜索从某顶点出发，要依次访问路径长度为1，2，? 的顶点。分析方法方法：画一棵“广度优先搜索树”。
例：下图从A出发广度优先遍历的结果是：ABCED。分析：画“广度优先搜索树”。与深度优先搜索树类似，A为根，其邻接点为其孩子，访问一个顶点，则扩展出其孩子。不过广度优先搜索的访问次序是对该树按层遍历的结果。
算法利用队列(类似按层遍历二叉树)。void BFSTraverse ( Graph G ){visited [0 .. G.vexnum-1] =
// 初始化访问标志为未访问(false)
InitQueue ( Q );for ( v=0; v&G. v++ )if ( ! visited[v] )
{// 从v出发广度优先搜索visit ( v );
visited [v] =EnQueue ( Q, v );while ( ! QueueEmpty(Q) )
{DeQueue ( Q, u );for ( w=FirstAdjVex(G,u); w&=0; w=NextAdjVex(G,u,w) )if ( ! visited[w] )
{visit ( w );
visited [w] =EnQueue ( Q, w );
} }时间复杂度分析观察搜索树可以看出，无论是深度优先搜索还是广度优先搜索，其搜索过程就是对每个顶点求所有邻接点的过程。当用邻接表存储图时，其时间复杂度为O(n+e)；当采用邻接矩阵作2为存储结构时，时间复杂度是O(n) (因为求一个顶点的所有邻接点就是搜索邻接矩阵的一2行中的n个数，而顶点的个数为n，总共就是n)。 最小生成树最小生成树及MST性质 最小生成树。MST性质。注意：同一个连通网的最小生成树可能是不唯一的，但其代价都是最小(唯一的)。 克鲁斯卡尔算法18一句话，“不构成环的情况下，每次选取最小边”。
(a) 无向网(b)-(e) 克鲁斯卡尔算法计算最小生成树(f) 得到的最小生成树(g) 另一个可能的最小生成树
提示：在不要步骤、只要结果的情况下可采用，边较少时特别有效。 普里姆算法记V是连通网的顶点集，U是求得生成树的顶点集，TE是求得生成树的边集。 普里姆算法：18不准确的说法，只为便于理解和记忆，不要在正式场合引用。(a) 开始时，U={v0}，TE=Φ；(b) 计算U到其余顶点V-U的最小代价，将该顶点纳入U，边纳入TE； (c) 重复(b)直到U=V。
例：用普里姆算法计算下图的最小生成树。
特点只与顶点个数n有关 与边的数目e无关 适用于稠密图只与边的数目e有关 与顶点个数n无关 适用于稀疏图拓扑排序有向无环图(DAG)，AOV网；拓扑排序。19拓扑排序，一句话“每次删除入度为0的顶点并输出之”。例：以下DAG图拓扑排序的结果是：ABCDE。 注意：拓扑排序的结果不一定是唯一的。如：ACBDE也是以上DAG图的拓扑有序序列。 关键路径AOE网，关键路径AOE 网(活动在边上)，边代表活动或任务，顶点代表事件。 事件i发生后，其后继活动a(i,*)都可以开始；只有所有先导活动a(*,j)都结束后，事件j才发生。关键路径算法问题：a) 整个工程完工需要多长时间？ b) 哪些活动影响工程的进度？或求关键路径。 事件(顶点) i： 最早发生时间ve(i)，最晚发生时间vl(i)； 活动(边) a(i,j)： 最早开始时间e(i,j)，最晚开始时间l(i,j)。于是，整个工程完工的时间就是终点的最早发生时间；关键路径就是路径长度最长的路径。 19不准确的说法，只为便于理解和记忆，不要在正式场合引用。
求关键路径的算法：(a) 按拓扑有序排列顶点：对顶点拓扑排序； (b) 计算ve(j)：
?ve(1)?0,其中*为任意前驱事件； ??ve(j)?max{ve(*)?a(*,j)}?vl(n)?ve(n),其中*为任意后继事件； ??vl(i)?min{vl(*)?a(i,*)}(c) 计算vl(i)：(d) 计算e(i,j)和l(i,j)：e(i,j)?ve(i),
l(i,j)?vl(j)?a(i,j)(e) 结论：工程总用时ve(n)，关键活动是e(i,j)=l(i,j)的活动a(i,j)。 说明：
1. 若只求工程的总用时只要进行步骤(a)-(b)即可求得。 02. 如何理解计算ve(j)和vl(i)的公式：事件j在所有前驱活动都完成后发生，所以其最早发生时间ve(j) = max{ve(*)+a(*,j)}，即取决于最慢的前驱活动。另一方面，事件i发生后所有后继活动都可以开始了，所以其最晚发生时间vl(i) = min{vl(*)-a(i,*)}，即不耽误最慢的后继活动。例：某工程的AOE网如下，求1) 整个工程完工需要多长时间，2) 关键路径。说明：图中的虚线仅表示事件的先后关系，不代表具体活动。
分析：按照拓扑有序排列顶点，然后“从前往后”计算事件的最早发生时间得到总时间，再“从后往前”计算事件的最晚发生时间，最后计算活动的最早和最晚开始时间得到关键活动和关键路径。表 错误！文档中没有指定样式的文字。.12 关键路径
所以，1) 工程完工需要时间15，2) 关键路径是1?2?5?6?8?9。 最短路径迪杰斯特拉算法求一个顶点到其他各顶点的最短路径。算法：(a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞； (b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径； (c) 修改最短路径：计算u的邻接点的最短路径，若(v,?,u)+(u,w)&(v,?,w)，则以(v,?,u,w)代替。(d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。 特点：总是按照从小到大的顺序求得最短路径。例：用迪杰斯特拉算法求下图中A到其余顶点的最短路径。
(比原来)有更短路径即可，这弗洛伊德算法求每对顶点之间的最短路径。(0)(1)(n)(0)(k)(k)(k-1)依次计算A，A，?，A。A为邻接矩阵，计算A时，A(i,j)=min{A(i,j), (k-1)(k-1)A(i,k)+A(k,j)}。(k)技巧：计算A的技巧。第k行、第k列、对角线的元素保持不变，对其余元素，考查A(i,j)20与A(i,k)+A(k,j) （“行+列”），如果后者更小则替换A(i,j)，同时修改路径。例：用弗洛伊德算法计算图中各顶点之间的最短路径。20第k列i“行”元素加上第k行j“列”元素。
3第4列也不变，这样，只剩下A(4,2)和A(4,3)需要计算。查找基础知识和算法 有关概念查找表，静态查找表（只进行“查找”），动态查找表（可“查找”，“插入”，“删除”）。 关键字，平均查找长度ASL??picii?1npi第i个关键字出现的概率，ci比较的关键字的个数。静态查找表，顺序查找表，折半查找表，静态树表，次优查找树，索引顺序表。 动态查找表，二叉排序树，平衡二叉树（AVL树），B-树，B+树，键树，哈希表。 顺序查找思路按顺序逐个比较，直到找到或找不到。算法程序，要灵活应用。例如：在数组a的前n个元素中查找x int Search ( int a[], int n, int x ) {for ( i=n-1; i&=0; i-- )
if ( a[i]==x )
return -1;
// -1表示找不到 }编程技巧：所有执行路径都要有正确的返回值，不要忘记最后那个return语句。 应试技巧：题目要求不明确时，按照方便的方法做，用适当的注释说明。分析顺序查找特点：思路简单(逐个比较)，适用面广(对查找表没有特殊要求)。平均查找长度一般在等概率情况下，查找成功时，平均查找长度
ASL?1?2?...?nn?1 ?n2思路：假设对每个元素进行1次查找，共进行n次查找，计算出进行比较的关键字的个数，然后除以查找次数n，就求得平均查找长度。例：10个元素的表等概率情况下查找成功时的平均查找长度
ASL?1?2?...?10?5.5 10判定树判定树是一种描述查找中比较过程的直观形式，个关键字所在层次就是其查找长度，有利于分析找过程。顺序查找的判定树是一棵深度为n的单支的树。课本上顺序查找从an开始，当然也可以开始。每查分从a1
时间复杂度从平均查找长度看顺序查找的时间复杂度是O(n)。折半查找思路待查找的表必须是有序的，先从中间开始比较，比较一次至少抛弃一半元素，逐渐缩小范围，直到查找成功或失败。算法要熟练掌握该算法。设a[]升序有序，有以下算法：int BinarySearch ( DataType a[], int n, DataType x ){low = 0; high = n-1;while ( low &= high ) {mid = ( low + high )/2;
// 折半if ( a[mid]==x )
// 找到else if ( x&a[mid] )
// x位于低半区 [low..mid-1]high = mid C 1;else
// x位于高半区 [mid+1..high]low = mid + 1;}return -1;
// -1表示未找到}或者有递归版本：int BinarySearch ( DataType a[], int low, int high, DataType x )
{if ( low&high )
return -1;
// 查找失败mid = (low+high)/2;
// 折半if ( a[mid]==x )
// 找到else if ( x&a[mid] )return BinarySearch (a, low, mid-1, x);elsereturn BinarySearch (a, mid+1, high, x);}另外，程序可有多种写法。例：a[]递减有序，折半查找，请填空。int bs ( T a[], int n, T x ){i = n-1; j = 0;while (____a____) {
m = ____b____;if (____c____)
// succeededelse if (____d____)
i = ____e____;else
____f____;}return -1;
// not found21}分析特点：速度很快，要求查找表是有序的，而且随机访问(以便计算折半的下标)。所以，链表不能进行折半查找(但可以采用二叉排序树等形式进行快速的查找)。判定树折半查找的判定树类似于完全二叉树，叶子结点所在层次之差最多为1，其深度为?logn??1。查找过程就是走了一条从根到该结点的路径。如：表长n=10的有序表折半查找的判定树如下。 21 答案：a: j&=i
b: (i+j)/2
c: a[m]==x
2 3 4平均查找长度结论：等概率查找成功时的平均查找长度n?501hn?1j?1ASLbs??j2?log(n?1)?1?log(n?1)?1 nj?1n分析方法：对等概率情况，假设查找n次，且每个查找1次，共比较关键字c次，则平均c/n次。例：表长为n = 10，平均查找长度如下。ASL?3?2?3?4?1?3?4?2?3?429??2.9时间复杂度结论：O(logn)，根据平均查找长度计算。
有时对需要反复查找的数据预先排序，再折半查找也是划算的。比如有1000个数据，顺序查找100次，平均比较约100×500=50000次；快排大约比较1.44nlogn = 1.44×1000×10 = 1次折半查找比较不超过100×9×2=1800次(考虑到同一关键字的两次比较)，排序后折半查找合计比较不超过大约16200次。索引顺序表分块，块间有序 + 块内无序，对应索引表有序 + 顺序表（无序）。索引顺序表的查找性能介于顺序查找与折半查找之间。
分块的最佳长度是多少？规定条件：每块的大小相同，对块索引表和块内查找均采用顺序查找。设表长为n，等分成b块，采用顺序查找确定块需要比较(b+1)/2次，块内顺序查找比较(n/b+1)/2次，总共C(b)=(b+1)/2+(n/b+1)/2，要使C(b)最小，有b?。二叉排序树二叉排序树二叉排序树或为空树；或者是这样一棵二叉树，若左子树不空，则左子树上所有结点均小于根结点，若右子树不空，则右子树上所有结点均大于根结点，其左、右子树也是二叉排序树。 技巧：如果中序遍历二叉排序树，得到的结果将从小到大有序。手工判别二叉排序树的方法之一。
例：判断对错：二叉排序树或是空树，或是这样一棵二叉树，若左子树不空，则左孩子小于根结点，若右子树不空，则右孩子大于根结点，左、右子树也是这样的二叉排序树。（×）请自己举反例。
查找思路：①若二叉树为空，则找不到，②先与根比较，相等则找到，否则若小于根则在左子树上继续查找，否则在右子树上继续查找。递归算法：BstTree BstSearch ( BstTree bst, DataType x ){if ( bst==NULL )return NULL;else if ( bst-&data==x )else if ( x&bst-&data )return BstSearch ( bst-&lchild, x);elsereturn BstSearch ( bst-&rchild, x);}非递归算法:BstTree BstSearch ( BstTree bst, DataType x ){p =while ( p ) {if ( p-&data==x )else if ( x&p-&data )p = p-&elsep = p-&}return NULL;
// not found}插入思路：先查找，若找不到则插入结点作为最后访问的叶子结点的孩子。新插入的结点总是叶子。建立经过一系列插入操作可以建立二叉排序树。给定关键字序列，建立二叉排序树。方法：①开始二叉树为空，②对每一个关键字，先进行查找，如果已存在，则不作任何处理，否则插入。22一句话，“从空树开始，每次插入一个关键字”。例：给定关键字序列{53，45，12，24，90，45，80}，建立二叉排序树。 22 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
删除叶子直接删除即可。
删除左子树或右子树为空
“移花接木”：将左子树或右子树接到双亲上。
删除左右子树都不空 “偷梁换柱”：借左子树上最大的结点替换被删除的结点，然后删除左子树最大结点。（或者借用右子树上最小结点然后删除之亦可。）
删除分析判定树和二叉排序树相同。结点的层次等于查找时比较关键字的个数。
等概率情况下查找成功时1n1?2?2?3?3?4ASL??h
i??2.5i?1若按照关键字有序的顺序插入结点建立二叉排序树，将得到一棵单支树，对其进行查找也退化为顺序查找，平均查找长度为(1+n)/2。一般地，如果在任一关键字k之后插入二叉排序树的关键字都大于或都小于k，则该二叉排序树是单分支的，深度是n，查找效率和顺序查找相同。 平衡二叉树平衡因子和平衡二叉树(AVL树)平衡因子：左子树深度 C 右子树深度。平衡二叉树中各个结点的平衡因子只能是0，1，-1。构造平衡二叉排序树思路：按照建立二叉排序树的方法逐个插入结点，失去平衡时作调整。23失去平衡时的调整方法：1) 确定三个代表性结点。(A是失去平衡的最小子树的根；B是A的孩子；C是B的孩子，也是新插入结点的子树)。关键是找到失去平衡的最小子树。2) 根据三个代表性结点的相对位置(C和A的相对位置)判断是哪种类型(LL, LR, RL, RR)。 3) 平衡化。“先摆好三个代表性结点(居中者为根)，再接好其余子树(根据大小)”。
例：给定关键字的序列{13，24，37，90，53，40}，建立平衡二叉排序树。 注意：失去平衡时先确定失去平衡的最小子树，这是关键，然后判断类型（LL，LR，RL，RR），再平衡化处理。分析查找 (同二叉排序树) 平均查找长度ASL结论：平均查找性能O(log n)。 23这里没有使用课本上“旋转”的概念，这只是做题的方法，并不是正规的算法描述。为求得n个结点的平衡二叉树的最大高度，考虑高度为h的平衡二叉树的最少结点数。? 0,
h?0 ? Nh?? 1,
h?1? N?N?1,
h?2k-2?k-1部分结果如下，Fh表示斐波纳契数列第h项。表 错误！文档中没有指定样式的文字。.13 平衡二叉树的高度和结点个数
观察可以得出Nh = Fh+2 C 1, h≥0。解得h?log?((n?1))?2?1.44 log (n?1)-0.328其中??(?1)/2。时间复杂度一次查找经过根到某结点的路径，所以查找的时间复杂度是O(log n)。+B-树和B树B-树一棵m阶B-树，或为空树，或满足： (1) 每个结点至多有m棵子树；(2) 若根结点不是叶子，则至少有两棵子树； (3) 除根之外的所有非终端结点至少有?m/2?棵子树；(4) 所有非终端结点包含n个关键字和n+1棵子树：(n, A0, K1, A1, ..., Kn, An)，其中关键字满足A0&K1&A1&...&Kn&An，关键字的个数?m/2??1?n?m?1。 (5) 所有叶子在同一层，不含信息，表示查找失败。B树B+树和B-树的差异：n棵子树的结点中含有n个关键字；所有叶子结点中包含了全部关键字，且按大小顺序排列；所有非终端结点都是索引。 对B+树既可以进行顺序查找又可以进行随机查找。 键树又叫数字查找树。常见的两种存储结构：孩子兄弟链表，多重链表。 哈希表24+
解斐波纳契递推式代入得?1???Nh?n??????1????h?2??????1????h?2?1?n?????1??????????1????h?2?1?1?h?2?1,其中???1
然后整理，取对数可解得h。哈希表(散列表，杂凑表)根据设定的哈希函数和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置，这种表称为哈希表，又叫散列表，杂凑表。哈希函数常用除留余数法。H(key) = key MOD p。冲突什么是冲突？H(key1)=H(key2)，且key1≠key2，称冲突。处理冲突的方法：当H(key)处已有记录，出现冲突，如何处理？开放定址法试用H(key)di，常见以下三种。(1) 线形探测再散列：试用H(key)1，H(key)2，...2222(2) 二次探测再散列：试用H(key)1，H(key)-1，H(key)2，H(key)-2，...(3) 伪随机探测再散列：试用H(key)f(1)，H(key)f(2)，...再哈希法H1(key)冲突，试用H2(key)，H3(key)，...链地址法发生冲突的记录链成单链表。建立公共溢出区所有冲突记录存入溢出区。装填因子
??n n个记录，m个地址空间。哈希表的平均查找长度与记录个数n不直接相关，而是取决于装填因子和处理冲突的方法。 举例例：已知一组关键字{19, 14, 23, 1, 68, 20, 85, 9}，采用哈希函数H(key)=key MOD 11，请分别采用以下处理冲突的方法构造哈希表，并求各自的平均查找长度。1) 采用线性探测再散列；2) 采用伪随机探测再散列，伪随机函数为f(n) = - n；3) 采用链地址法。
思路：开始时表为空，依次插入关键字建立哈希表。
1) 线性探测再散列
? 关键字? H(key) 68 20 85 9 2 9 8 9 key 19 14 23 1 H(key) 8 3 1 12 3
10 0查找长度 1 1 1 2 3 1 3
ASL = (1+1+1+2+3+1+3+3)/8 = 15/8
2) 伪随机探测再散列
? 冲突时计算下一地址 ?
3 ? 每个关键字的查找长度key 19 14 23 1 68 20H(key) 8 3 1 1 2 9
查找长度 1 1 1 2 1
ASL = (1+1+1+2+1+1+2+4)/8 = 13/8
3) 链地址法
12345678910 85 9 8 9 7
1 8 7 6 2 4ASL = (1×5+2×3)/8 = 11/8注：关键字在链表中的插入位置可以在表头或表尾，也可以在中间以便保持关键字有序。最后，此哈希表的装填因子是α= 8/11。内部排序基础知识和算法排序的有关概念排序（按关键字大小顺序排列数据）。2排序方法：内部排序，外部排序；简单的排序方法O(n)，先进的排序方法O(nlogn)，基数排序O(dn)；插入排序，交换排序，选择排序，归并排序，计数排序。排序方法的稳定性：取决于该方法采取的策略，不是由一次具体的排序结果决定的。但是通过列举不稳定的排序实例可以说明该排序算法的不稳定性。直接插入排序思路将待排序记录插入已排好的记录中，不断扩大有序序列25一句话，“将待排序记录插入有序序列，重复n-1次”。例：52，49，80，36，14，58，61 进行直接插入排序。
分析表 错误！文档中没有指定样式的文字。.14 直接插入排序
记录顺序有序时记录逆序有序时2比较 n-1 ((n+2)(n-1))/2 2移动 0 ((n+4)(n-1))/2
最好 最坏 平均n/4，算法的时间复杂度O(n)。直接插入排序是稳定的排序算法。折半插入排序思路在直接插入排序中，查找插入位置时采用折半查找的方法。程序void BinInsertSort ( T a[], int n ){for ( i=1; i&n; i++ ) {// 在a[0..i-1]中折半查找插入位置使a[high]≤a[i]&a[high+1..i-1]low = 0;
high = i-1;while ( low&=high ) {m = ( low+high )/2;if ( a[i]&a[m] )high = m-1;elselow = m+1;25 不准确的说法，只为便于理解和记忆，不要在正式场合引用。}// 向后移动元素a[high+1..i-1]，在a[high+1]处插入a[i]x = a[i];for ( j=i-1; j& j-- )a[j+1] = a[j];a [high+1] =
// 完成插入}}分析2时间复杂度O(n)。比直接插入排序减少了比较次数。折半插入排序是稳定的排序算法。希尔排序（缩小增量排序）思路先将待排序列分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进行直接插入排序。步骤：01. 分成子序列(按照增量dk)；02. 对子序列排序(直接插入排序)；03. 缩小增量，重复以上步骤，直到增量dk=1。增量序列中最后一个增量一定是1，如：... 9, 5, 3, 2, 1和... 13, 4, 1。如没有明确说明增量序列可以选择... 3, 2, 1或... 5, 3, 2, 1。例：希尔排序(52，49，80，36，14，58，61)。dk=3dk=2dk=1
3/2注意：希尔排序是不稳定的。时间复杂度大约为O(n)。程序void ShellSort ( T a[], int n ){dk = n/2;while ( dk&=1 ) {// 一趟希尔排序，对dk个序列分别进行插入排序for ( i= i&n; i++ ) {x = a[i];for ( j=i- j&=0 and x&a[j]; j-=dk )a[j+dk] = a[j];a[j+dk] =}// 缩小增量dk = dk/2;}}起泡排序思路26一句话，“依次比较相邻元素，‘逆序’则交换，重复n-1次”。例：冒泡排序(52，49，80，36，14，58，61)。52 49 80 36 14 58 61
程序请参考错误！未找到引用源。BubbleSort算法。分析2比较和交换总是发生在相邻元素之间，是稳定的排序算法。时间复杂度O(n)。快速排序思路一趟排序把记录分割成独立的两部分，一部分关键字均比另一部分小，然后再分别对两部分快排。例：{52
61} 快速排序。下面是一次划分的详细步骤：26 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
整个快速排序过程如下：(52 49 80 36 14 58 61)
程序void QuickSort ( T a[], int low, int high ) {if ( low & high ) {// 划分pivot = a[low];i = j =while ( i & j ) {while ( i&j && a[j] &= pivot )
a[i] = a[j];while ( i&j && a[i] &= pivot )
a[j] = a[i];}a[i] =// 对子序列快排
QuickSort ( a, low, i-1); 技巧： 选第1个记录为轴，分别从后向前，从前向后扫描记录，后面“抓大放小”(如：①②)，前面“抓小放大”(如：③④)，交替进行(⑤-⑦)，最后将轴QuickSort ( a, i+1, high);}}分析2平均情况下，时间复杂度O(nlogn)。记录本来有序时为最坏情况，时}
请打开cookies.
此网站 (www.) 的管理员禁止了您的访问。原因是您的访问包含了非浏览器特征(3a6a-ua98).
重新安装浏览器，或使用别的浏览器A.nB.n(n-1)C.n(n-1)/2D.n；5.在一个具有n个顶点的有向完全图中，所含的边数；A.nB.n(n-1)C.n(n-1)/2D.n；6.在一个无向图中，若两顶点之间的路径长度为k，；A.kB.k+1C.k+2D.2k；7.对于一个具有n个顶点的无向连通图，它包含的连；A.0B.1C.nD.n+1；8.若一个图中包含有k个连通分量，若要按照深
C. n(n-1)/2
D. n(n+1)/2
5. 在一个具有n个顶点的有向完全图中，所含的边数为(
C. n(n-1)/2
D. n(n+1)/2
6. 在一个无向图中，若两顶点之间的路径长度为k，则该路径上的顶点数为(
7. 对于一个具有n个顶点的无向连通图，它包含的连通分量的个数为(7. B)。
8. 若一个图中包含有k个连通分量，若要按照深度优先搜索的方法访问所有顶点，则
必须调用(8. A )次深度优先搜索遍历的算法。
9. 若要把n个顶点连接为一个连通图，则至少需要(9. C )条边。
10. 在一个具有n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素（又称为
有效元素）的个数为(
11. 在一个具有n个顶点和e条边的有向图的邻接矩阵中，表示边存在的元素个数为
12. 在一个具有n个顶点和e条边的无向图的邻接表中，边结点的个数为(12. D )。
13. 在一个具有n个顶点和e条边的有向图的邻接表中，保存顶点单链表的表头指针向
量的大小至少为(13. A )。
14. 在一个无权图的邻接表表示中，每个边结点至少包含(14. B )域。
15. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应邻接表中该顶点单链
表中的边结点数为(15. B )。
16. 对于一个有向图，若一个顶点的度为k1，出度为k2，则对应逆邻接表中该顶点单
链表中的边结点数为(16. C )。
17. 对于一个无向图，下面(17. A )种说法是正确的。
A. 每个顶点的入度等于出度
B. 每个顶点的度等于其入度与出度之和
C. 每个顶点的入度为0
D. 每个顶点的出度为0
18. 在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的(18. A)。
D. 度数减1
19. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进
行深度优先搜索，得到的顶点序列可能为(
A. A,B,C,F,D,E
B. A,C,F,D,E,B
C. A,B,D,C,F,E
D. A,B,D,F,E,C
20. 若一个图的边集为{(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)}，则从顶点A开始对该图进
行广度优先搜索，得到的顶点序列可能为(20. D )。
A. A,B,C,D,E,F
B. A,B,C,F,D,E
C. A,B,D,C,E,F
D. A,C,B,F,D,E
21. 若一个图的边集为{&1,2&,&1,4&,&2,5&,&3,1&,&3,5&,&4,3&}，则从顶点1开始对该图
进行深度优先搜索，得到的顶点序列可能为(21. A
A. 1,2,5,4,3
B. 1,2,3,4,5
C. 1,2,5,3,4
D. 1,4,3,2,5
22. 若一个图的边集为{&1,2&,&1,4&,&2,5&,&3,1&,&3,5&,&4,3&}，则从顶点1开始对该图
进行广度优先搜索，得到的顶点序列可能为(
A. 1,2,3,4,5
B. 1,2,4,3,5
C. 1,2,4,5,3
D. 1,4,2,5,3
23. 由一个具有n个顶点的连通图生成的最小生成树中，具有(23. B )条边。
24. 已知一个有向图的边集为{&a,b&,&a,c&,&a,d&,&b,d&,&b,e&,&d,e&}，则由该图产生的一
种可能的拓扑序列为(24. A
A. a,b,c,d,e
B. a,b,d,e,b
C. a,c,b,e,d
D. a,c,d,b,e
二、填空题
1. 在一个图中，所有顶点的度数之和等于所有边数的________倍。1. 2
2. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点
的有向完全图中，包含有________条边。
2. n(n-1)/2，n(n-1)
3. 假定一个有向图的顶点集为{a,b,c,d,e,f}，边集为{&a,c&, &a,e&, &c,f&, &d,c&, &e,b&,
&e,d&}，则出度为0的顶点个数为________，入度为1的顶点个数为________。3. 2，4
4. 在一个具有n个顶点的无向图中，要连通所有顶点则至少需要________条边。4. n-1
5. 表示图的两种存储结构为__________和__________。5. 邻接矩阵，邻接表
6. 在一个连通图中存在着________个连通分量。6. 1
7. 图中的一条路径长度为k，该路径所含的顶点数为________。7. k+1
8. 若一个图的顶点集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有________
个连通分量。
9. 对于一个具有n个顶点的图，若采用邻接矩阵表示，则矩阵大小至少为
________?________。9.
10. 对于具有n个顶点和e条边的有向图和无向图，在它们对应的邻接表中，所含边结
点的个数分别为________和________。10. 2e，e
11. 在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有
________和________结点。11. 出边，入边
12. 对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵和邻接表表示时，
求任一顶点度数的时间复杂度分别为________和________。
12. O（n），O（e/n）
13. 假定一个图具有n个顶点和e条边，则采用邻接矩阵和邻接表表示时，其相应的空
2间复杂度分别为________和________。13.O（n），O（n+e）
14. 一个图的边集为{(a,c),(a,e),(b,e),(c,d),(d,e)}，从顶点a出发进行深度优先搜索遍历得
到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点序列为
____________。
14. acdeb，acedb （答案不唯一）
15. 一个图的边集为{&a,c&,&a,e&,&c,f&,&d,c&,&e,b&,&e,d&}，从顶点a出发进行深度优先
搜索遍历得到的顶点序列为____________，从顶点a出发进行广度优先搜索遍历得到的顶点
序列为____________。15. acfebd，acefbd （答案不唯一）
16. 图的________优先搜索遍历算法是一种递归算法，图的________优先搜索遍历算法
需要使用队列。 16. 深度，广度
17. 对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数和边数分别为
________和________。17. n，n-1
18. 若一个连通图中每个边上的权值均不同，则得到的最小生成树是________（唯一/
不唯一）的。 18. 唯一
19. 根据图的存储结构进行某种次序的遍历，得到的顶点序列是__（唯一/不唯一）的。
20. 假定一个有向图的边集为{&a,c&,&a,e&,&c,f&,&d,c&,&e,b&,&e,d&}，对该图进行拓扑排序得
到的顶点序列为________。
20. aebdcf（答案不唯一）
三、应用题
1. 对于一个无向图6-11(a)，假定采用邻接矩阵表示，试分别写出从顶点0出发按深度
优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
注：每一种序列都是唯一的，因为都是在存储结构上得到的。
1. 深度优先搜索序列：0,1,2,8,3,4,5,6,7,9
广度优先搜索序列：0,1,4,2,7,3,8,6,5,9
2. 对于一个有向图6-11(b)，假定采用邻接表表示，并且假定每个顶点单链表中的边结
点是按出边邻接点序号从大到小的次序链接的，试分别写出从顶点0出发按深度优先搜索遍
历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。
注：每一种序列都是唯一的，因为都是在存储结构上得到的。
2. 深度优先搜索序列：0,4,7,5,8,3,6,1,2
广度优先搜索序列：0,4,3,1,7,5,6,2,8
3. 已知一个无向图的邻接矩阵如图6-12(a)所示，试写出从顶点0出发分别进行深度优
先和广度优先搜索遍历得到的顶点序列。
3. 深度优先搜索序列：0,2,3,5,6,1,4
广度优先搜索序列：0,2,3,5,6,1,4
4. 已知一个无向图的邻接表如图6-12(b)所示，试写出从顶点0出发分别进行深度优先
和广度优先搜索遍历得到的顶点序列。
4. 深度优先搜索序列：0,3,6,4,1,5,2
广度优先搜索序列：0,3,2,6,5,4,1
5. 已知图6-13所示的一个网，按照Prim方法，从顶点1 出发，求该网的最小生成树的产生过程。
5. 过程如图6-16所示
6. 已知图6-13所示的一个网，按照Kruskal方法，求该网的最小生成树的产生过程。
6. 求解过程如图6-17所示。
(b) (c) (e) (f) 图6-17
图6-14所示为一个有向网图及其带权邻接矩阵，要求对有向图采用
Dijkstra算法，求从
V0 到其余各顶点的最短路径。
有向带权图
图6-14 有向带权图及其邻接矩阵
7. 求解过程如下表所示。
三亿文库包含各类专业文献、应用写作文书、生活休闲娱乐、专业论文、各类资格考试、外语学习资料、文学作品欣赏、79图结构习题答案等内容。
1. 图结构习题 1.对于下列所示的图,给出从顶点 1 开始的 BFS 树。 2.对于题 1 中的图,给出从顶点 4 出发,使用 Dijkstra 最短路径算法产生的最短 路径... 平面力偶系习题答案_工学_高等教育_教育专区。建筑力学第三单元 平面力偶系 3-...3-4 在图3-4a 所示结构中,各构件的自重略去不计,在构件BC 上作用1 力偶... 第6章图练习题答案_信息与通信_工程科技_专业资料。第 6 章图练习题答案一、填空题 1. 图有 邻接矩阵 、 邻接表 等存储结构,遍历图有 深度优先遍历 、 广度... D 1 E 2 C A B 习题 2-7 图 习题 2-7 解答图 解:将题中的折杆用直杆代替,如图(b)所示。杆 CD 和链杆 1 由铰 D 联结构成二元 体可以去掉;同... q C B A D 八.(本大题 15 分) 用力法作图结构的 M 图.EI=常数. EI 2q EI EI 2EI l l EI 2q l 结构力学试卷答案三.是非题 1 . (X) ;2.... 结构力学课后习题答案_工学_高等教育_教育专区。习 题 7-1 试确定图示结构的...Z 1 ? 7 ql 4 348 EI 作出最终 M 图 85 2 ql 348 5 ql 2 768 41... 第6章 图习题参考答案_IT认证_资格考试/认证_教育专区。习题六参考答案一、选择...无向图采用邻接表存储结构,编写算法输出图中各连通分量的顶点序列。 参考答案: ... 数据结构图习题_理学_高等教育_教育专区。数据结构习题和答案 第7章 图 一、选择题 1.对于一个具有 n 个顶点和 e 条边的有向图,在用邻接表表示图时,拓扑... 建筑施工图自测练习题――答案 1.工业建筑;农业建筑;民用建筑 2.设计总说明;建筑施工图;结构施工图;设备施工图。 3.建筑设计总说明;总平面图;建筑平面图;建筑...您所在位置： &
 &  & 
图答案.doc 4页
本文档一共被下载：
次 ,您可全文免费在线阅读后下载本文档。
下载提示
1.本站不保证该用户上传的文档完整性，不预览、不比对内容而直接下载产生的反悔问题本站不予受理。
2.该文档所得收入(下载+内容+预览三)归上传者、原创者。
3.登录后可充值，立即自动返金币，充值渠道很便利
需要金币：200 &&
你可能关注的文档：
··········
··········
单项选择题
在一个具有n个顶点的有向图中，若所有顶点的出度数之和是s，则所有顶点的入度数之和为（）
A．ｓ B．ｓ－１ C．ｓ＋１ D． ｎ
２．在一个具有n个顶点的有向图中，若所有顶点的出度数之和是s，则所有顶点的度数之和为（）
A．ｓ B．ｓ－１ C．ｓ＋１ D． ２ｓ
３．在一个具有ｎ个顶点的无向图中，若具有ｅ条边，则所有顶点的度数之和为（）
A．ｎ B．ｅ C．ｎ＋ｅ D． ２ｅ
４．在一个具有ｎ个顶点的无向完全图中，所含的边数为（）
A．ｎ B．ｎ（ｎ－１） C．ｎ（ｎ－１）/２ D．ｎ（ｎ－１）/２
５．在一个具有ｎ个顶点的有向完全图中，所含的边数为（）
A．ｎ B．ｎ（ｎ－１） C．ｎ（ｎ－１）/２ D．ｎ（ｎ－１）/２
６．在一个无权图中，若两顶点之间的路径长度为ｋ，则该路径上的顶点数为（）
Ａ．ｋ Ｂ．ｋ＋１ Ｃ．ｋ＋２ Ｄ．２ｋ
７．对于一个具有ｎ个顶点的无向连通图，它包含的连通分量的个数为（）
Ａ．０ Ｂ．１ Ｃ．ｎ Ｄ．ｎ＋１
８．若一个图中包含有ｋ个连通分量，若要按照深度优先搜索的方法访问所有顶点，则必须用（）次深度优先搜索遍历的算法。
Ａ．ｋ Ｂ．１ Ｃ．ｋ－１ Ｄ．ｋ＋１
９．若要把ｎ个顶点连接为一个连通图，则至少需要（）条边。
Ａ．ｎ Ｂ．ｎ＋１ Ｃ．ｎ－１ Ｄ．２ｎ
１０．在一个具有ｎ个顶点和ｅ条边的无向图的邻接矩阵中，表示边存在的元素（又称为有效元素）的个数为（）。
Ａ．ｎ Ｂ．ｎ×ｅ Ｃ．ｅ Ｄ．２×ｅ
１１．在一个具有ｎ个顶点和ｅ条边的有向图的邻接矩阵中，表示边存在的元素的个数为（）。
Ａ．ｎ Ｂ．ｎ×ｅ Ｃ．ｅ Ｄ．２×ｅ
１２．在一个具有ｎ个顶点和ｅ条边的有无向图的邻接表中，边结点的个数为（）。
Ａ．ｎ Ｂ．ｎ×ｅ Ｃ．ｅ Ｄ．２×ｅ
１３．在一个具有ｎ个顶点和ｅ条边的有向图的邻接表中，保存顶点单链表的表头指针向量的大小至少为（）。
Ａ．ｎ Ｂ．２ｎ Ｃ．ｅ Ｄ．２×ｅ
１４．在一个无权图的邻接表表示中，每个边结点至少包含（）域。
Ａ．１ Ｂ．２ Ｃ．３ Ｄ．４
１５．对于一个有向图，若一个顶点的入度为ｋ１，出度为ｋ２，则对应邻接表中该顶点单链表中的边结点数为（）。
Ａ．Ｋ１ Ｂ．Ｋ２ Ｃ．Ｋ１－Ｋ２ Ｄ．Ｋ１＋Ｋ２
１６．对于一个有向图，若一个顶点的入度为ｋ１，出度为ｋ２，则对应逆邻接表中该顶点单链表中的边结点数为（）。
Ａ．Ｋ１ Ｂ．Ｋ２ Ｃ．Ｋ１－Ｋ２ Ｄ．Ｋ１＋Ｋ２
１７．对于一个无向图，下面（）说法是正确的。
Ａ．每个顶点的入度等于出度 Ｂ．每个顶点的度等于其入度与出度之和 Ｃ．每个顶点的入度为０ Ｄ．每个顶点的出度为０
１８．在一个有向图的邻接表中，每个顶点单链表中结点的个数等于该顶点的（）。
Ａ．出边数 Ｂ．入边数 Ｃ．度数 Ｄ．度数减１
１９．若一个图边集为｛（Ａ，Ｂ），（Ａ，Ｃ），（Ｂ，Ｄ），（Ｃ，Ｆ），（Ｄ，Ｅ），（Ｄ，Ｆ）｝，则从顶点Ａ开始对该图进行深度优先搜索，得到的顶点序列可能为（）。
Ａ．A,B,C,F,D,E Ｂ．A,C,F,D,E,B Ｃ．A,B,D,C,F,E Ｄ．A,B,D,F,E,C
２０．若一个图边集为｛（Ａ，Ｂ），（Ａ，Ｃ），（Ｂ，Ｄ），（Ｃ，Ｆ），（Ｄ，Ｅ），（Ｄ，Ｆ）｝，则从顶点Ａ开始对该图进行广度优先搜索，得到的顶点序列可能为（）。
Ａ．Ａ,B,C,D,E,F Ｂ．A,B,C,F,D,E Ｃ．A,B,D,C,E,F Ｄ．A,C,B,F,D,E
２１．若一个图边集为｛ 1,2 , 1,4 , 2,5 , 3,1 , 3,5 , 4,3 ｝,则从顶点１开始对该图进行深度优先搜索，得到的顶点序列可能为（）。
Ａ．1,2,5,4,3 Ｂ．1,2,3,4,5 Ｃ．1,2,5,3,4 Ｄ．1,4,3,2,5
２２．若一个图边集为｛ 1,2 , 1,4 , 2,5 , 3,1 , 3,5 , 4,3 ｝,则从顶点１开始对该图进行广度优先搜索，得到的顶点序列可能为（）。
Ａ．1,2,3,4,5 Ｂ．1,2,4,3,5 Ｃ．1,2,4,5,3 Ｄ．1,4,2,5,3
２３．由一个具有ｎ个顶点的连通图生成的最小生成树中，具有（）条边。
Ａ．ｎ Ｂ．ｎ－１ Ｃ．ｎ＋１ Ｄ．２＊ｎ
２４．已知一个无向图的边集为｛（０,1）3,（0,2）5,（0,3）6,（1,4）10,（2,3）2,（2,4）9,（3,4）8｝,则该图的最小生成树的权为（）。
Ａ．４３ Ｂ．１６ Ｃ．１８ Ｄ．２３
２５．已知一个无向图的边集为｛（０,1）3,（0,2）5,（0,3）6,（1,4）10,（2,3）2,（2,4）9,（3,4）8｝,则该图的最小生成树的边集为（）。
Ａ．｛（０,1
正在加载中，请稍后...南开13秋 数据结构-海文库
全站搜索：
您现在的位置：&>&&>&理学
南开13秋 数据结构
13秋学期《数据结构》在线作业
一、单选题1.
若已知一个栈的入栈序列是1，2，3，?，n，其输出序列为p1，p2，p3，?，pn，若p1=n，则pi为（）A. iB. n=iC. n-i+1D. 不确定正确答案：C
堆的形状是一棵()A. 二叉排序树B. 满二叉树C. 完全二叉树D. 平衡二叉树正确答案：C
设F是一个森林，B是由F变换得的二叉树。若F中有n个非终端结点，则B中右指针域为空的结点有()个A. n-1B. nC. n+1D. n+2正确答案：C
在表长为ｎ的链表中进行线性查找，它的平均查找长度为（
）A. ＡＳＬ＝ｎB. ＡＳＬ＝（ｎ＋１）／２C.D.正确答案：B
把一棵树转换为二叉树后，这棵二叉树的形态是（）A. 唯一的B. 有多种C. 有多种，但根结点都没有左孩子D. 有多种，但根结点都没有右孩子正确答案：A
在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（）A. 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B. 在第i个结点后插入一个新结点（1≤i≤n）C. 删除第i个结点（1≤i≤n）D. 将n个结点从小到大排序正确答案：A
判定一个队列QU（最多元素为m0）为满队列的条件是（）A.
QU-&rear － QU-&front = = m0B. QU-&rear － QU-&front －1= = m0C.
QU-&front = = QU-&rearD. QU-&front = = QU-&rear+1正确答案：A
若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为A. 38,40,46,56,79,84B. 40,38,46,79,56,84C. 40,38，46,56,79,84D. 40,38,46,84,56,79正确答案：C
在一个图中，所有顶点的度数之和等于图的边数的（）倍A. 1/2B. 1C. 2D. 4正确答案：C
用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的A. 栈B. 队列C. 树D. 图正确答案：B
设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为（）A. 循环链表B. 单链表C.
双向循环链表D. 双向链表正确答案：B
链表是一种采用
存储结构存储的线性表A. 顺序B. 链式C. 星式D. 网状正确答案：B
不含任何结点的空树（）A. 是一棵树B. 是一棵二叉树C. 是一棵树也是一棵二叉树D. 既不是树也不是二叉树正确答案：C
数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为A. r－fB. （n＋f－r）% nC. n＋r－fD. （n＋r－f）% n正确答案：D
若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用堆排序的方法建立的初始堆为()A. 79,46,56,38,40,84B. 84,79,56,38,40,46C. 84,79,56,46,40,38D. 84,56,79,40,46,38正确答案：B
从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）的一端的方法，称为()A. 希尔排序B. 归并排序C. 插入排序D. 选择排序正确答案：D
任何一个无向连通图的最小生成树()A. 只有一棵B. 一棵或多棵C. 一定有多棵D. 可能不存在正确答案：A
在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。A. 1/2B. 1C. 2D. 4正确答案：B
下述几种排序方法中，要求内存最大的是()A. 插入排序B. 快速排序C. 归并排序D. 选择排序正确答案：C
线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以正确答案：D
二、判断题1.
顺序存储方式的优点是存储密度大，且插入、删除运算效率高。A. 错误B. 正确正确答案：A
队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。A. 错误B. 正确正确答案：A
栈和队列的存储方式既可是顺序方式，也可是链接方式。A. 错误B. 正确正确答案：B
用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。A. 错误B. 正确正确答案：B
栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。A. 错误B. 正确正确答案：B
栈和队列是一种非线性数据结构。A. 错误B. 正确正确答案：A
对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表A. 错误B. 正确正确答案：B
二叉树中所有结点个数是2k-1-1，其中k是树的深度。A. 错误B. 正确正确答案：A
栈和链表是两种不同的数据结构。A. 错误B. 正确正确答案：A
在表结构中最常用的是线性表，栈和队列不太常用。A. 错误B. 正确正确答案：A
二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。A. 错误B. 正确正确答案：A
二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。A. 错误B. 正确正确答案：A
两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。A. 错误B. 正确正确答案：B
线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。A. 错误B. 正确正确答案：A
对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2i―1个结点。A. 错误B. 正确正确答案：A
顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。A. 错误B. 正确正确答案：A
顺序存储方式只能用于存储线性结构。A. 错误B. 正确正确答案：A
二叉树中每个结点有两棵非空子树或有两棵空子树。A. 错误B. 正确正确答案：A
线性表在物理存储空间中也一定是连续的。A. 错误B. 正确正确答案：A
若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n―1个非空指针域。A. 错误B. 正确正确答案：B
链表的物理存储结构具有同链表一样的顺序。A. 错误B. 正确正确答案：A
一个栈的输入序列是12345，则栈的输出序列不可能是12345。A. 错误B. 正确正确答案：A
链表的每个结点中都恰好包含一个指针。A. 错误B. 正确正确答案：A
二叉树中每个结点的两棵子树的高度差等于1。A. 错误B. 正确正确答案：A
线性表的逻辑顺序与存储顺序总是一致的。A. 错误B. 正确正确答案：A
具有12个结点的完全二叉树有5个度为2的结点。A. 错误B. 正确正确答案：B
线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。A. 错误B. 正确正确答案：A
线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。A. 错误B. 正确正确答案：A
二叉树中每个结点的两棵子树是有序的。A. 错误B. 正确正确答案：B
链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。A. 错误B. 正确正确答案：A
一、（共 10 道试题，共 60 分。）1.表达式a*(b+c)-d的后缀表达式是（ ）。A. abcd*+-B. abc+*d-C. abc*+d-D. -+*abcd-----------------选择：B2.最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是 （ ）。A. (rear+1) MOD n=frontB. rear=frontC. rear+1=frontD. (rear-l) MOD n=front-----------------选择：B3.在一个长度为n的线性表中，删除值为x的元素时需要比较元素和移动元素的总次数为（ ）。A. (n+1)/2B. n/2C. nD. n+1-----------------选择：C4.在一个单链表中，删除*p结点之后的一个结点的操作是（ ）。A. p-&next=p;B. p-&next-&next=p-&C. p-&next-&next=p;D. p-&next=p-&next-&-----------------选择：D5.广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（ ）。A. cB. b，cC. （b，c）D. （（b，c））-----------------选择：D6.在表长为n的顺序表中,若在每个位置插入数据元素的概率相等，插入一个数据元素平均需要移动（ ）个数据元素。A. (n-1)/2B. n/2C. n-1D. n-----------------选择：B7.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（ ）。A. head==NULLB. head→next==NULLC. head→next==headD. head!=NULL-----------------选择：B8.在一个单链表中，若要在p所指向的结点之后插入一个新结点，则需要相继修改（ ）个指针域的值。A. 1B. 2C. 3D. 4-----------------选择：B9.一个顺序栈S，元素a，b，c，d，e依次进栈，如果5个元素的出栈顺序为b，e，d，c，a，则顺序栈的容量至少应为（ ）。A. 2B. 3C. 4D. 5-----------------选择：C10.广义表((e))的表头是（ ）。A. eB. (e)C. ()D. (())-----------------选择：B
大工13春《数据结构》在线作业1
二、判断题（共 10 道试题，共 40 分。）1.顺序表中存取每一个元素的时间相同。（ ）A. 错误B. 正确-----------------选择：B2.算法分析的两个主要方面空间复杂度和时间复杂度。（ ）A. 错误B. 正确-----------------选择：B3.4个元素按a,b,c,d顺序连续进入队列，队头的元素是a。（ ）A. 错误B. 正确-----------------选择：B4.插入和删除只能在表的一端进行的线性表，称为队列。（ ）A. 错误B. 正确-----------------选择：A5.栈是限定只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。（ ）A. 错误B. 正确-----------------选择：A6.中缀表达式A-(B+C/D)*E的后缀形式是ABCD/+E*-。（ ）A. 错误B. 正确-----------------选择：B7.若n阶方阵的对角线右上方的元素均等于零，称为下三角矩阵。（ ）A. 错误B. 正确-----------------选择：B8.在栈中，出栈操作的时间复杂度为O(n)。（ ）A. 错误B. 正确-----------------选择：A9.栈和队列的共同特点是先进先出。（ ）A. 错误B. 正确-----------------选择：A10.顺序表的长度是表中的数据元素个数。（ ）A. 错误B. 正确-----------------选择：B
《数据结构》复习大纲――知识点剖析第一章：绪论一、基础知识概念和术语(黑体字部分)。另外，注意：1、数据元素是数据的基本单位。P42、数据项是数据不可分割的最小单位。P53、数据结构及其形式定义。P5四种基本结构：①集合②线性结构③树形结构④图（网）状结构4、数据结构的逻辑结构（抽象的，与实现无关）物理结构（存储结构）
顺序映像（顺序存储结构）位置“相邻”非顺序映像（链式存储结构）指针表示关系P65、数据类型
P7抽象数据类型（ADT）P7ADT=（数据对象，数据关系，基本操作）ADT细分为原子类型，固定聚合，可变聚合类型。P86、算法的概念
P137、算法的五个特征①有穷性 ②确定性 ③可行性 ④输入（0个或多个） ⑤输出（1个或多个）8、算法设计的要求：①正确性②可读性③健壮性④效率与低存储量
其中正确性的四个层次（通常要求达到C层）。9、算法的时间复杂度
常见有： O(1)，O(n)，O(n)，O(log2n)，O(n log2n)，O(2)语句频度，用归纳法计算。10、算法的空间复杂度
P17二、算法起泡排序。P16另一种形式void BubbleSort ( DataType a[], int n ){for ( i=0; i&n-1; i++ )for ( j=0; j&n-i-1; j++ )if ( a[j]&a[j+1] )a[j]&―&a[j+1];}或void BubbleSort ( DataType a[], int n ){for ( i=1; i&n; i++ )for ( j=0; j&n-i; j++ )if( a[j]&a[j+1] )a[j]&―&a[j+1];}或void BubbleSort ( DataType a[], int n ){for ( i=0; i&n-1; i++ ) {change =for ( j=0; j&n-i-1; j++ )if ( a[j]&a[j+1] ) {a[j]&―&a[j+1];change =}if ( !change )}} 1 分析算法的时间复杂度时，log2n常简单记作log n。
说明：a) 考试中要求写算法时，可用类C，也可用C程序。 b) 尽量书写算法说明，言简意赅。c) 技巧：用“边界值验证法”检查下标越界错误。如上第一个： 第二个循环条件若写作j&n-i，则当i=0时 a[j+1]会越界。2d) 时间复杂度为O(n)，第3个在最好情况下（待排记录有序），时间复杂度为O(n)。 第二章、线性表 一、基础知识和算法 1、线性表及其特点线性表是n个数据元素的有限序列。2线性结构的特点： ①“第一个” ②“最后一个” ③前驱 ④后继。 2、顺序表―线性表的顺序存储结构（1）特点：a) 逻辑上相邻的元素在物理位置上相邻。b) 随机访问。 （2）类型定义3简而言之，“数组+长度”。const int MAXSIZE = 线性表最大长度; typedef struct{DataType elem[MAXSIZE]; } SqL注：a) SqList为类型名，可换用其他写法。b) DataType是数据元素的类型，根据需要确定。
c) MAXSIZE根据需要确定。如
const int MAXSIZE=64;d) 课本上的SqList类型可在需要时增加存储空间，在上面这种定义下不可以e) 课本上的SqList类型定义中listsize表示已经分配的空间大小（容纳数据元素的个数）。当插入元素而遇到L.length==L.listsize时，用realloc (L.elem, L.listsize+增量) 重新分配内存，而realloc()函数在必要的时候自动复制原来的元素到新分配的空间中。（3）基本形态 a) 顺序表空条件
L.length==0 不允许删除操作b) 顺序表满条件
L.length==MAXSIZE 不允许插入操作0 1 ... MAXSIZE-1
L.length==0
L.length==MAXSIZ0&L.length&MAXSI23这里太简炼了，只是为了便于记忆。不准确的说法，只为便于理解和记忆，不要在正式场合引用。凡此情形，都加引号以示提醒。
c) 不空也不满可以插入，删除（4）基本算法――遍历d) 顺序访问所有元素for ( i=0; i&L. i++ )
visit ( L.elem[i] );
5 查找元素xfor ( i=0; i&L. i++ )if ( L.elem[i]==x )if ( i&L.length )找到;else未找到;2. 插入算法 ListInsert(&L,i,x)a) 前提：表不满b) 合理的插入范围：1≤i≤L.length+1注：位序i在C/C++中对应于下标i-1。c) 步骤第i至最后所有元素后移一个元素在第i个位置插入元素x表长增1d) 算法4bool ListInsert ( SqList& L, int i, DataType x ){if ( L.length==MAXSIZE || i&1 || i&L.length+1 ) // 失败// 元素后移for ( j=L.length-1; j&=i-1; j-- )
// 这里j为下标，从L.length-1到i-1L.elem[j+1] = L.elem[j];
若作为位序，有如何修改？// 插入xL.elem[i-1] =// 表长增1L.length++;
// 插入成功}3. 删除算法 ListDelete(&L,i,&x)a) 前提：表非空b) 合理的删除范围：1≤i≤L.lengthc) 步骤取出第i个元素第i个元素之后的元素向前移动一个位置 4 这里返回true表示正确插入，返回false表示插入失败。以下常用来区分操作是否正确执行。表长减1d) 算法bool ListDelete ( SqList& L, int i, DataType& x ){if ( L.length==0 || i&1 || i&L.length ) // 失败
x = L.elem[i-1];for ( j=i; j&L. j++ )L.elem[j-1] = L.elem[j];L.length--;
// 删除成功}
4. 算法分析表 错误！文档中没有指定样式的文字。.1 顺序表插入和删除算法的分析基本操作平均移动次数时间复杂度尾端操作 插入 移动元素 1n?1n(n?i?1)? ?i?1?删除 移动元素 1n?1?i(n?i)?n?1 O(n) O(n) 插入第n+1个元素，不移动 删除第n个元素，不移动 插入、删除需移动大量元素O(n)；但在尾端插入、删除效率高O(1)。5. 其他算法a) InitList (&L), ClearList (&L)L.length = 0;b) ListEmpty (L)return L.length == 0;c) ListLength (L)return L.d) GetElem (L, i, &e)e = L.elem[i-1];单链表――线性表的链式存储结构之一6. 概念线性链表，单链表，结点；数据域，指针域；头指针，头结点。7. 特点用指针表示数据之间的逻辑关系（逻辑相邻的元素物理位置不一定相邻）。8. 类型定义5简而言之，“数据 + 指针”。typedef struct LNode {DataTstruct LNode *} LNode, *LinkL9. 基本形态带头结点的单链表的基本形态有：a) 单链表空条件： L-&next == 0b) 单链表不空条件：L-&next != 0
10. 基本算法
a) 顺序访问所有元素借助指针，“顺藤摸瓜”(沿着链表访问结点)。 ．．．．p = L-&
// 注意起始位置的考虑while ( p!=NULL ) {
// 判表尾，另外 (p!=0)或(p)均可
visit( p-&data );
// 访问:可以换成各种操作
// 指针沿着链表向后移动 }
例：打印单链表中的数据。void PrintLinkList ( LinkList L ){p = L-&while ( p!=NULL ) {print ( p-&data );
// 访问：打印数据域p = p-&}}b) 查找元素x// 在单链表L中查找元素x// 若找到，返回指向该结点的指针；否则返回空指针LinkList Find ( LinkList L, DataType x ){p = L-&while ( p!=NULL ) {if ( p-&data == x )
// 找到xp = p-&} 5 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
return NULL;
// 未找到}
// 在单链表L中查找元素x// 若找到，返回该元素的位序；否则返回0 int Find ( LinkList L, DataType x ){p = L-&
j = 1;while ( p!=NULL ) {if ( p-&data == x )
// 计数器随指针改变
}return 0;
// 未找到}
前一个算法的另一种写法：p = L-&while ( p && p-&data!=x )p = p-&if ( p && p-&data==x )else
或者p = L-&while ( p && p-&data!=x )
// 为什么c) 查找第i个元素LinkList Get ( LinkList L, int i ){p = L-&
j = 1;while ( p && j&i ) {p = p-&
j++;}if ( p && j==i )else
return 0;}d) 查找第i-1个元素p = L;
j = 0;while ( p && j&i-1 ) {p = p-&
j++;}if ( p && j==i-1 )else
return 0;11. 插入算法 ListInsert(&L,i,x)技巧：画图辅助分析。思路：先查找第i-1个元素若找到，在其后插入新结点
6bool ListInsert ( LinkList &L, int i, DataType x ){// 查找第i-1个元素pp = L;
j = 0;while ( p && j&i-1 ) {插入前
j++;}// 若找到，在p后插入x
if ( p && j==i-1 ) {执行①之后
s = (LinkList) malloc(sizeof(LNode));s-&data =s-&next = p-&
// ②执行②之后
// 插入成功}else
// 插入失败}
注意：a) 要让p指向第i-1个而不是第i个元素（否则，不容易找到前驱以便插入）。b) 能够插入的条件： p && j==i-1 。即使第i个元素不存在，只要存在第i-1个元素，仍然可以插入第i个元素。c) 新建结点时需要动态分配内存。s = (LinkList) malloc(sizeof(LNode));若检查是否分配成功，可用if ( s==NULL )
// 分配失败则终止程序d) 完成插入的步骤：①②。技巧：先修改新结点的指针域。
12. 删除算法 ListDelete(&L,i,&x)思路：先查找第i-1个元素若找到且其后存在第i个元素，则用x返回数据，并删删除前
除之bool ListDelete ( LinkList &L, int i, int &x )执行①之后 { 6 这里返回true表示正确插入，返回false表示插入失败。
// 查找第i-1个元素pp = L;
j = 0;while ( p && j&i-1 ) {p = p-&
j++;}//若存在第i个元素，则用x返回数据，并删除之if ( p && j==i-1 && p-&next ) { // 可以删除s = p-&
// ①p-&next = s-&
// ②x = s-&free (s);}else}
注意：a) 要求p找到第i-1个而非第i个元素。为什么？b) 能够进行删除的条件： p && j==i-1 && p-&next 。条件中的p-&next就是要保证第i个元素存在，否则无法删除。若写成p-&next && j==i-1也不妥，因为此时(循环结束时)可能有p==NULL，所以必须先确定p不空。技巧：将条件中的“大前提”放在前面。该条件也不可以写成p-&next && p && j==i-1，因为先有p!=0才有p-&next，上式颠倒了这一关系。c) 释放结点的方法。 free(s);d) 完成删除的步骤：①②。
13. 建立链表的两种方法思路：建立空表（头结点）；依次插入数据结点（每次插入表尾得(a1,a2,?,an)，每次插入表头得(an,?,a2,a1)）。 a) 顺序建表void CreateLinkList ( LinkList &L, int n){// 建立空表L = (LinkList) malloc(sizeof(LNode));L-&next = NULL;
// 空表p = L;
// 用p指向表尾// 插入元素for ( i=0; i&n; i++ ) {scanf ( x );s = (LinkList) malloc(sizeof(LNode));s-&data =// 插入表尾s-&next = p-&p-&next =p =
// 新的表尾}}b) 逆序建表void CreateLinkList ( LinkList &L, int n){// 建立空表L = (LinkList) malloc(sizeof(LNode));L-&next = NULL;
// 空表// 插入元素for ( i=0; i&n; i++ ) {scanf ( x );s = (LinkList) malloc(sizeof(LNode));s-&data =// 插入表头s-&next = L-&L-&next =}}循环链表14. 特点最后一个结点的指针指向头结点。15. 类型定义同单链表。16. 基本形态空表：L-&next == L。非空表。
17. 与单链表的联系判断表尾的方法不同：单链表用p==NULL；循环链表用p==L。其余操作相同。双向循环链表18. 特点一个结点包含指向后继(next)和指向前驱(prior)两个指针，两个方向又分别构成循环链表。19. 类型定义typedef struct DuLNode {DataTstruct DuLNode *prior, *
// 两个 指针 } DuLNode, *DuLinkL20. 基本形态空表：用后向指针判断L-&next == L，或者用前向指针判断L-&prior == L。非空表。
21. 与单链表和循环链表的联系最大不同：前驱容易求得，可以向前遍历。 判断表尾的方法与循环链表相同：p==L。 插入和删除时需要修改两个方向的指针。 22. 插入和删除需要修改两个方向的指针。例如：(见下表)表 错误！文档中没有指定样式的文字。.2 双向循环链表的插入和删除
顺序表与单链表的比较
第三章、栈和队列 栈栈，栈顶，栈底，空栈，后进先出(LIFO)，入栈(Push)，出栈(Pop)。 顺序栈：栈的顺序存储结构；链栈：栈的链式存储结构。 链栈存储结构用不带头结点的单链表实现。 类型定义 同单链表。 基本形态 a) 栈空条件: S == NULLSS S/\b) 栈非空c) 栈满（一般不出现）基本算法d) 入栈 Push (&s, x)bool Push ( LinkList &s, DataType x ) {// 新建结点p = (LinkList) malloc (sizeof(LNode));
if ( !p ) // 失败
p-&data =// 插入栈顶p-&next =s =}e) 出栈 Pop (&s, &x)前提：栈非空。bool Pop ( LinkList &s, DataType &x ) {if ( s==NULL )
// 删除栈顶元素p =s = s-&x = p-&free ( p );}f) 栈顶元素前提：栈非空。bool Top ( LinkList &s, DataType &x ) {if ( s==NULL )
x = s-&}顺序栈存储结构类似于顺序表，插入和删除操作固定于表尾。 类型定义7简单说，“数组 + 长度”。 7 不准确的说法，只为便于理解和记忆，不要在正式场合引用。const int MAXSIZE = 栈的最大容量；typedef struct {DataType elem[MAXSIZE];} SqS基本形态g) 栈空条件
s.top == 0;h) 栈满条件
s.top == MAXSIZEi) 栈不空、不满
基本算法j) 入栈
Push (&s, x)前提：栈不满bool Push ( SqStack& s, DataType x ){if ( s.top == MAXSIZE )
s.elem[top] =
// 或者s.elem[top++] =
代替这两行}k) 出栈
Pop (&s, &x)前提：栈非空bool Pop ( SqStack &s, DataType &x ){if ( s.top==0 )top--;
// 可用x=s.elem[--top];
x = s.elem[top];
代替这两行}l) 栈顶元素前提：栈非空s.elem[top-1] 即是。队列队列，队头，队尾，空队列，先进先出(FIFO)。链队列：队列的链式存储结构。循环队列：队列的顺序存储结构之一。链队列存储结构简而言之，“单链表 + 尾指针”。类型定义课本P61。typedef struct {LinkLLinkL} LinkQ基本形态队列空：Q.front==Q.rear。非空队列。基本算法m) 入队列课本P62。插入队尾，注意保持Q.rear指向队尾。n) 出队列课本P62。删除队头元素，特别注意：如果队列中只有一个元素，则队头也同时是队尾，删除队头元素后也需要修改队尾指针。循环队列存储结构9简单说，“数组 + 头、尾位置”。类型定义const int MAXSIZE = 队列最大容量;typedef struct {DataType elem[MAXSIZE];int front,
// 队头、队尾位置} SqQ基本形态通常少用一个元素区分队列空和队列满，也可以加一标志。约定front指向队头元素的位置，rear指向队尾的下一个位置，队列内容为 [front, rear)。o) 队列空条件：Q.front == Q.rear。不能出队列。p) 队列满条件：(Q.rear+1)%MAXSIZE == Q.front （少用一个元素时）。不能入队列。 8Q.front Q.rear Q.front Q.rear 89 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
不准确的说法，只为便于理解和记忆，不要在正式场合引用。
q) 队列不空也不满
tag:1r) 加一标志区分队列空和队列满的情况可以用满所有空间。队列空和队列满时都有Q.front==Q.rear，再用标志区分。队列空：Q.front==Q.rear and Q.tag==0；队列满：Q.front==Q.rear and Q.tag==1。 基本算法s) 入队列前提：队列不满。bool EnQueue ( SqQueue &Q, DataType x ){if ( (Q.rear+1)%MAXSIZE==Q.front )
// 队列满// 入队列Q.elem [Q.rear] =Q.rear = (Q.rear+1)%MAXSIZE;}t) 出队列前提：队列非空。bool DeQueue ( SqQueue &Q, DataType &x ){if ( Q.front==Q.rear )
// 队列空// 出队列x = Q.elem [Q.front];Q.front = (Q.front+1)%MAXSIZE;}u) 队列中元素个数结论：(Q.rear-Q.front+MAXSIZE)%MAXSIZE。注：Q.rear-Q.front可能小于0，需要加上MAXSIZE。int QueueLength ( SqQueue Q ){return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;}v) 用标志区分队列空和满用标志区分队列空和满时，队列初始化、入队列、出队列和队列长度的算法如下： void InitQueue ( SqQueue &Q ) {
Q.front = Q.rear = 0;
Q.tag = 0;}bool EnQueue ( SqQueue &Q, DataType x ) {if ( Q.front==Q.rear and Q.tag==1 )Q.elem[ Q.rear ] =Q.rear = (Q.rear+1)%MAXSIZE;if ( Q.tag==0 )
Q.tag = 1;
// 队列非空}bool DeQueue ( SqQueue &Q, DataType &x ) {if ( Q.front==Q.rear and Q.tag==0 )x = Q.elem[ Q.front ];Q.front = (Q.front+1)%MAXSIZE;if ( Q.front==Q.rear )
Q.tag = 0;
// 队列空}int QueueLength ( SqQueue Q ){if ( Q.front==Q.rear and Q.tag==1 )return MAXSIZE;
// 队列满elsereturn (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
// 队列不满(包含队列空的情况) }栈和队列比较都是线形结构，栈的操作LIFO（后进先出），队列操作FIFO（先进先出）。简化的栈和队列结构在算法中使用栈和队列时可以采用简化的形式。表 错误！文档中没有指定样式的文字。.4 简化的栈和队列结构
栈和队列的应用w) 表达式求值参见课本P53。x) 括号匹配例：检查表达式中的括号是否正确匹配。如{ ( ) [ ] }正确，( [ ) ] }则错误。 分析：每个左括号都“期待”对应的右括号，匹配成功则可以消去。思路：遇到左括号则入栈，遇到右括号则与栈顶括号相比较，如果匹配则消去，否则匹配失败。当然，如果栈中没有括号可以匹配，或者最后栈中还有未匹配的左括号，也都是匹配错误。// 检查输入的表达式中括号是否匹配bool MatchBrackets (){const int MAXSIZE = 1024;
// 栈的最大容量char s [MAXSIZE];
// 简化的栈结构
// 栈顶// 栈初始化top = 0;// 检查括号是否匹配ch = getchar();while ( ch!=EOF ) {switch ( ch ) {case ‘(‘, ‘[’, ‘{’:s [top++] =
// 所有左括号入栈case ‘)’:if ( top==0 or s [--top]!=’(’ )
// 栈空或右括号与栈顶左括号失配case ‘]’:if ( top==0 or s [--top]!=’[’ )case ‘}’:if ( top==0 or s [--top]!=’{’ )}ch = getchar();
// 取下一个字符}if ( top==0 )
// 正好匹配
// 栈中尚有未匹配的左括号}y) 递归程序的非递归化将递归程序转化为非递归程序时常使用栈来实现。z) 作业排队如操作系统中的作业调度中的作业排队，打印机的打印作业也排成队列。aa) 按层次遍历二叉树void LevelOrder ( BinTree bt, VisitFunc visit ){const int MAXSIZE = 1024;
// 队列容量(足够大即可)BinTree q [MAXSIZE];
// 简化的队列结构int front,
队头、队尾
if ( ! bt )// 初始化队列，根结点入队列front = rear = 0;q [rear] =rear = (rear+1)%MAXSIZE;// 队列不空，则取出队头访问并将其左右孩子入队列while ( front!=rear ) {p = q [front];front = (front+1)%MAXSIZE;if ( p ) {visit ( p-&data );
// 访问结点q [rear] = p-&rear = (rear+1)%MAXSIZE;q [rear] = p-&rear = (rear+1)%MAXSIZE;}}}第四章串基础知识和算法概念串，空串，空格串，串的长度；子串，子串在主串中的位置，主串；串相等。 串的基本操作 表 错误！文档中没有指定样式的文字。.5 串的基本操作Assign (s, t), Create(s, cs)Equal (s, t), Length(s)Concat (s, t)Substr (s, pos, len)Index (s, t)Replace (s, t, v)Delete (s, pos, len) Assign(s,t)将变量t赋值给s，Create(s,cs)根据字串创建变量s。 判断串相等，求串长度。如Length(“”)=0。 串连接。如Concat(“ab”,”cd”)=”abcd”。 取子串，pos为开始位置，len为子串长度。 求子串t在主串s中的位置。如Index(“abc”,”ab”)=1，Index(“a bc”,”bc”)=3。 把串s中的字串t替换成v。如Replace(“aaa”,”aa”,”a”)=”aa”。 删除串s的一部分。注：完成习题集4.1~4.6。串的存储结构表 错误！文档中没有指定样式的文字。.6 串的存储结构定长顺序串堆分配存储表示块链存储表示基础知识和算法树及有关概念 最大长度固定，超过最大长度则作截断处理 串的长度几乎没有限制 块内存储空间连续，块间不连续 树和二叉树树，根，子树；结点，结点的度，叶子（终端结点），分支结点（非终端结点），内部结点，树的度；孩子，双亲，兄弟，祖先，子孙，堂兄弟；层次（根所在层为第1层），深度，高度；有序树，无序树，二叉树是有序树；森林。二叉树二叉树（二叉树与度为2的树不同，二叉树的度可能是0，1，2）；左孩子，右孩子。 二叉树的五种基本形态。二叉树的性质10i-1bb) 二叉树的第i层上至多有2个结点。kcc) 深度为k的二叉树至多有2-1个结点。k
满二叉树：深度为k，有2-1个结点。完全二叉树：给满二叉树的结点编号，从上至下，从左至右，n个结点的完全二叉树中结点在对应满二叉树中的编号正好是从1到n。dd) 叶子结点n0，度为2的结点为n2，则n0 = n2+1。考虑结点个数：n = n0 + n1 + n2考虑分支个数：n-1 = 2n2 + n1可得n0 = n2+1例：1) 二叉树有n个叶子，没有度为1的结点，共有
个结点。 2) 完全二叉树的第3层有2个叶子，则共有
个结点。分析：1) 度为2的结点有n-1个，所以共2n-1个结点。 2) 注意考虑到符合条件的二叉树的深度可能是3或4，所以有5、10或11个结点。ee)ff) n个结点的完全二叉树深度为?logn??1。 n个结点的完全二叉树，结点按层次编号有：
i的双亲是?n/2?，如果i = 1时为根（无双亲）；i的左孩子是2i，如果2i&n，则无左孩子；i的右孩子是2i + 1，如果2i + 1&n则无右孩子。二叉树的存储结构gg) 顺序存储结构用数组、编号i的结点存放在[i-1]处。适合于存储完全二叉树。hh) 链式存储结构二叉链表：typedef struct BTNode {DataTstruct BTNode *lchild, *} BTNode, *BinT三叉链表：typedef struct BTNode {DataTstruct BTNode *lchild, *rchild, *} BTNode, *BinT 10 本书中约定根结点在第1层，也有约定根在第0层的，则计算公式会有所不同。
例：用二叉链表存储n个结点的二叉树(n&0)，共有(_a_)个空指针域；采用三叉链表存储，11共有(_b_)个空指针域。二叉树的五种基本形态① ②①空树：bt==NULL
②左右子树均空：bt-&lchild==NULL and bt-&rchild==NULL ③右子树为空：bt-&rchild==NULL
④左子树为空：bt-&lchild==NULL⑤左右子树均非空。前两种常作为递归结束条件，后三者常需要递归。遍历二叉树ii) 常见有四种遍历方式按层次遍历，先序遍历，中序遍历，后序遍历。 按层次遍历：“从上至下，从左至右”，利用队列。
先序遍历：DLR；中序遍历：LDR；后序遍历LRD。
例：写出a+b*(c-d)-e/f的前缀、中缀和后缀表达式。 画出二叉树，分别进行前序、中序、后序遍历即可得到。前缀表达式：- + a * b - c d / e f中缀表达式：a + b * c - d - e / f后缀表达式：a b c d - * + e f / -
jj) 先序遍历算法void Preorder ( BinTree bt ){if ( bt ) {visit ( bt-&data );Preorder ( bt-&lchild );Preorder ( bt-&rchild );}}kk) 中序遍历算法void Inorder ( BinTree bt ){if ( bt ) {Inorder ( bt-&lchild );visit ( bt-&data );Inorder ( bt-&rchild );11 答案：(a) n+1 (b) n+2。提示：只有根结点没有双亲。}}ll) 后序遍历void Postorder ( BinTree bt ){if ( bt ) {Postorder ( bt-&lchild );Postorder ( bt-&rchild );visit ( bt-&data );}}mm) 按层次遍历思路：利用一个队列，首先将根（头指针）入队列，以后若队列不空则取队头元素p，如果p不空，则访问之，然后将其左右子树入队列，如此循环直到队列为空。void LevelOrder ( BinTree bt ){// 队列初始化为空InitQueue ( Q );// 根入队列EnQueue ( Q, bt );// 队列不空则继续遍历while ( ! QueueEmpty(Q) ) {DeQueue ( Q, p );if ( p!=NULL ) {visit ( p-&data );// 左、右子树入队列EnQueue ( Q, p-&lchild );EnQueue ( Q, p-&rchild );}}}
若队列表示为“数组q[] + 头尾 front, rear”有：void LevelOrder ( BinTree bt ){const int MAXSIZE = 1024;BinTree q[MAXSIZE];int front,// 队列初始化为空front = rear = 0;// 根入队列q[rear] =
rear = ( rear+1 ) % MAXSIZE;// 队列不空则循环while ( front != rear ) {p = q[front];
front = ( front+1 ) % MAXSIZE;if ( p ) {visit ( p-&data );// 左、右子树入队列q[rear] = p-&
rear = ( rear+1 ) % MAXSIZE;q[rear] = p-&
rear = ( rear+1 ) % MAXSIZE;}}}nn) 非递归遍历二叉树一般借助栈实现。设想一指针沿二叉树中序顺序移动，每当向上层移动时就要出栈。 (a) 中序非递归遍历指针p从根开始，首先沿着左子树向下移动，同时入栈保存；当到达空子树后需要退栈访问结点，然后移动到右子树上去。void InOrder ( BinTree bt, VisitFunc visit ){InitStack ( S );p =while ( p || ! StackEmpty(S) ) {if ( p ) {Push ( S, p );p = p-&} else {Pop ( S, p );visit ( p );
// 中序访问结点的位置p = p-&}}}(b) 先序非递归遍历按照中序遍历的顺序，将访问结点的位置放在第一次指向该结点时。void Preorder ( BinTree bt, VisitFunc visit ){InitStack ( S );p =while ( p || ! StackEmpty(S) ) {if ( p ) {visit ( p );
// 先序访问结点的位置Push ( S, p );p = p-&} else {Pop ( S, p );p = p-&}}}或者，由于访问过的结点便可以弃之不用，只要能访问其左右子树即可，写出如下算法。 void Preorder ( BinTree bt, VisitFunc visit ){InitStack ( S );Push ( S, bt );while ( ! StackEmpty(S) ) {Pop ( S, p );if ( p ) {visit ( p );Push ( S, p-&rchild );
// 先进栈，后访问，所以Push ( S, p-&lchild );
这里先让右子树进栈}}}(c) 后序非递归遍历后序遍历时，分别从左子树和右子树共两次返回根结点，只有从右子树返回时才访问根结点，所以增加一个栈标记到达结点的次序。void PostOrder ( BinTree bt, VisitFunc visit ){InitStack ( S ),
InitStack ( tag );p =while ( p || ! StackEmpty(S) ) {if ( p ) {Push ( S, p ),
Push ( tag, 1);
// 第一次入栈p = p-&} else {Pop ( S, p ),
Pop ( tag, f );if ( f==1 ) {// 从左子树返回，二次入栈，然后p转右子树Push ( S, p ),
Push ( tag, 2 );p = p-&} else {// 从右子树返回(二次出栈)，访问根结点，p转上层visit ( p );p = NULL;
// 必须的，使下一步继续退栈}}}}注：后序非递归遍历的过程中，栈中保留的是当前结点的所有祖先。这是和先序及中序遍历不同的。在某些和祖先有关的算法中，此算法很有价值。oo) 三叉链表的遍历算法下面以中序遍历为例。// 中序遍历三叉链表存储的二叉树void Inorder ( BinTree bt, VisitFunc visit ){if ( bt==NULL )
// 空树，以下考虑非空树// 找到遍历的起点p =
// Note: p!=null herewhile ( p-&lchild )
p = p-&// 开始遍历while ( p ) {// 访问结点visit ( p );// p转下一个结点if ( p-&rchild ) {
// 右子树不空，下一个在右子树p = p-&while ( p-&lchild )
转右子树的最左下结点
// 右子树为空，下一个在上层f = p-&while ( p == f-&rchild ) {
若p是右子树则一直上溯p =
f = f-&}}}}遍历二叉树的应用 pp) 写出遍历序列（前、中、后序）qq) 根据遍历序列画出二叉树(a) 已知前序和中序序列，唯一确定二叉树。 例：前序：ABDEGCFH，中序：DBGEAFHC，画出二叉树。分析：前序序列的第一个是根，这是解题的突破口。步骤：①前序序列的第一个是根 ②在中序序列中标出根，分成左右子树 ③在前序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的前序和中序序列重复以上步骤直至完成。(b) 已知后序和中序序列，唯一确定二叉树。例：后序：DGEBHFCA，中序：DBGEAFHC，画出二叉树。分析：后序序列的最后一个是根，这是解题的突破口。步骤：①后序序列的最后一个是根 ②在中序序列中标出根，分成左右子树 ③在后序序列中标出左右子树(根据结点个数即可) ④分别对左右子树的后序和中序序列重复以上步骤直至完成。(c) 已知前序和后序序列，不存在度为1的结点时能唯一确定二叉树。例：前序：ABDEC，后序：DEBCA，画出二叉树。又前序AB，后序BA则不能唯一确定二叉树。
注：对于不存在度为1的结点的二叉树，首先确定根结点，然后总可以将其余结点序列划分成左右子树，以此类推即可确定二叉树。
说明：画出二叉树后可以进行遍历以便验证。rr) 编写算法思路：按五种形态(①--⑤)分析，适度简化。例：求二叉树结点的个数。分析：① 0; ② 1; ③ L+1; ④ 1+R; ⑤ 1+L+R。简化：② 1+L=0+R=0 ③ 1+L+R=0 ④ 1+L=0+R ⑤ 1+L+R 可合并成⑤一种情况。int NodeCount ( BinTree bt ){if ( bt==0 )
return 0;else
return 1 + NodeCount(bt-&lchild) + NodeCount(bt-&rchild);}
例：求二叉树叶子结点的个数。分析：① 0; ② 1; ③ L; ④ R; ⑤ L+R。简化：③④⑤可合并成⑤。int LeafCount ( BinTree bt ){if ( bt==0 )
return 0;else if ( bt-&lchild==0 and bt-&rchild==0 )
return 1;else
return LeafCount(bt-&lchild) + LeafCount(bt-&rchild);}
例：求二叉树的深度。分析：① 0; ② 1; ③ 1+L; ④ 1+R; ⑤ 1+max(L,R)。简化：②③④⑤可合并成⑤。 int Depth ( BinTree bt ){if ( bt==0 )
return 0;else
return 1 + max(Depth(bt-&lchild), Depth(bt-&rchild));}线索二叉树ss) 线索n个结点的二叉链表中有n+1个空指针，可以利用其指向前驱或后继结点，叫线索，同时需附加一个标志，区分是子树还是线索。
lchild 有左子树，则指向左子树，标志ltag == 0；没有左子树，可作为前驱线索，标志ltag == 1。rchild 有右子树，则指向右子树，标志rtag == 0；没有右子树，可作为后继线索，标志rtag == 1。tt) 线索化二叉树利用空指针作为线索指向前驱或后继。左边空指针可以作为前驱线索，右边空指针可以作为后继线索，可以全线索化或部分线索化。表 错误！文档中没有指定样式的文字。.7 线索化二叉树的类型中序线索化 前序线索化 后序线索化uu) 画出线索二叉树思路：先写出遍历序列，再画线索。 步骤： 标出必要的空指针（前驱?左指针；后继?右指针，要点：“不要多标，也不要少标”）。
写出对应的遍历序列（前序，中序或后序）。
对照遍历结果画线索。例：画出图中二叉树的后序后继线索。步骤：先标出所有空的右指针(DGCH)；写出后序遍历结果：DGEBHFCA；标出后继线索：D?G, G?E,C?A, H?F。如图。
vv) 遍历线索二叉树反复利用孩子和线索进行遍历，可以避免递归。 树和森林ww) 树的存储结构双亲表示法，孩子表示法，孩子兄弟表示法。特点：双亲表示法容易求得双亲，但不容易求得孩子；孩子表示法容易求得孩子，但求双亲麻烦；两者可以结合起来使用。孩子兄弟表示法，容易求得孩子和兄弟，求双亲麻烦，也可以增加指向双亲的指针来解决。 xx) 树与二叉树的转换表 错误！文档中没有指定样式的文字。.8 树和二叉树的对应关系
前驱、后继线索 中序全线索 前序全线索 后序全线索前驱线索 中序前驱线索 前序前驱线索 后序前驱线索后继线索 中序后继线索 前序后继线索 后序后继线索特点：由树转化成的二叉树，根结点没有右孩子 例：树转换成二叉树。
yy) 森林与二叉树的转换森林中第1棵树的根作为对应的二叉树的根；其他的树看作第1棵树的兄弟；森林中的树转换成对应的二叉树。则森林转换成对应的二叉树。 例：将森林转换成对应的二叉树。参见课本P138。 zz) 树的遍历树的结构：①根，②根的子树。先根遍历：①②。例：ABCDEFGHIJK。 后根遍历：②①。例：CEDFBHGJKIA。 aaa) 遍历森林森林的结构：①第一棵树的根，②第一棵树的根的子树森林，③ 其余树(除第一棵外)组成的森林。先序遍历：①②③。例：ABCDEFGHIJ。 中序遍历：②①③。例：BDCEAGFIJH。 注：先序遍历森林，相当于依次先根遍历每一棵树；中根遍历森林相当于后根遍历每一棵树。树的结构划森林的结构划分
bbb) 遍历树、森林与遍历二叉树的关系表 错误！文档中没有指定样式的文字。.9 遍历树、森林和二叉树的关系树 先根遍历 后根遍历森林 先序遍历 中序遍历二叉树 先序遍历 中序遍历
赫夫曼树及其应用ccc) 最优二叉树(赫夫曼树，哈夫曼树)树的带权路径长度：所有叶子结点的带权路径长度之和。WPL??wklkk?1n路径长度lk按分支数目计算。带权路径长度最小的二叉树称为最优二叉树，或赫夫曼树(哈夫曼树)。 ddd) 构造赫夫曼树 算法：参见课本P145。12简单说，“每次取两个最小的树组成二叉树”。 eee) 赫夫曼编码(前缀码)向左分支为0，向右分支为1，从根到叶子的路径构成叶子的前缀编码。例：字符及其权值如下：A(6), B(7), C(1), D(5), E(2), F(8)，构造哈夫曼树和哈夫曼编码，计算带权路径长度。12不准确的说法，只为便于理解和记忆，不要在正式场合引用。
哈夫曼编码： A:00 B:01 C:1110 D:110 E:1111WPL = (6+7+8)*2+5*3+(1+2)*4 = 69或采用课本上的算法计算，如下。
说明：同样的一组权值可能构造出不同的哈夫曼树，结果不一定唯一，但带权路径长度都是最小的。 技巧：要使前一种方法构造出的赫夫曼树和课本上算法产生的一样，只要把每次合并产生的二叉树放在树的集合的末尾，并且总是用两个最小树的前者作为左子树后者作为右子树。图基础知识和算法图的有关概念图，顶点，弧，弧头，弧尾；有向图（顶点集+弧集），0≤e≤n(n-1)，无向图（顶点集+边集），0≤e≤n(n-1)/2；稀疏图（e&nlogn），稠密图；完全图e=n(n-1)/2，有向完全图e=n(n-1)；网，有向网，无向网。子图，邻接点，顶点的度，入度，出度；路径，路径长度（经过边或弧的数目），简单路径，回路（环），简单回路（简单环）；连通图，连通分量，强连通分量。例：有6个顶点组成的无向图构成连通图，最少需要(_a_)条边；当边的数目大于(_b_)时，该图必定连通。分析：a. 5。最少有n-1条边就可以构成连通图。 b. 10。考虑将n个顶点分成两组，一组有n-1个顶点，另一组只有1个顶点。首先在第一组中添加边，直到n-1个顶点构成全连通子图，共(n-1)(n-2)/2条边，此后若再在图中任意添加一条边将必定连通两组顶点，从而构成连通图。思考：对有向图有何结论。图的存储结构图的存储结构常见图的存储结构有：邻接矩阵，邻接表，逆邻接表，十字链表，邻接多重表。 邻接多重表只适用于存储无向图，其他存储结构可以存储无向图和有向图。
例：画出图的邻接矩阵、邻接表、逆邻接表和十字链表。邻接矩阵 13简言之，“数组(顶点)+二维数组(弧)+个数”。const int MAX_VERTEX = 最大顶点个数;typedef struct Graph {
// 图VertexType
vexs[MAX_VERTEX]; // 顶点向量
arcs[MAX_VERTEX] [MAX_VERTEX];
// 邻接矩阵int
vexnum, // 顶点和弧的个数} G
图：有边(弧)为1；否则为0。网：有边(弧)为权值；否则为∞。2存储空间个数为n，与边的数目无关。无向图的邻接矩阵是对称的。ABCDE
邻接表13 不准确的说法，只为便于理解和记忆，不要在正式场合引用。简言之，“数组(弧尾顶点)+链表(邻接点)+个数”。typedef struct ArcNode {
// 弧结点 // 邻接点struct ArcNode * // 下一个邻接点} ArcN
typedef struct VexNode {
// 顶点结点VertexT // 顶点信息ArcNode * // 第一个邻接点} VexN
const int MAX_VERTEX = 最大顶点个数;typedef struct Graph {
// 图VexNode
vexs[MAX_VERTEX]; // 顶点向量int
vexnum, // 顶点和弧的个数} G
边(弧)多则需要存储空间多。14
逆邻接表15简言之，“数组(弧头顶点)+链表(逆邻结点)+个数”。类型定义类似邻接表。
十字链表16简言之，“数组(顶点)+弧结点(含头和尾)+个数”。边可以看作两条弧。typedef struct ArcNode {
// 弧结点int
vtail, // 弧尾和弧头顶点编号struct ArcNode
*nexttail, * // 指向同弧尾和同弧头的弧结点 } ArcN
141516 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
不准确的说法，只为便于理解和记忆，不要在正式场合引用。
不准确的说法，只为便于理解和记忆，不要在正式场合引用。typedef struct VexNode {
// 顶点结点VertexT // 顶点信息ArcNode
*firstin, * // 指向第一条入弧和第一条出弧 } VexN
const int MAX_VERTEX = 最大顶点个数;typedef struct Graph {
// 图VexNode
vexs[MAX_VERTEX]; // 顶点向量int
vexnum, // 顶点和弧的个数} G
弧结点中包含两个指针分别指向同一弧头的下一个弧和同一个弧尾的下一个弧。顶点结点则指向第一个同弧头和弧尾的弧。十字链表相当于邻接表和逆邻接表的结合。
技巧：把弧结点按行排整齐，然后画链表。同弧尾的弧组成链表，同弧头的弧组成链表。 邻接多重表17简言之，“数组(顶点)+边结点”。typedef struct EdgeNode {
// 边结点int
vexi,struct EdgeNode
*nexti, *} EdgeN
typedef struct VexNode {
// 顶点结点VertexTypeEdgeNode
const int MAX_VERTEX = 最大顶点个数;typedef struct Graph {
// 图VexNode
vexs[MAX_VERTEX];int
vexnum,} G
只适合存储无向图，不能存储有向图。17// 边的两个顶点 // 两个顶点所依附的下一条边 // 顶点信息 // 指向第一条边 // 顶点向量 // 顶点和边的个数
不准确的说法，只为便于理解和记忆，不要在正式场合引用。
技巧：把边结点按列排整齐，然后画链表。相同顶点组成链表，这里没有起点和终点的区别。 图的遍历深度优先搜索遍历方法从图中某个顶点出发，访问此顶点，然后依次从其未被访问的邻接点出发深度优先遍历图；若图中尚有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述过程，直到图中所有顶点都被访问为止。分析方法方法：画一棵“深度优先搜索树”。
例：下图从A出发深度优先搜索的结果是：ABEDC。分析：画“深度优先搜索树”。从A出发，访问A(画圈作标记)，A的邻接点有B和C(作为A的孩子)，B未访问，访问B(画圈)，B的邻接点有E(作B的孩子)，...，以此类推，画出搜索树。深度优先搜索的过程就是沿着该搜索树先根遍历的过程。技巧：顶点的邻接点是无所谓次序的，所以同一个图的深度优先遍历序列可能不同，但在遍历时(除非邻接点的次序有明确规定)一般按照编号顺序安排邻接点的次序。
算法课本上的算法稍加改动：void DFSTraverse ( Graph G ){visited [0 .. G.vexnum-1] =
// 初始化访问标志为未访问(false)
for ( v=0; v&G. v++ )if ( ! visited[v] )
DFS ( G, v );
// 从未被访问的顶点开始DFS }
void DFS ( Graph G, int v ){visit ( v );
visited [v] =
// 访问顶点v并作标记for ( w=FirstAdjVex(G,v); w&=0; w=NextAdjVex(G,v,w) )if ( ! visited[w] )
DFS ( G, w );
// 分别从每个未访问的邻接点开始DFS }其中的FirstAdjVex(G,v)表示图G中顶点v的第一个邻接点，NextAdjVex(G,v,w)表示图G中顶点v的邻接点w之后v的下一个邻接点。深度优先搜索算法有广泛的应用，以上算法是这些应用的基础。广度优先搜索遍历方法从图中某顶点出发，访问此顶点之后依次访问其各个未被访问的邻接点，然后从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”要先于“后被访问的顶点的邻接点”被访问，直至所有已被访问的顶点的邻接点都被访问。若图中尚有顶点未被访问，则另选图中未被访问的顶点作为起始点，重复以上过程，直到图中所有顶点都被访问为止。 广度优先搜索从某顶点出发，要依次访问路径长度为1，2，? 的顶点。分析方法方法：画一棵“广度优先搜索树”。
例：下图从A出发广度优先遍历的结果是：ABCED。分析：画“广度优先搜索树”。与深度优先搜索树类似，A为根，其邻接点为其孩子，访问一个顶点，则扩展出其孩子。不过广度优先搜索的访问次序是对该树按层遍历的结果。
算法利用队列(类似按层遍历二叉树)。void BFSTraverse ( Graph G ){visited [0 .. G.vexnum-1] =
// 初始化访问标志为未访问(false)
InitQueue ( Q );for ( v=0; v&G. v++ )if ( ! visited[v] )
{// 从v出发广度优先搜索visit ( v );
visited [v] =EnQueue ( Q, v );while ( ! QueueEmpty(Q) )
{DeQueue ( Q, u );for ( w=FirstAdjVex(G,u); w&=0; w=NextAdjVex(G,u,w) )if ( ! visited[w] )
{visit ( w );
visited [w] =EnQueue ( Q, w );
} }时间复杂度分析观察搜索树可以看出，无论是深度优先搜索还是广度优先搜索，其搜索过程就是对每个顶点求所有邻接点的过程。当用邻接表存储图时，其时间复杂度为O(n+e)；当采用邻接矩阵作2为存储结构时，时间复杂度是O(n) (因为求一个顶点的所有邻接点就是搜索邻接矩阵的一2行中的n个数，而顶点的个数为n，总共就是n)。 最小生成树最小生成树及MST性质 最小生成树。MST性质。注意：同一个连通网的最小生成树可能是不唯一的，但其代价都是最小(唯一的)。 克鲁斯卡尔算法18一句话，“不构成环的情况下，每次选取最小边”。
(a) 无向网(b)-(e) 克鲁斯卡尔算法计算最小生成树(f) 得到的最小生成树(g) 另一个可能的最小生成树
提示：在不要步骤、只要结果的情况下可采用，边较少时特别有效。 普里姆算法记V是连通网的顶点集，U是求得生成树的顶点集，TE是求得生成树的边集。 普里姆算法：18不准确的说法，只为便于理解和记忆，不要在正式场合引用。(a) 开始时，U={v0}，TE=Φ；(b) 计算U到其余顶点V-U的最小代价，将该顶点纳入U，边纳入TE； (c) 重复(b)直到U=V。
例：用普里姆算法计算下图的最小生成树。
特点只与顶点个数n有关 与边的数目e无关 适用于稠密图只与边的数目e有关 与顶点个数n无关 适用于稀疏图拓扑排序有向无环图(DAG)，AOV网；拓扑排序。19拓扑排序，一句话“每次删除入度为0的顶点并输出之”。例：以下DAG图拓扑排序的结果是：ABCDE。 注意：拓扑排序的结果不一定是唯一的。如：ACBDE也是以上DAG图的拓扑有序序列。 关键路径AOE网，关键路径AOE 网(活动在边上)，边代表活动或任务，顶点代表事件。 事件i发生后，其后继活动a(i,*)都可以开始；只有所有先导活动a(*,j)都结束后，事件j才发生。关键路径算法问题：a) 整个工程完工需要多长时间？ b) 哪些活动影响工程的进度？或求关键路径。 事件(顶点) i： 最早发生时间ve(i)，最晚发生时间vl(i)； 活动(边) a(i,j)： 最早开始时间e(i,j)，最晚开始时间l(i,j)。于是，整个工程完工的时间就是终点的最早发生时间；关键路径就是路径长度最长的路径。 19不准确的说法，只为便于理解和记忆，不要在正式场合引用。
求关键路径的算法：(a) 按拓扑有序排列顶点：对顶点拓扑排序； (b) 计算ve(j)：
?ve(1)?0,其中*为任意前驱事件； ??ve(j)?max{ve(*)?a(*,j)}?vl(n)?ve(n),其中*为任意后继事件； ??vl(i)?min{vl(*)?a(i,*)}(c) 计算vl(i)：(d) 计算e(i,j)和l(i,j)：e(i,j)?ve(i),
l(i,j)?vl(j)?a(i,j)(e) 结论：工程总用时ve(n)，关键活动是e(i,j)=l(i,j)的活动a(i,j)。 说明：
1. 若只求工程的总用时只要进行步骤(a)-(b)即可求得。 02. 如何理解计算ve(j)和vl(i)的公式：事件j在所有前驱活动都完成后发生，所以其最早发生时间ve(j) = max{ve(*)+a(*,j)}，即取决于最慢的前驱活动。另一方面，事件i发生后所有后继活动都可以开始了，所以其最晚发生时间vl(i) = min{vl(*)-a(i,*)}，即不耽误最慢的后继活动。例：某工程的AOE网如下，求1) 整个工程完工需要多长时间，2) 关键路径。说明：图中的虚线仅表示事件的先后关系，不代表具体活动。
分析：按照拓扑有序排列顶点，然后“从前往后”计算事件的最早发生时间得到总时间，再“从后往前”计算事件的最晚发生时间，最后计算活动的最早和最晚开始时间得到关键活动和关键路径。表 错误！文档中没有指定样式的文字。.12 关键路径
所以，1) 工程完工需要时间15，2) 关键路径是1?2?5?6?8?9。 最短路径迪杰斯特拉算法求一个顶点到其他各顶点的最短路径。算法：(a) 初始化：用起点v到该顶点w的直接边(弧)初始化最短路径，否则设为∞； (b) 从未求得最短路径的终点中选择路径长度最小的终点u：即求得v到u的最短路径； (c) 修改最短路径：计算u的邻接点的最短路径，若(v,?,u)+(u,w)&(v,?,w)，则以(v,?,u,w)代替。(d) 重复(b)-(c)，直到求得v到其余所有顶点的最短路径。 特点：总是按照从小到大的顺序求得最短路径。例：用迪杰斯特拉算法求下图中A到其余顶点的最短路径。
(比原来)有更短路径即可，这弗洛伊德算法求每对顶点之间的最短路径。(0)(1)(n)(0)(k)(k)(k-1)依次计算A，A，?，A。A为邻接矩阵，计算A时，A(i,j)=min{A(i,j), (k-1)(k-1)A(i,k)+A(k,j)}。(k)技巧：计算A的技巧。第k行、第k列、对角线的元素保持不变，对其余元素，考查A(i,j)20与A(i,k)+A(k,j) （“行+列”），如果后者更小则替换A(i,j)，同时修改路径。例：用弗洛伊德算法计算图中各顶点之间的最短路径。20第k列i“行”元素加上第k行j“列”元素。
3第4列也不变，这样，只剩下A(4,2)和A(4,3)需要计算。查找基础知识和算法 有关概念查找表，静态查找表（只进行“查找”），动态查找表（可“查找”，“插入”，“删除”）。 关键字，平均查找长度ASL??picii?1npi第i个关键字出现的概率，ci比较的关键字的个数。静态查找表，顺序查找表，折半查找表，静态树表，次优查找树，索引顺序表。 动态查找表，二叉排序树，平衡二叉树（AVL树），B-树，B+树，键树，哈希表。 顺序查找思路按顺序逐个比较，直到找到或找不到。算法程序，要灵活应用。例如：在数组a的前n个元素中查找x int Search ( int a[], int n, int x ) {for ( i=n-1; i&=0; i-- )
if ( a[i]==x )
return -1;
// -1表示找不到 }编程技巧：所有执行路径都要有正确的返回值，不要忘记最后那个return语句。 应试技巧：题目要求不明确时，按照方便的方法做，用适当的注释说明。分析顺序查找特点：思路简单(逐个比较)，适用面广(对查找表没有特殊要求)。平均查找长度一般在等概率情况下，查找成功时，平均查找长度
ASL?1?2?...?nn?1 ?n2思路：假设对每个元素进行1次查找，共进行n次查找，计算出进行比较的关键字的个数，然后除以查找次数n，就求得平均查找长度。例：10个元素的表等概率情况下查找成功时的平均查找长度
ASL?1?2?...?10?5.5 10判定树判定树是一种描述查找中比较过程的直观形式，个关键字所在层次就是其查找长度，有利于分析找过程。顺序查找的判定树是一棵深度为n的单支的树。课本上顺序查找从an开始，当然也可以开始。每查分从a1
时间复杂度从平均查找长度看顺序查找的时间复杂度是O(n)。折半查找思路待查找的表必须是有序的，先从中间开始比较，比较一次至少抛弃一半元素，逐渐缩小范围，直到查找成功或失败。算法要熟练掌握该算法。设a[]升序有序，有以下算法：int BinarySearch ( DataType a[], int n, DataType x ){low = 0; high = n-1;while ( low &= high ) {mid = ( low + high )/2;
// 折半if ( a[mid]==x )
// 找到else if ( x&a[mid] )
// x位于低半区 [low..mid-1]high = mid C 1;else
// x位于高半区 [mid+1..high]low = mid + 1;}return -1;
// -1表示未找到}或者有递归版本：int BinarySearch ( DataType a[], int low, int high, DataType x )
{if ( low&high )
return -1;
// 查找失败mid = (low+high)/2;
// 折半if ( a[mid]==x )
// 找到else if ( x&a[mid] )return BinarySearch (a, low, mid-1, x);elsereturn BinarySearch (a, mid+1, high, x);}另外，程序可有多种写法。例：a[]递减有序，折半查找，请填空。int bs ( T a[], int n, T x ){i = n-1; j = 0;while (____a____) {
m = ____b____;if (____c____)
// succeededelse if (____d____)
i = ____e____;else
____f____;}return -1;
// not found21}分析特点：速度很快，要求查找表是有序的，而且随机访问(以便计算折半的下标)。所以，链表不能进行折半查找(但可以采用二叉排序树等形式进行快速的查找)。判定树折半查找的判定树类似于完全二叉树，叶子结点所在层次之差最多为1，其深度为?logn??1。查找过程就是走了一条从根到该结点的路径。如：表长n=10的有序表折半查找的判定树如下。 21 答案：a: j&=i
b: (i+j)/2
c: a[m]==x
2 3 4平均查找长度结论：等概率查找成功时的平均查找长度n?501hn?1j?1ASLbs??j2?log(n?1)?1?log(n?1)?1 nj?1n分析方法：对等概率情况，假设查找n次，且每个查找1次，共比较关键字c次，则平均c/n次。例：表长为n = 10，平均查找长度如下。ASL?3?2?3?4?1?3?4?2?3?429??2.9时间复杂度结论：O(logn)，根据平均查找长度计算。
有时对需要反复查找的数据预先排序，再折半查找也是划算的。比如有1000个数据，顺序查找100次，平均比较约100×500=50000次；快排大约比较1.44nlogn = 1.44×1000×10 = 1次折半查找比较不超过100×9×2=1800次(考虑到同一关键字的两次比较)，排序后折半查找合计比较不超过大约16200次。索引顺序表分块，块间有序 + 块内无序，对应索引表有序 + 顺序表（无序）。索引顺序表的查找性能介于顺序查找与折半查找之间。
分块的最佳长度是多少？规定条件：每块的大小相同，对块索引表和块内查找均采用顺序查找。设表长为n，等分成b块，采用顺序查找确定块需要比较(b+1)/2次，块内顺序查找比较(n/b+1)/2次，总共C(b)=(b+1)/2+(n/b+1)/2，要使C(b)最小，有b?。二叉排序树二叉排序树二叉排序树或为空树；或者是这样一棵二叉树，若左子树不空，则左子树上所有结点均小于根结点，若右子树不空，则右子树上所有结点均大于根结点，其左、右子树也是二叉排序树。 技巧：如果中序遍历二叉排序树，得到的结果将从小到大有序。手工判别二叉排序树的方法之一。
例：判断对错：二叉排序树或是空树，或是这样一棵二叉树，若左子树不空，则左孩子小于根结点，若右子树不空，则右孩子大于根结点，左、右子树也是这样的二叉排序树。（×）请自己举反例。
查找思路：①若二叉树为空，则找不到，②先与根比较，相等则找到，否则若小于根则在左子树上继续查找，否则在右子树上继续查找。递归算法：BstTree BstSearch ( BstTree bst, DataType x ){if ( bst==NULL )return NULL;else if ( bst-&data==x )else if ( x&bst-&data )return BstSearch ( bst-&lchild, x);elsereturn BstSearch ( bst-&rchild, x);}非递归算法:BstTree BstSearch ( BstTree bst, DataType x ){p =while ( p ) {if ( p-&data==x )else if ( x&p-&data )p = p-&elsep = p-&}return NULL;
// not found}插入思路：先查找，若找不到则插入结点作为最后访问的叶子结点的孩子。新插入的结点总是叶子。建立经过一系列插入操作可以建立二叉排序树。给定关键字序列，建立二叉排序树。方法：①开始二叉树为空，②对每一个关键字，先进行查找，如果已存在，则不作任何处理，否则插入。22一句话，“从空树开始，每次插入一个关键字”。例：给定关键字序列{53，45，12，24，90，45，80}，建立二叉排序树。 22 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
删除叶子直接删除即可。
删除左子树或右子树为空
“移花接木”：将左子树或右子树接到双亲上。
删除左右子树都不空 “偷梁换柱”：借左子树上最大的结点替换被删除的结点，然后删除左子树最大结点。（或者借用右子树上最小结点然后删除之亦可。）
删除分析判定树和二叉排序树相同。结点的层次等于查找时比较关键字的个数。
等概率情况下查找成功时1n1?2?2?3?3?4ASL??h
i??2.5i?1若按照关键字有序的顺序插入结点建立二叉排序树，将得到一棵单支树，对其进行查找也退化为顺序查找，平均查找长度为(1+n)/2。一般地，如果在任一关键字k之后插入二叉排序树的关键字都大于或都小于k，则该二叉排序树是单分支的，深度是n，查找效率和顺序查找相同。 平衡二叉树平衡因子和平衡二叉树(AVL树)平衡因子：左子树深度 C 右子树深度。平衡二叉树中各个结点的平衡因子只能是0，1，-1。构造平衡二叉排序树思路：按照建立二叉排序树的方法逐个插入结点，失去平衡时作调整。23失去平衡时的调整方法：1) 确定三个代表性结点。(A是失去平衡的最小子树的根；B是A的孩子；C是B的孩子，也是新插入结点的子树)。关键是找到失去平衡的最小子树。2) 根据三个代表性结点的相对位置(C和A的相对位置)判断是哪种类型(LL, LR, RL, RR)。 3) 平衡化。“先摆好三个代表性结点(居中者为根)，再接好其余子树(根据大小)”。
例：给定关键字的序列{13，24，37，90，53，40}，建立平衡二叉排序树。 注意：失去平衡时先确定失去平衡的最小子树，这是关键，然后判断类型（LL，LR，RL，RR），再平衡化处理。分析查找 (同二叉排序树) 平均查找长度ASL结论：平均查找性能O(log n)。 23这里没有使用课本上“旋转”的概念，这只是做题的方法，并不是正规的算法描述。为求得n个结点的平衡二叉树的最大高度，考虑高度为h的平衡二叉树的最少结点数。? 0,
h?0 ? Nh?? 1,
h?1? N?N?1,
h?2k-2?k-1部分结果如下，Fh表示斐波纳契数列第h项。表 错误！文档中没有指定样式的文字。.13 平衡二叉树的高度和结点个数
观察可以得出Nh = Fh+2 C 1, h≥0。解得h?log?((n?1))?2?1.44 log (n?1)-0.328其中??(?1)/2。时间复杂度一次查找经过根到某结点的路径，所以查找的时间复杂度是O(log n)。+B-树和B树B-树一棵m阶B-树，或为空树，或满足： (1) 每个结点至多有m棵子树；(2) 若根结点不是叶子，则至少有两棵子树； (3) 除根之外的所有非终端结点至少有?m/2?棵子树；(4) 所有非终端结点包含n个关键字和n+1棵子树：(n, A0, K1, A1, ..., Kn, An)，其中关键字满足A0&K1&A1&...&Kn&An，关键字的个数?m/2??1?n?m?1。 (5) 所有叶子在同一层，不含信息，表示查找失败。B树B+树和B-树的差异：n棵子树的结点中含有n个关键字；所有叶子结点中包含了全部关键字，且按大小顺序排列；所有非终端结点都是索引。 对B+树既可以进行顺序查找又可以进行随机查找。 键树又叫数字查找树。常见的两种存储结构：孩子兄弟链表，多重链表。 哈希表24+
解斐波纳契递推式代入得?1???Nh?n??????1????h?2??????1????h?2?1?n?????1??????????1????h?2?1?1?h?2?1,其中???1
然后整理，取对数可解得h。哈希表(散列表，杂凑表)根据设定的哈希函数和处理冲突的方法，将一组关键字映像到一个有限的连续的地址集上，并以关键字在地址集中的象作为记录在表中的存储位置，这种表称为哈希表，又叫散列表，杂凑表。哈希函数常用除留余数法。H(key) = key MOD p。冲突什么是冲突？H(key1)=H(key2)，且key1≠key2，称冲突。处理冲突的方法：当H(key)处已有记录，出现冲突，如何处理？开放定址法试用H(key)di，常见以下三种。(1) 线形探测再散列：试用H(key)1，H(key)2，...2222(2) 二次探测再散列：试用H(key)1，H(key)-1，H(key)2，H(key)-2，...(3) 伪随机探测再散列：试用H(key)f(1)，H(key)f(2)，...再哈希法H1(key)冲突，试用H2(key)，H3(key)，...链地址法发生冲突的记录链成单链表。建立公共溢出区所有冲突记录存入溢出区。装填因子
??n n个记录，m个地址空间。哈希表的平均查找长度与记录个数n不直接相关，而是取决于装填因子和处理冲突的方法。 举例例：已知一组关键字{19, 14, 23, 1, 68, 20, 85, 9}，采用哈希函数H(key)=key MOD 11，请分别采用以下处理冲突的方法构造哈希表，并求各自的平均查找长度。1) 采用线性探测再散列；2) 采用伪随机探测再散列，伪随机函数为f(n) = - n；3) 采用链地址法。
思路：开始时表为空，依次插入关键字建立哈希表。
1) 线性探测再散列
? 关键字? H(key) 68 20 85 9 2 9 8 9 key 19 14 23 1 H(key) 8 3 1 12 3
10 0查找长度 1 1 1 2 3 1 3
ASL = (1+1+1+2+3+1+3+3)/8 = 15/8
2) 伪随机探测再散列
? 冲突时计算下一地址 ?
3 ? 每个关键字的查找长度key 19 14 23 1 68 20H(key) 8 3 1 1 2 9
查找长度 1 1 1 2 1
ASL = (1+1+1+2+1+1+2+4)/8 = 13/8
3) 链地址法
12345678910 85 9 8 9 7
1 8 7 6 2 4ASL = (1×5+2×3)/8 = 11/8注：关键字在链表中的插入位置可以在表头或表尾，也可以在中间以便保持关键字有序。最后，此哈希表的装填因子是α= 8/11。内部排序基础知识和算法排序的有关概念排序（按关键字大小顺序排列数据）。2排序方法：内部排序，外部排序；简单的排序方法O(n)，先进的排序方法O(nlogn)，基数排序O(dn)；插入排序，交换排序，选择排序，归并排序，计数排序。排序方法的稳定性：取决于该方法采取的策略，不是由一次具体的排序结果决定的。但是通过列举不稳定的排序实例可以说明该排序算法的不稳定性。直接插入排序思路将待排序记录插入已排好的记录中，不断扩大有序序列25一句话，“将待排序记录插入有序序列，重复n-1次”。例：52，49，80，36，14，58，61 进行直接插入排序。
分析表 错误！文档中没有指定样式的文字。.14 直接插入排序
记录顺序有序时记录逆序有序时2比较 n-1 ((n+2)(n-1))/2 2移动 0 ((n+4)(n-1))/2
最好 最坏 平均n/4，算法的时间复杂度O(n)。直接插入排序是稳定的排序算法。折半插入排序思路在直接插入排序中，查找插入位置时采用折半查找的方法。程序void BinInsertSort ( T a[], int n ){for ( i=1; i&n; i++ ) {// 在a[0..i-1]中折半查找插入位置使a[high]≤a[i]&a[high+1..i-1]low = 0;
high = i-1;while ( low&=high ) {m = ( low+high )/2;if ( a[i]&a[m] )high = m-1;elselow = m+1;25 不准确的说法，只为便于理解和记忆，不要在正式场合引用。}// 向后移动元素a[high+1..i-1]，在a[high+1]处插入a[i]x = a[i];for ( j=i-1; j& j-- )a[j+1] = a[j];a [high+1] =
// 完成插入}}分析2时间复杂度O(n)。比直接插入排序减少了比较次数。折半插入排序是稳定的排序算法。希尔排序（缩小增量排序）思路先将待排序列分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进行直接插入排序。步骤：01. 分成子序列(按照增量dk)；02. 对子序列排序(直接插入排序)；03. 缩小增量，重复以上步骤，直到增量dk=1。增量序列中最后一个增量一定是1，如：... 9, 5, 3, 2, 1和... 13, 4, 1。如没有明确说明增量序列可以选择... 3, 2, 1或... 5, 3, 2, 1。例：希尔排序(52，49，80，36，14，58，61)。dk=3dk=2dk=1
3/2注意：希尔排序是不稳定的。时间复杂度大约为O(n)。程序void ShellSort ( T a[], int n ){dk = n/2;while ( dk&=1 ) {// 一趟希尔排序，对dk个序列分别进行插入排序for ( i= i&n; i++ ) {x = a[i];for ( j=i- j&=0 and x&a[j]; j-=dk )a[j+dk] = a[j];a[j+dk] =}// 缩小增量dk = dk/2;}}起泡排序思路26一句话，“依次比较相邻元素，‘逆序’则交换，重复n-1次”。例：冒泡排序(52，49，80，36，14，58，61)。52 49 80 36 14 58 61
程序请参考错误！未找到引用源。BubbleSort算法。分析2比较和交换总是发生在相邻元素之间，是稳定的排序算法。时间复杂度O(n)。快速排序思路一趟排序把记录分割成独立的两部分，一部分关键字均比另一部分小，然后再分别对两部分快排。例：{52
61} 快速排序。下面是一次划分的详细步骤：26 不准确的说法，只为便于理解和记忆，不要在正式场合引用。
整个快速排序过程如下：(52 49 80 36 14 58 61)
程序void QuickSort ( T a[], int low, int high ) {if ( low & high ) {// 划分pivot = a[low];i = j =while ( i & j ) {while ( i&j && a[j] &= pivot )
a[i] = a[j];while ( i&j && a[i] &= pivot )
a[j] = a[i];}a[i] =// 对子序列快排
QuickSort ( a, low, i-1); 技巧： 选第1个记录为轴，分别从后向前，从前向后扫描记录，后面“抓大放小”(如：①②)，前面“抓小放大”(如：③④)，交替进行(⑤-⑦)，最后将轴QuickSort ( a, i+1, high);}}分析2平均情况下，时间复杂度O(nlogn)。记录本来有序时为最坏情况，时}
我要回帖
更多推荐
- ·b站如何看已结束的直播在b站上观看直播？
- ·求一首阿伊呀伊呀一直重复的英文歌歌 我找了7年了 跪求大神帮我
- ·求日本的地狱叫什么2000年恐怖片（生地狱）
- ·开创了凡尔纳的作品成为现代什么小说先河现代科幻小说的先河？
- ·急求dirk的互以后我就不打扰了歌词的这首歌歌词唱完紧接着的大声的怼的没有唱的几声原曲名？
- ·这个logo的设计思路做起来的思路具体是什么？
- ·2019年高考届高考选择什么专业最好，那那个大学好？
- ·女儿在韩国探亲签证工作妈妈可以去探亲吗
- ·成百上千系统字典是什么意思思查查字典吧
- ·3岁骏马动漫儿童城溜冰怎么溜出幼儿园?
- ·有网贷中介能赚钱吗，银行贷款，有50万元，我想知道干什么最赚钱，最好三天赚50的
- ·壹号门的本科教学质量报告如何？ 各位同学们。。。
- ·问一下关于长沙ARM达内培训 嵌入式杭培训的问题
- ·水上水下施工所挂铁路信号施工图纸怎么填
- ·为什么油库内路灯灯杆安装套定额必须安装防雷接地
- ·常德眼袋做的好的第七元素是做啥子的哦？
- ·北京博为峰培训靠谱吗linux培训哪个比较靠谱呢？
- ·（日语）一路平安的祝福语
- ·若一个图的独立顶点集集为{a,b,c,d,e,f}，边集为{(a,b),(a,c),(b,c),(d,e)}，则该图含有__3_____个连通分量。
- ·72枚棋子 英文，每次只能取1~6颗，拿到最后一颗输，问怎样取胜
- ·爱乐乐享国际早教祺有哪些早教课程？怎么样？
- ·银行里my ideal job费用是什么意思
- ·水泥稳定碎石施工方案养护期结束，表面石头有一片片的松动，正常嘛，怎么补救
- ·小孩子从小宝宝几岁开始刷牙牙最合适？
- ·跪求这种金属小孩反复发烧处理方法法！！不是烧的，是化学药剂做的，
- ·早上睡起来下床，左脚小拇指一侧疼痛跟有点痛，怎么回事
- ·请问一下各位老师，这是那个时候她后悔过微盘的小刀
- ·700公顷mysql不等于怎么写700万平方米这样写对吗
- ·drlnk的ing和fit的过去式式
- ·大家觉得有必要参加linux技术linux运维培训机构构吗？
- ·风风火火的意思火什么字
- ·160平方米用1o钢材线膨胀系数搞线胶得多少吨钢材线膨胀系数
- ·人类登上月球的资料资料。
