下载文档原格式
习题11.图论诞生于七桥问题。
出生于瑞士的伟大数学家欧拉（Leonhard Euler ，1707—1783）提出并解决了该问题。
七桥问题是这样描述的：一个人是否能在一次步行中穿越哥尼斯堡（现在叫加里宁格勒，在波罗的海南岸）城中全部的七座桥后回到起点，且每座桥只经过一次，图是这条河以及河上的两个岛和七座桥的草图。
请将该问题的数据模型抽象出来，并判断此问题是否有解。
七桥问题属于一笔画问题。
输入：一个起点 输出：相同的点 1， 一次步行2， 经过七座桥，且每次只经历过一次 3， 回到起点该问题无解：能一笔画的图形只有两类：一类是所有的点都是偶点。
另一类是只有二个奇点的图形。
2．在欧几里德提出的欧几里德算法中（即最初的欧几里德算法）用的不是除法而是减法。
请用伪代码描述这个版本的欧几里德算法 =m-n2.循环直到r=0 m=n n=r r=m-n 3 输出m3．设计算法求数组中相差最小的两个元素（称为最接近数）的差。
要求分别给出伪代码和C++描述。
编写程序，求n 至少为多大时，n 个“1”组成的整数能被2013整除。
#include<iostream> using namespace std;int main() {double value=0;图 七桥问题for(int n=1;n<=10000 ;++n){value=value*10+1;if(value%2013==0){cout<<"n至少为:"<<n<<endl;break;}}计算π值的问题能精确求解吗？编写程序，求解满足给定精度要求的π值#include <iostream>using namespace std;int main (){double a,b;double arctan(double x);圣经上说：神6天创造天地万有，第7日安歇。
为什么是6天呢？任何一个自然数的因数中都有1和它本身，所有小于它本身的因数称为这个数的真因数，如果一个自然数的真因数之和等于它本身，这个自然数称为完美数。
编译原理一、单选题1、( B )是两类程序语言处理程序.A.高级语言程序和低级语言程序B.解释程序和编译程序C.编译程序和操作系统D.系统程序和应用程序2.解释程序处理语言时,大多数采用的是( A )方法.A.源程序命令被逐个直接解释执行B.先将源程序转化为中间代码,再解释执行C.先将源程序解释转化为目标程序,再执行D.以上方法都可以3.( A )是一种典型的解释型语言.A.BASICB.CC.FORTRAND.PASCAL4.与编译系统相比,解释系统( D ).A.比较简单,可移植性好,执行速度快B.比较复杂,可移植性好,执行速度快C.比较简单,可移植性差,执行速度慢D.比较简单,可移植性好,执行速度慢5.编译程序是一种( B ).A.汇编程序B.翻译程序C.解释程序D.目标程序6.编译程序是对( D ).A.汇编程序的翻译B.高级语言程序的解释执行C.机器语言的执行D.高级语言的翻译7.用高级语言编写的程序经编译后产生的程序叫( B ).A.源程序B.目标程序C.连接程序D.解释程序8.将编译程序分成若干个“遍”是为了( B ).A.提高程序的执行效率B.使程序的结构更加清晰C.利用有限的机器内存并提高机器的执行效率D.利用有限的机器内存但降低了机器的执行效率9.构造编译程序应掌握( D ).A.源程序B.目标语言C.编译方法D.以上三项都是10.通常一个编译程序中,不仅包含词法分析,语法分析,中间代码生成,代码优化,目标代码生成等五个部分,还应包括( C ).A.模拟执行器B.解释器C.表格处理和出错处理D.符号执行器11.编译程序绝大多数时间花在( D )上.A.出错处理B.词法分析C.目标代码生成D.管理表格12.程序的基本块是指( D ).A.一个子程序B.一个仅有一个入口和一个出口的语句C.一个没有嵌套的程序段D.一组顺序执行的程序段,仅有一个入口和一个出口13.变量应当( C ).A.持有左值B.持有右值C.既持有左值又持有右值D.既不持有左值也不持有右值14.数组的内情向量中肯定不含有数组的( A )的信息.A.维数B.类型C.维上下界D.各维的界差15.一个上下文无关文法G包括四个组成部分:一组终结符,一组非终结符,一个开始符号,以及一组( B ).A.字符串B.产生式C.非开始符号D.文法16.一个文法所描述的语言是( A ).A.唯一的B.不唯一的C.可能唯一,也可能不唯一D.都不对17.文法G产生的( D )的全体是该文法描述的语言.A.句型B.终结符集C.非终结符集D.句子18.若文法G定义的语言是无限集,则文法必然是( A ).A.递归的B.前后文无关的C.二义性的D.无二义性的19.文法分为四种类型,即0型,1型,2型,3型.其中2型文法是( C ).A.短语文法B.正则文法C.上下文有关文法D.上下文无关文法20.四种形式语言文法中,1型文法又称为( D )文法.A.短语文法B.正则文法C.上下文有关文法D.上下文无关文法21.正规式M1和M2等价是指( C ).A.M1和M2的状态数相等B.Ml和M2的有向弧条数相等C.M1和M2所识别的语言集相等D.Ml和M2状态数和有向弧条数相等22.词法分析器的输出结果是( C ).A.单词的种别编码B.单词在符号表中的位置C.单词的种别编码和自身值D.单词自身值23.词法分析器用于识别( C ).A.字符串B.语句C.单词D.标识符24.扫描器所完成的任务是从字符串形式的源程序中识别出一个个具有独立含义的最小语法单位即( B ).A.字符B.单词C.句子D.句型25.一个句型中称为句柄的是该句型的最左( D ).A.非终结符号B.短语C.句子D.直接短语26.下推自动机识别的语言是( C ).A.0型语言B.1型语言C.2型语言D.3型语言27.如果文法G是无二义的,则它的任何句子α( A ).A.最左推导和最右推导对应的语法树必定相同B.最左推导和最右推导对应的语法树可能不同C.最左推导和最右推导必定相同D.可能存在两个不同的最左推导,但它们对应的语法树相同28.采用自上而下分析,必须( C ).A.消除左递归B.消除右递归C.消除回溯D.提取公共左因子29.在规范归约中,用( B )来刻画可归约串.A.直接短语B.句柄C.最左素短语D.素短语30.若a为终结符,则A->α·aβ为( B )项目.A.归约B.移进C.接受D.待约31.高级语言编译程序常用的语法分析方法中,递归下降分析法属于( B )分析方法.A.自左向右B.自顶向下C.自底向上D.自右向左32.在通常的语法分析方法中,( A )特别适用于表达式的分析.A.算符优先分析法B.LR分析法C.递归下降分析法D.LL(1)分析法33.语法分析器则可以发现源程序中的( D ).A.语义错误B.语法和语义错误C.错误并校正D.语法错误34.后缀式ab+cd+/可用表达式( B )来表示.A.a+b/c+dB.(a+b)/(c+d)C.a+b/(c+d)D.a+b+c/d35.中间代码生成时所依据的是( C ).A.语法规则B.词法规则C.语义规则D.等价变换规则36.( B )和代码优化部分不是每个编译程序都必需的.A.语法分析B.中间代码生成C.词法分析D.目标代码生成37.常用的中间代码形式不含( D ).A.三元式B.四元式C.逆波兰式D.语法树38.代码优化的目的是( C ).A.节省时间B.节省空间C.节省时间和空间把编译程序进行等价交换39.优化可生成( D )的目标代码.A.运行时间较短B.占用存储空间较小C.运行时间短但占用内存空间大D.运行时间短且占用存储空间小40.下列( C )优化方法不是针对循环优化进行的.A.强度削弱B.删除归纳变量C.删除多余运算D.代码外提41.基本块内的优化为( B ).A.代码外提,删除归纳变量B.删除多余运算,删除无用赋值C.强度削弱,代码外提D.循环展开,循环合并42.代码生成阶段的主要任务是( C ).A.把高级语言翻译成汇编语言B.把高级语言翻译成机器语言C.把中间代码变换成依赖具体机器的目标代码D.把汇编语言翻译成机器语言43.在目标代码生成阶段,符号表用于( D ).A.目标代码生成B.语义检查C.语法检查D.地址分配44.程序所需的数据空间在程序运行前就可确定,称为( C )管理技术.A.动态存储B.栈式存储C.静态存储D.堆式存储45.堆式动态分配申请和释放存储空间遵守( D )原则.A.先请先放B.先请后放C.后请先放D.任意46.编译程序使用( B )区别标识符的作用域.A.说明标识符的过程或函数名B.说明标识符的过程或函数的静态层次C.说明标识符的过程或函数的动态层次D.标识符的行号47.生成能被5整除的正整数的文法G[Z]是( C ).A.G(Z):Z→AC,A→BA|B,B→0|1|2|…|9,C→0|5B.G(Z):Z→AC,A→BA|ε,B→0|1|2|…|9,C→0|5C.G(Z):Z→AC|5,A→BA|B,B→0|1|2|…|9,C→0|5D.G(Z):Z→AC|C,A→BA|B,B→0|1|2|…|9,C→0|548.符号串ab1b2是给定文法G[A]:A→aB,B→bB|b的句子,该句子的句柄是( B ).A.b1B.b2C.cD..b1b249.一般程序设计语言的定义都涉及( B )三个方面.①语法②语义③语用④程序基本符号的确定A.①,②和③B.①,②和④C.①,③和④D.②,③和④50.下述语句类中,( C )在编译阶段通常不产生可执行代码.A.赋值语句B.流程控制语句C.说明语句D.输入输出语句51.算符文法是指( A )的文法.①没有形如U→...VW...的规则(U,V,W VN)②VT中任意两个符号之间至多存在一种算符优先关系③没有相同右部的规则④没有形如U→ε的规则A.①B.①和②C.①,②和③D.①,②,③和④52.已知文法G[E]:E→ABC,A→1|2|3|4|5|6|7|8|9,B→BA|B0|ε,C→0|2|4|6|8,对符号串128,它的最左推导是( C ).A.EÞABCÞAB8ÞABA8ÞAB28ÞA28Þ128B.EÞABCÞABACÞAACÞ1ACÞ12CÞ128C.EÞABCÞ1BCÞ1BACÞ1ACÞ12CÞ128D.EÞABCÞ1BCÞ1BACÞ1ACÞ1A8Þ12853.程序的基本块是指( D ).A.不含无条件转移语句的程序段B.不含条件转移语句的程序段C.不含停机的语句程序段D.仅含有一个入口语句和一个出口语句的顺序程序段54.在编译程序采用的优化方法中,( D )是在循环语句范围内进行的.①合并已知常量②删除多余运算③删除归纳变量④强度削弱⑤代码外提A.①④B.①⑤C.①④⑤D.③④⑤55.设有文法G[I]:I→I1|I0|Ia|Ic|a|b|c,下列符号串中是该文法的句子的有( B ).①ab0 ②a0c01 ③aaa ④bc10A.①B.②③④C.③④D.①②③④56.LR(0)分析法中,语法分析栈中存放的状态是识别规范句型( B )的DFA状态.A.前缀B.活前缀C.LR(0)项目D.句柄57.常用( D )来识别一个正规集A.无穷自动机B.图灵机C.下推自动机D.有穷自动机58.文法所描述的语言是( D )的集合.A.文法的字汇表V中符号组成的符号串B.文法的字汇表V中终结符号组成的符号串C.由文法开始符推导的符号串D.由文法开始符推导的终结符号串59.LL(1)文法中第一个L表示( C ).A.最左推导B.最左归约C.从左到右识别输入串D.规范归约60.编译程序前三个阶段完成的工作是( C )A.词法分析,语法分析和代码优化代码生成,代码优化和词法分析B.词法分析,语法分析,语义分析和中间代码生成C.词法分析,语法分析和代码优化二.判断题1.逆波兰表示法表示表达式时无须使用括号.( ✔)2.静态数组的存储空间可以在编译时确定.（✘）3.进行代码优化时应着重考虑循环的代码优化,这对提高目标代码的效率将起更大作用.（✘）4.树形表示和四元式不便于优化,而三元式和间接三元式则便于优化.（✘）5.计算机高级语言翻译成低级语言只有解释一种方式.（✘）6.用高级语言书写的源程序都必须通过编译,产生目标代码后才能投入运行.（✘）7.在编译中进行语法检查的目的是为了发现程序中所有错误.（✘）8.甲机上的某编译程序在乙机上能直接使用的必要条件是甲机和乙机的操作系统功能完全相同.（✔）9.编译程序与具体的机器有关,与具体的语言无关.（✘）10.编译程序是对高级语言程序的解释执行.（✘）11.程序语言的语言处理程序是一种应用软件.（✘）12.在程序中标识符的出现仅为使用性的.（✘）13.仅考虑一个基本块,不能确定一个赋值是否真是无用的.（✔）14.符号表中的信息栏中登记了每个名字的属性和特征等有关信息,如类型,种属,所占单元大小,地址等等.（✘）15.一张转换图只包含有限个状态,其中有一个被认为是初态,最多只有一个终态.（✔）16.一个有限状态自动机中,有且仅有一个唯一的终态.（✘）17.产生式是用于定义词法成分的一种书写规则.（✘）18.若一个句型中出现了某产生式的右部,则此右部一定是该句型的句柄.（✘）19.一个句型的句柄一定是文法某产生式的右部.（✔）20.词法分析作为单独的一遍来处理较好.（✘）21.正则文法其产生式为A->a,A->Bb,A,B∈VN,a,b∈VT.（✘）22.正规文法产生的语言都可以用上下文无关文法来描述.（✘）23.设r和s分别是正规式,则有L(r|s)=L(r)L(s).（✘）24.确定的自动机以及不确定的自动机都能正确地识别正规集.（✔）25.每个文法都能改写为LL(1)文法.（✔）26.一个LL(l)文法一定是无二义的.（✘）27.如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的.（✔）28.语法分析时必须先消除文法中的左递归.（✘）29.综合属性是用于“自上而下”传递信息.（✘）30.规范归约和规范推导是互逆的两个过程.（✘）31.递归下降法允许任一非终极符是直接左递归的.（✔）32.递归下降分析法是自顶向上分析方法.（✔）33.算符优先关系表不一定存在对应的优先函数.（✘）34.一个算符优先文法可能不存在算符优先函数与之对应.（✔）35.自底而上语法分析方法的主要问题是候选式的选择.（✘）36.LR法是自顶向下语法分析方法.（✘）37.LR分析法在自左至右扫描输入串时就能发现错误,但不能准确地指出出错地点.（✔）38.构造LR分析器的任务就是产生LR分析表.（✔）39.LR分析技术无法适用二义文法.（✘）40.简单优先文法允许任意两个产生式具有相同右部.（✘）41.程序中的表达式语句在语义翻译时不需要回填技术.（✔）42.削减运算强度破坏了临时变量在一基本块内仅被定义一次的特性.（✔）43.在中间代码优化中循环上的优化主要有不变表达式外提和削减运算强度.（✘）44.对中间代码的优化依赖于具体的计算机.（✘）45.数组元素的地址计算与数组的存储方式有关.（✘）46.目标代码生成时,应考虑如何充分利用计算机的寄存器的问题.（✘）47.逆波兰法表示的表达式亦称前缀式.（✔）三.填空题1.编译方式与解释方式的根本区别在于是否生成目标代码 .2.若源程序是用高级语言编写的,目标程序是机器语言程序或汇编程序,则其翻译程序称为编译程序 .3.对编译程序而言,输入数据是源程序,输出结果是目标程序.4.编译程序的工作过程一般划分为5个阶段:词法分析, 语法分析,语义分析与中间代码生成,代码优化及目标代码生成.5.一个名字的属性包括类型和作用域.6.设G是一个给定的文法,S是文法的开始符号,如果S->x(其中x∈VT*),则称x是文法的一个句子 .7.扫描器的任务是从源程序中识别出一个个单词符号 .8.规范规约是最左规约.9.词法分析基于正则文法进行,即识别的单词是该类文法的句子.10.文法符号的属性有综合属性和继承属性 .11.语法分析器的输入是单词符号串,其输出是语法单位.12.语法分析的有效工具是语法树 .13.语法分析最常用的两类方法是自上而下和自下而上分析法.14.分析句型时,应用算符优先分析技术时,每步被直接归约的是最左素短语 .15.应用LR分析技术时,每步被直接归约的是句柄 .16.自顶向下的语法分析方法的基本思想是:从文法的开始符号开始,根据给定的输入串并按照文法的产生式一步一步的向下进行直接推导,试图推导出文法的句子,使之与给定的输入串匹配.17.自底向上的语法分析方法的基本思想是:从输入串入手,利用文法的产生式一步一步地向上进行直接归约,力求归约到文法的开始符号.18.自上而下分析法采用移进,归约,错误处理,接受等四种操作.19.一个LR分析器包括两部分:一个总控程序和一张分析表 .20.递归下降法不允许任一非终极符是直接左递归的.21.对于文法的每个产生式都配备了一组属性的计算规则,称为语义规则 .22.如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义性文法 .23.预测分析程序是使用一张分析表和一个符号栈进行联合控制的.四.问答题1.简述编译程序各组成部分的主要功能.[答案]:词法分析器:输入源程序,进行词法分析,输出单词符号.语法分析器:在词法分析的基础上,根据语言的语法规则(文法规则)把单词符号串分解成各类语法单位,并判断输入串是否构成语法上正确的“程序”.中间代码生成器:按照语义规则把语法分析器归约(或推导)出的语法单位翻译成一定形式的中间代码,比如说四元式.优化:对中间代码进行优化处理.目标代码生成器:把中间代码翻译成目标语言程序.表格管理模块保存一系列的表格,登记源程序的各类信息和编译各阶段的进展情况.编译程序各阶段所产生的中间结果都记录在表格中,所需信息多数都需从表格中获取,整个编译过程都在不断地和表格打交道.出错处理程序对出现在源程序中的错误进行处理.此外,编译的各阶段都可能出现错误,出错处理程序对发现的错误都及时进行处理.2.文法G[S]为:S->Ac|aBA->abB->bc写出L(G[S])的全部元素.[答案]:S=>Ac=>abcS=>aB=>abc所以L(G[S])={abc}3.什么是句子?什么是语言?[答案]:设G是一个给定的文法,S是文法的开始符号,如果Sx(其中x∈VT*),则称x是文法的一个句子.设G[S]是给定文法,则由文法G所定义的语言L(G)可描述为:L(G)＝{x│Sx,x∈VT*}.4.一字母表∑={a,b},试写出∑;上所有以a为首的字组成的正规集相对应的正规式.[答案]:正规式a(a|b)*。
课堂作业模块1 Java编程逻辑【第1课】【作业1】编写一个Java程序，在控制台上输出如下两行信息：Hello，World！Hello，Java！考核点1：了解一个Java程序的启动位置（即程序入口）。
考核点2：掌握基本输出语句：System.out.println(字符串)【第2课】【作业1】从键盘输入3个整数a、b、c，计算a+b*c的结果后输出，验证计算结果是否遵循运算符的优先级顺序。
考核点1：使用Scanner类获取键盘输入。
考核点2：基本运算符及其优先级顺序。
【作业2】从键盘输入1个实数r，计算以r为半径的圆的面积并输出结果，要求将π定义为符号常量。
考核点：符号常量的基本用法。
【第3课】【作业1】从键盘输入3个整数，比较大小后输出最大者。
考核点：if-else语句的运用。
【作业2】从键盘输入一个3位数，判断其是否为水仙花数。
所谓“水仙花数”是指一个三位整数，其各位数字立方和等于该数本身。
例如：153=13+53+33,所以153是一个水仙花数。
考核点：基本数学运算符和逻辑运算符的用法。
【第4课】【作业1】从键盘输入3个整数，比较大小后按由小到大的顺序输出。
考核点：if-else语句嵌套运用。
【作业2】从键盘输入一个年份和一个月份，输出此月份有多少天（考虑闰二月的情况）。
考核点：使用switch-case多分支语句。
【第5课】【作业1】从键盘输入一个正整数，判断其是否为素数。
素数指只有1和它本身两个因子的整数。
考核点：基本循环语句的用法。
【作业2】输出100-999之间的全部水仙花数。
考核点：基本循环语句的用法。
【作业3】从键盘输入一个正整数，判断并输出该正整数是几位数。
考核点1：基本循环语句的用法。
考核点2：分离一个整数各个位数字的方法。
【第6课】【作业1】编写一个Java程序，输出如下图案，图案的行数由键盘输入。
（1）观察图案中行、列及星星个数之间的关系。
（2）扩展练习，输出如下图案，图案的行数由键盘输入。
国开电大专科《程序设计基础》形考任务1至4试题及答案形考任务1试题及答案一、填空题1.计算机的五大主要应用领域是______、______、______、______和______。
[答案]科学计算、数据处理、过程控制、计算机辅助系统、人工智能2.总线是连接______、______和______的公共信息通道。
通常由三部分组成：______、______、______。
[答案]CPU、存储器、外部设备、数据总线、地址总线、控制总线3.计算机是一类智能机器，这是因为它除了完成算术运算外，还能完成某些______。
[答案]逻辑运算4.世界上第一台计算机取名为______。
[答案]ENIAC5.目前制造计算机所采用的电子器件是______。
[答案]大规模集成电路6.CPU是CentralProceingUnit的英文缩写，它主要由______、______和寄存器3个部分组成。
[答案]运算器、控制器7.完整的计算机系统是由______和______两大部分组成的。
[答案]硬件系统、件系统8.计算机的硬件系统一般可分为______、______、______和______等几个部分。
[答案]存储器、中央处理器、输入设备、输出设备9.计算机的存储器分为______和______两级。
[答案]内存、外存10.随机存储器和只读存储器的英文缩写分别为______和______。
[答案]RAM、ROM11.______是为有效利用计算机的资源、充分发挥计算机的潜力、保证正常运行、尽可能方便用户使用计算机而编制的软件。
[答案]程序13.______是计算机的概念模型，奠定了现代计算机的理论基础；______是计算机的结构模型，奠定了现代计算机的设计基础。
[答案]图灵机14.高级语言源程序的翻译成机器语言程序一般有两种做法:______方式和______方式。
[答案]编译、解释15.按照使用方式，程序设计语言分为______语言和______语言；按照应用范围则分为______语言和______语言。
字符串的全排列（字典序排列）题⽬描述输⼊⼀个字符串，打印出该字符串中字符的所有排列。
例如输⼊字符串abc，则输出由字符a、b、c 所能排列出来的所有字符串abc, acb, bac, bca, cab, cba。
题⽬分析穷举与递归⼜是⼀个经典问题，最容易想到的解决⽅法仍然是穷举（我实在是太爱穷举法了，每当被问到算法问题不知道如何解决的时候，总可以祭出穷举⼤旗，从⽽多争取3分钟的思考时间）。
穷举虽好，但它⼤多数情况下都不是被需要的那个答案，是因为看起来代码太Low不够⾼⼤上吗？在这种情况下，穷举法裹着貂⽪⼤⾐的亲戚——递归就出现了。
虽然空间复杂度和时间复杂度没有任何改进，⽽且还增加了系统开销（关于递归法的系统开销不在这⾥讨论，之后再找专门的时间阐述），但是就是因为长得好看（代码看起来精炼），递归的B格⼉就⾼了很多。
递归法对于这个题⽬同样⾮常适⽤，基本思路就是固定⼀个字符，然后对剩余的字符做全排列……不赘述，请⾃⼰想。
如果你也跟我⼀样永远想不明⽩递归，那就画画图，写写代码，debug⼀下，每天花3-4个⼩时，静下⼼来仔细捉摸，总（ye）会（bu）想（hui）明⽩的。
贴⼀段July和他伙伴们在《程序员编程艺术：⾯试和算法⼼得》中的代码实现，供做噩梦时使⽤。
p.s. 我已加了注释/** Permute full array of input string by general recusion* @ char* perm [in/out] The string need to do permutation* @ int from [in] The start position of the string* @ int to [in] The end position of the string*/void CalcAllPermutation(char* perm, int from, int to){if (to <= 1){return;}if (from == to){//all characters has been permutedfor (int i = 0; i <= to; i++)cout << perm[i];cout << endl;}else{// always select one character, then full array the left ones.for (int j = from; j <= to; j++){swap(perm[j], perm[from]); //swap the selected character to the beginning of stringCalcAllPermutation(perm, from + 1, to); // Permute left characters in full array.swap(perm[j], perm[from]); //recovery the string to original one (swap the selected character back to its position.)}}}字典序这是⼀个⽐递归更有趣的答案，不知道算不算经典解法，起码开拓了思路，跟每⼀次接触新鲜的算法⼀样，仍然想了半天的时间，因此照例把思考过程更细致的记录下来（虽然July和他伙伴们在《程序员编程艺术：⾯试和算法⼼得》中已经说了很多），再加上⼀些⼩修改。
动态规划经典——最长公共⼦序列问题（LCS）和最长公共⼦串问题⼀.最长公共⼦序列问题(LCS问题)给定两个字符串A和B，长度分别为m和n，要求找出它们最长的公共⼦序列，并返回其长度。
例如： A = "Hel lo W o rld" B = "loo p"则A与B的最长公共⼦序列为 "loo",返回的长度为3。
此处只给出动态规划的解法：定义⼦问题dp[i][j]为字符串A的第⼀个字符到第 i 个字符串和字符串B 的第⼀个字符到第 j 个字符的最长公共⼦序列，如A为“app”,B为“apple”，dp[2][3]表⽰ “ap” 和 “app” 的最长公共字串。
注意到代码中 dp 的⼤⼩为 (n + 1) x (m + 1) ，这多出来的⼀⾏和⼀列是第 0 ⾏和第 0 列，初始化为 0，表⽰空字符串和另⼀字符串的⼦串的最长公共⼦序列，例如dp[0][3]表⽰ "" 和“app” 的最长公共⼦串。
当我们要求dp[i][j]，我们要先判断A的第i个元素B的第j个元素是否相同即判断A[i - 1]和 B[j -1]是否相同，如果相同它就是dp[i-1][j-1]+ 1，相当于在两个字符串都去掉⼀个字符时的最长公共⼦序列再加 1；否则最长公共⼦序列取dp[i][j - 1] 和dp[i - 1][j]中⼤者。
所以整个问题的初始状态为：dp[i][0]=0,dp[0][j]=0相应的状态转移⽅程为：dp[i][j]=max{dp[i−1][j],dp[i][j−1]},A[i−1]!=B[j−1] dp[i−1][j−1]+1,A[i−1]==B[j−1]代码的实现如下：class LCS{public:int findLCS(string A, int n, string B, int m){if(n == 0 || m == 0)//特殊输⼊return 0;int dp[n + 1][m + 1];//定义状态数组for(int i = 0 ; i <= n; i++)//初始状态dp[i][0] = 0;for(int i = 0; i <= m; i++)dp[0][i] = 0;for(int i = 1; i <= n; i++)for(int j = 1; j<= m; j++){if(A[i - 1] == B[j - 1])//判断A的第i个字符和B的第j个字符是否相同dp[i][j] = dp[i -1][j - 1] + 1;elsedp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);}return dp[n][m];//最终的返回结果就是dp[n][m]}};该算法的时间复杂度为O(n*m)，空间复杂度为O(n*m)。
全国计算机等级考试二级Python真题及解析（5）一、选择题1. 关于二叉树的遍历，以下选项中描述错误的是A二叉树的遍历可以分为三种：前序遍历、中序遍历、后序遍历B前序遍历是先遍历左子树，然后访问根结点，最后遍历右子树C后序遍历二叉树的过程是一个递归的过程D二叉树的遍历是指不重复地访问二叉树中的所有结点正确答案： B2. 关于二叉树的描述，以下选项中错误的是A二叉树具有两个特点：非空二叉树只有一个根结点；每一个结点最多有两棵子树，且分别称为该结点的左子树与右子树B在任意一棵二叉树中，度为0的结点（叶子结点）比度为2的结点多一个C深度为m的二叉树最多有2的m次幂个结点D二叉树是一种非线性结构正确答案： C3. 关于查找技术的描述，以下选项中错误的是A如果采用链式存储结构的有序线性表，只能用顺序查找B二分查找只适用于顺序存储的有序表C顺序查找的效率很高D查找是指在一个给定的数据结构中查找某个特定的元素正确答案： C4. 关于排序技术的描述，以下选项中错误的是A选择排序法在最坏的情况下需要比较n(n–1)/2次B快速排序法比冒泡排序法的速度快C冒泡排序法是通过相邻数据元素的交换逐步将线性表变成有序D简单插入排序在最坏的情况下需要比较n的1.5幂次正确答案： D5. 关于面向对象的程序设计，以下选项中描述错误的是A面向对象方法可重用性好B Python 3.x 解释器内部采用完全面向对象的方式实现C用面向对象方法开发的软件不容易理解D面向对象方法与人类习惯的思维方法一致正确答案： C6. 在软件生命周期中，能准确地确定软件系统必须做什么和必须具备哪些功能的阶段是A需求设计B详细设计C可行性分析D概要设计正确答案： A7. 以下选项中，用于检测软件产品是否符合需求定义的是A集成测试B验证测试C验收测试D确认测试正确答案： C8. 在PFD图中用箭头表示A数据流B调用关系C组成关系D控制流正确答案： D9. 关于软件调试方法，以下选项中描述错误的是A软件调试可以分为静态调试和动态调试B软件调试的主要方法有强行排错法、回溯法、原因排除法等C软件调试的目的是发现错误D软件调试的关键在于推断程序内部的错误位置及原因正确答案： C10. 关于数据库设计，以下选项中描述错误的是A数据库设计可以采用生命周期法B数据库设计是数据库应用的核心C数据库设计的四个阶段按顺序为概念设计、需求分析、逻辑设计、物理设计D数据库设计的基本任务是根据用户对象的信息需求、处理需求和数据库的支持环境设计出数据模式正确答案： C11. 以下选项中值为False的是A 'abc' <'abcd'B ' ' <'a'C 'Hello' >'hello'D 'abcd' <'ad'正确答案： C12. Python语言中用来定义函数的关键字是A returnB defC functionD define正确答案： B13. 以下选项中，对文件的描述错误的是A文件中可以包含任何数据内容B文本文件和二进制文件都是文件C文本文件不能用二进制文件方式读入D文件是一个存储在辅助存储器上的数据序列正确答案： C14. ls = [3.5, "Python", [10, "LIST"], 3.6]，ls[2][ –1][1]的运行结果是A IB PC YD L正确答案： A15. 以下用于绘制弧形的函数是A turtle.seth()B turtle.right()C turtle.circle()D turtle.fd()正确答案： C16. 对于turtle绘图中颜色值的表示，以下选项中错误的是A (190, 190, 190)B BEBEBEC #BEBEBED “grey”正确答案： B17. 以下选项中不属于组合数据类型的是A变体类型B字典类型C映射类型D序列类型正确答案： A18. 关于random库，以下选项中描述错误的是A设定相同种子，每次调用随机函数生成的随机数相同B通过from random import *可以引入random随机库C通过import random可以引入random随机库D生成随机数之前必须要指定随机数种子正确答案： D19. 关于函数的可变参数，可变参数*args传入函数时存储的类型是A listB setC dictD tuple正确答案： D20. 关于局部变量和全局变量，以下选项中描述错误的是A局部变量和全局变量是不同的变量，但可以使用global保留字在函数内部使用全局变量B局部变量是函数内部的占位符，与全局变量可能重名但不同C函数运算结束后，局部变量不会被释放D局部变量为组合数据类型且未创建，等同于全局变量正确答案： C21.下面代码的输出结果是ls = ["F","f"]def fun(a):ls.append(a)returnfun("C")print(ls)A ['F', 'f']B ['C']C 出错D ['F', 'f', 'C']正确答案： D22. 关于函数作用的描述，以下选项中错误的是A复用代码B增强代码的可读性C降低编程复杂度D提高代码执行速度正确答案： D23. 假设函数中不包括global保留字，对于改变参数值的方法，以下选项中错误的是A参数是int类型时，不改变原参数的值B参数是组合类型（可变对象）时，改变原参数的值C参数的值是否改变与函数中对变量的操作有关，与参数类型无关D参数是list类型时，改变原参数的值正确答案： C24. 关于形参和实参的描述，以下选项中正确的是A参数列表中给出要传入函数内部的参数，这类参数称为形式参数，简称形参B函数调用时，实参默认采用按照位置顺序的方式传递给函数，Python也提供了按照形参名称输入实参的方式C程序在调用时，将形参复制给函数的实参D函数定义中参数列表里面的参数是实际参数，简称实参正确答案： B25. 以下选项中，正确地描述了浮点数0.0和整数0相同性的是A它们使用相同的计算机指令处理方法B它们具有相同的数据类型C它们具有相同的值D它们使用相同的硬件执行单元正确答案： C26. 关于random.uniform(a,b)的作用描述，以下选项中正确的是A生成一个[a, b]之间的随机小数B生成一个均值为a，方差为b的正态分布C生成一个(a, b)之间的随机数D生成一个[a, b]之间的随机整数正确答案： A27. 关于Python语句P = –P，以下选项中描述正确的是A P和P的负数相等B P和P的绝对值相等C给P赋值为它的负数D .P的值为0正确答案： C28. 以下选项中，用于文本处理方向的第三方库是A pdfminerB TVTKC matplotlibD mayavi正确答案： A29. 以下选项中，用于机器学习方向的第三方库是A jiebaB SnowNLPC losoD TensorFlow正确答案： D30. 以下选项中，用于Web开发方向的第三方库是A Panda3DB cocos2dC DjangoD Pygame正确答案： C31.下面代码的输出结果是x = 0x0101print(x)A 101B 257C 65D 5正确答案： B32.下面代码的输出结果是sum = 1.0for num in range(1,4):sum+=numprint(sum)A 6B 7.0C 1.0D 7正确答案： B33. 下面代码的输出结果是a = 4.2e–1b = 1.3e2print(a+b)A 130.042B 5.5e31C 130.42D 5.5e3正确答案： C34.下面代码的输出结果是name = "Python语言程序设计"print(name[2: –2])A thon语言程序B thon语言程序设C ython语言程序D ython语言程序设正确答案： A35. 下面代码的输出结果是weekstr = "星期一星期二星期三星期四星期五星期六星期日" weekid = 3print(weekstr[weekid*3: weekid*3+3])A 星期二B星期三C星期四D星期一正确答案： C36.下面代码的输出结果是a = [5,1,3,4]print(sorted(a,reverse = True))A [5, 1, 3, 4]B [5, 4, 3, 1]C [4, 3, 1, 5]D [1, 3, 4, 5]正确答案： B37.下面代码的输出结果是for s in "abc":for i in range(3):print (s,end="")if s=="c":breakA aaabcccB aaabbbcC abbbcccD aaabbbccc正确答案： B38.下面代码的输出结果是for i in range(10):if i%2==0: continueelse:print(i, end=",")A 2,4,6,8,B 0,2,4,6,8,C 0,2,4,6,8,10,D 1,3,5,7,9,正确答案： D39. 下面代码的输出结果是ls = list(range(1,4))print(ls)A{0,1,2,3}B[1,2,3]C{1,2,3}D[0,1,2,3]正确答案： B40.下面代码的输出结果是def change(a,b):a = 10b += aa = 4b = 5change(a,b)print(a,b)A 10 5B 4 15C 10 15D 4 5正确答案： D二、操作题1.编写程序，从键盘上获得用户连续输入且用逗号分隔的若干个数字（不必以逗号结尾），计算所有输入数字的和并输出，给出代码提示如下。
【字符串】1、输入一个字符串，打印出该字符串中字符的所有排列。
例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
2、有一个由大小写组成的字符串，现在需要对他进行修改，将其中的所有小写字母排在大写字母的前面（大写或小写字母之间不要求保持原来次序），如有可能尽量选择时间和空间效率高的算法。
c语言函数原型void proc（char *str），也可以采用你自己熟悉的语言。
3、编写反转字符串的程序，要求优化速度、优化空间。
4、用C语言实现函数void * memmove(void *dest, const void *src, size_t n)。
memmove函数的功能是拷贝src所指的内存内容前n个字节到dest所指的地址上。
分析：由于可以把任何类型的指针赋给void类型的指针，这个函数主要是实现各种数据类型的拷贝。
5、编程找出两个字符串中最大公共子字符串,如"abccade", "dgcadde"的最大子串为"cad"。
6、输入一个字符串，输出该字符串中对称的子字符串的最大长度。
比如输入字符串"google"，由于该字符串里最长的对称子字符串是"goog"，因此输出4。
7、字符串原地压缩。
题目描述：“eeeeeaaaff" 压缩为"e5a3f2"，请编程实现。
8、请以回溯与不回溯算法实现字符串匹配。
9、输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。
句子中单词以空格符隔开。
为简单起见，标点符号和普通字母一样处理。
例如：输入"I am a student."，则输出"student. a am I"。
10、在一个字符串中找到第一个只出现一次的字符。
如输入abaccdeff，则输出b。
一、分治算法在计算机科学中，分治法是一种很重要的算法。
字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)……任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。
问题的规模越小，越容易直接求解，解题所需的计算时间也越少。
例如，对于n个元素的排序问题，当n=1时，不需任何计算。
n=2时，只要作一次比较即可排好序。
n=3时只要作3次比较即可，…。
而当n较大时，问题就不那么容易处理了。
要想直接解决一个规模较大的问题，有时是相当困难的。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
这种算法设计策略叫做分治法。
如果原问题可分割成k个子问题，1<k≤n ，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。
由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。
在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。
这自然导致递归过程的产生。
分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。
分治法所能解决的问题一般具有以下几个特征：1) 该问题的规模缩小到一定的程度就可以容易地解决2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解；4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
