西安邮电大学算法考试.doc

《西安邮电大学算法考试.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第1章算法概述（1）算法的性质包括输入、输出、确定性、有限性。（2）算法复杂性：算法所运行所需要的计算机资源的量，所需资源多，算法的复杂性高；反之则复杂性低。时间复杂性：需要时间资源的量(指令数)空间复杂性：需要空间资源的量(存储器的大小)（3）计算题第2章递归与分治策略（1）分治法主要思想：将一个规模为n的问题分解为k个规模较小子问题，这些子问题互相独立且与原问题相同，递归解决这些子问题，然后将各子问题的解合并得到原问题解。（2）使用分治算法找一组数的最大最小数。采用如下设计思想：将数据集S均分为S1和S2；求解S1和S2中的最大和最小值；最终的最大和最小值可以

2、计算得到：min(S1,S2),max(S1,S2)；采用同样的处理方法递归处理S1和S2。可以得到该算法复杂性的递推公式如下根据递推公式推导出该复杂性表达式:3）分治法所能解决的问题具有的特征.（1）该问题规模缩小到一定的程度就可以容易地解决；因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。（2）该问题可分解为若干个规模较小相同问题，即该问题具有“最优子结构性质”。这条特征是应用分治法前提，它也是大多数问题可满足的，反映了递归思想的应用。（3）利用该问题分解出的子问题的解可以合并为该问题的解。能否利用分治法完全取决于问题是否具有这

3、条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。（4）该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。4）数组A含有9个元素，这些元素恰好是第2至第10个Fibonacci数，写出在数组A中查找x=17的二分查找过程（写出过程即可，不需要写代码）。（5）下面给出了非递归形式的二分搜索方法代码，请补充下划线处的代码。templateintBin

4、arySearch(Typea[],constType&x,intn){//在a[0]<=a[1]<=...<=a[n–1]中搜索x，找到x时返回其在数组中的位置，否则返回-1intleft=0;intright=n-1;while(left<=right){intmiddle=(left+right)/2;if(x==a[middle])returnmiddle;if(x>a[middle])left=middle+1;elseright=middle-1;}return-1;//未找到x}（6）判断下列递归算法（计算n！）是否正确，如果不正确，请说明原因，并改

5、正。intfactoral(inti){if(n>0)return(n*factoral(n-1));}【分析】不正确，因为递归函数没有边界值的判断，无法得出正确的值。另外入口参数与下面的使用不一致。修改如下：intfactoral(intn){if(n==0)return1;return(n*factoral(n–1));}第3章动态规划（1）备忘录法是那种算法的变形（B）。A、分治算法B、动态规划算法C、贪心算法D、回溯法（2）分治法与动态规划算法的相同点和不同点是什么？（3）利用动态规划法设计如下的矩阵连乘最小次数问题，写出动态规划法求解过程。A1：40×2

6、5A2：25×25A3：25×15解：m[0][0]=m[1][1]=m[2][2]=m[3][3]=0r=2i=1j=2m[1][2]=40*25*10=10000i=2j=3m[2][3]=25*10*15=3750r=3i=1j=3m[1][3]=m[1][1]+m[2][3]+40*25*15=18750k=2t=m[1][2]+m[3][3]+40*10*15=16000m[1][3]=t=16000（4）具有最优子结构的算法有（D）。A．概率算法B．回溯法C．分支限界法D．动态规划法（5）证明题。（6）计算题（7）有一个箱子容量为V（正整数），同时有n

7、个物品，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。编写程序实现，自定义输入和输出。【提示】使用二维数组f[i][j],表示前i个物品装入容量为j的箱子能获得的最大体积，则状态转移方程：f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);（8）已知字符串A的值是sot，字符串B的值是stop，将字符串A转换为字符串B的编辑距离值为（）。A．1B．2C．3D．4【分析】根据“编辑距离”的定义，可知答案为B。sot通过一个“增加”操作变为stot，然后通过一个“编辑”操作就可以变为stop

8、。注意答案