公共基础重点内容.doc

第一章 数据结构 1.循环队列中的元素个数算法（前提条件是头指针指向队头的前一个元素） 当队尾指针大于队头指针时，队列中元素个数为队尾指针-队头指针 例：队头指针为5, 队尾指针为40,则队列中的元素个数为35==》40-5 当队尾指针小于队头指针时，队列中元素个数为用总容量-队头指针+队尾指针 例：总容量为50，队头指针为45, 队尾指针为10，则队列中的元素个数为15==》50-45+10 2、入栈和出栈 例：入栈顺序为A B C D （在进栈的同时可以出栈）那么出栈的序例可以为 (1)DCBA (2)ABCD (3)BCDA (4)CDBA ……… 不可能出现的为 1.ADBC 2 BDAC …….. 3、完全二叉树的叶子结点算法，例一个完全二叉树共有700个结点，则有多少个叶子结点 log2N+1向上取整 =10;易求出总层数和末层叶子数。总层数k= 且前9层总结点数为29-1=511 (完全二叉树的前k-1层肯定是满的) 所以末层叶子数为700-511=189个。 请注意叶子结点总数≠末层叶子数！ 还应当加上第k-1层（靠右边）的0度结点个数。 )，上层（k=9)右边的0度结点数还有2(9-1)-95=161个。末层的189个叶子只占据了上层的95个结点（）所以，全部叶子数＝189(末层)＋161(k-1层)=350个、 程序设计方法和技术的发展经过了结构化程序设计和面向对象设计两个阶段。 　　2、 当今程序设计的风格是“清晰第一，效率第二”。 　　3、 程序可以没有输入，但是一定要有输出。 　　4、 结构化程序设计遵循：自顶向下，逐步求精，模块化，限制使用goto语句（常考）。 　　5、 面向对象的基本特点：标志唯一性，分类性，多态性，封装性，模块独立性。尤其重要的是多态性和封装性。没有类比性。 　　6、 多态性：统一操作可以是不同对象的行为。同样的消息被不同的对象接收时可导致不同的动作的现象。 　　7、 封装性：从外面看不到对象的内部，只能看到对象的外部特性。 　　8、 类：是具有共同属性、共同方法的对象的集合。描述了属于该对象类型的所有对象的性质，而一个对象则是对应类的一个实例。（常考） 　　9、 消息：是指对象间的相互合作的协作机制，是一个对象与另一个对象之间的传递的消息。 　　10、 继承：是指使用已有的类定义作为基础建立新类的定义技术。继承分为单继承和多继承。单继承只有一个父亲，多继承可以有多个父亲。 　　11、 面向对象中，类的实例叫做对象。 　　12、 源程序文档化要求程序应该加上注释。注释一般为序言性注释和功能性注释。 13、 面向对象方法和技术是以对象为核心。1、 软件工程的核心思想是把软件当作一个工程产品来处理。 　2、软件周期：软件产品从提出、实现、使用维护到停止使用退役的过程的三个阶段以及每个阶段的任务：?? 定义阶段：（1）可行性研究与计划制定；（2）需求分析开发（3）软件设计；（4）软件实现；（5）软件测试；运行和维护（6）运行和维护?? 　　3、 软件开发方法包括分析方法，设计方法，程序设计方法。 　　4、 结构化方法包括结构化分析方法，结构化设计方法，结构化编程方法。 　　5、软件工程的主要思想是：强调在软件开发过程中需要应用工程化的原则 　　6、 结构化分析常用的工具中最重要的工具是数据流图）。○表示加工，→表示数据流，—数据源，□表示源。 　　7、 软件规格说明书（SRS）是需求分析阶段的最后结果，是软件开发文档重要的文档之一。 　　8、 软件设计要求低耦合性和高内聚性是考试的重点,要知道什么是耦合,内聚。 　　9、 软件测试和程序调试的区别。软件测试的过程涵盖了整个软件生命周期。目的是为了发现错误而执行程序的过程。 　　10、 从是否要执行被测试软件的角度，软件测试分为静态测试和动态测试。 　　11、 从功能上划分，软件测试分为白盒测试和黑盒测试。 　　12、 白盒测试是检查内部成分，方法有：逻辑覆盖测试方法，基本路径测试。 　　13、 黑盒测试是对软件已经实现的功能是否满足需求进行测试和验证。方法有：等价类划分法，边界值划分法，错误推测法。 　　14、 软件测试的四个步骤。自己默写一遍。 　　15、 程序调试的任务：诊断和改正程序中错误，它和软件测试不同，调试主要在开发阶段。 　　16、 软件调试方法：强制排错法，回朔法，原因排除法。 　　17、 软件维护不属于软件生命周期开发阶段的任务。 　　18、 软件进行了程序调试后还要进行测试。 　　19、为每一个模块确定实现算法和局部数据结构的是详细设计阶段的任务。 　　20、 软件设计中，不属于过程设计工具的是：DFD图。 　　21、 结构化分析常见的工具：DFD图，