资源描述：
《西北工业大学软件工程专业算法总复习》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一.简答题1.写出回溯算法的一般模式。a)用回溯算法搜索子集树的一般模式voidsearch(intm){if(m>n)//递归结束条件output();//相应的处理(输出结果)else{a[m]=0;//设置状态：0表示不要该物品search(m+1);//递归搜索：继续确定下一个物品a[m]=1;//设置状态：1表示要该物品search(m+1);//递归搜索：继续确定下一个物品}}b)用回溯算法搜索子集树的一般模式voidsearch(intm){if(m>n)//递归结束条件output();//相应的处理(输出结果)elsefor(i=m;i<=n;i++){swap(m,i);
2、//交换a[m]和a[i]if()if(canplace(m))//如果m处可放置search(m+1);//搜索下一层swpa(m,i);//交换a[m]和a[i](换回来)}}2.分治算法的基本思想是什么？分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。递归地解这些子问题，然后将各个子问题的解合并得到原问题的解。它的一般的算法设计模式如下：divide-and-conquer(P){if(
3、P
4、<=n0)adhoc(P);dividePintosmallersubinstancesP1,P2,...,Pk;for(i=1;i<=k;i+
5、+)yi=divide-and-conquer(Pi);returnmerge(y1,...,yk);}其中，
6、P
7、表示问题P的规模。n0为一阀值，表示当问题P的规模不超过n0时，问题已容易解出，不必再继续分解。adhoc(P)是该分治法中的基本子算法，用于直接解小规模的问题P。当P的规模不超过n0时，直接算法adhoc(P)求解。算法merge(y1,y2,...,yk)是该分治法中的合并子算法，用于将P的子问题P1,P2,...,Pk的解y1,y2,...,yk合并为P的解。3.什么是最优子结构性质？1）重叠子问题2）最优子结构我们在这里讨论的最优子结构性质2）最优子结构：如果问题的最优
8、解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。最优子结构性质为动态规划算法解决问题提供了重要线索。例如，最短路径问题有以下最优子结构性质：如果一个节点x是到源节点ü的最短路径，同时又是到目的节点V的最短路径，则最短路径从u到v是结合最短路径：u到x和x到v。解决任意两点间的最短路径的算法的Floyd-Warshall算法和贝尔曼-福特是动态规划的典型例子。1.分支限界法的基本思想。2.简述分治法与动态规划算法的区别于联系？一.算法设计（1、2两题任选一题）1.矩阵连乘问题。2.最长公共子序列问题。#include#include9、ring.h>intlcs_length(charx[],chary[]);intmain(){charx[100],y[100];intlen;while(1){scanf("%s%s",x,y);if(x[0]=='0')//约定第一个字符串以‘0’开始表示结束break;len=lcs_length(x,y);printf("%d",len);}}intlcs_length(charx[],chary[]){intm,n,i,j,l[100][100];m=strlen(x);n=strlen(y);for(i=0;i10、;j++)l[0][j]=0;for(i=1;i<=m;i++)for(j=1;j<=n;j++)if(x[i-1]==y[j-1])//i,j从1开始，但字符串是从0开始l[i][j]=l[i-1][j-1]+1;elseif(l[i][j-1]>l[i-1][j])l[i][j]=l[i][j-1];elsel[i][j]=l[i-1][j];returnl[m][n];}由于每个数组单元的计算耗费Ο(1)时间，算法lcs_length耗时Ο(mn)。一.应用题（3、4选一题3易4难）1.用优先队列式分支限界法解决。2.写出对下面的序列进行合并排序的过程（从小到大）。3.63149982
11、3481570（举例）privatestaticvoidMerge(T[]array,intlo,intmid,inthi){inti=lo,j=mid+1;//把元素拷贝到辅助数组中for(intk=lo;k<=hi;k++){aux[k]=array[k];}//然后按照规则将数据从辅助数组中拷贝回原始的array中for(intk=lo;k<=hi;k++){//如果左边元素没了，直接将右边的剩余元素都
