程序的设计方法学考试简答资料.doc

第一章 1. 程序设计方法学产生的历史背景 答：软件危机。 2. 什么是程序设计方法学 答：简单地说，程序设计方法学是讲述程序的性质以及程序设计的理论和方法的一门学科。 3.程序设计方法学与结构程序设计的关系 答：在程序设计方法学中，结构程序占着十分重要的位置，可以说，程序设计方法学是在结构程序设计的基础上逐步发展和完善起来的。 4. D.Gries教授将已有的对结构程序设计的不同解释归纳为几种？ 答：主要有6种。 （图手工画） 5. 什么是结构程序设计？ 答：结构程序设计是一种进行程序设计的原则和方法，按照这种原则和方法设计出的程序的特点是结构清晰、容易阅读、容易修改、容易验证。按照结构程序设计的要求设计出的程序语言称为结构程序设计语言。 6. 结构程序设计的目标是什么？ 答：得到一个好结构程序 7. 结构化程序由哪些结构组成：P5 答：序列结构、选择结构、循环结构。 8. 什么是逐步求精程序设计方法 答：就是在编制一个程序时，首先考虑程序的整体结构而忽视一些细节问题，然后逐步的、一层一层地细化程序直至所选用的语言完全描述一个细节，即得到所期望的程序为止。 9. 逐步求精的优点是什么？ 答：摆脱了传统的程序设计方法的束缚，按照先全局后局部，先整体后细节，先抽象后具体的过程组织人们的思维活动，使得编写出的程序结构清晰、容易阅读、容易修改。同时，还可以结合逐步求精的过程进行程序正确性验证，即采取边设计、边验证的方法，以简化程序正确性的验证。 第二章： 1. 流程图程序 答：一个程序可以用流程图的形式表示出来，这种程序就称为流程图程序。 2. 正规程序 答：一个流程图程序如果满足一下两个条件就称为正规程序 （1）具有一个入口线和一个出口线； （2）对每一个结点，都有一条从入口线到出口线的通路结点。 3. 基本程序 答：一个正规程序如果不包含多于一个结点的正规子程序称为基本程序。 4.结构化程序 答：由基本程序的一个固定的基集合构造出的复合程序称为结构化程序。 5. 程序函数 答：已知一正规程序P，对于每一个初始的数据状态X，若程序是终止的，那么有确定的最终数据状态Y，如果每一个给定的X，值Y是唯一的，那么所有的有序对的集合｛（X，Y）｝定义了一个函数，我们称这个函数为程序P的程序函数，记为[P]. 6. 程序函数等价 答：如果程序P1和P2有相同的程序函数，称他们是等价的，简称是等价的。 7. 结构化定理：使用方式 答：任一正规程序都可以函数等价于一个由基集合｛序列，if-then-else，while-do｝产生的结构化程序。 第三章： 第四章： 1. 面向对象的程序设计方法是新型的结构化程序设计。20世纪80年代 2. 什么是应用框架 应用框架就是在某特定的应用领域中，程序之间的共同特征。框架就是整个或部分系统的可重用设计，一个框架是一个可复用的设计组件 3. 框架与一般类库的主要区别 答：反向调用 第五章： 1. 证明与测试的区别 答：测试：给程序一组或者几组初始值进行试算，然后将试算的结果与事先已知的结果进行比较，若两者相同，则认为程序是正确的，若两者不同，则认为是错误的。 证明：证明方法不仅可以证明程序的正确性，有些还可以证明非确定性程序及并行程序的正确性。 2. 部分正确性与完全正确性 答：程序正确性严格定义通常分为三种类型，及程序的部分正确性、终止性、和完全正确正确性。完全正确等价于改程序是部分正确的同时又是终止的，因此，为了证明一个程序的完全正确性，通常采用的方法是分别证明该程序的部分正确性和终止性。 3. 不变式断言法步骤 答：分三个步骤:建立断言，建立检验条件，证明检验条件。 4. 子目标断言法与不变式断言法的区别 答：两种方法对循环所建立的断言不同，两种方法进行归纳的方向不同 5. Hoare定义的赋值公理、推理规则 答：赋值公理。条件规则、while规则、并置规则、结论规则 6. Hoare推理过程的两种形式？答：组装、分解 7. 良序集 答：设（w，）是一个偏序集，如果不存在由w中的元素构成的无限递减序列，a0a1a2…则称（w，）是一个良序集 8. 良序集方法的步骤 答：1.选取一个点集去截断程序的各个循环部分，并且在每个断点i处建立一个中间断言Qi（x，y）。这样程序就被分解为若干条通路，同时规定每一条通路都不包有中间阶段点。 2.选取一个良序集（w，），并且在每一截断点i处定义一个终止表达式Ei（x，y） 3.证明所选取的断言是“良断言” 4.证明终止表达式是良函数 5.证明终止条件成立 9. 计数器方法 答：计数器方法是D.E.Knuth在1968年提出来的。它的基本思想是对程序中的每一个循环附加一个新的变量O，循环通路每执行一次，计数器加1同时，对每一个循环提供一个新的中间断言，他表示