首页 > 建筑工程类考试> 二级注册建筑师

网友您好，请在下方输入框内输入要搜索的题目：

请输入或粘贴题目内容搜题

搜题

拍照、语音搜题，请扫码下载APP

题目内容（请给出正确答案）

[主观题]

问题描述:设计一个用回溯法搜索子集空间树的函数,参数包括结点可行性判定函数和上界函数等必

要的函数,并将此的数用于解0-1背包问题.

0-1背包问题描述如下;给定n种物品和一个背包.物品i的重量是w_i,其价值为v_i背包的容量为C.应如何选择装入背包的物品,使装入背包中物品的总价值最大？

在选择装入肯包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包.不能将物品i装入背包多次,也不能只装入部分的物品i.

0-1背包问题形式化描述如下:给定,要求n元0-1向量,使得而且达到最大.

算法设计:对于给定的n种物品的重量和价值,以及背包的容量,计算可装入背包的最大价值.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是物品数,c是背包的容量.接下来的1行中有n个正整数,表示物品的价值.第3行中有n个正整数,表示物品的重量.

结果输出:将计算的装入背包物品的最大价值和最优装入方案输出到文件output.txt

答案

查看答案

发布时间：2022-05-26

轻松一刻：免费趣味测试

更多 >

测一测你的大脑水平有多高？

测一测你在他人眼中有多难接近？

趣味测试：你会正确聊天吗？测测你的网聊吸引力！

测一测你有多容易被掰弯？

更多“问题描述:设计一个用回溯法搜索子集空间树的函数,参数包括结点可行性判定函数和上界函数等必”相关的问题

第1题

问题描述:试设计一个用队列式分支限界法搜索子集空间树的函数,其参数包括结点可行性判定函数

和上界函数等必要的函数,并将此函数用于解装载问题.

装载问题描述如下:有一批共n个集装箱要装上一艘载重量为c的轮船,其中集装箱i的重量为w_i找出一种最优装载方案,将轮船尽可能装满,即在装载体积不受限制的情况下,将尽可能重的集装箱装上轮船.

算法设计:对于给定的n个集装箱和轮船的载重量,计算最优装载方案.

数据输入:由文件input.txt给出输入数据.第1行有2个正整数n和c,n是集装箱数,c是轮船的载重量.接下来的1行中有n个正整数,表示集装箱的重量.

结果输出:将计算的最大装载重量输出到文件output.txt.

点击查看答案

第2题

在对问题的解空间树进行搜索的方法中,一个活结点有多次机会成为活结点的是（)

A.回溯法

B.分支限界法

C.回溯法和分支限界法

D.动态规划

点击查看答案

第3题

问题描述:试设计一个用回溯法搜索排列空间树的函数.该函数的参数包括结点可行性判定函数和上

界函数等必要的函数,并将此的数用于解圆排列问题.

圆排列问题描述如下:给定n个大小不等的圆,现要将这n个圆排进一个矩形框中,且要求各圆与矩形框的底边相切.圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列.例如,当n=3,且所给的3个圆的半径分别为1、1、2时,这3个圆的最小长度的圆排列见图5-9,其最小长度为.

算法设计:对于给定的n个圆,计算最小长度圆排列.

数据输入:由文件input.txt提供输入数据.文件的第1行是1个正整数n,表示有n个圆.第2行有n个正数,分别表示n个圆的半径.

结果输出:将计算的最小长度输出到文件output.txt.文件的第1行是最小长度,保留5位小数.

点击查看答案

第4题

分支限界法与回溯法都是在问题的解空间树T上搜索问题的解,二者（)。

A.求解目标不同,搜索方式相同

B.求解目标不同,搜索方式也不同

C.求解目标相同,搜索方式不同

D.求解目标相同,搜索方式也相同

点击查看答案

第5题

问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否

问题描述:子集和问题的一个实例为.其中,是一个正整数的集合,c是一个正整数.子集和问题判定是否存在S的一个子集S₁,使得.试设计一个解子集和问题的回溯法.

算法设计:对于给定的正整数的集合和正整数c,计算S的一个了集S₁,使得

数据输入:由文件input.txt提供输入数据.文件第1行有2个正整数n和c,n表示S的大小,c是子集和的目标值.接下来的1行中,有n个正整数,表示集合S中的元素.

结果输出:将子集和问题的解输出到文件output.txt.当问题无解时,输出“NoSolution!".

点击查看答案

第6题

问题描述:设计一个用回溯法搜索一般解空间的函数,参数包括:生成解空间中下一扩展结点的函数、

结点可行性判定函数和上界函数等必要的函数,并将此函数用于解图的m着色问题.

图的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.

点击查看答案

第7题

问题描述:试设计一个用优先队列式分支限界法搜索排列空间树的函数,其参数包括结点可行性判定

雨数和上界的数等必要的函数,并将此函数用于解批处理作业调度问题.给定n个作业的集合

.每个作业J_i都有2项任务分别在2台机器上完成.每个作业必须先由机器1处理,再由机器2处理.作业J_i需要机器j的处理时间为t_ij(=1,2,...,n;j=1,2).对于一个确定的作业调度,设F_ij是作业i在机器j上完成处理的时间.所有作业在机器2上完成处理的时间和

称为该作业调度的完成时间和.

批处理作业调度问题要求对于给定的n个作业,制定最佳作业调度方案,使其完成时间和达到最小.

算法设计:对于给定的n个作业,计算最佳作业调度方案.

数据输入:由文件input.txt提供输入数据.文件第1行有1个正整数n,表示作业数.接下来的n行中,每行有2个正整数i和j,分别表示在机器1和机器2上完成该作业所需的处理时间.

结果输出:将最佳作业调度方案及其完成时间和输出到文件output.txt.文件的第1行是完成时间和,第2行是最佳作业调度方案.

点击查看答案

第8题

所谓半无穷范围查询（semi-infinite range query)，是教材8.4节中所介绍一般性范围查询的特例，具

所谓半无穷范围查询(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为实际命中并被报告的点数。

点击查看答案

第9题

Apriori挖掘算法描述正确的是（)。

A.通过使用先验原理对搜索空间进行剪枝，解决了候选频繁集组合爆炸的问题

B.候选集的产生：通过前一次迭代的(k-1)项频繁集产生新的k项候选频繁集

C.候选项集的剪枝：采用基于支持度的剪枝。原理：如果一个项是频繁集，则它的所有子集一定也是频繁集

D.规则产生：每个k项频繁集会产生多达2^k-2个关联规则，需要基于置信度进行剪枝

点击查看答案

第10题

分支限界法通常按广度优先遍历问题的解空间树，以深度优先方式系统搜索问题解的算法称为__________。

点击查看答案

账号：尚未登录

登录没有账号？去注册

购买搜题卡

下载APP

关注公众号

TOP