算法设计与分析试题

算法设计与分析试题对于下图使用Dijkstra算法求由顶点a到顶点h的最短路径。解：用V1表示已经找到最短路径的顶点，V2表示与V1中某个顶点相邻接且不在V1中的顶点；E1表示加入到最短路径中的边，E2为与V1中的顶点相邻接且距离最短的路径。【1分】步骤V1V2E1 E2{a} {b}{} {ab}{a,b} {d}{ab} {bd}{a,b,d} {c,f} {ab,bd} {dc,df}{a,b,d,c} {f}{ab,bd} {df}{a,b,c,d,f}{e} {ab,bd,dc,df} {fe}{a,b,c,d,e,f} {g} {ab,bd,dc,df,fe} {eg}{a,b,c,d,e,f,g} {h} {ab,bd,dc,df,fe,eg} {gh}{a,b,c,d,e,f,g,h} {} {ab,bd,de,df,fe,eg,gh} {}【以上每步2分】结果：从a到h的最短路径为，权值为18。【1分】求所有顶点对之间的最短路径可以使用Dijkstra算法，使其起始节点从a循环到h，每次求起始节点到其他节点的最短路径，最终可以求得所有顶点对之间的最短路径。【2分】假设有7个物品，它们的重量和价值如下表所示。若这些物品均不能被分割，且背包容量M＝150，使用回溯方法求解此背包问题。请写出状态空间搜索树。物品ABCDEFG重量35306050401025价值10403050354030解：按照单位效益从大到小依次排列这7个物品为：FBGDECA。将它们的序号分别记为1～7。则可生产如下的状态空间搜索树。其中各个节点处的限界函数值通过如下方式求得：【排序1分】【状态空间搜索树及其计算过程17分，每个节点1分】a．b.c． d. e. f. g. h. i.j.在Q1处获得该问题的最优解为，背包效益为170。即在背包中装入物品F、B、G、D、A时达到最大效益，为170，重量为150。【结论2分】已知，k=1，2，3，4，5，6，r1=5，r2=10，r3=3，r4=12，r5=5，r6=50，r7=6，求矩阵链积A1×A2×A3×A4×A5×A6的最佳求积顺序。（要求：给出计算步骤）解：使用动态规划算法进行求解。求解矩阵为：【每个矩阵18分】12345610150330405165520102036033024301950301809301770403000186050150060123456101224220222230344404450560因此，最佳乘积序列为（A1A2）（（A3A4）（A5A6）），共执行乘法2010次。【结论2分】四、回答如下问题：什么是算法？算法的特征有哪些？什么是P类问题？什么是NP类问题？请描述集合覆盖问题的近似算法的基本思想。解：（1）算法是解决某类问题的一系列运算的集合【2分】。具有有穷行、可行性、确定性、0个或者多个输入、1个或者多个输出【8分】。（2）用确定的图灵机可以在多项式实践内可解的判定问题称为P类问题【2分】。用不确定的图灵机在多项式实践内可解的判定问题称为P类问题。【2分】集合覆盖问题的近似算法采用贪心思想：对于问题<X,F>，每次选择F中覆盖了尽可能多的未被覆盖元素的子集S，然后将U中被S覆盖的元素删除，并将S加入C中，最后得到的C就是近似最优解。【6分】五、排序和查找是常用的计算机算法。按照要求完成以下各题：对数组A={15，9，115，118，3，90，27，25，5}，使用合并排序方法将其排成递减序。若改变二分搜索法为三分搜索法，即从一个递减序列A中寻找元素Z，先与元素比较，若，则在前面个元素中寻找Z；否则与比较，总之使余下的序列为个元素。给出该方法的伪代码描述。使用上述算法对（1）所得到的结果搜索如下元素，并给出搜索过程：118，31，25。解：（1）第一步：15911511839027255 第二步：15911811590327255 第三步：11811515990272535 第四步：11811590272515935 第五步：11811590272515953【5分，每步1分】（2）输入：递减数组A[left:right]，待搜索元素v。【1分】输出：v在A中的位置pos，或者不在A中的消息（-1）。【1分】步骤：【8分】intBinarySearch(intA[],intleft,intright,intv){ intmid; while(left<=right) { first=left+(right-left+1)/3; second=left+(right-left+1)/3*2; if(v==A[first])returnfirst; elseif(v>A[first])right=first-1; elseif(v==A[second])returnsecond; elseif(v>A[second]){left=first+1;right=second-1;} elseleft=second+1; } return-1; }（3）搜索118：118>27，所以right＝3；118>115，所以right＝1；118＝118，找到。【2分】搜索31：31>27，所以right＝3；31<90，所以left=4，结束，未找到。【2分】搜索25：9<25<27，所以left=5，right=6；25＝25，找到。【1分】六、假设有7个物品，它们的重量和价值如下表所示。若这些物品均可以被分割，且背包容量M＝150，如果使用贪心方法求解此背包问题，请回答：（20分）。对各个物品进行排序时，依据的标准都有哪些？使用上述标准分别对7个物品进行排序，并给出利用各个顺序进行贪心求解时获得解。上述解中哪个是最优的？物品ABCDEFG重量35306050401025价值10403050354030解：（1）标准：重量、价值和单位价值。【3分，每个1分】（2）使用重量从小到大：FGBAEDC。得到贪心解为：FGBAE全部放入，而D放入20%，得到价值为165。【5分】使用价值从大到小：DFBEGCA，得到贪心解为：DFBE全部放入，而G放入80%，得到价值为：189。【5分】使用单位价值从大到小：FBGDECA，得到贪心解为：FBGD全部放入，而E放入87.5%，得到价值为190.625。【5分】（3）显然使用单位价值作为标准得到的是最优解。【2分】七、多段图问题：设G＝(V，E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi：，其中，V1和Vk分别只有一个顶点s（称为源）和一个顶点t（称为汇），图中所有的边（u,v），，。求由s到t的最小成本路径。（25分）给出使用动态规划算法求解多段图问题的基本思想。使用上述方法求解如下多段图问题。解：（1）基本思想：设P(i,j)是从Vi中的节点j到汇点t的最小成本路径，Cost(i,j)是其成本。则。边界条件是（1）若h=t，则Cost(h,t)＝0；（2）Cost(k-1,j)＝c(j,t)。【10分】（2）求解过程可以表示为：【6分，每个节点0.5分】其中每个节点标示的序偶(p,q)中，p表示节点到t的成本，q表示后继节点的编号。从而，最优路径为：1271012和1361012，成本为16。【4分】八、设x1、x2、x3是一个三角形的三条边，而且x1+x2+x3=14。请问有多少种不同的三角形？给出解答过程。解：由于x1、x2、x3是三角形的三条边，从而xi+xj>xk，|xi-xj|<xk，（i,j,k=1,2,3），【4分】根据x1+x2+x3=14可知1<xi<7（i=1,2,3）【4分】。利用回溯法求解得到：【7分，每个节点0.5分】即有4个可行解：（6，6，2），（6，5，3），（6，4，4，）（5，5，4）。【5分】九、15谜问题：在一个4×4的方格的棋盘上，将数字1到15代表的15个棋子以任意的顺序置入各方格中，空出一格。要求通过有限次的移动，把一个给定的初始状态变成目标状态。移动的规则是：每次只能把空格周围的四格数字（棋子）中的任意一个移入空格，从而形成一个新的状态。为了有效的移动，设计了估值函数C1(x)，表示在结点x的状态下，没有到达目标状态下的正确位置的棋子的个数。解：【每个节点1分，注意限界值。总共20分】十、设数组A有n个元素，需要找出其中的最大最小值。（20分）请给出一个解决方法，并分析其复杂性。把n个元素等分为两组A1和A2，分别求这两组的最大值和最小值，然后分别将这两组的最大值和最小值相比较，求出全部元素的最大值和最小值。如果A1和A2中的元素多于两个，则再用上述方法各分为两个子集。直至子集中元素至多两个元素为止。这是什么方法的思想？请给出该方法的算法描述，并分析其复杂性。解：（1）基本思想：从头到尾逐个扫描，纪录最大和最小元素。【2分】输入：具有n个元素的数组【1分】输出：最大值和最小值【1分】步骤：【4分】voidFindMaxMin(intA[],intn,intmax,intmin){ max=min=A[0]; for(i=1;i<n;i++) { if(A[i]>max)max=A[i]; if(A[i]<min)min=A[i]; }}复杂性分析：由于是从头到尾扫描各个元素，而每个元素都要与max和min比较一遍，从而时间复杂性为：O(n)。【2分】（2）【10分】voidFindMaxMin(intleft,intright,intmax,intmin) { if(left==right)max=min=A[left]; elseif(left=right-1) { max=(A[left]<A[right]?A[right]:A[left]); min=(A[left]<A[right]?A[left]:A[right]); } else{ mid=(left+right)/2; FindMaxMin(left,mid,gmax,gmin); FindMaxMin(mid+1,right,hmax,hmin); max=(gmax<hmax?hmax:gmax); min=(gmin<hmin?gmin:hmin]); }}十一、用分支限界法解装载问题时，对算法进行了一些改进，下面的程序段给出了改进部分；试说明斜线部分完成什么功能，以及这样做的原因，即采用这样的方式，算法在执行上有什么不同。////检查左儿子结点Typewt=Ew+w[i];//左儿子结点的重量if(wt<=c){//可行结点if(wt>bestw)bestw=wt;//加入活结点队列if(i<n)Q.Add(wt);}//检查右儿子结点if(Ew+r>bestw&&i<n)Q.Add(Ew);//可能含最优解Q.Delete(Ew);//取下一扩展结点解：斜线标识的部分完成的功能为：提前更新bestw值；这样做可以尽早的进行对右子树的剪枝。具体为：算法Maxloading初始时将bestw设置为0，直到搜索到第一个叶结点时才更新bestw。因此在算法搜索到第一个叶子结点之前，总有bestw=0，r>0故Ew+r>bestw总是成立。也就是说，此时右子树测试不起作用。为了使上述右子树测试尽早生效，应提早更新bestw。又知算法最终找到的最优值是所求问题的子集树中所有可行结点相应重量的最大值。而结点所相应得重量仅在搜索进入左子树是增加，因此，可以在算法每一次进入左子树时更新bestw的值。十二、简要回答下列问题：1.算法重要特性是什么？算法分析的目的是什么？算法的时间复杂性与问题的什么因素相关？2.什么是哈密顿环问题？用回溯法求解哈密顿环，如何定义判定函数？答：1.（1）确定性、可实现性、输入、输出、有穷性，（2）分析算法占用计算机资源的情况，对算法做出比较和评价，设计出额更好的算法，（3）算法的时间复杂性与问题的规模相关，是问题大小n的函数；2.（1）哈密顿环是指一条沿着图G的N条边环行的路径，它的访问每个节点一次并且返回它的开始位置，（2）当前选择的节点X[k]是从未到过的节点,即X[k]≠X[i](i=1,2,…,k-1)，且C(X[k-1],X[k])≠∞，如果k=-1，则C(X[k],X[1])≠∞。十三、简要回答下列问题：快速排序的基本思想是什么。什么是直接递归和间接递归？消除递归一般要用到什么数据结构？答：1.快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。2..在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。十四、写出多段图最短路经动态规划算法求解下列实例的过程，并求出最优值。5252863186317474各边的代价如下：C(1,2)=3，C(1,3)=5，C(1,4)=2C(2,6)=8，C(2,7)=4，C(3,5)=5，C(3,6)=4，C(4,5)=2，C(4,6)=1C(5,8)=4，C(6,8)=5，C(7,8)=6解：Cost(4,8)=0Cost(3,7)=C(7,8)+0=6，D[5]=8Cost(3,6)=C(6，8)+0=5,D[6]=8Cost(3,5)=C(5，8)+0=4D[7]=8Cost(2,4)=min{C(4，6)+Cost(3,6),C(4，5)+Cost(3,5)}=min{1+5,2+4}=6D[4]=6Cost(2,3)=min{C(3，6)+Cost(3,6)}=min{4+5}=9D[3]=5Cost(2,2)=min{C(2，6)+Cost(3,6),C(2，7)+Cost(3,7)}=min{8+5,4+6}=10D[2]=7Cost(1,1)=min{C(1,2)+Cost(2,2),C(1,3)+Cost(2,3),C(1,4)+Cost(2,4)}=min{3+10,5+9,2+6}=8D[1]=41→4→6→8十五、写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=(48,12,61,3,5,19,32,7)解：写出maxmin算法对下列实例中找最大数和最小数的过程。数组A=()1、48,12,61,3,5,19,32,72、48,1261,35,1932,73、48～61,12～319～32，5～74、61～323～55、613十六、快速排序算法对下列实例排序，算法执行过程中，写出数组A第一次被分割的过程。A=(65,70,75,80,85,55,50,2)解：第一个分割元素为65(1)(2)(3)(4)(5)(6)(7)(8)ip(1)(2)(3)(4)(5)(6)(7)(8)ip65707580855550228652758085555070376525080855575704665250558580757046557075808565502十七、一个旅行者要驾车从A地