…
深度优先搜索：
V1->V2->V4->V8->V5->V6->v3->v7 广度优先搜索
V1->V2->V3->V4->v5->v6->v7->v8
(2)已知邻接矩阵求遍历序列 深度优先搜索： ?01110?V1->V2->V3->V4->V5 ?00000??? ?00010?宽度优先搜索： ??01000?V1->V2->V3->V4->V5 ??01100???
(3)已知邻接表求遍历序列
深度优先遍历：V1->V2->V3->V6->V5->V4 宽度优先遍历：V1->V2->V5->V4->V3->V6
9.深度优先(广度优先)生成树 v1 v2 v3 v4 v5 v6 10.最小生成树
1 0 1 0 0 1 3 2 4 4 2 2 6 v1 v2 v3 v4 v5 v6 v7 v8 0 1
V1 V ∧ 2 V V ∧ 3
V3456V2 ① ⑤ 1 2 5 ∧ 4 4 ∧ 3∧ 3 5 2 ∧ 4 ∧ 5 ∧ 5 ∧ 3 4 ∧ 5 ∧ v1 19 16 21 11 v2 6 v1 v2 ④ ② 33 v6 14 v3 5 v6 v5 v4 ③ v3 v5 18 v4
…
11.试画出从顶点v1开始利用Prim算法得到的最小生成树
8 V2 V3 112510?????12 1 1?89???V1 ?128??2?9 2 10 5 ??59??4?? V4 V5 ?10??24???4
12.利用Kruskal算法求最小生成树
11
14
41 232232
454 538 4438 33 2256 6656
45 457 7
…
13.用DAG图描述((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e) 14.AOV-网的拓扑排序 v2 v2
表
达
式+ * * * + e * v5 + v1 v3 v5 v1 v3 a d b c vv6 4 v6 v4
15.写出有向图的所有拓扑排序，并指出应用教材中的算法求得的是哪个序列，设邻接表的边表结点中的邻接点序号是递增的。
1 100 10 V016.求最短路径 V1 30 V2V32 5 10 50 60 V5V4
3 4 20 V6 17.求最短路径－Floyd算法
18.设图如右所示，在下面的5个序列中，符合深度优先遍历的序列有多少？（ D ）
aa e b d f c a c f d e b a e d f c b a e f d c b a e f d b c
A．5个 B．4个 C．3个 D．2个
bec19.下面哪一方法可以判断出一个有向图是否有环（回路）：（AB） A. 深度优先遍历 B. 拓扑排序C. 求最短路径 D. 求关键路径 df
…
20.在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是（ D ）。
A．G中有弧
A. 从始点到终点的最短路径 B. 从始点到终点的最长路径
C. 从始点到终点的边数最多的路径 D. 从始点到终点的边数最少的路径 22.下列关于AOE网的叙述中，不正确的是（ B ）。 A．关键活动不按期完成就会影响整个工程的完成时间
B．任何一个关键活动提前完成，那么整个工程将会提前完成 C．所有的关键活动提前完成，那么整个工程将会提前完成 D．某些关键活动若提前完成，那么整个工程将会提前完成 23.下列有关图的说法错误的是（ C ）
A. 在有向图中，出度为0的结点4称为叶子。
B. 用邻接矩阵表示图，容易判断任意两个结点之间是否有边相连，并求得各结点的度。 C. 按深度方向遍历图和先根次序遍历树类似，得到的结果是唯一的。
D. 若有向图G中从结点Vi到结点Vj有一条路径，则在图G的结点的线性序列中结点Vi必在结点Vj之前的话，则称为一个拓扑序列。
第八章
1.地址为(1664)10大小为(128)10的存储块的伙伴地址是什么？buddy(1664,7)=1664-2=1536 2.地址为(2816)10大小为(64)10的存储块的伙伴地址是什么？buddy(2816,6)=2816+2=2880 3.已知一个大小为512个字长的存储，假设先后有6个用户申请大小分别为23，45，52，100，11和19的存储空间，然后再顺序释放大小为45，52，11的占用块。假设以伙伴系统实现动态存储管理。
（1） 画出可利用空间表的初始状态。
（2） 画出为6个用户分配所需要的存储空间后可利用空间表的状态以及每个用户所得到的存储块的起始地址。
（3） 画出在回收3个占用块之后可利用空间表的状态。
67第九章
1.画出含有12个元素的有序表的判定树
（1）求查找成功时的平均查找长度（2）求查找失败时的平均查找长度
2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( C )。
A. (n-1)/2 B. n/2 C. (n+1)/2 D. n
3.对线性表进行二分查找（就是折半查找）时，要求线性表必须（ ） A.以顺序方式存储 B.以顺序方式存储,且数据元素有序 C.以链接方式存储 D.以链接方式存储,且数据元素有序
4.当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( C )
A. 必定快 B. 不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减 5.在有序表A[1…20]中，按二分查找方法进行查找，查找长度为4的元素的下标从小到大依
…
次是___1，3，6，8，11，13，16，19_______ 6.分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成___30______块最好：若分成25块，其平均查找长度为__31.5（块内顺序查找）_______。
7.设关键码序列为：63，90，70，55，67，42，98，83，则构造一棵二叉排序树的过程如下：
8.二叉排序树上删除10 或40或45或55
9.构造二叉排序树
将{for,case,while,switch,break,do,define,const,if,int}中的关键字依次插入初态为空的二叉排序树（按字母在字母表中的序号排序）中，请画出所得到的树T。然后画出删除for之后的二叉排序树T。
10.按关键字序列15,21,27,43,36,8,11构造平衡二叉树
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构课件题目（附答案） - 图文(2)在线全文阅读。
相关推荐：