桂-林-电-子-科-技-大-学-试-卷B答案.doc

桂 林 电 子 科 技 大 学 试 卷 20162017 学年第 1 学期 课号 课程名称 网络与信息安全实验（ B 卷 ，开卷）适用班级（或年级、专业） 13、14 考试时间 120 分钟 班级 学号 姓名 题 号一二三四五六七八九十成绩满 分20303020100得 分评卷人第一题、（20分）请编写一个函数fun(char *str)，其功能是：判别字符串str是否是回文，若是，返回；否则返回。例如：“12321”,“adcdcba”；而“hello”，“123”就不是回文。部分源程序如下：#include #include #include intfun(char *str)intk;char*head,*rear;return!(*head-*rear);main() chars100;intflag;clrscr();printf(n please enter stringn);gets(s);flag=fun(s);printf(%d,flag);#include#include#includeintfun(char*str)intk;char*head,*rear;k=0;for(head=str;*head!=0;head+)k+;for(head=str,rear=head+k-1;headrear;head+,rear-)if(head=rear)continue;elsebreak;return!(*head-*rear);voidmain()chars100;intflag;/clrscr();printf(npleaseenterstringn);gets(s);flag=fun(s);printf(%d,flag);第二题、（30分）分别用动态规划法、递归算法法设计0-1背包问题。要求：说明所使用的算法策略；写出算法实现的主要步骤；分析算法的时间。动态规划法:#includeint V200200;/前i个物品装入容量为j的背包中获得的最大价值int max(int a,int b) if(a=b) return a; else return b;int KnapSack(int n,int w,int v,int x,int C) int i,j; for(i=0;i=n;i+) Vi0=0; for(j=0;j=C;j+) V0j=0; for(i=0;i=n-1;i+) for(j=0;j=C;j+)for(int k=1;k=j/wi;k+) if(j=0;i-) if(VijVi-1j) xi=1; j=j-wi; else xi=0; printf(选中的物品是:n); for(i=0;in;i+) printf(%d ,xi); printf(n); return Vn-1C; void main() int s;/获得的最大价值 int w15;/物品的重量 int v15;/物品的价值 int x15;/物品的选取状态 int n,i; int C;/背包最大容量 n=5; printf(请输入背包的最大容量:n); scanf(%d,&C); printf(输入物品数:n); scanf(%d,&n); printf(请分别输入物品的重量:n); for(i=0;in;i+) scanf(%d,&wi); printf(请分别输入物品的价值:n); for(i=0;in;i+) scanf(%d,&vi); s=KnapSack(n,w,v,x,C); printf(最大物品价值为:n); printf(%dn,s); 时间复杂度为O(n3)递归算法：#include using namespace std; const int W = 150; const int number = 5; const int VALUE = 60, 20, 10, 60, 100; const int WEIGHT = 20, 30, 50, 60, 80; /function Make( i 处理到第i件物品 , j剩余的空间为j) :integer; int Make(int i, int j) int r1 = 0; int r2 = 0; int r = 0; if (i = -1) return 0; if(j = WEIGHTi) /背包剩余空间可以放下物品 i r1 = Make(i-1,j - WEIGHTi) + VALUEi; /第i件物品放入所能得到的价值 r2 = Make(i-1,j); /第i件物品不放所能得到的价值 r = (r1r2)?r1:r2; return r; void main() int maxValue = Make(number-1, W); coutmaxValue: maxValueendl; 第三题、（30分）通过键盘输入一个高精度的正整数n(n的有效位数240)，去掉其中任意s个数字后，剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s，寻找一种方案，使得剩下的数字组成的新数最小。【样例输入】178543S=4【样例输出】13#includeint maxNum(char num240) int i,max=0,k; for(i=0;numi!=0;i+) if(max(int)numi) max=(int)numi; k=i; return k;void move(char num240,int n) int i;for(i=n;numi+1!=0;i+) numi=numi+1;numi=0;void fun(int s,char num240)while(s-)move(num,maxNum(num);void main() char num240; int s,i;