第十七章数据结构与算法.docx
- 文档编号:15881646
- 上传时间:2023-07-08
- 格式:DOCX
- 页数:38
- 大小:105.72KB
第十七章数据结构与算法.docx
《第十七章数据结构与算法.docx》由会员分享,可在线阅读,更多相关《第十七章数据结构与算法.docx(38页珍藏版)》请在冰点文库上搜索。
第十七章数据结构与算法
数据结构与算法
您现在的位置:
希赛网 > 云阅读 > 软件设计师考试试题分类精解(2018版) > 试题1(2017年下半年试题4)
试题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+1
x[k]:
第k个访问的顶点编号,从0开始
Visited[x[k]]:
第k个顶点的访问标志,0表示未访问,1表示已访问
⑵C程序
#include<>
#include<>
#defineMAX100
VidoHamilton(intn,intx[MAX,intc[MAX][MAX]){
int;
intvisited[MAX];
intk;
/*初始化x数组贺visited数组*/
for(i=0:
i x[i]=0; visited[i]=0; } /*访问起始顶点*/ k=0 ( ); x[0]=0 K=k+1 /*访问其他顶点*/ while(k>=0){ x[k]=x[k]+1; while(x[k]> if( )&&c[x-[k-1]][x[k]=1){/*邻接顶点x[k]未被访问过*/ break; }else{ x[k]=x[k]+1 } } if(x[k] for(k=0;k prinf(〝%d--〝,x[k]; /*输出哈密尔顿回路*/ } prinf(〝%d--〝,x[0]; return; }elseifx[k] ( ) 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]=1 2、visited[x[k]]==0 3、visited[x[k]]==1 4、visited[x[k]]=1 5、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: 当前考虑的硬币数组中的第一个和最后一个下标 #include<> intgetCounterfeitCoin(intcoins[],intfirst,intlast) { intfirstSum=0,lastSum=0; intì; If(first==last-1){ /*只剩两枚硬币*/ if(coins[first] returnfirst; returnlast; } if((last-first+1)%2==0){ /*偶数枚硬币*/ for(i=first;i<( 1 );i++){ firstSum+=coins[i]; } for(i=first+(last-first)/2+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;i firstSum+=coins[i]; } For(i=first+(last-first)/2+1;i lastSum+=coins[i]; } If(firstSum returngetCounterfeitCoin(coins,first,first+(last-first)/2-1); }elseif(firstSum>lastSum){ 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)firstSum (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程序 #include<> #include<> #include<> /*求next[]的值*/ voidget_next(int*next,char*s,intIs) { inti=0,j=-1; next[0]=-1;/*初始化next[0]*/ while(i if(j==-1lls[i]==s[j]){/*匹配*/ j++; i++; if(s[i]==s[j]) next[i]=next[j]; else Next[i]=j; } else j=next[j]; } } intkmp(int*next,char*t,char*s,intlt,intIs) { Inti=0,j=0; while(i (1) ){ if(j==-1|| (2) ){ i++; j++; }else (3) ; } if(j>=ls) return (4) ; else return-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是否还有字符,即j i表示字符串t的下标,j表示字符串s的下标。 根据伪代码第步可以推导 (2)是判断字符串t和字符串s当前位置的字符是否相同,即t[i]==s[j]。 根据伪代码第步可以推导(3)是当第步判断条件不满足时,改变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,2,0,0]。 并计算得到起始位置为6。 试题答案 (4)问题1: (1): j (2): t[i]==s[j]; (3): get_next(next,s,ls); j=next[j]; (4): i+1-ls; 问题2: O(It+Is) 问题3: (6): [-1,-1,1,-1,-1,2,0,0],(7)6。 试题4(2016年上半年试题4) 试题四(共15分) 阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 在一块电路板的上下两端分别有n个接线柱。 根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱π(i)相连,称其为该电路板上的第i条连线。 如图4-1所示的π(i)排列为{8,7,4,2,5,1,9,3,10,6}。 对于任何1≤i 图4-1电路布线示意 在制作电路板时,要求将这n条连线分布到若干绝缘层上,在同一层上的连线不相交。 现在要确定将哪些连线安排在一层上,使得该层上有尽可能多的连线,即确定连线集Nets={(i,π(i)),1≤i≤n}的最大不相交子集。 【分析问题】 记N(i,j)={t|(t,π(t))∈Nets,t≤i,π(t)≤j}。 N(i,j)的最大不相交子集为MNS(i,j),size(i,j)=|MNS(i,j)|。 经分析,该问题具有最优子结构性质。 对规模为n的电路布线问题,可以构造如下递归式: 【C代码】 下面是算法的C语言实现。 (1)变量说明 size[i][j]: 上下端分别有i个和j个接线柱的电路板的第一层最大不相交连接数 pi[i]: π(i),下标从1开始 (2)C程序 #include"" #include<> #define N 10 /*问题规模*/ intm=0; /*牢记录最大连接集合中的接线柱*/ VoidmaxNum(intpi[],intsize[N+1][N+1],intn) {/*求最大不相交连接数*/ inti,j; for(j=0;j (1)时 */ for(j=pi[1];j<=n;j++) (1) ;/*当j>=π (1)时 */ for(i=2;i for(j=0;j (2) ;/*当j for(j=pi[i];j<=n;j++) {/*当j>=c[i]时,考虑两种情况*/ size[i][j]=size[i-1][j]>=size[i-1][pi[i]-1]+1size[i-1][j]: size[i-1][pi[i]-1]+1; } } /*最大连接数 */ size[n][n]=size[n-1][n]>=size[n-1][pi[n]-1]+1size[n-1][n]: size[n-1][pi[n]-1]+1; } /*构造最大不相交连接集合,net[i]表示最大不相交子集中第i条连线的上端接线柱的序号 */ voidconstructSet(intpi[],intsize[N+1][N+1],intn,intnet[n]){ inti,j=n; m=0; for(i=n;i>1;i--) { /*从后往前*/ if(size[i][j]! =size[i-1][j]){ /*(i,pi[i])是最大不相交子集的一条连线*/ (3) ; /*将i记录到数组net中,连接线数自增1*/ j=pi[i]-1; /*更新扩展连线柱区间*/ } } if(j>=pi[1]) net[m++]=1; /*当i=1时*/ } 【问题1】(6分) 根据以上说明和C代码,填充C代码中的空 (1)~(3)。 【问题2】(6分) 据题干说明和以上C代码,算法采用了 (4) 算法设计策略。 函数maxNum和constructSet的时间复杂度分别为 (5) 和 (6) (用O表示)。 【问题3】(3分) 若连接排列为{8,7,4,2,5,1,9,3,10,6},即如图4-1所示,则最大不相交连接数为 (7) ,包含的连线为 (8) (用(i,π(i))的形式给出)。 试题分析 这个是动态规划问题,不想交的平行线,算法思路来才能完整。 设a[i][j]为上端接线柱i与下端接线柱j前的最大不相交子集,则: 若i与j不相连,则i与j前的最大不想交子集等于i与j-1前或i-1与j前的最大不相交子集的最大值,即a[i][j]=max(a[i][j-1],a[i-1][j]) 若i与j相连,则i与j前的最大不想交子集等于i-1与j-1前的最大不想交子集加1,即a[i][j]=a[i-1][j-1]+1 题目的意思就是要求出,没有交叉的这种连线的数量达到最大的情况。 此时,有4条这样的线不会交叉,所以是大不相交子集连接数为4。 如果你能找到5条这样不交叉的线,则是5。 就这个意思。 试题答案 (4) 【问题1】 (1)size[i][j]=1 (2)size[i][j]=size[i-1][j] (3)net[m++]=i; 【问题2】 (4)动态规划算法 (5)O(n2) (6)O(n) 【问题3】 (7)4 (8)(3,π(3),(5,π(5)),(7,π(7)),(9,π(9)) 或: (3,4),(5,5),(7,9),(9,10) 试题5(2015年下半年试题4) 阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 计算两个字符串x和y的最长公共子串(LongestCommonSubstring)。 假设字符串x和字符串y的长度分别为m和n,用数组c的元素c[i][j]记录x中前i个字符和y中前j个字符的最长公共子串的长度。 c[i][j]满足最优子结构,其递归定义为: 计算所有c[i][j](0≤i≤m,0≤j≤n)的值,值最大的c[i][j]即为字符串x和y的最长公共子串的长度。 根据该长度即i和j,确定一个最长公共子串。 【C代码】 (1)常量和变量说明 x,y: 长度分别为m和n的字符串 c[i][j]: 记录x中前i个字符和y中前j个字符的最长公共子串的长度 max: x和y的最长公共子串的长度 maxi,maXj: 分别表示x和y的某个最长公共子串的最后一个字符在x和y中的位置(序号) (2)C程序 #include<> #include<> intc[50][50]; intmaxi; intmaxj; intlcs(char*x,intm,char*y,intn) { inti,j; intmax=0; maxi=0; maxj=0; for(i=0;i<=m;i++) c[i][0]=0; for(i=1;i<=n;i++) c[0][i]=0; for(i=1;i<=m;i++) { for(j=1;j<=n;j++) { if( (1) ) { c[i][j]=c[i-1][j-1]+1; if(max
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十七 数据结构 算法