第十七章-数据结构与算法

数据结构与算法您现在的位置：希赛网云阅读软件设计师考试试题分类精解（2018版）试题1(2017年下半年试题4)第17章：数据结构与算法应用作者：希赛软考学院来源：希赛软考学院2017年11月21日试题1(2017年下半年试题4)阅读下列说明和C代码，回答问题1至问题2，将解答写在答题纸的对应栏内。【说明】一个无向连通图G点上的哈密尔顿（Hamiltion）回路是指从图G上的某个顶点出发，经过图上所有其他顶点一次且仅一次，最后回到该顶点的路劲。一种求解无向图上哈密尔顿回路算法的基础私下如下：假设图G存在一个从顶点V0出发的哈密尔顿回路V1——V2——V3——...——Vn-1——V0。算法从顶点V0出发，访问该顶点的一个未被访问的邻接顶点V1，接着从顶点V1出发，访问V1一个未被访问的邻接顶点V2，..。；对顶点Vi，重复进行以下操作：访问Vi的一个未被访问的邻接接点Vi+1；若Vi的所有邻接顶点均已被访问，则返回到顶点Vi-1，考虑Vi-1的下一个未被访问的邻接顶点，仍记为Vi；知道找到一条哈密尔顿回路或者找不到哈密尔顿回路，算法结束。【C代码】下面是算法的C语言实现。（1）常量和变量说明n:图G中的顶点数c［］［］:图G的邻接矩阵K:统计变量，当期已经访问的定点数为k+1x［k］:第k个访问的顶点编号，从0开始Visited［x［k］］：第k个顶点的访问标志，0表示未访问，1表示已访问⑵C程序#includestido.h#includestidb.h#defineMAX100VidoHamilton（intn,intx［MAX,intc[MAX][MAX]）｛int;intvisited[MAX];intk;/*初始化x数组贺visited数组*/for（i=0:in;i++）｛x[i]=0;visited[i]=0;｝/*访问起始顶点*/k=0（）；x[0]=0K=k+1/*访问其他顶点*/while（k=0）｛x[k]=x[k]+1;while（x[k]n）｛if（）&&c[x-[k-1]][x[k]＝1）｛/*邻接顶点x[k]未被访问过*/break；｝else｛x[k]=x[k]+1｝｝if（x[k]n-1&&（）｛/*找到一条哈密尔顿回路*/for（k=0;kn;k++）｛prinf（〝%d--〝,x[k];/*输出哈密尔顿回路*/｝prinf（〝%d--〝,x[0];return；｝elseifx[k]n&&kn-1）｛/*设置当期顶点的访问标志，继续下一个顶点*/（）k=k+1;｝else｛/*没有未被访问过的邻接顶点，回退到上一个顶点*/x[k]=0；visitedx[k]=0；（）；｝｝｝【问题1】（10分）根据题干说明。填充C代码中的空（1）~（5）.【问题2】（5分）根据题干说明和C代码，算法采用的设计策略为（6），该方法在遍历图的顶点时，采用的是（7）方法（深度优先或广度优先）。试题分析哈密顿图是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路，含有图中所有顶点的路径称作哈密顿路径。回溯法是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个解时，只要搜索到问题的一个解就可以结束。算法题历来都被认为是比较难的题，一个程序开发人员都不喜欢看别人的代码。但是要得分也不是太难。问题2比较容易得分，而且第二空就是个二选一的填空。只要了解到回溯法的相关原理，基本可以得满分。对于问题1就需要花一些心思，去读懂题干和代码，但是这里的第1空和第5空也是比较容易发挖出来的空。第一空是初始化第一个结点，第五空是此路不通，得回走，所以得退回。。试题答案（4）问题1：1、visited[0]=12、visited[x[k]]==03、visited[x[k]]==14、visited[x[k]]=15、k=k-1问题2：6、回溯法7、深度优先试题2(2017年上半年试题4)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】假币问题：有n枚硬币，其中有一枚是假币，己知假币的重量较轻。现只有一个天平，要求用尽量少的比较次数找出这枚假币。【分析问题】将n枚硬币分成相等的两部分:(1)当n为偶数时，将前后两部分，即1...n/2和n/2+1...0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币:(2)当n为奇数时，将前后两部分，即1..(n-1)/2和(n+1)/2+1...0，放在天平的两端，较轻的一端里有假币，继续在较轻的这部分硬币中用同样的方法找出假币；若两端重量相等，则中间的硬币，即第(n+1)/2枚硬币是假币。【C代码】下面是算法的C语言实现，其中:coins[]：硬币数组first，last：当前考虑的硬币数组中的第一个和最后一个下标#includestdio.hintgetCounterfeitCoin(intcoins[]，intfirst，intlast){intfirstSum=0，lastSum=0;intì;If(first==last-1){/*只剩两枚硬币*/if(coins[first]coins[last])returnfirst;returnlast;}if((last-first+1)%2==0){/*偶数枚硬币*/for(i=first;i(1);i++){firstSum+=coins[i];}for(i=first+(last-first)/2+1;ilast+1;i++){lastSum+=coins[i];}if(2){ReturngetCounterfeitCoin(coins,first,first+(last-first)/2;)}else{ReturngetCounterfeitCoin(coins,first+(last-first)/2+1,last;)}}else{/*奇数枚硬币*/For(i=first;ifirst+(last-first)/2;i++){firstSum+=coins[i];}For(i=first+(last-first)/2+1;ilast+1;i++){lastSum+=coins[i];}If(firstSumlastSum){returngetCounterfeitCoin(coins,first,first+(last-first)/2-1);}elseif(firstSumlastSum){returngetCounterfeitCoin(coins,first+(last-first)/2-1,last);}else{Return(3)}}}【问题一】根据题干说明，填充C代码中的空（1）-（3）【问题二】根据题干说明和C代码，算法采用了（）设计策略。函数getCounterfeitCoin的时间复杂度为（）（用O表示）。【问题三】若输入的硬币数为30，则最少的比较次数为（），最多的比较次数为（）。试题分析若输入30个硬币，找假硬币的比较过程为：第1次：15比15，此时能发现假币在15个的范围内。第2次：7比7，此时，如果天平两端重量相同，则中间的硬币为假币，此时可找到假币，这是最理想的状态。第3次：3比3，此时若平衡，则能找出假币，不平衡，则能确定假币为3个中的1个。第4次：1比1，到这一步无论是否平衡都能找出假币，此时为最多比较次数。参考答案试题答案（4）问题1（1）first+(last-first)/2或(first+last)/2（2）firstSumlastSum（3）first+(last-first)/2或(first+last)/2问题2（4）分治法（5）O（nlogn）问题3（6）2（7）4试题3(2016年下半年试题4)阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。【说明】模式匹配是指给定主串t和子串s，在主串t中寻找子串s的过程，其中s称为模式。如果匹配成功，返回s在t中的位置，否则返回-1。KMP算法用next数组对匹配过程进行了优化。KMP算法的伪代码描述如下：1．在串t和串s中，分别设比较的起始下标i=j=0。2．如果串t和串s都还有字符，则循环执行下列操作：（1）如果j=-l或者t[i]=s[j]，则将i和j分别加1，继续比较t和s的下一个字符；（2）否则，将j向右滑动到next[j]的位置，即j=next[j]。3．如果s中所有字符均已比较完毕，则返回匹配的起始位置（从1开始）；否则返回-1．其中，next数组根据子串s求解。求解next数组的代码已由get_next函数给出。【C代码】（1）常量和变量说明t，s：长度为悯铂Is的字符串next:next数组，长度为Is（2）C程序#includestdio.h#includestdlib.h#includestring.h/*求next[]的值*/voidget_next(int*next,char*s,intIs){inti=0，j=-1;next[0]=-1;/*初始化next[0]*/while(ils){/*还有字符*/if(j==-1lls[i]==s[j]){/*匹配*/j++;i++;if(s[i]==s[j])next[i]=next[j];elseNext[i]=j;}elsej=next[j];}}intkmp(int*next,char*t,char*s,intlt,intIs){Inti=0,j=0;while(ilt&&（1）){if(j==-1||（2）){i++;j++;}else（3）;}if(j=ls)return（4）;elsereturn-1;}【问题1】（8分）根据题干说明，填充C代码中的空（1）～（4）.【问题2】（2分）根据题干说明和C代码，分析出kmp算法的时间复杂度为（5）（主串和子串的长度分别为It和Is，用O符号表示）。【问题3】（5分）根据C代码，字符串“BBABBCAC”的next数组元素值为（6）（直接写素值，之间用逗号隔开）。若主串为“AABBCBBABBCACCD”，子串为“BBABBCAC”，则函数Kmp的返回值是（7）。试题分析本题问题1根据KMP算法的伪代码描述进行推导。根据伪代码中第2步可以推导（1）是判断字符串s是否还有字符，即jls。i表示字符串t的下标，j表示字符串s的下标。根据伪代码第2.1步可以推导（2）是判断字符串t和字符串s当前位置的字符是否相同，即t[i]==s[j]。根据伪代码第2.2步可以推导（3）是当第2.1步判断条件不满足时，改变j所指向的字符位置。即调用函数get_next(next,s,ls)，且j=next[j]。根据伪代码第3步可以推导（4）是返回匹配的起始位置。由于当前i所指向字符串中匹配子串的最后一个字符的位置，且已知子串的长度为ls。（4）的代码为i+1-ls。本题问题2是计算KMP算法的复杂度。算法的复杂度一般考虑最坏情况，那么在子串读到ls及主串读到It的时候是最坏情况。所以复杂度是O(It+Is)本题问题3中已知字符串“BBABBCAC”，则根据get_next()函数可以求得next数组的元素值为[-1,-1,1,-1,-1,