程序员面试宝典1

28十二月20231程序员面试宝典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-2002

1965年，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如果a>b,执行2.2，否则执行2.3S2.2如果a>c，最大数为a，否则最大数为cS2.3如果b>c，最大数为b，否则最大数为c例1(III)S2.求出三个数中的最大数算法二：（引入temp变量）S2.1如果a>b,temp=a，否则temp=bS2.2如果temp>c，max=temp，max=c例2：判断一个整数m是否为素数算法如下：S1：输入m的值。S2：判断m是否为素数。S3：输出m是否为素数。S4：算法结束。第2步分析：判断整数m（m>2）是否为素数的方法是：如果m不能被i整除（i为2到m-1的所有整数），则m是素数。算法如下：S2.1：i赋初值为2：标记m是素数S2.2：判断m能否被i整除。若能，标记m不为素数，结束循环。S2.3：若m不为被i整除，给i的值加1。若i<m,则转到S3。例3(I)例3：编程找出1000以内的所有“完数”，并按照下面格式输出因子：6Itsfactorsare1,2,3S1:a=2S2:如果a<1000,执行S3，否则转S7S3:求出a的所有因子S4:如果是完数，按照格式输出S5：a=a+1S6：转S2S7：算法结束例3(II)S3分析：判断整数a是否为完数的算法是：从1到a-1找出因子，看这些因子的和是否等于aS3.1:i=1,n=0(n记录找到的第几个因子)S3.2:判断i<a，如果成立转3.3，否则结束a的分解，转到S4S3.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=aS4.2如果i<=n，s=s-k[n];否则转S4.4S4.3i=i+1；转到S4.2S4.4如果s=0，按照格式输出a和所有的因子例3(IV)(S3-S4整合)S3.1:i=1,n=0(n记录找到的第几个因子)，s=aS3.2:判断i<a，如果成立转3.3，否则结束a的分解，转到S4S3.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;i<26;i++)结束deffor(j=0;j<26;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...z

outone('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=(y2-y1)/(x2-x1)x1,y1,x2,y2：两点坐标*a,*b：直线方程系数

验证外心定理可以如下进行：求每条边的垂直平分线；验证该三条直线是否交于一点；若交于一点，则验证该点到三角形各顶点距离是否相等否则错误命题。验证外心定理求每条边的垂直平分线方程结束三条直线交于一点印O.K该点到三角形各顶点距离相等印false求每条边的垂直平分线方程可以写一个求一条线段的垂直平分线方程的函数，然后分别三次调用该函数。

每条边的垂直平分线方程结束求边L12的垂直平分线：vline(ax,ay,bx,by,&a_a,&a_b)求边L23的垂直平分线：vline(bx,by,cx,cy,&b_a,&b_b)求边L13的垂直平分线：vline(cx,cy,ax,ay,&c_a,&c_b)求一条边的垂直平分线方程可以先调用前述函数line，求该边的直线方程;再求该边的中点,然后求过该中点的与该边垂直的直线方程，得下图vline直线方程:line(x1,y1,x2,y2,&ta,&tb)结束中点:x=(x1+x2)/2;y=(y1+y2)/2垂直平分线方程：*a=-1/ta;*b=y-(*ta)*xx1,y1,x2,y2：两点*a,*b：垂线方程验证该三条直线是否交于一点编成一个函数isOnePoint，可以先求两条直线的交点，然后再判断第三条直线是否过该点。三条直线交于一点结束求L12与L23交点:*x=(b1-b2)/(a1-a2);*y=a1*(*x)+b1returnfalsereturntruefabs(a3*(*x)+b3-y)<eps设有一个函数 distance(x1,y1,x2,y2)可以计算两点间距离，验证三条垂直平分线的交点到三角形各顶点距离是否相等，是一个布尔表达式。distance结束returnsqrt((x2-x1)2+(y2-y1)2)

x1,y1,x2,y2：两点坐标算法的描述1.自然语言描述:用自然语言给出解决问题的详细步骤.如前面的例子。2.流程图：用图框表示。3.N-S图4.PAD图4.伪代码：使用介于自然语言和计算机语言之间的文字、符号来描述算法。5.计算机语言：采用这种方法必须严格遵守所使用的语言的语法规则。程序流程图(I)传统流程图里常用的符号开始或结束框“处理框”--运算步骤输入或输出框判断框连接符：一个程序中两个部分之间的连接程序的流程线注释6.3.1程序流程图(III)程序流程图的特点优点直观描绘控制流程易学缺点不是逐步求精的工具随意转移控制不易表示数据结构盒图(N-S图)(I)出于要有一种不允许违背结构程序设计精神的图形工具的考虑，Nassi和Shneiderman提出了盒图，又称为N-S图。盒图(N-S图)(II)嵌套的表示盒图的特点控制结构作用域明确不能任意转移控制SP方式思考和解决问题的习惯易表示嵌套关系、模块的层次结构PAD(ProblemAnalysisDiagram)图(I)PAD图(II)PAD示例PAD图(II)对应于增量型循环结构

fori:=n1ton2stepn3do

在PAD中有相应的循环控制结构PAD图(III)PAD图的特点优点结构化程序结构清晰表现程序逻辑，易读、易懂、易记描绘数据结构支持自顶向下、逐步求精方法的使用PAD图高级程序设计语言缺点不适合于初学者，算法未考虑成熟时的设计过程设计语言(I)过程设计语言（PDL）也称为伪码，现在有许多种不同的过程设计语言在使用。它是用正文形式表示数据和处理过程的设计工具。PDL具有严格的关键字外部语法，内部语法灵活PDL-----关键字+自然语言(1)数据说明:格式:

TYPE

<变量名>

AS

<限定词1><限定词2>其功能是定义数据的类型和作用域

TYPEnumberASSTRING

LENGTH(12)过程设计语言(II)(2)程序块:PDL的