在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是()
A.回溯法
B.分支限界法
C.回溯法和分支限界法
D.动态规划
A.回溯法
B.分支限界法
C.回溯法和分支限界法
D.动态规划
装载问题描述如下:有一批共n个集装箱要装上艘载重量为c的轮船,其中集装箱i的重量为wi.找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.
算法设计:对于给定的n个集装箱的重量和轮船的重量,计算最优装载方案.
数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.
结果输出:将计算的最大装载重量输出到文件output.txt.
批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小.
算法设计:对于给定的n个作业,计算最佳作业调度方案.
数据输入:由文件input.txt提供输入数据.文件第1行有1个正整数n,表示作业数.接下来的n行中,每行有2个正整数i和j,分别表示在机器1和机器2上完成该作业所需的处理时间.
结果输出:将最佳作业调度方案及其完成时间和输出到文件output.txt.文件的第1行是完成时间和,第2行是最佳作业调度方案.
所谓半无穷范围查询(semi-infinite range query),是教材8.4节中所介绍一般性范围查询的特例,具体地,这里的查询区域是某一侧无界的广义矩形区域,比如R=[-1,+1]x[0,﹢∞),即是对称地包含正半y坐标轴、宽度为2的一个广义矩形区域,当然,对查询的语义功能要求依然不变——从某一相对固定的点集中,找出落在任意指定区域R内部的所有点。
范围树(176页习题[8-20])稍作调整之后,固然也可交持半无穷范围查询,但若能针对这一特定问题所固有的性质,改用优先级搜索树(priority search tree,PST)之类的数据结构,则不仅可以保持O(r+logn)的最优时间效率,而且更重要的是,可以将空间复杂度从范围树的O(nlogn)优化至O(n)。
如图x10.3所示,优先级搜索树除了首先在拓扑上应是一棵二叉树,还同时遵守以下三条规则。
①首先,各节点的y坐标均不小于其左右孩子(如果存在)——因此,整体上可以视作为以y坐标为优先级的二叉堆。
②此外,相对于任一父节点,左子树中节点的x坐标均不得大于右子树中的节点。
③最后,互为兄弟的每一对左、右子树,在规模上相差不得超过一。
a)试按照以上描述,用C/C++定义并实现优先级搜索树结构;
b)试设计一个算法,在O(nlogn)时间内将平面上的n个点组织为一棵优先级搜索树;
c)试设计一个算法,利用已创建的优先级搜索树,在O(r+logn)时间内完成每次半无穷范围查询,其中r为实际命中并被报告的点数。
图的m着色问题描述如下:给定无向连通图G和m种不同的颜色.用这些颜色为图G的各顶点着色,每个顶点着一种颜色.如果有一种着色法,使G中每条边的2个顶点着不同颜色,则称这个图是m可着色的.图的m着色问题是对于给定图G和m种颜色,找出所有不同的着色法.
算法设计:对于给定的无向连通图G和m种不同的颜色,计算图的所有不同的着色法.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n,k和m,表示给定的图G有n个项点和k条边,m种颜色.顶点编号为1,2,...,n接下来的k行中,每行有2个正整数u、v,表示图G的一条边(u,v).
结果输出:将计算的不同的着色方案数输出到文件output.txt.
印制电路板将布线区域划分成n×m个方格阵列(见图6-3(a).精确的电路布线问题要求确定连接方格a的中点到方格b的中点的最短布线方案.在布线时,电路只能沿直线或直角布线(见图6-3(b).为了避免线路相交,已布线了的方格做了封锁标记,其他线路不允许穿过被封锁的方格.
算法设计:对于给定的布线区域,计算最短布线方案.
数据输入:由文件input.txt给出输入数据.第1行有3个正整数n、m.k,分别表示布线区域方格阵列的行数、列数和封闭的方格数.接下来的k行中,每行2个正整数,表示被封闭的方格所在的行号和列号.最后的2行,每行也有2个正整数,分别表示开始布线的方格(p,q)和结束布线的方格(r,s).
结果输出:将计算的最短布线长度和最短布线方案输出到文件output.txt.文件的第1行是最短布线长度.从第2行起,每行2个正整数,表示布线经过的方格坐标.如果无法布线,则输出“NoSolution!".
设有一个关键码的输入序列(55,31,11,37,46,73,63,02,07):
(1)从空树开始构造平衡二叉搜索树,画出每加入一个新结点时二叉树的形态。若发生不平衡,指明需进行的平衡旋转的类型及平衡旋转的结果
(2)计算该平衡二叉搜索树在等概率下的搜索成功的平均搜索长度和搜索不成功的平均搜索长度。
A、顺序搜索
B、折半搜索
C、前两者都不正确
A、4
B、5次
C、7次
D、10次