程序员面试宝典1

程序员面试宝典参考书程序员面试宝典(第三版)欧立奇等编著电子工业出版社程序员求职成功路周扬荣编著机械工业出版社高质量程序设计指南林锐等编著电子工业出版社1、结构化程序设计思想2、编译器3、C语言4、编程规范5、操作系统6、内存管理7、优化8、测试9、求职之路2010年7月编程语言排行榜语言所占比例1Java18.72C18.53C++10.54PHP8.65C#5.76VisualBasic5.57Python4.28Perl3.19Objective-C2.510JavaScript2.4一、结构化程序设计思想EdsgerWybeDijkstra1930-20021965年，Dijkstra指出：“可以从高级语言中取消GOTO语句”著名计算机科学家沃思(NikiklausWirth)提出一个公式数据结构＋算法＝程序程序＝算法＋数据结构＋程序设计方法＋语言工具和环境算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。1966年Bohm等证明了，只用顺序、选择、循环三种基本的控制结构就能实现任何单入口单出口的没有“死循环”的程序。1968年Dijkstra再次建议从一切高级语言中取消GOTO语句，只使用三种基本控制结构编写程序。AB顺序BAexpTFIF_THEN_ELSEAexpTFDO_WHILE扩展的结构程序设计为了实际使用方便起见，常常还允许使用DO_UNTIL和DO＿CASE两种控制结构DO_CASECASE1DOCASEICASE2CASEn…DO_UNTILAexpTF修正的结构程序设计如果需在循环体中或选择语句的内部有出口时，可以使用LEAVE（BREAK）结构。WhileSdoBegin…LEAVE/BREAK…End;受限制的GOTO语句70年代初采用结构化程序设计取得成功的例子：1971，IBM，纽约时报信息库管理系统，8.3万行美国宇航局空间实验室飞行模拟系统，40万行1972年Mills提出“程序应该只有一个入口和一个出口”，从而补充了结构程序设计的规则。SP经典定义如果一个程序的代码块仅仅通过顺序、选择和循环这三种控制结构进行连接，并且每个代码块只有一个入口和一个出口，则称这个程序是结构化的。结构程序设计是一种尽可能少用GOTO语句的程序设计技术，它采用自顶向下、逐步细化的设计方法和单入口单出口的控制技术。结构化程序设计方法自顶向下逐步细化模块化设计结构化编码自顶向下逐步求精的程序设计技术自顶向下、逐步求精若想让计算机解题必须用清晰而无两义性的方式给它提供算法。要求：找出一个算法，它能提供所解问题的从输入到输出所需的映象。选择一种程序语言写出程序，用计算机能接受的方式表述算法。关键是如何找出算法。因为写出程序，只是表述算法，应该没有困难。编程过程问题解决一个复杂的过程.算法解决问题所使用的一系列合乎逻辑的、简洁的步骤.解决问题包含的步骤:分析问题，找出解决问题的模型。根据模型设计出适合计算机特点的处理方法即算法．选择适合的计算机语言进行编程，以实现算法。上机编辑、调试、运行所编制的程序．得到结果．对结果进行分析，整理出文字材料即文档。求解一个问题粗略的解决方案细化第一步子问题第二步子问题第n步子问题...前处理结束条件后处理进展一步前处理后处理条件处理1处理2处理n......条件条件条件前处理后处理递归条件递归顺序连接循环分支选择递归算法的特点有穷性：一个算法应包含有限个操作步骤。确定性：每个步骤应该是确定的。有0个或多个输入有1个或多个输出有效性：每个步骤都能有效执行。例1(I)例1：由键盘输入三个整数，输出其中最大的数；S1.输入a,b,c三个整数S2.求出三个数中的最大数S3.输出最大数如何求出最大数？现在还没有讨论例1(II)S2.求出三个数中的最大数算法一：S2.1如果ab,执行2.2，否则执行2.3S2.2如果ac，最大数为a，否则最大数为cS2.3如果bc，最大数为b，否则最大数为c例1(III)S2.求出三个数中的最大数算法二：（引入temp变量）S2.1如果ab,temp=a，否则temp=bS2.2如果tempc，max=temp，max=c例2：判断一个整数m是否为素数算法如下：S1：输入m的值。S2：判断m是否为素数。S3：输出m是否为素数。S4：算法结束。第2步分析：判断整数m（m2）是否为素数的方法是：如果m不能被i整除（i为2到m-1的所有整数），则m是素数。算法如下：S2.1：i赋初值为2：标记m是素数S2.2：判断m能否被i整除。若能，标记m不为素数，结束循环。S2.3：若m不为被i整除，给i的值加1。若im,则转到S3。例3(I)例3：编程找出1000以内的所有“完数”，并按照下面格式输出因子：6Itsfactorsare1,2,3S1:a=2S2:如果a1000,执行S3，否则转S7S3:求出a的所有因子S4:如果是完数，按照格式输出S5：a=a+1S6：转S2S7：算法结束例3(II)S3分析：判断整数a是否为完数的算法是：从1到a-1找出因子，看这些因子的和是否等于aS3.1:i=1,n=0(n记录找到的第几个因子)S3.2:判断ia，如果成立转3.3，否则结束a的分解，转到S4S3.3：如果i是a的因子,保存因子到k[n],n=n+1(因子个数加1)S3.4:i=i+1，转3.2例3(III)S4分析：判断是否为完数，将数a减去所有的因子，得数为0的既是完数S4.1i=0,s=aS4.2如果i=n，s=s-k[n];否则转S4.4S4.3i=i+1；转到S4.2S4.4如果s=0，按照格式输出a和所有的因子例3(IV)(S3-S4整合)S3.1:i=1,n=0(n记录找到的第几个因子)，s=aS3.2:判断ia，如果成立转3.3，否则结束a的分解，转到S4S3.3：如果i是a的因子,保存因子到k[n],n=n+1(因子个数加1),s=s-k[n]S3.4:i=i+1，转3.2例4：测定字母偶的出现频率测定小写字符串中相邻字母偶出现频率。例如，针对thecat对th、he、ca、at计数。设有说明：intconmat[26][26];字母偶he的出现次数存入下标变量conmat[‘h'-‘a’]['e'-’a’]首先把该问题分解成如下几步：S1初始化计数器数组conmat；S2统计每个字母偶的出现频率；S3输出统计结果。initial初始化statistical统计out输出求精上述PAD中的每一个步骤：S1:初始化数组conmat,显然应该一行一行的初始化；对于每行又应该一个元素一个元素的初始化。初始化第i行initial初始化for(i=0;i26;i++)结束deffor(j=0;j26;j++)conmat[i][j]=0S2:考虑统计部分：假设被统计的字符串是从终端输入的，则显然我们应该把该字符串全部读入，并在读入的过程中边读边统计。用下图表示。读(prevchar)statisticalwhile(!EOF)统计一次结束def读(thischar)再考虑S2具体统计算法，为统计字母偶的出现频率，显然在读入字符串的过程中应该始终保存两个字符prevchar、thischar，并且当该两个字符都是字母时，相应计数单元加1；最后在读入下一个字符之前还应该把保存的两个字符向前串。统计一次conmat[prevchar][thischar]++结束thischar,prevchar都是字母prevchar=thischar最后考虑输出部分,我们把结果输出成两个26×13的表，每个表元素是相应字母偶的出现次数：*abcde...mab...z*nopqr...zab...zoutone('a','m')输出a..m部分outone('n','z')输出n..z部分out输出结束def打印一个表（第一个表），显然应该先打印表头再打印下边各行打印表头打印表体outone结束beginch,endch打印表头可以求精成先输出一个“*”；再顺次输出各个字符。顺次输出各个字符是一个循环。打印表头打印表体outone结束beginch,endch输出('*')输出(\n)顺次输出各个字符for(c1=beginch;c1=endch;c1++)输出(c1)打印表体应该一行一行的打印，每行应该先打印行头，再打印本行各个元素；打印本行各个元素，应该一个元素一个元素的打印，是一个循环打印表体outone结束beginch,endch输出('*')输出(\n)for(c1=beginch;c1=endch;c1++)输出(c1)for(c1=‘a’;c1=‘z’;c1++)输出一行输出(c1)输出(\n)输出本行各个元素for(c2=beginch;c2=endch;c2++)输出conmat[c1][c2]例5：三个齿轮啮合问题设有三个齿轮互相衔接，求当三个齿轮的某两对齿互相衔接后到下一次这两对齿再互相衔接，每个齿轮最少各转多少圈。解:这是求最小公倍数的问题。每个齿轮需转圈数是三个齿轮齿数的最小公倍数除以自己的齿数。设三个齿轮的齿数分别为:na、nb、nc；啮合最小圈数分别为:ma、mb、mc；三齿轮齿数的最小公倍数为k3。计算步骤表示为：开始读入三齿轮齿数求三齿数的最小公倍数k3分别计算啮合的最小圈数输出结果结束读入三齿轮齿数和输出结果，分别只是一次调用读或写函数，不必求精。求精计算三齿数的最小公倍数k3。可以把该问题分解成先求两个齿数na与nb的最小公倍数k2，然后再求k2与第三个齿数nc的最小公倍数k3，k3即为na、nb、nc三个齿轮齿数的最小公倍数。设已经有求两个数的最小公倍数的函数intlowestcm(intx,inty)则该求精过程可表示成。求三齿数的最小公倍数k3=lowestcm(lowestcm(na,nb),nc)结束求精求两个数的最小公倍数的函lowestcm。x、y的最小公倍数是x、y的积除以x、y的最大公约数。设已经有求两个数的最大公约数的函数intgcd(intx,inty)则该求精过程可表示成：intlowestcm(intx,inty)returnx*y/gcd(x,y)结束def采用展转相除法求两个数的最大公约数，函数intgcd(intx,inty)定义如下函数gcd是一个递归函数，先采用分支求精过程、再采用递归求精过程，可以求精成下图intgcd(intx,inty)结束y≠0returngcd(y,x%y)returnx最后，分别计算啮合的最小圈数可以被求精成下图。开始ma=k3/namb=k3/nbmc=k3/nc结束例6：验证三角形外心定理三角形三条边的垂直平分线交于一点，该点是三角形外接圆的圆心。解：不失一般性，假设三角形的任意一条边都不平行于任意一个坐标轴。依据平面几何知识，该问题的验证步骤应该是：读入三点a,b,c的坐标(x1,y1)、(x2,y2)、(x3,y3)；检验三点是否构成一个三角形；若三点构成三角形，则验证外心定理。开始验证外心定理结束是三角形读入三点a,b,c坐标读入三点坐标只是一个读语句，不必求精，下边求精检验是否三角形和验证外心定理。检验三点是否构成三角形使用一个bool型函数isTriange，可以求精成：求两点p1,p2确定的直线方程L12；判断若p3在L12上，则isTriange为false，否则isTriange为true。求p1,p2两点直线方程L12：y=a*x+bisTriange结束w在L12上returnfalsereturntrue求两点间直线方程可以写一个函数line(x1,y1,x2,y2,*a,*b)并求精成下图。line*b=y1-a*x1结束*a=(y