算法设计与分析期末考试卷及答案a

一．填空题（每空2分，共30分）1．算法的时间复杂性指算法中的执行次数。2．在忽略常数因子的情况下，O、和三个符号中，提供了算法运行时间的一个上界。3．设Dn表示大小为n的输入集合，t(I)表示输入为I时算法的运算时间,p(I)表示输入I出现的概率，则算法的平均情况下时间复杂性A(n)=。4．分治算法的时间复杂性常常满足如下形式的递归方程：00nn,g(n)af(n/c)f(n)nn,d)n(f其中，g(n)表示。5.分治算法的基本步骤包括。6．回溯算法的基本思想是。7．动态规划和分治法在分解子问题方面的不同点是。8．贪心算法中每次做出的贪心选择都是最优选择。9．PQ式的分支限界法中，对于活结点表中的结点，其下界函数值越小，优先级越。10．选择排序、插入排序和归并排序算法中，算法是分治算法。11．随机算法的一个基本特征是对于同一组输入，不同的运行可能得到的结果。12.对于下面的确定性快速排序算法，只要在步骤3前加入随机化步骤，就可得到一个随机化快速排序算法，该随机化步骤的功能是。算法QUICKSORT输入：n个元素的数组A[1..n]。输出：按非降序排列的数组A中的元素。考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线1.quicksort(1,n)endQUICKSORT过程quicksort(A,low,high)//对A[low..high]中的元素按非降序排序。2.iflowhighthen3.w=SPLIT(A,low,high)//算法SPLIT以A[low]为主元将A[low..high]划分成两部//分，返回主元的新位置。4.quicksort(A,low,w-1)5.quicksort(A,w+1,high)6．endifendquicksort13．下面算法的基本运算是运算，该算法的时间复杂性阶为()。算法SPLIT输入：正整数n，数组A[1..n]。输出：…。i=1x=A[1]forj=2tonifA[j]=xtheni=i+1ifijthenA[i]A[j]endifendforA[i]A[1]w=ireturnw,AendSPLIT二．计算题和简答题（每小题7分，共21分）1．用O、、表示函数f与g之间阶的关系，并分别指出下列函数中阶最低和最高的函数：(1)f(n)=100g(n)=100n(2)f(n)=6n+nnlogg(n)=3n(3)f(n)=n/logn-1g(n)=n2(4)f(n)=22nng(n)=n3(5)f(n)=n3logg(n)=n2log2．下面是一个递归算法，其中，过程pro1和pro2的运算时间分别是1和nlog2。给出该算法的时间复杂性T(n)满足的递归方程，并求解该递归方程，估计T(n)的阶（用表示）。算法EX1输入：正整数n，n=2k。输出：…ex1(n)endEX1过程ex1(n)ifn=1thenpro1(n)else考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线pro2(n)ex1(n/2)endifreturnendex13．用Floyd算法求下图每一对顶点之间的最短路径长度，计算矩阵D0，D1，D2和D3，其中Dk[i,j]表示从顶点i到顶点j的不经过编号大于k的顶点的最短路径长度。三．算法填空题（共34分）1．（10分）设n个不同的整数按升序存于数组A[1..n]中，求使得A[i]=i的下标i。下面是求解该问题的分治算法。算法SEARCH输入：正整数n，存储n个按升序排列的不同整数的数组A[1..n]。输出：A[1..n]中使得A[i]=i的一个下标i，若不存在，则输出nosolution。i=find((1))ifi0thenoutputielseoutput“nosolution”endSEARCH过程find(low,high)//求A[low..high]中使得A[i]=i的一个下标并返回，若不存在，//则返回0。if(2)thenreturn0elsemid=2/)highlow(if(3)thenreturnmidelseifA[mid]midthenreturnfind((4))elsereturn(5)endifendifendifendfind2．(10分)下面是求解矩阵链乘问题的动态规划算法。矩阵链乘问题：给出n个矩阵M1,M2,…,Mn,Mi为riri+1阶矩阵，i=1,2,…,n，求计算M1M2…Mn所需的最少数量乘法次数。记Mi,j=MiMi+1…Mj,i=j。设C[i,j],1=i=j=n,表示计算Mi,j的所需的最少数量乘法次数，则ji,}rrrj]C[k,1]-k,i[C{minji,0j],i[C1jkijki算法MATCHAIN输入：矩阵链长度n,n个矩阵的阶r[1..n+1],其中r[1..n]为n个矩阵的行数，r[n+1]为第n个矩阵的列数。输出：n个矩阵链乘所需的数量乘法的最少次数。考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线fori=1tonC[i,i]=（1）ford=1ton-1fori=1ton-dj=(2)C[i,j]=∞fork=i+1tojx=(3)ifxC[i,j]then(4)=xendifendforendforendforreturn(5)endMATCHAIN3．(14分)下面是用回溯法求解马的周游问题的算法。马的周游问题：给出一个nxn棋盘，已知一个中国象棋马在棋盘上的某个起点位置（x0,y0），求一条访问每个棋盘格点恰好一次，最后回到起点的周游路线。（设马走日字。）算法HORSETRAVEL输入：正整数n，马的起点位置(x0,y0)，1=x0,y0=n。输出：一条从起点始访问nxn棋盘每个格点恰好一次，最后回到起点的周游路线；若问题无解，则输出nosolution。tag[1..n,1..n]=0dx[1..8]={2,1,-1,-2,-2,-1,1,2}dy[1..8]={1,2,2,1,-1,-2,-2,-1}flag=falsex=x0;y=y0;tag[x,y]=1m=n*ni=1;k[i]=0while(1)andnotflagwhilek[i]8andnotflagk[i]=(2)x1=x+dx[k[i]];y1=y+dy[k[i]]if((x1,y1)无越界andtag[x1,y1]=0)or((x1,y1)=(x0,y0)andi=m)thenx=x1;y=y1tag[x,y]=(3)ifi=mthenflag=trueelsei=(4)(5)endifendifendwhilei=i-1(6)(7)endwhileifflagthenoutputroute(k)//输出路径elseoutput“nosolution”endHORSETRAVEL《算法设计与分析》期考试卷(A)标准答案一.填空题：1.元运算考生信息栏＿＿＿＿＿＿学院＿＿＿＿＿＿系＿＿＿＿＿＿专业＿＿＿＿＿＿年级姓名＿＿＿＿＿＿学号＿＿＿＿＿装订线四．算法设计题（15分）1.一个旅行者要驾车从A地到B地，A、B两地间距离为s。A、B两地之间有n个加油站，已知第i个加油站离起点A的距离为id公里，0=sdddn21，车加满油后可行驶m公里，出发之前汽车油箱为空。应如何加油使得从A地到B地沿途加油次数最少？给出用贪心法求解该最优化问题的贪心选择策略，写出求该最优化问题的最优值和最优解的贪心算法，并分析算法的时间复杂性。2.O3.nDIItIp)()(4.将规模为n的问题分解为子问题以及组合相应的子问题的解所需的时间5.分解，递归，组合6.在问题的状态空间树上作带剪枝的DFS搜索（或：DFS+剪枝）7.前者分解出的子问题有重叠的，而后者分解出的子问题是相互独立（不重叠）的8.局部9.高10.归并排序算法11.不同12.v=random(low,high);交换A[low]和A[v]的值随机选主元13.比较n二.计算题和简答题：1.阶的关系：(1)f(n)=O(g(n))(2)f(n)=(g(n))(3)f(n)=(g(n))(4)f(n)=O(g(n))(5)f(n)=(g(n))阶最低的函数是：100阶最高的函数是：n32.该递归算法的时间复杂性T(n)满足下列递归方程：1n,nlogT(n/2)T(n)1n,1T(n)2将n=k2,a=1,c=2,g(n)=nlog2,d=1代入该类递归方程解的一般形式得：T(n)=1+1k0ii22nlog=1+knlog2-1k0ii=1+knlog2-2)1k(k=nlog2122+nlog212+1所以，T(n)=nlog2122+nlog212+1=)(log2n。3.051060320D0051050320D105850320D2058503270D3三.算法填空题：1.(1)1,n(2)lowhigh(3)A[mid]=mid(4)mid+1,high(5)find(low,mid-1)2.(1)0(2)i+d(3)C[i,k-1]+C[k,j]+r[i]*r[k]*r[j+1](4)C[i,j](5)C[1,n]3.(1)i=1(2)k[i]+1(3)1(4)i+1(5)k[i]=0(6)tag[x,y]=0(7)x=x-dx[k[i]];y=y-dy[k[i]]四.算法设计题：1.贪心选择策略：从起点的加油站起每次加满油后不加油行驶尽可能远，直至油箱中的油耗尽前所能到达的最远的油站为止，在该油站再加满油。算法MINSTOPS输入：A、B两地间的距离s，A、B两地间的加油站数n，车加满油后可行驶的公里数m，存储各加油站离起点A的距离的数组d[1..n]。输出：从A地到B地的最少加油次数k以及最优解x[1..k]（x[i]表示第i次加油的加油站序号），若问题无解，则输出nosolution。d[n+1]=s;//设置虚拟加油站第n+1站。fori=1tonifd[i+1]-d[i]mthenoutput“nosolution”;return//无解，返回endifendfork=1;x[k]=1//在第1站加满油。s1=m//s1为用汽车的当前油量可行驶至的地点与A点的距离i=2whiles1sifd[i+1]s1then//以汽车的当前油量无法到达第i+1站。k=k+1;x[k]=i//在第i站加满油。s1=d[i]+m//刷新s1的值endifi=i+1endwhileoutputk,x[1..k]MINSTOPS最坏情况下的时间复杂性：Θ(n)