05计本算法设计与分析期考试卷(C卷)

福建师范大学试卷纸共10页，第1页一．填空题（每空2分，共30分）1．计算复杂性包括两个方面。2．在忽略常数因子的情况下，提供了算法运行时间的一个界。3．算法的平均情况下时间复杂性A(n)=nDI)I(t)I(p，其中Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间,p(I)表示。4．从算法时间复杂性的角度看，时间复杂性阶为的算法是实际可接受的。5．用动态规划算法解题时，，算法的效率越高。6．分治算法的基本步骤包括。7．回溯算法的搜索顺序是。8．贪心法通常用于求解问题。9．PQ式的分支限界法中，活结点表的结构是。10．Prim算法、Dijkstra算法、快速排序算法和Huffman算法中不是贪心算法。11．一个问题满足递归关系是指。12．随机算法不同于确定性算法，对于同一输入，不同的运行执行的时间。13对于下面的确定性二分查找算法，只要将步骤3改为随机化步骤，就可得到一个随机化查找算法。算法BISEARCH输入：正整数n，n个元素的升序数组A[1..n]和元素x。输出：如果存在j，1=j=n使得x=A[j]，则输出j，否则输出0。1.low=1;high=n;j=02.while(low=high)and(j=0)3.mid=2/)highlow(4.ifx=A[mid]thenj=mid5.elseifxA[mid]thenhigh=mid-1福建师范大学试卷纸共10页，第2页考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线6.elselow=mid+17.endif8.endif9.endwhile10.returnjendBISEARCH14．下面算法的基本运算是运算，该算法中第4步执行了次。算法COUNT输入：正整数n（n=k2）。输出：count的值。1.count=02.whilen=13.forj=1ton4.count=count+15.endfor6.n=n/27.endwhileendCOUNT二．计算题和简答题（每小题7分，共21分）1．用表示下列各函数的阶，并按阶从低到高的顺序排列这些函数。n3/(n+5),2n+3n/2,5n2log3n+n3log2n,n!+nn,log(logn)/1000福建师范大学试卷纸共10页，第3页2．下面是一个分治算法，其中，过程pro1和pro2的运算时间分别是1和nnlog2。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用表示）。算法EX2输入：正整数n，n=2k。输出：…ex2(1,n)endEX2过程ex2(low,high)iflow=highthenpro1()elsem=2/)highlow(ex2(low,m)ex2(m+1,high)pro2(low,high)endifreturnendex23．设矩阵M1，M2，M3，M4，M5的阶如下：M1：102M2：25M3：52M4：24M5：410。下面表1和表2是用动态规划算法MATCHAIN求矩阵链乘积M1M2M3M4M5所需的最少数量乘法次数的有关结果，福建师范大学试卷纸共10页，第4页考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线C[1,1]=0C[1,2]=100C[1,3]=60C[1,4]=C[1,5]=C[2,2]=0C[2,3]=20C[2,4]=36C[2,5]=C[3,3]=0C[3,4]=40C[3,5]=180C[4,4]=0C[4,5]=80C[5,5]=0表1S[1,1]=0S[1,2]=2S[1,3]=2S[1,4]=S[1,5]=S[2,2]=0S[2,3]=3S[2,4]=4S[2,5]=S[3,3]=0S[3,4]=4S[3,5]=4S[4,4]=0S[4,5]=5S[5,5]=0表2其中，C[i,j]表示求MiMi+1…Mj所需的最少数量乘法次数，S[i,j]表示相应的最优解信息。填充表1和表2中空缺的数据，并根据数组S确定求M1M2M3M4M5的最优顺序（通过加括号表示）。三．算法填空题（共34分）1．（10分）下面是快速排序算法。算法QUICKSORT输入：正整数n，n个元素的数组A[1..n]。输出：按非降序排列的数组A中的元素。quicksort(A,1,n)endQUICKSORT过程quicksort(A,low,high)//将A[low..high]中的元素按非降序快速排序。iflowhighthenw=SPLIT(A,low,high)福建师范大学试卷纸共10页，第5页quichsort((1))quichsort((2))endifendquicksort过程SPLIT(A,low,high)//以A[low]为主元划分A[low..high],返回主元的新位置。i=low;x=A[low]forj=low+1tohighifA[j]=xtheni=(3)ifi≠jthen(4)endifendfor(5)w=ireturnwendSPLIT2.(10分)下面是用回溯法解n皇后问题的算法（求出所有解）。n皇后问题：在nxn棋盘上放置n个皇后使得任何两个皇后不能互相攻击。（如果两个皇后处在同一行，或同一列，或同一斜线上，则她们能互相攻击。）算法NQUEENS输入：正整数n。输出：n皇后问题的一个解x[1..n],若无解，则输出Nosolution。flag=falsek=1;x[1]=0福建师范大学试卷纸共10页，第6页考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线while(1)whilex[k]nx[k]=(2)ifplace(k)thenifk=nthenflag=true；outputx[1..n]elsek=(3)(4)endifendifendwhile(5)endwhileifnotflagthenoutput“Nosolution”endNQUEENS过程place(k)//判断第k行皇后是否与前k-1行皇后冲突，是则返回false,否//则返回true。……endplace3.（14分）下面是解可复选的背包问题的动态规划算法。问题描述：有一个容量为C的背包和n种物品，每种物品的个数都是无限的。设第i种物品的体积和价值分别为si和vi，C,si,vi都是正整数，i=1,2,…,。在这n种物品中选择物品装入背包，使得福建师范大学试卷纸共10页，第7页装入背包的物品总价值最大。设每种物品都可选择任意个装入背包。设f[i,j]表示背包容量为j，在第1~i种物品中进行选择的可复选背包问题的最优值，则0i,}v*k]s*k-j1,{f[imax0i,0j]f[i,iij/sk0i算法KNAPSACK输入：物品种数n,n种物品的体积数组s[1..n]和价值数组v[1..n],背包容量C。输出：装入背包物品的最大总价值maxv，以及存储最优解信息的数组H[0..n,0..C]。f[0..n,0..C]=-1maxv=knapsack(n,C)returnmaxv,HendKNAPSACK过程knapsack(i,j)//从第1~i种物品中选择物品装入容量为j的背包中，求背包中物品//所能达到的最大总价值并返回，同时将最优解的相应信息存入数//组H[0..n,0..C]。iff[i,j]=(1)thenifi=0thenf[i,j]=0elsemax=knapsack(i-1,j)k0=0;j1=j;v1=0fork=1toj/s[i]j1=j1-s[i];v1=v1+v[i]福建师范大学试卷纸共10页，第8页考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线a=(2)ifamaxthenmax=a(3)endifendforf[i,j]=(4)(5)endifendifreturnf[i,j]endknapsack算法KNAPSACK_SOLUTION输入：物品种数n,背包容量C,n种物品的体积数组s[1..n],相应的可复选的背包问题的最优解信息数组H[0..n,0..C]。输出：相应的可复选的背包问题的最优解x[1..n]。y=C;x[n]=H[n,C]fori=n-1to1y=(6)x[i]=(7)endforreturnx[1..n]endKNAPSACK_SOLUTION福建师范大学试卷纸共10页，第9页四．算法设计题（15分）1.设有n种不同面值的硬币，面值分别为n21c,,c,c，1ic=iics，is为正整数，i=1,2,…,n-1，每种硬币的个数不限，要求用最少个数的硬币，兑换价值为m的钱（m为非负整数），给出用贪心法求解该最优化问题的贪心选择策略，写出求最优值和最优解的贪心算法，并分析算法的时间复杂性。福建师范大学试卷纸共10页，第10页2005计本《算法设计与分析》期考试卷(C)标准答案一.填空题：1.时间复杂性和空间复杂性2.下3.输入I出现的概率4.多项式阶5.重叠的子问题越多6.分解，递归，组合7.深度优先搜索顺序（或DFS搜索顺序）8.最优化9.优先队列10.快速排序算法11.对原问题的求解可转化为对其性质相同的子问题的求解。12.可能不同13.mid=random(low,high)14.加法（或：赋值）2n-1二.计算题和简答题：1.1.各函数的阶为：n3/(n+5)=(n2),2n+3n/2=(2n),5n2log3n+n3log2n=(n3log2n),n!+nn=(nn),log(logn)/1000=(log(logn))按阶从低到高的顺序排列这些函数的结果是：log(logn)/1000,n3/(n+5),5n2log3n+n3log2n,2n+3n/2,n!+nn2.该分治算法的时间复杂性T(n)满足下列递归方程：1n,1nnlog2T(n/2)T(n)1n,1T(n)2将n=k2,a=2,c=2,g(n)=nnlog2+1,d=1代入该类递归方程解的一般形式得：T(n)=n+1k0ii2ii12nlog2n2=n+n)in(log1k0i2+1-k0ii2福建师范大学试卷纸共10页，第11页=n+knnlog2-2)1k(nk+12k=2n+nlogn2122+nlogn212-1所以，T(n)=2n+nlogn2122+nlogn212-1=)nlogn(22。3.C[1,4]=116C[2,5]=116C[1,5]=316S[1,4]=2S[2,5]=5S[1,5]=2最优顺序：M1(((M2M3)M4)M5)三.算法填空题：1.(1)A,low,w-1(2)A,w+1,high(3)i+1(4)A[i]A[j](5)A[i]A[low]2.(1)k=1(2)x[k]+1(3)k+1(4)x[k]=0(5)k=k-13.(1)–1(2)knapsack(i-1,j1)+v1(3)k0=k(4)max(5)H[i,j]=k0(6)y-x[i+1]*s[i+1](7)H[i,y]四.算法设计题：1.贪心选择策略：按面值从高到低的顺序即按面值11-nnc,,c,c的顺序找出硬币，对面值高的硬币尽可能多找出。算法COINCHANGING输入：正整数n，非负整数m，存储n种硬币面值的数组c[1..n]。输出：兑换价值为m的钱所用硬币的最少个数以及最优解x[1..n](x[i]表示所兑换出的面值为c[i]的硬币的个数)，若无解，则输出“nosolution”。min=0;x[1..n]=0i=nwhilem0andi=1x[i]=]i[c/mmin=min+x[i]m=m-x[i]*c[i]i=i-1endwhile