国家计算机二级公共基础知识点部分.docx

程序设计基础 1.程序设计风格 好的程序设计风格有利于提高程序的正确性、可读性、可维护性和可用性。要是程序有良好的风格概括起来可以分为4部分：源程序文档化、数据说明、语句结构、输入输出方法。 用户所定义的标示符必须以字母或下划线开头。大、小写字母代表不同标识。 2.结构化程序设计 （1）结构化程序设计的基本特征： 程序有3种基本结构组成：顺序结构、选择结构、循环结构 整个程序采用模块化结构。模块划分的原则：模块内具有高内聚度、模块间具有低耦合度。 有限的使用goto语句，只限定在一个结构的内部跳转，不允许从一个结构跳到另一结构。 程序设计时采用“自顶向下、逐步求精”的实施方法。 3种基本结构组成的算法只能完成符合结构化的任务 （3）结构化程序设计的方法：逐步求精和模块化程序设计方法。 结构化设计的总体思想是采用模块化结构，自上而下，逐步求精。 3. 面向对象程序设计 基本概念 对象：系统中运行的实体，是有特殊属性（数据）和方法的实体 类：由属性和方法构成。 一组具有相同的数据结构和相同的行为特征的对象的集合称为类 在面对对象的方法中，类的实例称为对象 面向对象程序设计特征的是：继承性、多态性、封装性 在面向对象的方法中，实现信息隐蔽是依靠对象的封装 任何对象都必须有继承性（错） 例题精选: 1. 在面对对象的方法中，一个对象请求另一个对象为其服务的方式是通过发送：信息 2. 面对对象的设计方法与传统的面向过程的方法有本质的区别,它的基本原理是:使用现实世界的概念抽象的思考问题从而自然地解决问题. 3. 结构化方法中,软件功能分解属于软件开发阶段中的总体设计 4. 结构化程序设计主要强调的是:程序的易读性 5. 面向对象的设计程序主要考虑的是:提高软件的可重用性 6. 类 通过接口与外界发生关系.数据结构与算法 算法的基本概念 1. 算法：是对问题处理方案的正确而完整的描述，是求解问题的方法，是指令的有效序列。 2. 具有5个特性： （1） 有穷性（在有穷步后完成）算法程序的运行时间是有限的 （2） 确定性（每一步都有确定的含义） （3） 可行性 （4） 输入（一个算法有零个或多个输入） （5） 输出（一个算法有一个或多个输出） 3. 算法的复杂度 包括：时间复杂度和空间复杂度。 二者没有必然的联系。 时间复杂度：执行算法所需要的计算工作量或基本运算次数。 空间复杂度：算法所需要的空间的度量。 数据结构的定义 1. 数据结构包括数据的逻辑结构、数据的存储结构、数据的操作 数据的逻辑结构：数据的外部结构，指各数据元素之间的逻辑关系，反映人们对数据含义的解释。 包括：线性结构（线性表、栈、队列）和非线性结构（树和图） 数据的存储结构：数据的物理结构，指数据的逻辑结构在计算机中的表示。 一个逻辑结构可以有多种存储结构。 线性表：线性表中元素的个数n（n=0）定义为线性表的长度。 顺序存储是线性表的一种最常用的存储方式。 线性表的顺序存储结构和线性表的链式存储结构分别是随机存取的存储结构和顺序存取的存储结构。 1.栈：是限定在表尾进行插入和删除操作的线性表。 具有记忆功能 只能顺序存储（错） 允许插入和删除的一端叫栈顶。另一端叫栈底。 后进先出的线性表 2队列：是限定在一端插入而在另一端删除，插入端叫队尾，删除端叫对头。 先进先出的线性表 3栈和队列的顺序存储结构 循环队列属于线性表存储结构中顺序存储结构和链式存储结构的前者。 树 1.定义:树的结点、度（结点的度）、叶子（终端结点）、数的度、深度、有序树和无序数 2.二叉树：结点至多有两棵子树，并且二叉树的子树有之分，次序不能颠倒。 性质：在二叉树的第i层上至多有2i-1个结点 深度为k的二叉树至多有2k-1个结点。 对任一个二叉树T，如果其叶子（终端结点数）为n，度为二的结点数为m,则n=m +1. 具有n个结点的完全二叉树的深度为k+1，其中k是2n的整数部分。 2. 二叉树的遍历 先序遍历（根左右） 中序遍历（左根右） 后序遍历（左右根） 查找算法 （1）顺序查找 顺序查找的平均查找长度为（n+1）2，最坏的情况下比较的次数为n (2) 二分查找 限定于顺序存储的有序线性表 排序算法 （1）插入类排序 直接插入排序 折半插入排序 希尔排序 （2）交换类排序 冒泡排序 最坏情况下的比较次数n(n-1)2 快速排序 最坏情况下的比较次数n(n-1)2 (3)选择类排序 例题精选: 1. 设一棵完全二叉树共有699个结点,则在该二叉树中的叶子结点数为:350 2. 已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列为：c e d b a 3. 要求内存量最大的是：归并排序 4. 在数据结构中，与所使用的计算机无关的是数据的是：逻辑结构 5. 栈底至栈顶依次存放元素A.B.C.D,在第五个元素E入栈前，栈中元素可以出栈，则出栈序列可能是：DCBEA 6. 已知数据表A 中每个元素距其最终位置不远，为节省时间，应采取的算法是：直接插入排序 7. 用链式表示线性表的优点是：便于插入和删除操作。软件工程基础 1.软件工程的基本概念 (1)定义:软件是程序、数据与相关文档的集合。软件包括系统软件和应用软件 (2)软件工程的基本思想是软件开发中，应用工程化原则进行软件开发，并将这个思想贯穿在软件开发的整个过程中。 软件工程的3要素：方法、工具和过程 (3)软件的生命周期：从软件定义、开发、使用、维护到报废为止的整个过程。 分三阶段：设计阶段、开发阶段、维护阶段 包括：问题定义、可行性分析、需求分析、总体设计、详细设计、编码、测试和维护 问题定义：确定开发的任务 可行性分析：确定问题的可行性 需求分析：对用户要求进行分析，明确目标系统要做什么 总体设计：把软件功能转化为所需要的体系结构，即如何解决问题。 详细设计：怎样具体的解决问题 2.结构化分析方法 （1）结构化分析（SA）是面向数据流进行需求分析的方法 SA方法的基本思想正是运用了分解和抽象两个基本手段，采用：自顶向下，逐步分解的分析思路。 （2）数据流图 基本图形符号： 在结构化方法中,用数据流程图(DFD)作为描述工具的软件开发阶段是:需求分析 (3)数据字典 在结构化分析的数据流图中,利用数据字典对其中的图形元素进行确切解释. 3.软件设计 （1）概要设计（总体设计） 包括两个主要阶段：系统设计（确定具体的实现方案）和结构设计（确定每个系统的模块组成及模块间的关系） 模块之间联系越紧密,其耦合性就越强,模块的独立性就越差; 一个模块内个要素联系越紧密，则它的内聚性就越高。 模块划分原则：高内聚低耦合 （2）详细设计 结构化程序设计的要点：采用自顶向下、逐步求精的程序设计方法，一个程序只有一个入口和一个出口。 详细设计的常用工具：程序流程图、盒图、PAD和PDL （3）软件测试目的 软件测试的目的是尽可能多的发现程序中的错误。 软件测试方法：静态测试和动态测试（黑盒测试法和白盒测试法） 黑盒测试包括：等价分析法、边值分析法、因果图法和错误推测法 白盒测试法测试的原则之一就是保证所测模块中的每一个独立的路径至少执行一次。 （4）程序调试 分为静态调试和动态调试 调试的目的:改正错误 经调试后还必须进行再测试 （5）软件维护 软件维护就是在软件已经交付使用以后，为改正错误或满足新的需求而修改软件的过程。 例题精选： 1 分析的结果是产生需求规格说明书。 2 软件详细设计的主要任务是确定每一个模块的算法和使用的数据结构。 3 进行单元测试时，常用的方法时采用 白盒测试，辅以黑盒测试。 4 软件工程的出现是由于软件危机的出现，人们提出了软件工程学的原理设计软件。 5 数据字典是各类数据描述的集合，通常包括4个部分：数据项、数据流、数据存储和数据加工。数据库设计基础 1. 数据库 （1） 数据库设计的根本目的是：要解决数据共享的问题。 （2） 数据库的特点： 数据按一定的数据模型组织和存储。 冗余度较小 数据的独立性较高。数据独立性：数据的组织结构和存储方法与应用程序互不依赖、彼此独立。 易扩展 可为多种用户共享 2. 数据库管理系统（DBMS） 位于用户与操作系统之间的完成数据管理的系统软件。 3. 数据库系统 由数据库、数据库管理系统、应用系统、数据库管理员和用户组成。 最核心的部分是数据库管理系统。 4. 数据模型 （1） 实体联系模型及E-R图 3部分：实体、联系和属性 实体集间的联系：一对一联系、一对多联系和多对多联系 （2） 层次、网状、关系模型 层次模型：有且只有一个结点无双亲，其他结点只有一个双亲。 用树形结构来表示各实体与实体之间的联系。 在关系数据库中，把数据表示成二维表，每个二维表称为关系。一个关系对应一张二维表。 关系的属性名称为关系模式。 5. 关系运算 （1）并 （2）差 （3）交 （4）笛卡尔积（） 6.专门关系运算：选择、连接和投影 （1）从关系中找到满足条件的所有元组称为选择 （2）从关系中挑选若干属性组成新的关系称为投影 7.数据库设计步骤： （1）需求分析阶段 （2）概念设计阶段 （3）逻辑结构设计阶段 将E-R图转化数据模型 （4）数据库物理设计阶段 数据库内模式，给出数据库物理存储结构和物理存取方法。例题精选： 1. 数据库管理系统的主要功能是：定义数据库 2. 关系表中每一横行称为一个元组，每一列称为属性。 3. 设计数据库的存储结构属于物理设计.第9章 模板 9.1 函数模板 1函数模板的概念、定义与应用 函数模板是一系列相关函数的模型或样板，这些函数的源代码形式相同，只是所针对的数据类型不同。对于函数模板，数据类型本身成了它的参数，因而是一种参数化类型的函数。声明一个函数模板的格式是： template模板形参表声明函数声明 其中的模板形参表声明是由一个或多个模板形参组成（如果是多个，需要用逗号隔开）。每个模板形参具有下面几种形式： （1）typename参数名 （2）class参数名 （3）类型修饰参数名 这里的参数名可以是任意的标识符。在这三种形式中，前两种是等价的：在声明模板参数时，关键字typename与class可以互换。用typename或class声明的参数称为虚拟类型参数；而用类型修饰声明的参数则挑为常规参数，在形式上与普通的函数参数声明相同。格式中的函数声明与一般函数的声明类似，只是某些类型修饰符被虚拟类型参数所替代。 2模板实参的省略 在调用一个模板函数时，编译系统需要足够的信息来判别每个虚拟类型参数所对应的实际类型，可以从两个不同的渠道获得这样的信息：从模板实参表（用和括起来的参数表）或从模板函数实参表（用（和）括起来的参数表），模板实参的信息优先于函数实参的信息。如果从后者获得的信息已经能够判定其中部分或全部虚拟类型参数所对应的实际参数，而且它们又正好是参数表中最后的若干参数，则模板实参表中的那几个参数可以省略。如果模板实参表中的实参都被省略了，则连空表也可以不要。因此，若x和y都是unsigned型，则addTounsigned（x，y，9）、addT （x、y、9）和addTo(x，y，9)三者是等价的。反之，对于某个模板实参，如果从模板函数的实参表中无法获得同样的信息，就不能省略；或者虽然能够获得同样的信息，但在它后面还有其他不能省略的实参，则其自身还是不能省略。 下面列举几种模板实参不能省略的情况。 （1）从模板函数实参表获得的信息矛盾。 （2）需要获得特定类型的返回值，而不管参数的类型如何。 （3）虚拟类型参数没有出现在模板函数的形参表中。 （4）函数模板含有常规形参。 3函数模板的定制 对不同的数据类型在处理形式上的统一性是建立模板的基础。但是，这种统一性是相对的，个别数据类型有可能比较特殊，在处理形式上与大多数数据类型不一致。针对这样的特殊情况，可以通过重载模板函数进行定制。这样把重载的模板称为补充模板，相应地，原模板则称为主模板。 9.2 类模板 1类模板的概念、定义与应用 类模板就是一系列相关类的模型或样板，这些类的成员组成相同，成员函数的源代码形式相同，所不同的只是所针对的类型（成员的类型以及成员函数的参数和返回值的类型）。对于类模板，数据类型本身成了它的参数，因而是一种参数化类型的类，是类的生成器。类模板中声明的类称为模板类。 声明一个类模板的格式是： template模板形参表声明类声明 模板形参表声明是由一个或多个模板形参组成；与一般的类声明的不同之处在于，这里的类声明要用模板形参表声明中声明的虚拟类型参数来修饰它的某些成员，使模板类独立于任何具体的数据类型。 在模板外对成员函数的声明格式是： template模板形参表声明 返回类型类名模板形参表：函数名（函数形参表）函数体 其中模板形参表就是由模板形参表声明中声明的参数名组成的序列。应注意，类模板的成员函数都是模板函数，因此在模板外声明成员函数的格式与声明普通模板函数十分相似。 用类模板定义对象的格式是： 类名模板实参表 对象名； 或 类名模板实参表 对象名（构造函数实参表）； 在定义对象的过程中，编译系统会自动地根据需要生成相应的类定义，这种依据类模板生成类定义的过程称为类模板的实例化。类模板实例所生成的每一个类定义就是相应类模板的一个实例。 在用类模板定义对象时，由于没有像函数实参表这样的额外信息渠道，因此无法按函数模板的方式省略模板实参。但是，可以为类模板的参数设置默认值。具体地说，在定义类模板时，可以为模板形参表声明的最后若干个参数设置默认值；而这些有默认值的参数中，最后的若干个对应实参可以在定义对象时省略。 3类模板的派生与继承 一谈到继承总涉及到两个类：基类和派生类，它们中任何一个都有可能是模板类，或模板类的实例。下面列出常见的几种情况。 （1）普通类继承类模板的一个实例。 可以通过继承类模板的一个实例来声明一个类。 （2）模板类继承普通类。 在声明一个类模板时，应尽可能将类模板中与虚拟类型参数无关的成员剥离出来，构成一个普通类，作为类模板的基类。因此，类模板继承普通类的情况是十分常见的。 （3）模板类继承模板类。 可以通过继承一个模板类来声明一个类模板。 （4）模板类继承模板参数给出的基类。 模板的派生甚至可以继承一个未知的基类。也就是说，继承哪个基类由模板参数决定。 3类模板的定制 与函数模板类似，类模板有时也需要定制，以适应某些特殊情况。类模板的定制也是通过定义补充模板实现的，称为模板的特例化，每个补充模板就是主模板的一个特例。第10章 C+流 10.1 C+流的概念 1C+ +流的体系结构 要利用C+ +流，必须在程序中包含有关的头文件，以便获得相关流类的声明。为了使用新标准的流，相关头文件的文件名中不得有扩展名。与C+ +流有关的头文件有： iostream：要使用cin、cout的预定义流对象进行针对标准设备的I/O操作，须包含此文件。 fstream：要使用文件流对象进行针对磁盘文件的I/O，操作须包含此文件。 strstream：要使用字符串流对象进行针对内存字符串空间的I/O操作，须包含此文件。 iomanip：要使用setw、fixed等大多数操作符，须包含此文件。 注意，为了使用新标准的C+ +流，还必须在程序文件的开始部分插入下面这个名字空间声明： using namespace std； 2 预定义流对象 C+ +流有4 个预定义的流对象，它们的名称及与之联系的I/O设备如下： cin 标准输入 cout 标准输出 cerr 标准出错信息输出 clog 带缓冲的标准出错信息输出 3提取运算符和插入运算符 输入流类istream重载了运算符，用于数据输入，其原形具有 istream& operator（ istream&，类型修饰&）； 的形式。重载的的功能是从输入流中提取数据赋值给一个变量，因此称之为提取运算符（extractor）。当系统执行cinx操作时，将根据实参x的类型生成相应的提取运算符重载函数的实例并调用该函数，把x 引用传送给对应的形参，接着从键盘的输入 缓冲区中读入一个值并赋给x（因形参是x的引用）后，返回istream流，以便继续使用提取运算符为下一个变量输入数据。 输出流类ostream重载了运算符，用于数据输出，其原形具有 ostream& operator（ostream&，类型修饰）； 的形式。重载的的功能是把表达式的值插入到输出流中，因此称之为插入运算符（inserter）。当系统执行coutx操作时，首先根据x值的类型调用相应的插入运算符重载函数，把x 的值传送给对应的形参，接着执行函数体，把x 的值（亦即形参的值）输出到显示器屏幕上，在当前屏幕光标位置起显示出来，然后返回ostream流，以便继续使用插入运算符输出下一个表达式的值。 上面格式中的“类型修饰符”是指char、int、double、char*、bool等等C+ +中固有类型的修饰符。也就是说，只要输入输出的数据属于这些C+ +固有类型中的一种，就可以直接使用或完成输入输出任务。在完成输入输出任务后，和把第一参数（即流对象的引用）返回，因此这两个运算符可以连续使用，如cinabc；等。 4有格式输入输出和无格式输入输出 利用C+ +流既可进行有格式输入输出，也可进行无格式输入输出。 计算机所处理的数据都有内部存储格式和外部表现形式的区分，因此在输入输出过程中必须进行适当的转换，有格式输入输出就是完成这一任务的。有格式输入输出针对的是键盘、显示器、打印机等字符设备以及磁盘中的文本文件。对于有格式输入输出，无论输入输出的数据是什么数据类型，体现在外部设备上都是字符序列。 对于无格式输入输出，数据的内部存储存格式与外部存储格式完全相同，因此无格式输入输出只能针对磁盘文件（或磁带、光盘上的文件），而且这样的文件通常不能用一般的文本编辑器查看。进行无格式输入输出需调用流对象的专门的成员函数实现。 5操作符 C+ +流提供了提取运算符和插入运算符，使得输入输出的表达简洁、形象、直观，这最能体现C+ +流的风格。C+ +流还提供了很多输入、输出或控制输入输出的成员函数，须通过或加以调用，不能与运算符或配合使用，因而与C+ +流的整体风格很不协调。为此，C+ +提供了一系列可与运算符或配合使用的特殊函数，称为操作符（manipulator）。每个操作符都与一个具体的函数相联系，使得或可间接地通过它们调用与之联系的函数，完成相应的输入 、输出功能或输入输出控制功能。前面经常用到的endl、setw等就是操作符。有了操作符，C+ +流操作在风格上就更加统一，输入输出操作也显得更加流畅。 10.2 输入输出的格式控制 1默认的输入输出格式 在没有特地进行格式控制的情况下，输入输出采用默认格式。 （1）默认的输入格式 C+ +流所识别的输入数据的类型及其默认的输入格式包括： short、int、long（signed、unsigned）：与整型常量同 float、double、long double：与浮点数常量同 char（signed、unsigned）