程序员面试宝典1.ppt

程序员面试宝典 参考书 程序员面试宝典(第三版) 欧立奇 等编著 电子工业出版社 程序员求职成功路 周扬荣 编著 机械工业出版社 高质量程序设计指南 林锐 等编著 电子工业出版社 1、结构化程序设计思想 2、编译器 3、C语言 4、编程规范 5、操作系统 6、内存管理 7、优化 8、测试 9、求职之路 2010年7月编程语言排行榜 一、结构化程序设计思想 著名计算机科学家沃思(Nikiklaus Wirth)提出一个公式数据结构＋算法＝程序 程序＝算法＋数据结构＋程序设计方法＋语言工具和环境算法是灵魂，数据结构是加工对象，语言是工具，编程需要采用合适的方法。 算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。 1966年Bohm等证明了，只用顺序、选择、循环三种基本的控制结构就能实现任何单入口单出口的没有“死循环”的程序。 1968年Dijkstra再次建议从一切高级语言中取消GOTO语句，只使用三种基本控制结构编写程序。 扩展的结构程序设计 为了实际使用方便起见，常常还允许使用DO_UNTIL和DO＿CASE两种控制结构 修正的结构程序设计 如果需在循环体中或选择语句的内部有出口时，可以使用LEAVE（BREAK）结构。 70年代初采用结构化程序设计取得成功的例子： 1971，IBM，纽约时报信息库管理系统，8.3万行 美国宇航局空间实验室飞行模拟系统，40万行 1972年Mills提出“程序应该只有一个入口和一个出口”，从而补充了结构程序设计的规则。 SP经典定义 如果一个程序的代码块仅仅通过顺序、选择和循环这三种控制结构进行连接，并且每个代码块只有一个入口和一个出口，则称这个程序是结构化的。 结构程序设计是一种尽可能少用GOTO语句的程序设计技术，它采用自顶向下、逐步细化的设计方法和单入口单出口的控制技术。 结构化程序设计方法 自顶向下 逐步细化 模块化设计 结构化编码 自顶向下逐步求精的程序设计技术 自顶向下、逐步求精 若想让计算机解题必须用清晰而无两义性的方式给它提供算法。要求： 找出一个算法，它能提供所解问题的从输入到输出所需的映象。 选择一种程序语言写出程序，用计算机能接受的方式表述算法。 关键是如何找出算法。因为写出程序，只是表述算法，应该没有困难。 算法的特点 有穷性：一个算法应包含有限个操作步骤。 确定性：每个步骤应该是确定的。 有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以内的所有“完数”，并按照下面格式输出因子： 6 Its factors are 1,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.1 i=0,s=a S4.2 如果i=n，s=s-k[n];否则转S4.4 S4.3 i=i+1；转到S4.2 S4.4 如果s=0，按照格式输出a和所有的因子 例3(IV)(S3-S4整合) S3.1:i=1,n=0(