全国计算机二级C语言.ppt

1、知识点分布，第一章数据结构和算法第二章编程基础第三章软件工程基础第四章数据库设置修订基础，第一章数据结构和算法，1，算法是指解题方案的准确和完整描述。 换句话说，该算法是描述特定问题解决步骤。 算法不等于程序，不等于修正计算方法。 2 .算法的基本特点，1.1算法，可行性，确定性，贫穷性，有充分的信息，08年4月选题第5题算法的贫穷性和_A_ A )算法程序的运行时间有限b )算法程序处理的数据量有限(1)算法时间复杂性是执行该算法所需的校正操作量，并且能够以在执行该算法的过程中所需的基本计算的执行次数进行校正。 (2)算法空间复杂度是执行该算法所需的存储器空间。 06年9月选题第7题以下记载

2、正确的是： _D_ A )一个算法的空间复杂度大，其时间复杂度也必定大b )一个算法的空间复杂度大，其时间复杂度必定小c )一个算法的时间复杂度大，其空间复杂度上述三种说法都是错误的2 .数据结构主要是(1)研究和讨论数据集合中各数据元素之间固有的逻辑关系，即数据的逻辑结构。 (2)在处理对数数据时每个数据元素在校正器中的存储关系，即数据的存储结构。 数据的存储结构包括顺序、链接和索引。数据的逻辑结构反映了数据元素之间的逻辑关系，数据的存储结构(也称为数据的物理结构)是数据的逻辑结构被存储在校正机存储空间中的形式。 相同逻辑结构的数据可以采用不同的存储结构，但会影响数据处理效率。 1.2数据结

3、构的基本概念是，将逻辑上相邻的节点存储在物理上相邻的存储器单元中，用存储器单元的相邻关系来表现节点间的逻辑关系。 这样得到的内存表现称为顺序内存结构。 中的组合图层性质变更选项。 逻辑上相邻的节点也不需要物理上相邻。 节点之间的逻辑关系由附加的指针字段表示。 这样得到的内存表现称为链内存结构。 创建附加索引表，以识别节点的地址以及存储节点信息。07年4月选择问题第1题以下记述正确的是： _B_ A )算法的效率只关系到问题的规模，与数据的存储结构无关；b )算法的时间复杂性是运行算法所需的修正工作量；c )数据的逻辑结构和存储结构一一对应；d )算法的时间线性结构(非空数据结构)条件：1)有根

4、节点，而且只有一个；2 )每个节点最多有一个前因，最多有一个后果。典型的线性结构包括线性表、堆栈、队列、线性链表等。 (2)非线性结构：不满足线性结构条件的数据结构。常见的非线性结构有树、二叉树、图等。 1.2数据结构的基本概念，07年9月选题第6题以下的记述正确的是： _D_ A )数据的逻辑结构和存储结构必须一对一对应的b )修正算机存储空间是向量式的存储结构，因此数据的存储结构必须是线性结构c ) 编程语言中的数组通常是顺序存储结构，其中允许插入和删除的一方称为堆栈顶部，不允许插入和删除的一方称为堆栈顶部。 堆栈中最上面的元素始终是最后插入的元素，而最下面的元素始终是第一个插入的元素。即

5、，堆栈按照“先入先出”或者“后入先出”的原则来组织数据。 堆栈有记忆作用。 06年9月填补问题第4题先进后出的原则整理数据的数据构造是_堆栈_ _。 1.3堆栈和队列、2、队列及其基本运算队列是线性表，允许在一端(队列端)插入，而在另一端(队列端)删除。 末尾指针(Rear )指队列的末尾元素，前端指针(front )指第一个元素之前的位置(队列头)。 队列是“先进先出”或“后进先出”的线性表。 06年9月填海问题第五题数据结构分为线性结构和非线性结构，带链队列属于 07年4月选择问题第5题以下队列的记述正确的是_ A )队列属于非线性表b )队列是“先进先出”原则，数据c )队列是队列的最后

6、删除数据d )队列是“先进先出”原则，数据、1.3堆栈和队列、循环队列和其他08年4月填充问题如果设有第3题的循环对列的容量为50，标头指针front=5(指标头元素的前面的位置)，尾指针rear=29 (指队列元素)，则在该循环列中有_个元素。 07年9月填空题第三题线性表的记忆结构主要分为逐步记忆结构和连锁记忆结构。 队列是一个特殊的线性表，循环队列是队列的_链_存储结构。 1.3堆栈和队列，1、树的基本概念树是简单的非线性结构。 没有前件的节点只有一个，称为树的根节点，简称为树的根。 没有后项的节点称为叶节点。 在树结构中，将一个节点具有的子孙的个数称为该节点的度，将全部节点中最大的度称

