![](https://csdnimg.cn/release/download_crawler_static/86295364/bg3.jpg)
点 U 到点 V 有一条弧,则在拓扑序列中 U 一定在 V 之前,深度优先算法搜索路径恰恰是一条弧,栈的输
出是从最后一个被访问点开始输出,最后一个输出的点是第一个被访问的点,所以是逆拓扑有序序列。
7、已知无向图 G 如下所示,使用克鲁斯卡尔(Kruskal)算法求图 G 的最小生成树,加入到最小生成树中
的边依次是:
A、(b,f)(b,d)(a,e)(c,e)(b,e)
B、(b,f)(b,d)(b,e)(a,e)(e,c)
C、(a,e)(b,e)(c,e)(b,d)(b,f)
D、(a,e)(c,e)(b,e)(b,f)(b,d)
参考答案:A
答案解析:「数据结构」考研复习攻略出处:http://www.noobdream.com/Major/article/211/
先将所有边按权值排序,然后依次取权值最小的边但不能在图中形成环,此时取得权值序列
为
5
,
6
,此时
7
不能取因为形成了环,接下来去
9
,
10
,
11
,按权值对应的边。
8、若使 AOE 网估算工程进度则下列叙述中正确的是:
A、关键路径是从原点到汇点边数最多的一条路径;
B、关键路径是从原点到汇点路径长度最长的路径;
C、增加任一关键活动的时间不会延长工程的工期;
D、缩短任一关键活动的时间将会缩短工程的工期。
参考答案:B
答案解析:「数据结构」考研复习攻略出处:http://www.noobdream.com/Major/article/224/
A 改为权值之和最大的路径,B 的最长就是指权值之和最大,C 增加关键活动一定会增加工
期,D 减小一关键活动不一定会缩短工期
9、下列关于大根堆(至少含 2 个元素)的叙述中正确的是:
I.可以将堆看成一颗完全二叉树; II、可采用顺序存储方式保存堆;
III、可以将堆看成一棵二叉排序树; IV、堆中的次大值一定在根的下一层。
A、I II III B、II III IV C、I II IV D、I II III IV
参考答案:C
答案解析:「数据结构」考研复习攻略出处:http://www.noobdream.com/Major/article/241/
III 错误,因为堆只要求根大于左右子树,并不要求左右子树有序。
10、依次将关键字 5,6,9,13,8,2,12,15 插入初始为空的 4 阶 B 树后,根
节点中包含的关键字是:
A、8 B、6,9 C、8,13 D、9,12
参考答案:B
答案解析:「数据结构」考研复习攻略出处:http://www.noobdream.com/Major/article/241/
根据 B 树的性质,最后生成的 B 树如下图所示: