在启发式图搜索策略中,下面描述正确的是()。
A.open表用于存放已扩展过的节点
B.closed表表用于存放所有已生成而未扩展的节点
C.closed表用于存放已扩展过的节点
D.open表用于存放所有已生成的节点
A.open表用于存放已扩展过的节点
B.closed表表用于存放所有已生成而未扩展的节点
C.closed表用于存放已扩展过的节点
D.open表用于存放所有已生成的节点
A.蚁群算法是通过人工模拟蚂蚁搜索食物的过程,即通过个体之间的信息交流与相互协作最终找到从蚁穴到食物源的最短路径的
B.蚂蚁系统是一种增强型学习系统
C.蚁群算法中,蚂蚁选择路径的原理是一种负反馈机制
D.蚁群算法是一种应用于组合优化问题的启发式搜索算法
在数据技术中,采用一定的数据模型来描述数据库中数据的逻辑结构。下面列出的项目中,()是用来描述关系数据库的逻辑结构的。
A.二维表
B.数据流程图
C.B树
D.E-R图
【问题 1】(8 分)
用回溯法求解此 0-1 背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点已经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W )函数,其中 v、w、k 和 W分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出 0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
(20)
A. PERT 网络分析
B. 甘特图
C. 优先日程图法
D. 启发式分析法
(21)
A. PERT 网络分析
B. 甘特图
C. 优先日程图法
D. 启发式分析法
(22)
A. PERT 网络分析
B. 甘特图
C. 优先日程图法
D. 启发式分析法
● 下面关于软件测试模型的描述中,不正确的包括(21) 。
①V模型的软件测试策略既包括低层测试又包括了高层测试,高层测试是为了源代码的正确性,低层测试是为了使整个系统满足用户的需求
②V模型存在一定的局限性,它仅仅把测试过程作为在需求分析、概要设计、详细设计及编码之后的一个阶段 ③W模型可以说是V模型自然而然的发展。它强调:测试伴随着整个软件开发周期,而且测试的对象不仅仅是程序,需求、功能和设计同样要测试
④H模型中软件测试是一个独立的流程,贯穿产品整个生命周期,与其他流程并发地进行
⑤H模型中测试准备和测试实施紧密结合,有利于资源调配
(21)
A.①⑤
B.②④
C.③④
D.②③
(52)
A. PERT网络分析
B. 甘特图
C. 优先日程图法
D. 启发式分析法
(53)
A. PERT网络分析
B. 甘特图
C. 优先日程图法
D. 启发式分析法
在分支一限界算法设计策略中,通常采用(54)搜索问题的解空间。
A.深度优先
B.广度优先
C.自底向上
D.拓扑序列
下面描述中错误的是()。
A.系统总体结构图支持软件系统的详细设计
B.软件设计是将软件需求转换为软件表示的过程
C.数据结构与数据库设计是软件设计的任务之一
D.PAD图是软件详细设计的表示工具
0-1背包问题可以描述为:有n个物品,对i=1,2,…,n,第i个物品价值为vi ,重量为wi(vi,和wi为非负数),背包容量为W(W为非负数),选择其中一些物品装入背包,使装入背包物品的总价值最大,,且总重量不超过背包容量,即,其中,xi∈{0,1},xi=0表示第i个物品不放入背包,xi=1表示第i个物品 放入背包。
【问题1】(8分)
用回溯法求解此0-1背包问题,请填充下面伪代码中(1)~(4)处空缺。
回溯法是一种系统的搜索方法。在确定解空间后,回溯法从根结点开始,按照深度优先策略遍历解空间树,搜索满足约束条件的解。对每一个当前结点,若扩展该结点己经不满足约束条件,则不再继续扩展。为了进一步提高算法的搜索效率,往往需要设计一个限界函数,判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了BOUND(v,w,k,W)函数,其中v, w, k和W分别表示当前已经获得的价值、当前背包的重量、己经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点,该函数值表示确定了部分物品是否选择之后,对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值,若该价值小于等于当前已经得到的最优解,则该结点无需再扩展。
下面给出0-1背包问题的回溯算法伪代码。
函数参数说明如下:
W:背包容量;n:物品个数;w:重量数组;v:价值数组;fw:获得最大价值时背包的重量;fp:背包获得的最大价值;X:问题的最优解。
变量说明如下:
cw:当前的背包重量;cp:当前获得的价值;k:当前考虑的物品编号;Y:当前已获得的部分解。
BKNAP(W,n,w,v,fw,fp,X)
1 cw ← cp ← 0
2 (1)
3 fp ← -1
4 while true
5 while k≤n and cw+w[k]≤W do
6 (2)
7 cp ← cp+v[k]
8 Y[k]← 1
9 k ← k+1
10 if k>n then
11 if fp<cp then
12 fp ← cp
13 fw ← ew
14 k ← n
15 X ← Y
16 else Y(k)← 0
17 while BOUND(cp,cw,k,W) ≤fp do
18 while k≠0 and Y(k)≠1 do
19 (3)
20 if k=0 then return
21 Y[k]←0
22 cw ← cw ← w[k]
23 cp ← cp ← v[k]
24 (4)
下面描述中错误的是______。
A) 系统总体结构图支持软件系统的详细设计
B) 软件设计是将软件需求转换为软件表示的过程
C) 数据结构与数据库设计是软件设计的任务之一
D) PAD图是软件详细设计的表示工具
下面描述中错误的是()。
A.系统总体结构图支持软件系统的详细设计
B.软件设计是将软件需求转换为软件表示的过程
C.数据结构与数据库设计是软件设计的任务之一
D.PAD图是软件详细设计的表示工具