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←cw
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)
【问题2】（7分）
考虑表4-1的实例，假设有3个物品，背包容量为22。图4-1中是根据上述算法构造的搜索树，其中结点的编号表示了搜索树生成的顺序，边上的数字1/0分别表示选择／不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品（5），获得的价值为（6）。
对于表4-1的实例，若采用穷举法搜索整个解空间，则搜索树的结点数为（7），而用了上述回溯法，搜索树的结点数为（8）。
【问题1】（共8分，各2分）
（1）k←1或其等价形式
（2）cw←cw+w[k]或其等价形式
（3）k←k–1或其等价形式
（4）k←k+1或其等价形式
【问题2】（共7分）
（5）物品2和物品3（2分）
（6）35（1分）
（7）15（2分）
（8）8（2分）
本题考查算法设计技术——回溯法。
此类题目要求考生掌握基本的算法设计技术，包括分治法、动态规划法、贪心算法、回溯法和分支限界法等，然后结合具体的问题，用对应的算法设计技术来解决问题。
【问题1】
本题考查的是用回溯法求解0-1背包问题。回溯法有两类算法框架：非递归形式和递归形式，本题采用非递归形式表示。理解回溯法的基本思想和这两类算法框架是正确解答本题的根本要求。
回溯法从第一项物品开始考虑是否应该装入背包中，因此当前考虑的物品编号k从1开始，即k←1。然后逐项往后检查，若能全部放入背包则将该项放入背包，此时背包的重量应该是当前的重量加上当前考虑物品的重量，即cw←cw+w[k]，当然背包中物品的价值也为当前的价值加上当前考虑物品的价值。若己经考虑完了所有的物品，则得到一个解，判断该解是否为当前最优，若为最优，则将该解的信息放入变量fp、fw和X中。若还没有考虑完所有的物品，意味着有些物品不能放入背包，此时先判断若不将当前的物品放入背包中，则其余物品放入背包是否可能得到比当前最优解更优的解，若得不到则回溯；否则继续考虑其余的物品。
【问题2】
根据问题1中给出的伪代码运行该实例，可以很容易得到此0-1背包问题的最优解，应该选择物品2和物品3，此时背包的重量为10＋10＝20，获得的价值为17＋18＝35。
若采用穷举法搜索整个解空间，即要构造一颗完全二叉树，此时搜索树的结点数应为24-1=15，而采用了上述回溯法，搜索树的结点数仅为8个，如上图所示。
一台主机的IP地址为202.123.25.36，掩码为255.255.254.0。如果该主机需要在该网络进行直接广播，那么它应该使用的目的地址为（ ）
在计算机系统的日常维护工作中，应当注意硬盘工作时不能__(2)__。另外，需要防范病毒，而__(3)__是不会被病毒感觉的。
有 4 个 IP 地址：201.117.15.254、201.117.17.01、201.117.24.5 和 201.117.29.3，如果子网掩码为 255.255.248.0，则这 4 个地址分别属于3个子网；其中属于同一个子网的是（）
在异步通信中，每个字符包含1位起始位、7位数据位、1位奇偶位和1位终止位，每秒钟传送200个字符，采用4相位调制，则码元速率为（）。
在 Windows 中，运行（ ）命令得到下图所示结果。以下关于该结果的叙述中，错误的是（ ）。
Pinging 59.74.111.8 with 32 bytes of data:
Reply from 59.74.111.8: bytes=32 time=3ms TTL=60
Reply from 59.74.111.8: bytes=32 time=5ms TTL=60
Reply from 59.74.111.8: bytes=32 time=3ms TTL=60
Reply from 59.74.111.8: bytes=32 time=5ms TTL=60
Ping statistics for 59.74.111.8:
Packets: Sent = 4, Received = 4, Lost = 0 (0% loss),
Approximate round trip times in milli-seconds:
Minimum = 3ms, Maximum = 5ms, Average = 4ms
在ISO OSF/RM参考模型中，七层协议中的__(1)__利用通信子网提供的服务实现两个用户进程之间端到端的通信。在这个模型中，如果A用户需要通过网络向B用户传送数据，则首先将数据送入应用层，在该层给它附加控制信息后送入表示层；在表示层对数据进行必要的变换并加头标后送入会话层；在会话层加头标送入传输层；在传输层将数据分解为__(本题)__后送至网络层；在网络层将数据封装成__(3)__后送至数据链路层；在数据链路层将数据加上头标和尾标封装成__(4)__后发送到物理层；在物理层数据以__(5)__形式发送到物理线路。B用户所在的系统接收到数据后，层层剥去控制信息，把原数据传送给B用户。
在OSI/RM中，解释应用数据语义的协议层是（）。
在TCP/IP协议栈中，ARP协议的作用是（）,RARP协议的作用是（请作答此空）。
在地址 http://www.dailynews.com.cn/channel/welcome.htm 中，www.dailynews.com.cn 表示（ ），welcome.htm 表示（请作答此空）。
在电子表格软件Excel中，假设A1单元格的值为15，若在A2单元格输入“=AND(15＜A1，A1＜100)”，则A2单元格显示的值为 （）
