第一部分公共基础部分知识归纳
数据结构与算法
算法---是一组严谨地定义运算顺序的规则
算法的基本要素---一是对数据对象的运算和操作，二是算法的控制结构
算法设计基本方法---列举法、归纳法、递推、递归、减半递推
算法的复杂度---包括时间复杂度和空间复杂度
时间复杂度---执行算法所需的计算工作量
空间复杂度---执行算法所需的内存空间
数据结构---相互有关联的数据元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。；父亲、儿子、女儿等都是数据元素。
前件---数据元素之间的关系，如父亲是儿子和女儿的前件
后件---如儿子是父亲的后件
结构---指数据元素之间的前后件关系
数据的逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关
数据的存储结构（物理结构）---数据的逻辑结构在计算机存储空间中的存放形式，数据元素在计算机存储空间的位置关系可能与逻辑关系不同。
根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分两类---线性结构与非线性结构
线性结构（线性表）---满足下列两个条件（1）有且只有一个根结点（2）每一个结点最多有一个前件和后件。则称该数据结构为线性结构，否则为非线性结构。
线性表是最简单、最常用的一种数据结构，其数据元素之间的相对位置是线性的，其存储方式为顺序存储的，如数组
栈---是限定在一端进行插入与删除的线性表，一端封闭，另一端开口，其操作原则是“先进后出”，栈的运算有入栈、退栈、读栈顶元素
队列---是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）的线性表，其操作规则是“先进先出”，其运算有入队和退队。
树---是一种简单的非线性结构，而且是层次结构，是倒立的大树，有根结点、父结点、子结点、叶子结点。根结点在第一层，一个结点所拥有的后件的个数称为该结点的度，所有结点中最大的度称为树的度，树的最大层次称为树的深度。
二叉树---（1）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树（左子树和右子树），其存储结构为链式。
二叉树性质---（1）K层上最多有2（K-1）个结点（2）深度为m的二叉树最多有2m-1个结点
（3）度为0的结点（叶子结点）比度为2的结点多一个（4）具有n个结点的二叉树，其深度至少为[Log2n]+1，其中[Log2n]表示对Log2n取整
满二叉树---除最后一层外，其余层的结点都有两个子结点
完全二叉树---除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的若干结点，叶子结点只可能在层次最大的两层上出现。满二叉树是完全二叉树，而完全二叉树不是满二叉树。完全二叉树有两个性质：（1）具有n个结点的完全二叉树的深度为[Log2n]+1（2）二叉树遍历---不重复地访问各个结点。分为前序遍历(DLR-根左右)、中序遍历(LDR-左根右)和后序遍历（LRD-左右根）
查找技术---顺序查找——对于长度为n的有序线性表，查找时需要比较n次
二分法查找——对于长度为n的有序线性表，查找时需要比较log2n次
排序技术---假设线性表的长度为n，则冒泡排序和简单插入排序的比较次数（时间复杂度）为n(n-1)/2;希尔排序的比较次数为O(n1.5);简单选择排序的比较次数为n(n-1)/2;堆排序的比较次数为O(nlog2n).
习题1
算法的时间复杂度是指（），算法的空间复杂度是指（）；
线性表、栈、队列、线性链表是（线性结构），树是（非线性结构）；数据的存储结构是指（）；
队列是（先进先出），栈是（先进后出）；
下列二叉树的遍历结果：前序遍历（ABDECF）、中序遍历（DBEAFC）、后续遍历（DEBFCA）
在深度为5的满二叉树中，叶子结点的个数为（16）；设树T的度为4，其中度为1，2，3，4的结点的个数分别为4，2，1，1。则T中的叶子结点的个数为（8）；对于长度为n的有序线性表，顺序查找次数为（n）,二分法查找次数为（log2n）；一棵完全二叉树共有700个结点，则在该二叉树中有（350）个叶子结点；一棵二叉树的中序遍历结果为DBEAFC，前序遍历结果为ABDECF，则后续遍历结果为（DEBFCA）；冒泡排序的时间复杂度为（n(n-1)/2）;在一个容量为15的循环队列中，若头指针front=6,尾指针rear=9,则该循环队列中共有（3）元素；
程序设计基础
结构化程序设计的三种结构---是顺序、选择和循环
对象---表示客观世界的任何实体
类---是具有共同属性和方法的对象的集合
实例---任何一个对象都是其对应类的实例
消息---一个实例和另一个实例之间传递的信息
继承---是指直接获得已有的性质和特征，而不必重复定义它们。例如子类继承父类
结构化程序设计主要强调---程序的易读性
良好的程序设计风格是---程序应简单、清晰、可读性好
在面向对象方法中，一个对象请求另一个对象为其服务的方式是通过发送（消息）来实现的
信息隐蔽的概念与（模块独立性）概念直接相关
（任何对象都具有继承性）这句话是错误的
注释分为（序言性注释）和（功能性注释）
在面向对象方法中，信息隐蔽是通过对象的（封装性）来实现的
类是一个支持集成的抽象数据类型，而对象是类的（实例）
在面向对象方法中，类之间共享属性和操作的机制称为（继承）
第三章软件工程基础
软件生命周期---软件产品从提出、实现、使用维护到停止使用退役的过程。分为软件定义、软件开发、软件运行维护三个阶段。
软件生命周期的主要活动阶段---可行性分析、需求分析、软件设计、软件实现、软件测试、运行和维护。
常见的需求分析方法---（1）结构化分析方法---主要包括面向数据流的结构化分析方法SA；面向数据结构的Jackson方法JSD；面向数据结构的结构化数据系统开发方法DSSD。
（2）面向对象的分析方法OOA
结构化分析方法工具---（1）数据流图DFD，记住DFD图的几个符号：
（2）数据字典DD
（3）判定树
（4）判定表
程序结构图（SC），N-S图，问题分析图（PAD）
程序流程图（PFD）的几个符号：
软件测试---黑盒测试：功能测试
白盒测试：内部结构测试，穷举路径测试
习题3
在软件生命周期中，能准确地判断软件系统必须做什么和必须具备哪些功能的阶段是（需求分析）
软件工程的3个要素（工具），（过程），（方法）
检查软件产品是否符合需求定义的过程称为（确认测试）
软件设计原则是（抽象）、（模块化）、（信息隐蔽）
需求分析常用的工具是（DFD）
在结构化方法中，软件功能分解属于（总体设计）阶段
软件测试的目的是（改正错误）
软件需求分析阶段可分为四个方面（需求获取）、（需求分析）、（编写需求格式说明）、（需求评审）
软件是（程序）、（数据）、（文档）的集合
Jakson方法是一中面向（数据流）的结构化方法
软件工程研究的内容包括（软件开发技术）、（软件工程管理）
数据流图的类型有（交换型）、（事务型）
软件开发环境是全面支持软件开发全过程的（软件工具）集合
第四章数据库设计基础
数据库---DB；数据库管理系统---DBMS；数据库管理员---DBA；数据库系统---DBS；数据库应用系统---DBAS
数据模型所描述的内容分三个部分（数据结构）、（数据操作）、（数据约束）
逻辑数据模型分（层次模型）、（网状模型）、（关系模型）、（面向对象模型）
E-R模型---实体关系模型，主要由实体、属性、联系组成，联系分：1对1，1对多，多对多；
以二维表为基本结构所建立的模型称为关系模型，关系模型采用二维表来表示，简称表，由行和列组成，行称为元组或记录，列称为字段
主键---唯一标识一个记录的字段
外键---一个表的字段是其他表的主键
在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段、数据库系统阶段，其中数据独立性最高的阶段是（数据库系统）
数据库系统减少了（数据冗余）；数据库系统的核心是（数据库管理系统）
用树型结构来表示实体间联系的模型称为（层次模型）
关系表中的每一行称为（元组）
关系数据库管理系统能实现的专门关系运算包括（选择）、（投影）、（连接）
在关系数据库中，用来表示实体之间联系的是（二维表）
数据库设计包括两方面的设计内容（概念设计）、（逻辑设计）
将E-R图转换到关系模式时，实体与联系都可以表示成（关系）
一个项目具有一个项目主管，一个项目主管可以管理多个项目，则实体“项目主管”与“项目”的联系属于（一对多）
数据独立性分为逻辑独立性和物理独立性，当数据的存储结构改变时，其逻辑结构可以不变，因此，基于逻辑结构的应用程序不必修改，称为（逻辑独立性）
数据库系统中实现各种数据管理功能的核心软件称为（数据库管理系统DBMS）
关系模型的完整性规则是对关系的某种约束条件，包括实体完整性、（参照完整性）和自定义完整性
第四章数据库设计基础
4．1 数据库系统的基本概念
数据：实际上就是描述事物的符号记录。
数据的特点：有一定的结构，有型与值之分，如整型、实型、字符型等。而数据的值给出了符合定型的值，如整型值15。
数据库：是数据的集合，具有统一的结构形式并存放于统一的存储介质内，是多种应用数据的集成，并可被各个应用程序共享。
数据库存放数据是按数据所提供的数据模式存放的，具有集成与共享的特点。
数据库管理系统：一种系统软件，负责数据库中的数据组织、数据操纵、数据维护、控制及保护和数据服务等，是数据库的核心。
数据库管理系统功能：
（1）数据模式定义：即为数据库构建其数据框架；
（2）数据存取的物理构建：为数据模式的物理存取与构建提供有效的存取方法与手段；
（3）数据操纵：为用户使用数据库的数据提供方便，如查询、插入、修改、删除等以及简单的算术运算及统计；
（4）数据的完整性、安生性定义与检查；
（5）数据库的并发控制与故障恢复；
（6）数据的服务：如拷贝、转存、重组、性能监测、分析等。
为完成以上六个功能，数据库管理系统提供以下的数据语言：
（1）数据定义语言：负责数据的模式定义与数据的物理存取构建；
（2）数据操纵语言：负责数据的操纵，如查询与增、删、改等；
（3）数据控制语言：负责数据完整性、安全性的定义与检查以及并发控制、故障恢复等。
数据语言按其使用方式具有两种结构形式：交互式命令(又称自含型或自主型语言)宿主型语言（一般可嵌入某些宿主语言中）。
数据库管理员：对数据库进行规划、设计、维护、监视等的专业管理人员。
数据库系统：由数据库（数据）、数据库管理系统（软件）、数据库管理员（人员）、硬件平台（硬件）、软件平台（软件）五个部分构成的运行实体。
数据库应用系统：由数据库系统、应用软件及应用界面三者组成。
文件系统阶段：提供了简单的数据共享与数据管理能力，但是它无法提供完整的、统一的、管理和数据共享的能力。
层次数据库与网状数据库系统阶段：为统一与共享数据提供了有力支撑。
关系数据库系统阶段
数据库系统的基本特点：数据的集成性、数据的高共享性与低冗余性、数据独立性（物理独立性与逻辑独立性）、数据统一管理与控制。
数据库系统的三级模式：
（1）概念模式：数据库系统中全局数据逻辑结构的描述，全体用户公共数据视图；
（2）外模式：也称子模式与用户模式。是用户的数据视图，也就是用户所见到的数据模式；
（3）内模式：又称物理模式，它给出了数据库物理存储结构与物理存取方法。
数据库系统的两级映射：
（1）概念模式到内模式的映射；
（2）外模式到概念模式的映射。
4.2 数据模型
数据模型的概念：是数据特征的抽象，从抽象层次上描述了系统的静态特征、动态行为和约束条件，为数据库系统的信息表与操作提供一个抽象的框架。描述了数据结构、数据操作及数据约束。
E-R模型的基本概念
（1）实体：现实世界中的事物；
（2）属性：事物的特性；
（3）联系：现实世界中事物间的关系。实体集的关系有一对一、一对多、多对多的联系。
E-R模型三个基本概念之间的联接关系：实体是概念世界中的基本单位，属性有属性域，每个实体可取属性域内的值。一个实体的所有属性值叫元组。
E-R模型的图示法：（1）实体集表示法；（2）属性表法；（3）联系表示法。
层次模型的基本结构是树形结构，具有以下特点：
（1）每棵树有且仅有一个无双亲结点，称为根；
（2）树中除根外所有结点有且仅有一个双亲。
从图论上看，网状模型是一个不加任何条件限制的无向图。
关系模型采用二维表来表示，简称表，由表框架及表的元组组成。一个二维表就是一个关系。
在二维表中凡能唯一标识元组的最小属性称为键或码。从所有侯选健中选取一个作为用户使用的键称主键。表A中的某属性是某表B的键，则称该属性集为A的外键或外码。
关系中的数据约束：
（1）实体完整性约束：约束关系的主键中属性值不能为空值；
（2）参照完全性约束：是关系之间的基本约束；
（3）用户定义的完整性约束：它反映了具体应用中数据的语义要求。
4.3关系代数
关系数据库系统的特点之一是它建立在数据理论的基础之上，有很多数据理论可以表示关系模型的数据操作，其中最为著名的是关系代数与关系演算。
关系模型的基本运算：
（1）插入（2）删除 (3)修改（4）查询（包括投影、选择、笛卡尔积运算）
4.4 数据库设计与管理
数据库设计是数据应用的核心。
数据库设计的两种方法：
（1）面向数据：以信息需求为主，兼顾处理需求；
（2）面向过程：以处理需求为主，兼顾信息需求。
数据库的生命周期：需求分析阶段、概念设计阶段、逻辑设计阶段、物理设计阶段、编码阶段、测试阶段、运行阶段、进一步修改阶段。
需求分析常用结构析方法和面向对象的方法。结构化分析（简称SA）方法用自顶向下、逐层分解的方式分析系统。用数据流图表达数据和处理过程的关系。对数据库设计来讲，数据字典是进行详细的数据收集和数据分析所获得的主要结果。
数据字典是各类数据描述的集合，包括5个部分：数据项、数据结构、数据流（可以是数据项，也可以是数据结构）、数据存储、处理过程。
数据库概念设计的目的是分析数据内在语义关系。设计的方法有两种
（1）集中式模式设计法（适用于小型或并不复杂的单位或部门）；
（2）视图集成设计法。
设计方法：E-R模型与视图集成。
视图设计一般有三种设计次序：自顶向下、由底向上、由内向外。
视图集成的几种冲突：命名冲突、概念冲突、域冲突、约束冲突。
关系视图设计：关系视图的设计又称外模式设计。
关系视图的主要作用：
（1）提供数据逻辑独立性；
（2）能适应用户对数据的不同需求；
（3）有一定数据保密功能。
数据库的物理设计主要目标是对数据内部物理结构作调整并选择合理的存取路径，以提高数据库访问速度有效利用存储空间。一般RDBMS中留给用户参与物理设计的内容大致有索引设计、集成簇设计和分区设计。
数据库管理的内容：
（1）数据库的建立；
（2）数据库的调整；
（3）数据库的重组；
（4）数据库安全性与完整性控制；
（5）数据库的故障恢复；
（6）数据库监控。
目录 二级公共基础知识考纲 (1) 第一章数据结构与算法 (2) 第二章程序设计基础 (19) 第三章软件工程基础 (23) 第四章数据库设计基础 (32) 全国计算机等级考试二级公共基础知识考纲 考试内容 一、基本数据结构与算法 1.算法的基本概念；算法复杂度的概念和意义（时间复杂度与空间复杂度）。 2.数据结构的定义；数据的逻辑结构与存储结构；数据结构的图形表示；线性结构与非线性结构的概念。 3.线性表的定义；线性表的顺序存储结构及其插入与删除运算。 4.栈和队列的定义；栈和队列的顺序存储结构及其基本运算。 5.线性单链表、双向链表与循环链表的结构及其基本运算。 6.树的基本概念；二叉树的定义及其存储结构；二叉树的前序、中序和后序遍历。 7.顺序查找与二分法查找算法；基本排序算法（交换类排序，选择类排序，插入类排序）。 二、程序设计基础 1.程序设计方法与风格。 2.结构化程序设计。 3.面向对象的程序设计方法，对象，方法，属性及继承与多态性。 三、软件工程基础 1.软件工程基本概念，软件生命周戎概念，软件工具与软件开发环境。 2.结构化分析方法，数据流图，数据字典，软件需求规格说明书。 3.结构化设计方法，总体设计与详细设计。 4.软件测试的方法，白盒测试与黑盒测试，测试用例设计，软件测试的实施，单元测试、集成测试和系统测试。 5.程序的调试，静态调试与动态调试。 四、数据库设计基础 1.数据库的基本概念：数据库，数据库管理系统，数据库系统。 2.数据模型，实体联系模型及E-R图，从E-R图导出关系数据模型。 3.关系代数运算，包括集合运算及选择、投影、连接运算，数据库规范化理论。 4.数据库设计方法和步骤：需求分析、概念设计、逻辑设计和物理设计的相关策略。 考试方式 公共基础的考试方式为笔试，与C语言（V isualBASIC、V isual FoxPro、Java、Access、Visual C++）的笔试部分合为一张试卷。 公共基础部分占全卷的30分。公共基础知识有10道选择题和5道填空题。 第一章数据结构与算法 一、内容要点 （一）算法 1．算法的基本概念 算法是指解题方案的准确而完整的描述。即是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，没有二义性，同时该规则将在有限次运算后可终止。 1）算法的基本特征 （1）可行性 由于算法的设计是为了在某一个特定的计算工具上解决某一个实际的问题而设计的，因此，它总是受到计算工具的限制，使执行产生偏差。
全国计算机等级考试二级公共基础知识要点汇总 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件；
计算机二级C语言公共基础知识手册 1.算法的时间复杂度是指执行算法所需要的计算工作量.算法的工作量由算法所执行的基本运算次数来度量,而算法所执行的基本运算次数是问题规模的函数. 2.算法的空间复杂度是指算法执行过程中所需要的存储空间,存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间. 3.一个算法通常由两种基本要素组成:一是对数据对象的运算和操作;而是算法的控制结构. 4算法设计基本方法主要包括有列举法、归纳法、递推、递归和减半递推技术. 5.数据的逻辑结构在计算机存储空间中的存放形式称为数据的存储结构(也称数据的物理结构).、 6.数据处理是指对数据集合中的各元素以各种方式进行运算,包括插入、删除、查找、更改等运算,也包括对数据元素进行分析. 7.数据元素是指相互有关联的数据元素的集合. 8.前驱和后继关系是数据元素之间的一个基本关系,但前驱个后继关系所表示的实际意义随具体对象的不同而不同.一般说来,数据元素之间的任何关系都可以用前驱和后继关系来描述. 9.常用的存储结构有顺序链接、索引等存储结构.而采用不同的存储结构,其数据处理的效率是不同的.
10.在数据结构中,没有前驱的结点称为根结点;没有后继的结点称为终端结点(叶子结点);数据结构中除了根结点与终端结点外的其他结点一般称为内部结点. 11.在数据结构中,结点几结点的相互关系有线性结构和非线性结构. 12.线性结构(线性表):非空数据结构满足(1)有且只有一个根结点;(2)每个结点最多有一个前驱,也最多有一个后继. 在一个线性结构中插入或删除任何一个结点后还应该是线性结构,若删除或插入后不是线性结构,则该数据结构不能称为线性结构. 13.线性表是最简单、最常用的一种数据结构.有一组数据元素组成.在稍微复杂的线性表中,一个数据元素可以由若干个数据项组成,在这种情况下,常把数据元素称为记录,含有大量记录的线性表就称作文件. 14.非空线性表如与如下结构特征(1)有且只有一个根结点A1,它无前驱;(2)有且只有一个终端结点AI,它无后继;(3)除根结点与终端结点外,其他所有结点有且只有一个前驱,也只有一个后继.线性表中结点的个数N称为线性表的长度.当 N=0时,称其为空表. 15.在计算机中存放线性表,一种最简单的方法是顺序存储,也称顺序分配. 16.线性表的顺序存储结构具有以下两种基本特点:(1)线性表中所有元素所占的存储空间是连续的;(2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的. 在线性表的存储结构中,其前后继两个元素在存 储空间中是紧邻的,且前驱元素一定存储在后继元素的前面. 17.假设线性表中第一个数据元素的存储地址是ADR(AI),每一个数据元素占K 个字节,则线性表中第I个元素AI在计算机存储空间中的存储地址是 ADR(AI)=ADR(A1)+(I-1)K.
1算法 1.1 算法的基本概念 1．算法的概念(必记)： 算法是指解题方案的准确而完整的描述。 分析：要用计算机实现某一任务时，先应设计出一整套解决问题的指导方案，然后具体实现。整套的指导方 案称之为算法，而具体的实现称之为程序。并且在设计指导方案时，可不用过多考虑到实现程序的具体细节(即可以一点点的理想化)，但在程序实现时，必须受到具体环境的约束(现实不同于理想)。 结论：算法不等于程序，也不等于计算方法，程序的编制不可能优于算法的设计。 2．算法的基本特征(必记)： a.可行性：由于算法总是在某个特定的计算工具上实现并执行的，因而受到计算工具的限制，所以在设计算法时，要考虑到设计的算法是否是可性的。 b.确定性：算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。 c.有穷性：算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后终止。 d.拥有足够的情报：算法有相应的初始数据。 3．算法的基本要素： 一个算法通常由两个基本要素所组成：一是对数据对象的运算和操作，二是算法的控制结构。 基本运算和操作分为四类： a. 算术运算: (加、减、乘、除等运算) b. 逻辑运算: (与、或、非等运算) c. 关系运算: (大于、小于、等于、不等于等运算) d. 数据传输: (赋值、输入、输出等操作) 算法的控制结构： 算法中各操作之间的执行顺序称之为算法的控制结构。一个算法一般都可以用顺序、选择、循环三种基本控 制结构组合而成。 注意：一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。 4．算法设计基本方法： 列举法、归纳法、递推、递归、减半递推技术、回溯法。 1.2 算法的复杂度 (必记) 算法的复杂度主要包括时间复杂度和空间复杂度。 1．算法的时间复杂度： 是指执行算法所需要的计算工作量，是由算法所执行的基本运算次数来度量。 可用平均性态和最坏情况两种分析方法。其中平均性态分析是指用各种特定输入下的基本运算次数的加权平 均值来度量算法的工作量；而最坏情况分析是指在所有特定输入下的基本运算次数据的最大次数。 2．算法的空间复杂度： 一个算法的空间复杂度，是指执行这个算法所需要的内存空间。包含有三部分所组成：算法程序所占的空间 +输入的初始数据所占的存储空间+算法执行过程中所需要的额外空间。 历届的考题： 1、算法具有五个特性，以下选项中不属于算法特性的是(______) [2005.4] A)有穷性B)简洁性C)可行性D)确定性 2、问题处理方案的正确而完整的描述称为______。[2005.4] 3、下列叙述中正确的是________。[2006.9] A）一个算法的空间复杂度大，则其时间复杂度也必定大
公共基础知识教材电子版 党的一大:中国共产党诞生 1921年，中国共产党在上海召开第一次全国代表大会，宣告了中国共产党的成立。 党的二大:提出反帝反封建的民主革命纲领 1922年，中共二大，正确分析了中国的社会性质，中国革命的性质、对象、动力和前途，指出了中国革命要分两步走，在中国近代史上第一次提出了彻底的反帝反封建的民主革命纲领。党的最高纲领是实现社会主义、共产主义。现阶段的革命纲领即最低纲领是统一中国为真正的民主共和国。二大为中国各民族人民的革命斗争指明了方向，对中国革命具有重大的深远的意义。 党的三大:大革命洪流中召开的党的代表大会 1923年，党的三大召开，决定共产党员以个人身份加入国民党，实现国共合作，同时保持共产党在政治、思想、组织上的独立性。1924年，国民党一大召开，确立联俄、联共、扶助农工的三大政策，形成了新三民主义，标志着第一次国共合作正式形成。 党的四大:大革命洪流中召开的党的代表大会 1925年四大召开，提出了无产阶级在民主革命中的领导权问题和工农联盟问题。四大的缺点和不足是:虽然提出了领导权的问题，但对于如何争取领导权，缺乏具体明确的方针，只讲对群众运动的领导权，而完全忽视了对政权和武装力量的领导权。提出了农民是革命同盟军的问题，但没有提出土地革命这一解决农民问题的根本思想。 党的五大:大革命洪流中召开的党的代表大会
1927年五大召开，大大虽然批判了陈独秀的右倾错误，但对争夺革命领导权所迫切需要解决的重大问题，如改造武汉国民党、改造武汉国民政府、组织和扩大党对革命武装的领导等问题，均未做出切合实际的回答。大会对陈独秀右倾投降主义的实质和危害也缺乏深刻的认识。五大实际上并未解决挽救时局的问题。 党的六大:唯一一次在国外召开的党的代表大会 1928年六大在莫斯科召开，中共六大制定的路线基本是正确的，对后来中国革命的发展起了积极的作用。但这次会议也存在着缺点，即对中间阶级的作用、反动势力内部的矛盾缺乏正确的估计和政策，特别是对中国革命的长期性和农村革命根据地的重要意义认识不足，仍旧把城市工作放在全党工作的中心，这对中国革命的发展起了消极的影响。 党的七大:确立毛泽东思想在全党的指导地位 1945年七大在延安召开，大会确立毛泽东思想为全党的指导思想，这是七大做出的历史性贡献。大会把党在长期奋斗中形成的优良传统和作风概括为三大作风。即理论联系实际，密切联系群众，批评与自我批评。 党的八大:探索建设社会主义道路的良好开端 1956年八大召开，大会正确分析了国内外形势和国内主要矛盾的变化，指出:由于社会主义改造已经取得决定性胜利，我国无产阶级同资产阶级之间的矛盾已经基本解决，国内的主要矛盾，已经是人民对于建立先进的工业国的要求同落后的农业国的现实之间的矛盾，已经是人民对于经济文化迅速发展的需要同当前经济文化不能满足人民需要的状况之间的矛盾。党和人民当前的主要任务，就是要集中力量解决这个矛盾，把我国尽快地从落后的农业国变成先进的工业国。八大是探索中国自己的建设社会主义道路的良好开端。 党的九大:文化大革命中的大会
二级公共基础知识总结 第一章数据结构与算法 1.1 算法算法：是指解题方案的准确而完整的描述。算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。指令系统：一个计算机系统能执行的所有指令的集合。基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；
（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含：（1）表示数据元素的信息；（2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。非空线性表的结构特征：（1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件； （3）除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。结点个数n称为线性表的长度，当n=0时，称为空表。线性表的顺序存储结构具有以下两个基本特点：（1）线性表中所有元素的所占的存储空间是连续的；（2）线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。ai的存储地址为：ADR(ai)=ADR(a1)+(i-1)k,，ADR(a1)为第一个元素的地址，k代表每个元素占的字节数。顺序表的运算：插入、删除。 （4）1．4 栈和队列栈是限定在一端进行插入与删除的线性表，允许
计算机二级C语言的二级共公基础知识教程 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念
数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位臵只取决于自己的序号，元素之间的相对位臵是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； （2）有且只有一个终端结点an，它无后件；
1.1 算法 考点1 算法的基本概念 计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 1算法的基本特征 (1)可行性(effectiveness)：针对实际问题而设计的算法，执行后能够得到满意的结果。 (2)确定性(definiteness)：算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 (3)有穷性(finiteness)：算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报：要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2算法的基本要素 (1)算法中对数据的运算和操作：每个算法实际上是按解题要求从环境能进行的所有操作中选择合适的操作所组成的一组指令序列。 计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下4类： ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算：主要包括“与”、“或”、“非”等运算； ③关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算； ④数据传输：主要包括赋值、输入、输出等操作。 (2)算法的控制结构：一个算法的功能不仅仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。 算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。 (3)算法设计的基本方法 计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。 (1)列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。 (2)归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。
二年级公共基础知识教 材精讲 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】
目 录 视频讲解教师简介 .................................................................... 教材精讲部分[视频讲解] .............................................................. 第1章 数据结构与算法[视频讲解] ................................................ 1.1 算 法 ................................................................. 1.2 数据结构的基本概念 ..................................................... 1.3 线性表及其顺序存储结构 ................................................. 1.4 栈和队列 ............................................................... 1.5 线性链表 ............................................................... 1.6 树与二叉树 ............................................................. 1.7 查找技术 ............................................................... 2018年9月全国计算机等级考试《二级公共基础知识》【教材精讲＋真题解析】讲义 与视频课程 最新资料，WORD 格式，可编辑修改！
计算机公共基础部分知识归纳 第一章数据结构与算法 算法---是一组严谨地定义运算顺序的规则 算法的基本要素---一是对数据对象的运算和操作，二是算法的控制结构 算法设计基本方法---列举法、归纳法、递推、递归、减半递推 算法的复杂度---包括时间复杂度和空间复杂度 时间复杂度---执行算法所需的计算工作量 空间复杂度---执行算法所需的内存空间 数据结构---相互有关联的数据元素的集合。如春、夏、秋、冬；18、11、35、23、16。。。； 父亲、儿子、女儿等都是数据元素。 前件---数据元素之间的关系，如父亲是儿子和女儿的前件 后件---如儿子是父亲的后件 结构---指数据元素之间的前后件关系 数据的逻辑结构—是指反映数据元素之间逻辑关系，而与它们在计算机中的存储位置无关数据的存储结构（物理结构）---数据的逻辑结构在计算机存储空间中的存放形式，数据元素 在计算机存储空间的位置关系可能与逻辑关系不同。 根据数据结构中各数据元素之间前后件关系的复杂程度，可将数据结构分两类---线性结构与 非线性结构 线性结构（线性表）---满足下列两个条件（1）有且只有一个根结点（2）每一个结点最多有 一个前件和后件。则称该数据结构为线性结构，否则为非线 性结构。 线性表是最简单、最常用的一种数据结构，其数据元素之间的相对位置是线性的，其存储方 式为顺序存储的，如数组 栈---是限定在一端进行插入与删除的线性表，一端封闭，另一端开口，其操作原则是“先进 后出”，栈的运算有入栈、退栈、读栈顶元素 队列---是指在一端进行插入（称为队尾）而在另一端进行删除（称为队头）的线性表，其操 作规则是“先进先出”，其运算有入队和退队。 树---是一种简单的非线性结构，而且是层次结构，是倒立的大树，有根结点、父结点、子结 点、叶子结点。根结点在第一层，一个结点所拥有的后件的 个数称为该结点的度，所有结点中最大的度称为树的度， 树的最大层次称为树的深度。 二叉树---（1）非空二叉树只有一个根结点（2）每一个结点最多有两棵子树（左子树和右子 树），其存储结构为链式。 二叉树性质---（1）K层上最多有2（K-1）个结点（2）深度为m的二叉树最多有2m-1个结点（3）度为0的结点（叶子结点）比度为2的结点多一个（4）具有n个结点的 二叉树，其深度至少为[Log2n]+1，其中[Log2n]表示对Log2n 取整 满二叉树---除最后一层外，其余层的结点都有两个子结点 完全二叉树---除最后一层外，每一层上的结点数均达到最大值，在最后一层上只缺少右边的 若干结点，叶子结点只可能在层次最大的两层上出现。满二 叉树是完全二叉树，而完全二叉树不是满二叉树。完全二叉 树有两个性质：（1）具有n个结点的完全二叉树的深度为
全国计算机等级考试二级公共基础知识复习资料 全国计算机等级考试二级公共基础知识复习资料 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。算法的控制结构：顺序结构、选择结构、循环结构。
算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件：（1）有且只有一个根结点；（2）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表是由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。
计算机二级公共基础知识要点总结 1.栈按先进后出的原则组织数据，所以入栈最早的最后出栈，而队列是先进先出的线性 表。 2.循环队列有队头和队尾两个指针，但是循环队列仍是线性结构的线性表。 在循环队列中只需要对头指针与队尾两个指针来共同反映队列中元素的动态变化情况。 3.当有序线性表为顺序存储时才能用二分法查找。可以证明的是对于长度为n的有序线性 表，在最坏的情况下二分法查找只需要比较log2n次，而顺序查找需要比较n次。 4.链式存储结构既可以针对线性结构也可以针对非线性结构。 链式存储结构中每个结点都由数据域与指针域两部分组成，增加了存储空间。 顺序存储结构的存储一定是连续的，链式存储结构的存储空间不一定是连续的。 5.数据流图中带箭头的线段表示的是数据流，即沿箭头方向传送数据的通道一般在旁边标 注数据流名。 程序流程图中带有箭头的线段表示的是控制流。 6.在软件开发中，需求分析阶段可以使用的工具有数据流图DFD图，数据字典DD，判定 树与判定表。 7.“对象”有如下一些基本特点：标识唯一性，分类型，多态性，封装性，模块独立性好。 8.数据管理发展至今已经历了三个阶段：人工管理阶段，文件系统阶段和数据库系统阶段。 其中最后一个阶段结构简单，使用方便，逻辑性强，物理性少，在各方面的表现都最好，一直占据数据库领域的主导地位。 9.自然链接是一种特殊的等值连接，它要求两个关系中进行比较的分量必须是相同的属性 组，并且在结果中把重复的属性列去掉。 10.内存又称主存，是CPU能直接寻址的存储空间，由半导体器件制成。内存的特点是存取 速率快。所以微机中访问速度最快的存储器是内存。 11.计算机能直接识别和执行的语言是机器语言，机器语言是用二进制代码表示的计算机能 直接识别和执行的一种机器指令的集合。它是计算机的设计者通过计算机的硬件结构赋予计算机的操作功能。机器语言具有灵活，直接执行和速度快等特点。 12.1MB=1024KB=1024*1024B=220B 13.Internet的四层结构分别是：网络接口层，网络层，传输层和应用层。 14.有序线性表既可以采用顺序存储结构，也可以采用链式存储结构。 15.栈支持子程序调用。栈是一种只能在一端进行插入或删除的线性表。 16.二叉树的基本性质：在任意一棵二叉树中，度为0的叶子结点总是比度为2的结点多一 个。 例如:某二叉树有五个度为2的结点，则该二叉树中的叶子结点数是5+1=6个。 17.冒泡排序与简单插入排序与简单选择排序法在最坏情况下均需要比较n(n-1)/2次，而堆 排序在最坏的情况下需要比较的次数是nlog2n，即在排序方法中，最坏情况下比较次数最少的是堆排序。 18.软件按功能可分为：应用软件，系统软件和支撑软件（或工具软件）。 19.软件测试的目的是为了发现错误而执行程序的过程，并不涉及改正错误。 程序调试的基本步骤有：错误定位，修改设计和代码，以排除错误进行回归测试，防止引进新的错误。程序调试通常称为Debug,即排错。 20.软件测试的基本准则有：所有测试都应追溯到需求，严格执行测试计划，排除测试的随 意性，充分注意测试中的群集现象，程序员应避免检查自己的程序，穷举测试不可能，
全国计算机等级考试二级教程（全套） 全国计算机等级考试二级教程--公共基础知识(2008年版)教程 全国计算机等级考试二级教程--VisualFoxPro(2008年版)教程 全国计算机等级考试二级教程--VB语言程序设计(2008年版)教程 全国计算机等级考试二级教程--Delphi语言程序设计(2008年版)教程 全国计算机等级考试-二级教程-Java语言程序设计（2008年版）教程 全国计算机等级考试-二级教程-C语言程序设计（2008年版）教程 全国计算机等级考试-二级教程-C++语言程序设计（2008年版）教程 全国计算机等级考试-二级教程-Access数据库程序设计（2008年版）教程 2010年计算机等级考试二级公共基础教程 2010年全国计算机等级考试二级VB上机考试新版题库pdf电子书免费下载 2010年全国计算机等级考试二级Access上机考试新版题库pdf电子书免费下载2010年计算机等级考试上机题库(二级VFP)pdf电子书免费下载 2010年计算机等级考试上机题库(二级C++)pdf电子书免费下载 2010年全国计算机等级考试二级C上机考试新版题库pdf电子书免费下载 2010年最新计算机等级考试软件—二级VFP(包含上机模拟系统,笔试系统,视频教程) 2010年最新计算机等级考试软件—二级VB(包含上机模拟系统,笔试系统,视频教程) 2010年最新计算机等级考试软件—二级Access(包含上机模拟系统,笔试系统,视频教程)
2010年最新计算机等级考试软件—二级C语言(包含上机模拟系统,笔试系统,视频教程) 2010年最新计算机等级考试软件—二级C++(包含上机模拟系统,笔试系统,视频教程) 计算机等级考试二级上机试题,模拟系统,笔试系统,视频教程汇总 2010年最新计算机等级考试二级VB上机试题50套解析 2010年9月最新计算机等级考试三级网络技术笔试模拟试卷10套含答案解析
第一章数据结构与算法 算法 1、算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。 2、算法的基本特征：是一组严谨地定义运算顺序的规则,每一个规则都是有效的，是明确的,此顺序将在有限的次数下终止。特征包括：（1）可行性;（2)确定性(3）有穷性（4）拥有足够的情报。 ３、算法的基本要素:一是对数据对象的运算和操作；二是算法的控制结构。 ４、指令系统:一个计算机系统能执行的所有指令的集合。 5、基本运算包括:算术运算、逻辑运算、关系运算、数据传输。 ６、算法的控制结构：顺序结构、选择结构、循环结构。 7、算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 8、算法复杂度:算法时间复杂度和算法空间复杂度。 9、算法时间复杂度是指执行算法所需要的计算工作量。 10、算法空间复杂度是指执行这个算法所需要的内存空间。 数据结构的基本基本概念 1、数据结构研究的三个方面: (1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构; （2）在对数据进行处理时，各数据元素在计算机中的存储关系,即数据的存储结构;（3）对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。 ２、数据的逻辑结构包含:(1）表示数据元素的信息;(2）表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。 ３、线性结构条件：(1）有且只有一个根结点;(２）每一个结点最多有一个前件，也最多有一个后件。非线性结构：不满足线性结构条件的数据结构。 线性表及其顺序存储结构 １、线性表是由一组数据元素构成,数据元素的位置只取决于自己的序号,元素之间的相对位置是线性的。在复杂线性表中,由若干项数据元素组成的数据元素称为记录,而由多个记录构成的线性表又称为文件。 2、非空线性表的结构特征: (1）且只有一个根结点ａ1，它无前件；(2)有且只有一个终端结点an，它无后件; （3)除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数n称为线性表的长度,当ｎ=0时，称为空表。 3、线性表的顺序存储结构具有以下两个基本特点：(１）线性表中所有元素的所占的存储空间是连续的; (2)线性表中各数据元素在存储空间中是按逻辑顺序依次存放的。 4、顺序表的运算:插入、删除。 栈和队列 1、栈是限定在一端进行插入与删除的线性表,允许插入与删除的一端称为栈顶，不允许插入与删除的另一端称为栈底。栈按照“先进后出”（FILO)或“后进先出”(LＩFO）组织数据,栈具有记忆作用。用ｔop表示栈顶位置，用ｂottoｍ 表示栈底。 2、栈的基本运算：(1）插入元素称为入栈运算；（2)删除元素称为退栈运算;（３）读栈顶元素是将栈顶元素赋给一个指定的变量,此时指针无变化。 3、队列是指允许在一端（队尾）进入插入,而在另一端(队头）进行删除的线性表。Ｒear指针指向队尾,frｏnt 指针指向队头。 4、队列是“先进行出”(FIFO)或“后进后出”(LILO)的线性表。 线性链表
二级公共基础知识分类模拟题43 单项选择题 1、下列叙述中正确的是______。 A．所谓算法就是计算方法 B．程序可以作为算法的一种描述方法 C．算法设计只需考虑得到计算结果 D．算法设计可以忽略算法的运算时间 2、下列叙述中正确的是______。 A．算法的复杂度包括时间复杂度与空间复杂度 B．算法的复杂度是指算法控制结构的复杂程度 C．算法的复杂度是指算法程序中指令的数量 D．算法的复杂度是指算法所处理的数据量 3、下列叙述中正确的是______。 A．算法的时间复杂度与计算机的运行速度有关 B．算法的时间复杂度与运行算法时特定的输入有关 C．算法的时间复杂度与算法程序中的语句条数成正比 D．算法的时间复杂度与算法程序编制者的水平有关 4、下列叙述中正确的是______。 A．非线性结构可以为空 B．只有一个根结点和一个叶子结点的必定是线性结构 C．只有一个根结点的必定是线性结构或二叉树 D．没有根结点的一定是非线性结构 5、设数据结构B=(D，R)，其中 D={a,b,c,d,e,f} R={(f,a),(d,b),(e,d),(c,e),(a,c)} 该数据结构为______。 A．线性结构 B．循环队列 C．循环链表 D．非线性结构 6、下列叙述中正确的是______。 A．矩阵是非线性结构 B．数组是长度固定的线性表 C．对线性表只能作插入与删除运算 D．线性表中各元素的数据类型可以不同 7、在线性表的顺序存储结构中，其存储空间连续，各个元素所占的字节数______。 A．不同，但元素的存储顺序与逻辑顺序一致 B．不同，且其元素的存储顺序可以与逻辑顺序不一致 C．相同，元素的存储顺序与逻辑顺序一致 D．相同，但其元素的存储顺序可以与逻辑顺序不一致 8、下列叙述中正确的是______。 A．能采用顺序存储的必定是线性结构 B．所有的线性结构都可以采用顺序存储结构 C．具有两个以上指针的链表必定是非线性结构 D．循环队列是队列的链式存储结构 9、下列叙述中正确的是______。 A．在栈中，栈顶指针的动态变化决定栈中元素的个数
1.1 算法 考点1 算法的基本概念计算机解题的过程实际上是在实施某种算法，这种算法称为计算机算法。 算法(algorithm)是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，同时是明确的；此顺序将在有限的次数后终止。算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 1 算法的基本特征 (1) 可行性(effectiveness):针对实际问题而设计的算法，执行后能够得到满意的结果。 (2) 确定性(definiteness):算法中的每一个步骤都必须有明确的定义，不允许有模棱两可的解释和多义性。 ⑶有穷性(finiteness):算法必需在有限时间内做完，即算法必需能在执行有限个步骤之后终止。 (4)拥有足够的情报:要使算法有效必需为算法提供足够的情报当算法拥有足够的情报时，此算法才最有效的；而当提供的情报不够时，算法可能无效。 2 算法的基本要素 (1) 算法中对数据的运算和操作:每个算法实际上是按解题要求从环境能进行的所 有操作中选择合适的操作所组成的一组指令序列。计算机可以执行的基本操作是以指令的形式描述的。一个计算机系统能执行的所有指令的集合，称为该计算机系统的指令系统。计算机程序就是按解题要求从计算机指令系统中选择合适的指令所组成的指令序列在一般的计算机系统中，基本的运算和操作有以下 4 类: ①算术运算：主要包括加、减、乘、除等运算； ②逻辑运算:主要包括“与” 、“或”、“非”等运算； ③关系运算:主要包括“大于” 、“小于”、“等于”、“不等于”等运算； ④数据传输：主要包括赋值、输入、输出等操作。 (2) 算法的控制结构:一个算法的功能不仅仅取决于所选用的操作，而且还与各操 作之间的执行顺序有关。算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，它不仅决定了算法中各操作的执行顺序，而且 也直接反映了算法的设计是否符合结构化原则。描述算法的工具通常有传统流程图、N-S 结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3 种基本控制结构组合而成。 (3) 算法设计的基本方法 计算机算法不同于人工处理的方法，下面是工程上常用的几种算法设计，在实际应用时，各种方法之间往往存在着一定的联系。 (1) 列举法 列举法是计算机算法中的一个基础算法。列举法的基本思想是，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。 列举法的特点是算法比较简单。但当列举的可能情况较多时，执行列举算法的工作量将会很大。因此，在用列举法设计算法时，使方案优化，尽量减少运算工作量，是应该重点注意的。 (2) 归纳法 归纳法的基本思想是，通过列举少量的特殊情况，经过分析，最后找出一般的关系。从 本质上讲，归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。 (3) 递推递推是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的，因此，递推 关系式往往是归纳的结果。对于数值型的递推算法必须要注意数值计算的稳定性问题。
` 第1章数据结构与算法 §1.1 算法的复杂度 1. 算法的基本概念 ①.算法：即解题方案的准确而完整的描述【注意：算法不等于程序，也不等于计算方法，通常，程序的编制不可能优于算法的设计】 ②.利用计算机算法为计算机解题的过程实际上是在实施某种算法。 （1）算法的基本特征 算法一般具有4个基本特征：可行性、确定性、有穷性（包括精度要求确定的计算过程和合理的执行时间的含义）、拥有足够的情报。 （2）算法的基本要素 ①.对数据对象的运算和操作 计算机算法就是计算机能处理的操作所组成的指令序列。通常，计算机可以执行的基本操作是以指令的形式描述的，一个计算机系统能执行的所有指令的集合称为该计算机系统的指令系统。其中基本的运算和操作包括：算术运算、逻辑运算、关系运算、数据传输（赋值、输入、输出等）。 ②.控制结构：算法中各操作之间的执行顺序称为算法的控制结构。 ⅰ.描述算法的工具通常有：传统流程图、N—S结构化流程图、算法描述语言。 ⅱ.一个算法的3种基本控制结构：顺序结构、选择结构、循环结构。 （3）算法基本设计方法 算法基本设计方法：列举法、归纳法、递推（逐成分解）、递归、减半递推技术、回溯法。 2. 算法复杂度 算法复杂度包括时间复杂度和空间复杂度。注意两者的区别，不要混淆，见表1-1 §1.2 数据结构 1.2.1 逻辑结构和存储结构 1. 数据结构的基本概念 （1）数据结构：指相互有关联的数据元素的集合。 （2）数据处理：指对数据集合中的各元素以各种方式进行运算，包括插入、删除、查找、更改等运算、也包括对数据元素进行分析。 （3）数据结构研究的3个方面 ①.数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构; ②.在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构; ③.对各种数据结构进行的运算。 2. 数据的逻辑结构 数据的逻辑结构是对数据元素之间的逻辑关系的描述，它可以用一个数据元素的集合和定义在此集合中的若干关系来表示。数据的逻辑结构有两个要素：一是数据元素的集合，通常记为D；二是D上的关系，它反映了数据元素之间的前后件关系，通常记为R。一个数据结构可以表示成：B=(D,R) 其中，B表示数据结构。为了反映D中各数据元素之间的前后件关系，一般用二元组来表示。在数据处理领域中，通常把数据元素之间的这种固有的关系简单地用前后件关系（或直接前驱或直接后继关系）来描述。例如，假设a 与b是D中的；两个数据，则二元组（a，b）表示a是b的前件，b是a的后件 例如，如果把一年四季看作一个数据结构，则可表示成：B =(D,R)