7、为树的度。 树的最大层次称为树的深度。 06年9月填补问题第1题以下的软件系统构成图的幅度. 1.4树和二叉树，2，二叉树及其基本性质(1)二叉树是有用的非线性结构，它具有以下两个特征：1)非空二叉树只有一个根节点2 )每个节点最多有两个子树，分别是该节点的左子树和右子树：从二叉树的概念可知，二叉树的度可以是0 (叶节点)、1 (子树只有1个)或2 (子树有2个)。 (2)二叉树的基本性质1二叉树的第k层中有最多的节点。 性质2深度m的二叉树最多有一个节点。 性质3任意1根二叉树中，度数为0的节点(即叶节点)比总比度为2的节点多1个。 具有性质4n个节点的二叉树至少表示其深度在其中取的整数部分

8、。 1.4树和二叉树，07年4月选题第7题二叉树中若有n个度为2的节点，则该二叉树中的叶的节点数为A (A)n 1 B)n-1 C)2n D)n/2 07年9月选题第8题的一叉树中有70个叶的节点和80个度为1的节点该二叉树中的总分数为_ _ _ _ a ) 219 b ) 221 c ) 229 d ) 231，1.4树和二叉树，3，满二叉树和完全二叉树：除了最后一层，各层上的所有节点都有两个子节点。 完全二叉树：除了最后一层，每层上的节点数达到最大值的最后一层只缺少右边的几个节点。 08年4月填海问题第2题深度为5的二叉树有_16_个叶的结点。根据完全二叉树的定义，度1的节点个数为0或1。

9、1.4树和二叉树、4、二叉树的扫描二叉树的扫描是指访问二叉树中的所有节点时不重复。 二叉树的扫描可分为1.4树和二叉树，(1)前向扫描(DLR ) :如果二叉树为空，则结束门这3种。 否则：首先访问根节点，然后遍历左侧子树，最后遍历右侧子树，另外，在扫描左右子树时，还要访问根节点，然后扫描左侧子树，最后扫描右侧子树。(2)中顺序扫描(LDR ) :如果二叉树为空，则结束门。 否则：先遍历左侧子树，然后访问根节点，最后遍历右侧子树，或者遍历左右子树时，仍然遍历左侧子树，然后访问根节点，最后遍历右侧子树(3)后序扫描(LRD ) :如果二叉树为空，则结束门。 否则：首先扫描左侧的子树，然后扫描右侧

10、的子树，最后访问根节点，此外，扫描左侧、右侧的子树时，还扫描左侧的子树，然后扫描右侧的子树，最后访问根节点。 2007年4月选题的第6题是对以下二叉树进行上次扫描的结果为_ c _ _ a ) dybeafczxb ) ydebfzxcac ) abdyecfxzd ) abcdef XYZ，1.4树和二叉树，1.5检索技术检索。 2006年9月选题的第8题在长64的规则性表中进行顺序检索，最坏的情况下需要比较的次数是_A_。 A)63 B)64 C)6 D)7 1.6排序技术排序是指按照不是降序的值的排序顺序来排列无序的顺序，以及将无序的记录顺序调整为排序记录顺序的操作。 1 .交换等级排序

11、法(方法：鼓泡排序、快速排序)。 2 .插入类排序法(方法：简单插入排序、希尔排序)。 3 .选择类排序法(方法：简单地选择排序，堆积排序)。 总结：各种排序方法的比较：2008年4月选题第6题对长度为n的线性表进行排序，最坏的情况是，比较次数为n(n-1)/2的排序方法不是_D_ A )高速排序b )鼓泡，而是，第二章编程的基础，编程的星座主要应该重视(1)源程序的文件化。 符号名称的命名。 符号名反映了它所表示的实际，应该有一定的实际意义。 程序的评论。 分为序文注释和功能注释。 序言注释：位于程序开头，包括程序标题、程序功能说明、主要算法、接口说明、程序位置、开发简历、程序员、复审者、复

