本文主要是介绍算法分析与设计 第九次理论作业，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法分析与设计 第九次理论作业
文章目录
- 算法分析与设计 第九次理论作业
- 一. 单选题（共3题，30分）
- 二. 填空题（共5题，50分）
- 三. 简答题（共1题，20分）
一. 单选题（共3题，30分）
-
(单选题, 10分) 优先队列通常采用（ ）来实现。
A. 栈
B. 堆
C.队列
D.二叉查找树正确答案: B:堆;
-
(单选题, 10分) 分支限界法在问题的解空间书中，按（）策略，从根节点出发搜索解空间树。
A.广度优先
B.活结点优先
C.扩展结点优先
D.深度优先正确答案: A:广度优先 ;
-
(单选题, 10分) 对布线问题，以下叙述中错误的是（ ）。
A.布线问题的解空间是一个图。
B.为了便于处理方格边界的情况，可以在所给方格阵列四周设置一道“围墙”，即增设标记为“1”的附加方格。
C.采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的
D.采用先入先出的队列作为活结点表，以终点b为扩展结点或活结点队列为空作为算法结束条件。正确答案: C:采用广度优先的标号法找到从起点到终点的布线方案（这个方案如果存在的话）不一定是最短的 ;
二. 填空题（共5题，50分）
-
(填空题, 10分) 从活结点表中选择下一扩展结点的不同方式导致不同的分支限界法，最常见的两种方式是____分支限界法和____分支限界法。
正确答案： (1) 队列式（FIFO）(2) 优先队列式
-
(填空题, 10分) 优先队列式分支限界法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前____。
正确答案： (1) 扩展结点
-
(填空题, 10分) 最小优先队列分支限界法中，优先值较小的结点优先级较高，通常用____实现，体现最小费用优先的原则。
正确答案： (1) 最小堆
-
(填空题, 10分) 单源最短路径问题既可以用贪心算法（Dijkstra算法）求解，也可以用____分支限界法求解。
正确答案： (1) 优先队列式
-
(填空题, 10分) 批处理作业调度问题的解空间树是一颗____。
正确答案： (1) 排列树
三. 简答题（共1题，20分）
-
(简答题, 20分) 在分支限界法中，从活结点表中选择下一个扩展结点有两种最常见的方式，分析说明这两种方式中活结点表的组织形式及其特点。
正确答案：
（1）队列式（FIFO）分支限界法
队列式分支限界法将活结点组织成一个队列，并按队列的先进先出FIFO(First In First Out)原则选取下一个结点为当前扩展结点。
（2）优先队列式分支限界法
优先队列式分支限界法将活结点组织成一个优先队列，并按优先队列中规定的结点优先级选取下一个结点为当前扩展结点。
这篇关于算法分析与设计 第九次理论作业的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
