1、软件设计师-常用算法设计及答案解析(总分：255.00，做题时间：90 分钟)阅读下列函数说明和 C 代码，将应填入 (n) 处的字句写在对应栏内。说明函数 int Toplogical(LinkedWDigraph G)的功能是对图 G 中的顶点进行拓扑排序，并返回关键路径的长度。其中图 G 表示一个具有 n 个顶点的 AOE 网，图中顶点从 1n 依次编号，图 G 的存储结构采用邻接表表示，其数据类型定义如下：typedef struct Gnode /*邻接表的表结点类型*/int adjvex； /*邻接顶点编号*/int weight； /*弧上的权值*/struct Gnode*n
2、extarc；/*指示下一个弧的结点*/Gnode；typedef struct Adj list /*邻接表的头结点类型*/char vdata； /*顶点的数据信息*/struct Gnode *Firstadj；/*指向邻接表的第一个表结点*/Adjulist；typedef struct LinkedWDigraph/*图的类型*/int n，e； /*图中顶点个数和边数*/struct Adjlist *head； /*指向图中第一个顶点的邻接表的头结点*/LinkedWDigraph；例如，某 AOE 网如图 21-1 所示，其邻接表存储结构如图 21-2 所示。（分数：15.00
3、）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读以下说明和 C 程序，将应填入 (n) 处的字句写在对应栏内。说明假设需要将 N 个任务分配给 N 个工人同时去完成，每个人都能承担这 N 个任务，但费用不同。下面的程序用回溯法计算总费用最小的一种工作分配方案，在该方案中，为每个人分配 1 个不同的任务。程序中，N 个任务从 0 开始依次编号，N 个工人也从 0 开始依次编号，主要的变量说明如下：cii：将任务 i 分配给工人 j 的费用。taski：值为 0 表示任务 i 未分配；值为 j 表示任务 i 分配给工人 j。workerk：值为 0 表示工人 k 未分配
4、任务；值为 1 表示工人 k 已分配任务。mincost：最小总费用。程序#includestdio.h#define N 8 /*N 表示任务数和工人数*/int cNN；unsigned int mincost=65535； /*设置 min 的初始值，大于可能的总费用*/int taskN，tempN，workerN；void plan(int k，unsigned int cost)int i；if( (1) costmincost)mincost=cost；for(i=0；iN；i+)tempi=taski；eisefor(i=0；iN；i+) /*分配任务 k*/if(worker
5、i=0 (2) )workeri=1；taskk= (3) ；plan( (4) ，cost+cki)；(5) ；taskk=0；/*if*/*plan*/void main()int i，j；for(i=0；iN；i+)/*设置每个任务由不同工人承担时的费用及全局数组的初值*/workeri=0；taski=0；tempi=0；for(j=0；jN；j+)scanf(“%d“，cij)；plan(0，0)； /*从任务 0 开始分配*/printf(“/n 最小费用=%d/n“，mincost)；for(i=0；iN；i+)printf(“Task%d is assigned to Work
6、er%d/n“，i，tempi)；/*main*/（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读以下函数说明、图和 C 代码，将应填入 (n) 处的字句写在对应栏内。说明散列文件的存储单位称为桶(Bucket)。假如一个桶能存放 m 个记录，当桶中已有 m 个同义词(散列函数值相同)的记录时，存放第 m+1 个同义词会发生“溢出”。此时需要将第 m+1 个同义词存放到另一个称为“溢出桶”的桶中。相对地，称存放前 m 个同义词的桶为“基桶”。溢出桶和基桶大小相同，用指针链接。查找指定元素记录时，首先在基桶中查找。若找到，则成功返回；否则沿指针到溢出
7、桶中进行查找。例如： 设散列函数为 Hash(Key)=Key mod 7，记录的关键字序列为15，14，21，87，96，293，35，24，149，19，63，16，103，77，5，153，145，356，51，68，705，453，建立的散列文件内容如图 21-3 所示。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明、图和 C 代码，将应填入 (n) 处的字句写在对应栏内。说明 1B 树是一种多叉平衡查找树。一棵 m 阶的 B 树，或为空树，或为满足下列特性的 m 叉树。树中每个结点至多有 m 棵子树；若根结点不是叶
8、子结点，则它至少有两棵子树：除根之外的所有非叶子结点至少有m/2棵子树：所有的非叶子结点中包含下列数据信息：(n，A 0，K 1，A 1，K 2，A 2，K 11，A 11)其中，K(i=1，2，n)为关键字，且 KK i+1(i=1，2，n-1)；A i(i=0，1，n)为指向子树根结点的指针，且指针 Ai-1所指子树中所有结点的关键字均小于 Ki，A i+1所指子树中所有结点的关键字均大于Ki，n 为结点中关键字的数目。所有的叶子结点都出现在同一层次上，并且不带信息(可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空)。例如，一棵 4 阶 B 树如图 21-4
9、 所示(结点中关键字的数目省略)。B 树的阶 m、Bool 类型、关键字类型及 B 树结点的定义如下。#define M 4 /*B 树的阶数*/typedef enumFALSE=0，TRUE=1bool；typedef int E1emKeyType；typedef struct BTreeNodeint numkeys； /*结点中关键字的数目*/struct BTreeNode *parent；/*指向父结点的指针，树根的父结点指针为空*/Struct BTreeNode *AM； /*指向子树结点的指针数组*/ElemKeyType KM； /*存储关键字的数组，K0闲置不用*/BT
10、reeNode；函数 SearchBtree(BTreeNode *root，ElemKeyType akey，BTreeNode *ptr)的功能是：在给定的一棵 m阶 B 树中查找关键字 akey 所在结点，若找到则返回 TRUE，否则返回 FALSE。其中，root 是指向该 m 阶 B树根结点的指针，参数 ptr 返回 akey 所在结点的指针，若 akey 不在该 B 树中，则 ptr 返回查找失败时空指针所在结点的指针。例如，在如图 21-4 所示的 4 阶 B 树中查找关键字 akey 时，ptr 返回指向结点 e 的指针。注：在结点中查找关键字 akey 时采用二分法。本题函数
11、bool SearchBtree(BTreeNode *root，ElemKeyType akey，BTreeNode *ptr)int lw，hik mid；BTreeNode *P=root；*ptr=NULL；while(p)lw=1；hi= (1) ；while(lw=hi)mid=(lw+hi)/2；if(p-Kmid=akey)*ptr=p；return TRUE；elseif( (2) )hi=mid-1；elselw=mid+1；*ptr=p；p= (3) ；return FALSE；说明 2在 m 阶 B 树中插入一个关键字时，首先在最接近外部结点的某个非叶子结点中增加一个关
12、键字，若该结点中关键字的个数不超过 m-1，则完成插入；否则，要进行结点的“分裂”处理。所谓“分裂”，就是把结点中处于中间位置上的关键字取出来并插入其父结点中，然后以该关键字为分界线，把原结点分成两个结点。“分裂”过程可能会一直持续到树根，若树根结点也需要分裂，则整棵树的高度增 1。例如，在如图 21-4 所示的 B 树中插入关键字 25 时，需将其插入结点 e 中，由于 e 中已经有 3 个关键字，因此将关键字 24 插入结点 e 的父结点 b 中，并以 24 为分界线将结点 e 分裂为 e1 和 e2 两个结点，结果如图 21-5 所示。（分数：15.00）填空项 1:_填空项 1:_填空
13、项 1:_填空项 1:_填空项 1:_阅读以下说明、图和 C 代码，将应填入 (n) 处的字句写在对应栏内。说明一般的树结构常采用孩子一兄弟表示法表示，即用二叉链表作为树的存储结构，链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如，如图 21-6(a)所示的树的孩子一兄弟表示如图21-6(b)所示。（分数：14.98）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读以下说明和 C 语言函数，将应填入 (n) 处的字句写在对应栏内。说明在一个分布网络中，资源(石油、天然气、电力等)可从生产地送往其他地方。在传输过程中，
14、资源会有损耗。例如，天然气的气压会减少，电压会降低。我们将需要输送的资源信息称为信号。在信号从信源地送往消耗地的过程中，仅能容忍一定范围的信号衰减，称为容忍值。分布网络可表示为一个树形结构，如图21-7 所示。信号源是树根，树中的每个结点(除了根)表示一个可以放置放大器的子结点，其中某些结点同时也是信号消耗点，信号从一个结点流向其子结点。每个结点有一个 d 值，表示从其父结点到该结点的信号衰减量。例如，在图 21-7 中，结点 w、p、q 的 d值分别为 2、1、3，树根结点表示信号源，其 d 值为 0。每个结点有一个 M 值，表示从该结点出发到其所有叶子结点的信号衰减量的最大值。显然，叶子结
15、点的 M值为 0。对于非叶子结点 j，Mj)=maxM(k)+d(k)k 是 j 的孩子结点)。在此公式中，要计算结点的 M 值，必须先算出其所有子结点的 M 值。在计算 M 值的过程中，对于某个结点 i，其有一个子结点 k 满足 d(k)+M(k)大于容忍值，则应在 k 处放置放大器；否则，从结点 i 到某叶子结点的信号衰减量会超过容忍值，使得到达该叶子结点时信号不可用，而在结点 i 处放置放大器并不能解决到达叶子结点的信号衰减问题。例如，在图 21-7 中，从结点 p 到其所有叶子结点的最大衰减值为 4。若容忍值为 3，则必须在 s 处放置信号放大器，这样可使得结点 p 的 M 值为 2。
16、同样，需要在结点 q、v 处放置信号放大器，如图 21-8 中阴影结点所示。若在某结点放置了信号放大器，则从该结点输出的信号与信号源输出的信号等价。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读以下说明和 C 代码，将应填入 (n) 处的字句写在对应栏内。说明在一个简化的绘图程序中，支持的图形种类有点(point)和圆(ckcle)，在设计过程中采用面向对象思想，认为所有的点和圆都是一种图形(shape)，并定义了类型 shape_t、point_t 和 circle_t 分别表示基本图形、点和圆，并且点和圆具有基本图形的所有特征。C 代码typ
17、edef enumpoint，circle)shape_type； /*程序中的两种图形：点和圆*/typedef struct /*基本的图形类型*/shape_type type； /*图形种类标识：点或者圆*/void(*destroy)()； /*销毁图形操作的函数指针*/void(*draw)()； /*绘制图形操作的函数指针*/shape_t；typedef struct(shape_t common；int x；int y；)point_t；/*定义点类型，x、y 为点坐标*/void destroyPoint(point_t* this) free(this)；printf(“
18、Point destoryed!/n“)；/*销毁点对象*/void drawPoint(point_t* this) printf(“P(%d，%d)“，this-x，this-y)； /*绘制点对象*/shape_t* createPoint(va_list* ap)/*创建点对象，并设置其属性*/point_t* p_point；if(p_point=(point_t*)malloc(sizeof(point_t)=NULL)return NULL；p_point-common.type=point；p_point-common.destroy=destroyPoint；p_point-
19、common.draw=drawPoint；p_point-x=va_arg(*ap，int)； /*设置点的横坐标*/p_point-y=va_arg(*ap，int)； /*设置点的纵坐标*/return(shape_t*)p_point； /*返回点对象指针*/typedef struct/*定义圆类型*/shape_t common；point_t*center； /*圆心点*/int radius； /*圆半径*/circle_t；void destroyCircle(Circle_t* this)free( (1) )；free(this)；printf(“Circle desto
20、ryed!/n“)；void drawCircle(Circle_t* this)printf“C“；(2) .draw(this-center)； /*绘制圆心*/printf(“.%d)“，this-radius)；shape_t* createCircle(va_list* ap) /*创建一个圆，并设置其属性*/Circle_t* p_circle；if(p_circle=(circle_t*)malloc(Sizeof(circle_t)=NULL)return NULL；p_circle-common.type=circle；p_circle-common.destroy=dest
21、royCircle；p_circle-common.draw=drawCircle；(3) =createPoint(ap)； /*设置圆心*/p_circle-radius=va_arg(*ap，int)； /*设置圆半径*/return p_circle；shape_t* createShape(shape_type st，)/*创建某一种具体的图形*/va_list ap； /*可变参数列表*/shape_t* p_shape=NULL；(4) (ap，st)；if(st=point)p_shape=createPoint(ap)； /*创建点对象*/if(st=circle) p_sh
22、ape=createCircle(ap)； /*创建圆对象*/va_end(ap)；return p_shape；int main()int i； /*循环控制变量，用于循环计数*/shape_t* shapes2； /*图形指针数组，存储图形的地址*/shapes0=createShape(point，2，3)；/*横坐标为 2，纵坐标为 3*/shapes1=createShape(Circle，20，40，10)；/*圆心坐标为(20，40)，半径为 10*/for(i=0；i2；i+)(shapesi-draw(shapesi)；printf(“/n“)； /*绘制数组中图形*/for
23、(i=1；i=0；i-) shapesi-destroy(shapesi)；/*销毁数组中图形*/return 0；运行结果P(2，3)(5) Circle destoryed!Point destoryed!（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明和 C 代码，将应填入 (n) 处的字句写在对应栏内。说明栈(Stack)结构是计算机语言实现中的一种重要数据结构。对于任意栈，进行插入和删除操作的一端称为栈顶(Stack Top)，而另一端称为栈底(Stack Bottom)。栈的基本操作包括：创建栈(NewStack)、判断栈是否为
24、空(IsEmpty)、判断栈是否已满(IsFull)、获取栈顶数据(Top)、压栈/入栈(Push)、弹栈/出栈(Pop)。当设计栈的存储结构时，可以采取多种方式。其中，采用链式存储结构实现的栈中各数据项不必连续存储(如图 21-9 所示)。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。说明快速排序是一种典型的分治算法。采用快速排序对数组 Apr排序的 3 个步骤如下：(1)分解：选择一个枢轴(pivot)元素划分数组。将数组 Apr划分为两个子数组(可能为空)Apq-1和 Aq+1r，使得
25、 Aq大于等于 Apq-1中的每个元素，小于 Aq+1r中的每个元素。q 的值在划分过程中计算。(2)递归求解：通过递归的调用快速排序，对子数组 Apq-1和 Aq+1r分别排序。(3)合并：快速排序在原地排序，故不需要合并操作。问题 1下面是快速排序的伪代码，请填补其中的空缺。伪代码中的主要变量说明如下：A：待排序数组；p，r：数组元素下标，从 p 到 r；q：划分的位置；x：枢轴元素；i：整型变量，用于描述数组下标。下标小于或等于 i 的元素的值小于或等于枢轴元素的值：j：循环控制变量，表示数组元素下标。QUICKSORT(A，P，r)if(pr)q=PARTITION(A，p，r)；QU
26、ICKSORT(A，p，q-1)；QUICKSORT(A，q+1，r)；PARTITION(A，p，r)X=Ar；i=p-1；for(j=p；jr-1；j+)if(Ajx)i=i+1；交换 Aj和 Aj交换 (1) 和 (2) /注：空(1)和空(2)答案可以互换，但两个空全部答对方可得分return (3) 问题 2(1)假设要排序包含 n 个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用 O 记号。最佳情况为 (4) ，平均情况为 (5) ，最坏情况为 (6) 。(2)假设要排序的 n 个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况? (7) 。(最佳、平均
27、、最坏)问题 3(1)待排序数组是否能被较均匀地划分对快速排序的性能有重要影响，因此枢轴元素的选取非常重要。有人提出从待排序的数组元素中随机地取出一个元素作为枢轴元素，下面是随机化快速排序划分的伪代码利用原有的快速排序的划分操作，请填充其中的空缺处。其中，RANDOM(i，j)表示随机取 i 到 j 之间的一个数，包括 i 和 j。RANDOMIZED-PARTITION(A，p，r)i=RANDOM(p，r)；交换 (8) 和 (9) ；/注：空(8)和空(9)答案可以互换，但两个空全部答对方可得分return PARTITION(A，p，r)；(2)随机化快速排序是否能够消除最坏情况的发生
28、? (10) 。(是或否)（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明，回答问题 1 至问题 3，将解答填入对应栏内。说明希赛公司供应各种标准的营养套餐。假设菜单上共有 n 项食物 m1，m 2，m n，每项食物 mi的营养价值为vi，价格为 pi，其中 i=1，2，n，套餐中每项食物至多出现一次。客人常需要一个算法来求解总价格不超过 M 的营养价值最大的套餐。问题 1下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺(1)、(2)和(3)。伪代码中的主要变量说
29、明如下：n：总的食物项数；v：营养价值数组，下标从 1 到 n，对应第 1 项到第 n 项食物的营养价值；p：价格数组，下标从 1 到 n，对应第 1 项到第 n 项食物的价格；M：总价格标准，即套餐的价格不超过 M；x：解向量(数组)，下标从 1 到 n，其元素值为 0 或 1，其中元素值为 0 表示对应的食物不出现在套餐中，元素值为 1 表示对应的食物出现在套餐中；nv：n+1 行 M+1 列的二维数组，其中行和列的下标均从 0 开始，nvij表示由前 i 项食物组合且价格不超过 j 的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为 nvnM。伪代码如下：MaxNutrientVa
30、lue(n，v，p，M，x)1 for i=0 to n2 nvi0=03 for j=1 to M4 nv0j=05 for i=1 to n6 for j=1 to M7 if jpi /若食物 mi不能加入到套餐中8 nvij=nvi-1j9 else if (1) 10 nvij=nvi-1j11 else12 nvij=nvi-1j-pi+vi13 j=M14 for i=n downto 115 if (2) 16 xi=017 else18 xi=119 (3) 20 return x and nvnM问题 2现有 5 项食物，每项食物的营养价值和价格如表 21-2 所示。表 2
31、1-2 食物的营养价值和价格表编码 营养价值 价格ml 200 50m2 180 30m3 225 45m4 200 25m5 50 5若要求总价格不超过 100 的营养价值最大的套餐，则套餐应包含的食物有 (4) (用食物项的编码表示)，对应的最大营养价值为 (5) 。问题 3问题 1 中伪代码的时间复杂度为 (6) (用 O 符号表示)。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明和 c 函数，将应填入 (n) 处的字句写在对应栏内。说明已知集合 A 和 B 的元素分别用不含头结点的单链表存储，函数 Differenc
32、e()用于求解集合 A 与 B 的差集，并将结果保存在集合 A 的单链表中。例如，若集合 A=5，10，20，15，25，30，集合 B=5，15，35，25，如图 21-10(a)所示，运算完成后的结果如图 21-10(b)所示。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明，回答问题 1 和问题 2，将解答填入对应栏内。说明现需要在某城市中选择一个社区建一个大型超市，使该城市的其他社区到该超市的距离总和最小。用图模型表示该城市的地图，其中顶点表示社区，边表示社区间的路线，边上的权重表示该路线的长度。现设计一个算法来找到该
33、大型超市的最佳位置，即在给定图中选择一个顶点，使该顶点到其他各顶点的最短路径之和最小。首先，算法需要求出每个顶点到其他任一顶点的最短路径，即需要计算任意两个顶点之间的最短路径；然后，对每个顶点计算其他各顶点到该顶点的最短路径之和；最后，选择最短路径之和最小的顶点作为建大型超市的最佳位置。问题 1本题采用 Floyd-Warshall 算法求解任意两个顶点之间的最短路径。已知图 G 的顶点集合为V=1，2，n)，W=W ijn*n为权重矩阵。设 为从顶点 i 到顶点 j 的一条最短路径的权重。当 k=0 时，不存在中间顶点，因此 ；当 k0 时，该最短路径上所有的中间顶点均属于集合 1，2，k。
34、若中间顶点包括顶点 k，则 ；若中间顶点不包括顶点 k，则 。于是得到如下递归式：因为对于任意路径，所有的中间顶点都在集合 1，2，n 内，因此矩阵 给出了任意两个顶点之间的最短路径，即对所有 i，jV， 表示顶点 i 到顶点 j 的最短路径。下面是求解该问题的伪代码，请填充其中的空缺(1)(6)。伪代码中的主要变量说明如下：W：权重矩阵；n：图的顶点个数；SP：最短路径权重之和数组，SPi表示顶点 i 到其他各顶点的最短路径权重之和，i 取值为 1n；min_SP：最小的最短路径权重之和；min_v：具有最小的最短路径权重之和的顶点；i：循环控制变量；j：循环控制变量；k：循环控制变量。LO
35、CATE -SHC)PPINGNALL(W，n)1 D(0)=W2 for (1) 3 for i=1 to n4 for j=1 to n5 if （分数：14.98）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明和 C 函数代码，将应填入 (n) 处的字句写在对应栏内。说明对二叉树进行遍历是二叉树的一个基本运算。遍历是指按某种策略访问二又树的每个结点，且每个结点仅访问一次的过程。函数 InOrder()借助栈实现二叉树的非递归中序遍历运算。设二叉树采用二叉链表存储，结点类型定义如下：typedef struct BtNodeE
36、lemType data； /*结点的数据域，ElemType 的具体定义省略*/struct BtNode *lchiid，*rchiid； /*结点的左、右孩子指针域*/BtNode，*BTree；在函数 InOrderO 中，用栈暂存二叉树中各个结点的指针，并将栈表示为不含头结点的单向链表(简称链栈)，其结点类型定义如下：typedef struct StNode /*链栈的结点类型*/BTree elem； /*栈中的元素是指向二叉链表结点的指针*/Struct StNode *link；StNode；假设从栈顶到栈底的元素为 en，e n-1，e 1，则不含头结点的链栈示意图如图 2
37、1-11 所示。（分数：15.00）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明，回答问题 1 和问题 2，将解答填入对应栏内。说明0-1 背包问题可以描述为：有 n 个物品，i=1，2，n，第 i 个物品价值为 vi，重量为 wi(vi和 wi为非负数)，背包容量为 W(W 为非负数)，选择其中一些物品装入背包，使装入背包物品的总价值最大，即，且总重量不超过背包容量，即 ，其中，x i0，1，x i=0 表示第 i 个物品不放入背包，x i=1表示第 i 个物品放入背包。问题 1用回溯法求解此 0-1 背包问题，请填充伪代码中的空缺(1)(4)。回溯法是
38、一种系统的搜索方法。在确定解空间后，回溯法从根结点开始，按照深度优先策略遍历解空间树，搜索满足约束条件的解。对每一个当前结点，若扩展该结点已经不满足约束条件，则不再继续扩展。为了进一步提高算法的搜索效率，往往需要设计一个限界函数，判断并剪枝那些即使扩展了也不能得到最优解的结点。现在假设已经设计了 BOUND(v，w，k，w)函数，其中 v、w、k 和 W 分别表示当前已经获得的价值、当前背包的重量、已经确定是否选择的物品数和背包的总容量。对应于搜索树中的某个结点，该函数值表示确定了部分物品是否选择之后，对剩下的物品在满足约束条件的前提下进行选择可能获得的最大价值，若该价值小于等于当前已经得到的
39、最优解，则该结点无须再扩展。下面给出 0-1 背包问题的回溯算法伪代码。函数参数说明如下：W：背包容量；n：物品个数；w：重量数组；v：价值数组；fw：获得最大价值时背包的重量；fp：背包获得的最大价值；X：问题的最优解。变量说明如下：cw：当前的背包重量；cp：当前获得的价值；k：当前考虑的物品编号；Y：当前已获得的部分解。BKNAP(W，n，w，v，fw，fp，X)1 cwcp02 (1) 3 fp-14 While true5 while kn and cw+wkW do6 (2) 7 cpcp+vk8 Yk19 kk+110 if kn then11 if fpcp then12 fp
40、cp13 fwcw14 kn15 XY16 else Y(k)017 while BOUND(cp，cw，k，W)fp do18 while k0 and Y(k)1 do19 (3) 20 if k=0 then return21 Yk022 cwcwwk23 cpcpvk24 (4) 问题 2考虑表 21-3 所示的实例，假设有 3 个物品，背包容量为 22。图 21-12 是根据上述算法构造的搜索树，其中结点的编号表示搜索树生成的顺序，边上的数字 I/O 分别表示选择/不选择对应物品。除了根结点之外，每个左孩子结点旁边的上下两个数字分别表示当前背包的重量和已获得的价值，右孩子结点旁边的数
41、字表示扩展了该结点后最多可能获得的价值。为获得最优解，应该选择物品 (5) ，获得的价值为 (6) 。表 21-3 0-1 背包问题实例物品 1物品 2物品 3重量 15 10 10价值 30 18 17单位价值 2 1.8 1.7（分数：15.04）填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_填空项 1:_阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在对应栏内。说明对有向图进行拓扑排序的方法如下。(1)初始时拓扑序列为空。(2)任意选择一个入度为 0 的顶点，将其放入拓扑序列中，同时从图中删除该顶点以及从该顶点出发的弧。(
42、3)重复(2)，直到不存在入度为 0 的顶点为止(若所有顶点都进入拓扑序列，则完成拓扑排序；否则，由于有向图中存在回路无法完成拓扑排序)。函数 int* TopSort(LinkedDigraph G)的功能是对有向图 G 中的顶点进行拓扑排序，返回拓扑序列中的顶点编号序列，若不能完成拓扑排序，则返回空指针。其中，图 G 中的项点从 1 开始依次编号，顶点序列为v1，v2，vn，图 G 采用邻接表表示，其数据类型定义如下：#define MAXVNUM 50 /*最大顶点数*/typedef struct ArcNode /*表结点类型*/int adjvex； /*邻接顶点编号*/Struc
43、t ArcNode *nextarc； /*指示下一个邻接顶点*/ArcNode；typedef struct AdjList /*头结点类型*/char vdata； /*顶点的数据信息*/ArcNode *firstarc； /*指向邻接表的第一个表结点*/AdjList；typedef struct LinkedDigraph /*图的类型*/int n； /*图中顶点个数*/AdjList VheadMAXVNUM； /*所有顶点的头结点数组*/LinkedDigraph；例如，某有向图 G 如图 21-13 所示，其邻接表如图 21-14 所示。（分数：15.00）_阅读下列说明和 C 代码，回答问题 1 至问题 3，将解答写在对应栏内。说