12、审日期及修改日期等。 功能性注释：嵌入在源程序主体中，用于描述后续语句和程序的主要功能。 视觉组织。 利用空间、空行、缩进等技巧，明确程序的层次。 (2)输入输出。 以验证输入数据的合法性的交互式输入输出方式进行输入时，在画面上使用提示明确提示输入的要求的同时，在数据输入中和输入结束时，在画面上提示状态信息。 2.1编程风格，06年9月选题第一题以下选项中不符合良好编程风格的是_D_ . a )源程序必须书面化b )数据说明的顺序必须规范避免滥用goto语句d )模块设置修订在高结合、高凝聚(高凝聚、低结合) 07年9月选择问题第4题以下选项中不符合良好的程序设置修订风格的是_A_ A 2.1

13、编程风格，1，结构化编程方法的主要原则是自上而下、逐步求精，以便在输入程序效率第一的效率第二) b )程序可读性好的c )程序所需的注释d )数据之前提示信息(1)自上而下。 在编程时，要先考虑整体，再考虑细节。首先考虑全球目标，然后考虑本地目标。 从一开始就不要过于追求很多细节，从最上层的总目标开始设定修订，慢慢将问题具体化。 (2)逐步求精。 对于复杂的问题，必须设定几个子目标，并逐步细分。 (3)模块化。 一个复杂的问题，一定是由几个简单的问题构成的。模块化是将程序应解决的总目标分解成分解目标，进而分解成具体的小目标，将各小目标称为1个模块。 修改模块设定需要高凝聚、低结合。 (限制go

14、to语句的使用。 08年4月选择问题第2题结构化程序设定订正的基本原则是： _ A )多态性b )自上而下c )模块化d )逐次求精2、结构化程序的基本构造：不包括顺序构造、选择构造、重复构造。 2.2结构化编程(面向过程的编程方法)、面向对象的方法的主要优点： (1)与人的习惯性想法一致；(2)稳定性好；(3)再利用性好；(4)大型软件产品的开发容易；(5)维护性好。面向对象的编程主要考虑提高软件的可重用性。 对象是属性和方法的包。一个对象由三部分组成：对象名称、属性和操作。 面向对象的基本特征：继承性、多态性、包装性。 (1)继承。 意味着可以直接获取现有特性和要素，而无需重复定义现有特性

15、和要素。类的继承性是一种在类之间共享属性和操作的机制，提高了软件的重用性。 (2)多态性。 意味着相同的操作可以是不同对象的行为。 (3)密封性。 从外部看只能看到对象的外部特性，即，只知道数据的可取值的范围和可以添加到该数据中的操作，不需要知道实现数据的具体构造和操作的算法。 对象的内部，即处理能力的执行和内部状态，对外看不见。 不能直接从外部使用对象的处理能力，也不能直接修改其内部状态，对象的内部状态只能自己变更。信息隐藏是通过对象的封装来实现的。 2.3面向对象的编程和软件重用是指在不同的软件开发过程中重用相同软件或相似软件的过程。 07年4月选择问题第4题以下选项中不属于面向对象编程特

16、征的是_C_ A )继承性b )多态性c )类比性d )封闭性07年9月选择问题第3题在面向对象方法中实现信息隐藏依赖于_ A，因此类对象的抽象化消息是在一个实例和另一个实例之间传递的信息。在面向对象的方法中，一个对象向另一个对象请求服务的方法是发送消息。 本章考试点刻度盘：本章是考试中出现约1个题目，所占分数约占2分，出题量少的章节。 本章的内容比较少，简单，只要把握基本的概念就可以简单地应对考试，所以在这一部分失分很遗憾。2.2结构化编程(面向过程的编程方法)、方便的第三章软件工程基础、1、软件相关概念纠正机软件是完整的集合，包括程序、数据和相关文档。 07年9月选题第一题软件为_D_ A )程序b )程序和文档c )算法和数据结构d )程序，数据和相关文档的完整集合2，软件危机和软件工程软件工程来自软件危机。 软件危机是指计算机软件开发和维护过程中面临的一系列重大问题。 软件工程的主要思想是将工程化原则应用到软件开发过程中，包括方法、工具和过程三个要素。 方法是完成软件工程项目的技术手段工具支持软件开发、管理、文档生成的过程支持软件开发各阶段的控制管理。 3.1软件工程的基本概念，3，软