国二公共基础知识 第一章数据结构与算法
算法
1. 算法的基木特征：可行性、确定性、有穷性、拥有足够的情报。 2. 算法的基本要素：
（1） 算法屮对数据的运算和操作，包括：算术、逻辑、关系运算以及数据传输。
（2） 算法的控制结构，一般部可由顺序、选择、循坏（重复）三种控制结构纟H?合而成。
3. 算法的设计基方法：列举法、归纳法、递推、递归、减半递推、冋溯法。 4. 算法的时间复杂度：是指算法所需要的计算工作量，由基木运算次数来度量。
5算法的空间复杂度：指执行算法所需要的内存空间。包括，算法程序所占空间、输入初始 数
据所占的存储空间、算法执行过程屮所需要的额外空间。
1.2数据结构的基本概念
1. 数据结构主要研究以下三个方面：
（1） 逻辑结构：数据集合屮各数据元素Z间所固有的逻辑关系。
（2） 存储结构：在对数据讲行处理时，备数据元素在计算机屮的存储关系。 （3） 对各种数据结构进行的运算。
2. 数据处理：指对数据集合屮各元索以各种方式进行运算，包括插入、删除、查找、更改、
以及对数据元素进行分析。
3. 数据结构：是指带有结构的数据元素的集合，它包含以下两方血信息：
（1） 表示数据元素的信息；
（2） 表示各数据元素之间的前后件关系。
4. 数据逻辑结构：B= （D, R） B：数据结构 D：数据元素集合
R：备数据元素Z间的前后件关系
5. 数据存储结构：数据的逻辑结构在计算机存储空间屮的存放形式，也叫物理结构。 常用的
存储结构有顺序、链接、索引。
&线性结构：若非空数据结构满足：（1）有且只有一个根结点；（2）每一个结点最多有一个
前件，也最多有一个后件。则称线性结构，也叫线性表。
1.3线性表及其顺序存储结构
1. 线性表是由一纟R元素纟R成，可是以是矩阵。 2.线性表的顺序存储结构有两个基木特点：
（1） 线性表屮所有元素所占的存储空间是连续的； （2） 线性表屮各数据元素在存储空间屮是按逻辑顺序依次存放的。
3. 线性表屮笫i个元素在计算机存储空间屮的存储地址为：ADR（ai）=ADR（al）+（i-l）k 4. 在程序设计语言屮，通常定义一个一维数纟R来表示线性表的顺序存储空间。 5. 对线性表的各种处理：插入、删除、查找、排序、分解、合并、复制、逆转等。 6. 插入：从最后一个元素开始向后移动，直到第i个元素。 7. 删除：从第i+1个元素开始向后移动，直到第n个元素。
1?4栈和队列
1. 栈：是限定在一端进行插入与删除的线性表，先进后出或后进先出。
2. 栈顶：允许插入的一端，用top表示；栈底：允许删除的另一端，用bottom来表示。 3. 用一维数组S （1： m）作为栈的顺序存储空间，其屮m为栈的最大容量。 4. Top=0表示栈空；top=m表示栈满。 5. 栈的基木运算有三种：
（1） 入栈运算：在栈顶位置插入一个新元素
（2） 退栈运算：取出栈顶元素并赋给一个指定的变量 （3） 读栈顶元素：指将栈顶元素赋给一个指定的变量
1?2队列：指允许在一端进行插入、而在另一端进行删除的线性表，先进先出或后进后出。 1?队尾：允许插入的一端，用尾指针（rear）来指向队尾元素 2. 排头：允许删除的一端，用排头指针（front）指向排头元索 3?入队运算：在队尾插入一个元素，只涉及尾指针（rear）的变化 4. 退队运算：在排头删除一个元素，只涉及排头指针（front）的变化
5. 循环队列：将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供
队列环状使用。
&循环队列的初始状态为空，即rear=front=m3
每进行一次入队运算，队尾指针就进一。当队尾指针rear=m+l时，则置rear=lo 第进行一次退队运算,排头指针就进一。当排头指针front=m+l时,则置front\。
7.当队列满和空时，都有front=rear
用30表示队列空，用SJ表示队列非空
（1） 队列空的条件为S=0；
（2） 队列满的条件为S=1 front二rear。
1.5线性链表的基本概念
1. 链式存储方式，要求毎个结点由两部分纟R成：（1）用于存放数据元素值，称数据域；
（2）用于存放指针，称指针域。
2?线性链表：线性表的链式存储结构。最后一个结点指针域为空（NULL或0 ）,表链表终II,
3. 线性单链表只能找到后件结点，不能找到前件结点。
4. 线性双链表：（1）左指针，用以指向前件结点；（2）右指针，有以指向向件结点。 5. 带链的栈：采用链式存储结构的栈，称为可利用栈。 6. 循环链表有以下两个特点：
（1） 在循环链表屮增加了一个表头结点，其数据域为任意或根据需要来设置，指针域指向
线性链表的第一个元素的结点。循环链表的头指针指向表头结点。 （2） 循坏链表屮最后一个结点的指针域不是空，而是指向表头结点。
7. 在循环链表屮，只要指出表屮任何一个结点的位置，就可以从它出发访问到表屮其他所有 的结占，面线性单链表做不到这一点。 1.6树与二叉树
1. 树：树是一种简单的非线性结构。
2. 具有层次关系的数据都可以用树这种数据结构來描述。
3. 在树结构屮，每一个结点都只有一个前件，称为父结点；没有前件的结点只有一个，称为 根
结点，简称树的根。
4. 第一个结点可以有多个后件，它们祁称为该结点的子结点；没行后件的结点称为叶子结点
5. 度：一个结点拥有的后件个数称该结点的度。在树屮，所有结点屮的最大的度称为树的度 6. 深度：树的最大层次称为树的深度。 7 ?二叉树的性质：
（1） 在二叉树的第k层上，最多有 个结点。 （2） 深度为m的二叉树最多有 个结点。
（3） 任意一棵二叉树屮，度为0的结点（树子结点）总比度为2的结点多一个。 （4） 具有n个结点的二叉树，其深度至少为［log2n］+l，其屮［］表示取整。
完全二叉树有以下两个性质：
（5） 具有n个结点的完全二叉树的深度为［log2n］+lo
（6） 设完全二叉树有n结点。如果从根结点开始,按层序（每一层从左到右）用自然数字
1, 2, 3,……，n给结点进行编号，则对于编号为k的结点有以下结论：
a. 若kJ,则该结点为根结点；若k>l,则该结点的父结点的编号为int（k/2）o
b. 若2k<=n,则编号为k的结点的左了结点编号为2k；否则该结点无左了结点（和右了结点） c. 若2k+l<=n,则编号为k的结点的右子结点编号为2k+l,否则该结点无右子结点。
8?二叉树通常采用链式存储结构，也由两部分组成：数据域和指针域（左指针域、右指针域） 9.二叉树的链式存储结构称为二叉链表，盯称为二叉链表的头指针。 1.6二叉树的遍历（递归过程）
1?前序遍历：（1）访问根结点；（2）前序遍历左了树；（3）前序遍历右了树。 2. 中序遍历：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。 3. 后序遍历：（1）后序遍历左了树：（2）后序遍历右了树:（3）访问根结点。
注：这里的前序、屮序、示序是指根结点的访问次序，左了树始终比右了树先访问。
1.7査找技术
1. 顺序查找：无序表、链式存储的有序表只能用顺序法查找。最多要查找n次。 2. 二分杳找：只适用于顺序存储的有序表。最多要杳找log2no 1.8排序技术 1. 交换类排序法：
（1） 冒泡排序法（下沉排序法），最多n（n-l）/2次。 （2） 快速排序法
2. 插入类排序法：
（1） 简单插入排序法,最多n（n-l）/2次。
（2） 希杀排序法，最多0 （）
3. 选择类排序法
（1） 简单选择类排序法,最多n（n-l）/2次 （2） 堆排序法，最多0 （nlog2n）次。
第二章程序设计基础
2.1程序设计方法与风格
1. 稈序编写风格：是指编写稈序时所表现出的特点、习惯和逻辑思路， 2. 要形成良好的稈序设计风格，应注重和考虑以下因素：
（1） 源程序文档化：符号名的命名、程序注释（序言性注释和功能性注释）、视觉组织。 （2） 数据说明的方法：（1）数据说明的次序规范化
（2） 说明语句中变量安排有序化 （3） 使用注释来说明复杂数据的结构
（3） 语句结构
（4） 输入和输出
2.2结构化程序设计（20世纪70年代提出）
1. 结构化程序设计的原则：白顶向下、逐步求精、模块化、限制使用got。语言。 2. 程序设计的三种基本结构：
（1） 顺序结构：按照程序语句，一条语旬一条语句地执行程序。
（2） 选择结构：又称分支结构，包括简单选择和多分支选择结构。 （3） 重复结构：又称循环结构。
3. 结构化程序设计的优点：
（1） 程序易于理解、使用和维护；
（2） 提高了编程工作的效率了软件开发的成木。
4. 结构化程序设计原则和方法的应用
（1） 使用稈序设计语言屮顺序、选择、循环等有限的控制结构表示稈序的控制逻辑; （2） 使用的控制结构只准许有一个入口和一个出口；
（3） 程序语句纽?成容易识别的块，每块只有一个入口和一个出口； （4） 复杂结构应该用嵌套的基木控制结构进行组合嵌套来实现； （5） 语言屮所没有的控制结构，应该采用前后一致的方法来模拟； （6） 严格限制goto语言的使用。
2.2.3面向对象的稈序设计 1. 面向对象方法的优点：
（1） 与人类的习惯思维方法一致 （2） 稳定性好 （3） 可重用性好
（4） 易于开发大型软件产品 （5） 可维护性好
2. 对彖：对彖是可以用来表示客观世界屮的任何实体，也就是说，应用领域屮有意义的、与
所要解决问题有关的任何事物都可以作为对象。
3. 对象的操作称为方法或服务
4. 属性：对象所包含的信息。属性值应该是指纯粹的数据值，还不能指对象。 5. 对彖的基木特点:
（1） 标识唯一性：指对彖是可区分的，且由对彖的内在木质区分，不是通过描述来区分。 （2） 分类性：指可以将具有相同属性和操作的对象抽象成类。
（3） 多态性：指同样的消息被不同的对象接受时可导致完全不同的行为。 （4） 封装性：从外面只能看到对象的外部特性。
（5） 模块独立性好：对象内部各种元素结合得很紧密，同聚性强。
6. 类：将属性和操作相似的对彖归为类。类是对彖的抽彖，而一个对彖是对应类的一个实例。
类是关于对象性质的描述,它同对象一样，包括一组数据性性和在数据上的一组合法的操作。
7. 消息：一个实例与另一个实例Z间传递的信息，它由以下三部分组成：
（1）接收消息的对象的名称；
（2） 消息标识符（也称为消息名）
（3） 零个或多个参数如:Mycircle.Show（GREEN）
Mycircle是接收消息的对象的名字，Show消息名，Green是消息参数。
8. 继承：是指能够直接获得己有的性质和特征，不必重复定义它们。多继承可有多个父类。
第三章软件工程基础 3.1软件工稈基木概念 1?计算机软件：是计算机系统中与硬件相互依存的另一部分,是包括程序、
的完整集合。
2. 软件的特点：
（1） 软件是一种逻辑实体，而不是物理实体，具有抽彖性。 （2） 软件的生产与硬件不同，它没有明显的制作过程。 （3） 软件在运行、使用期间不存在磨损、老化问题。
（4） 软件的开发、运行对计算机系统具有依赖性，受计算机系统的限制，有软件移植问题。 （5） 软件复杂性高，成木昂贵。 （6） 软件开发涉及诸多社会因素。
3. 软件按功能可分为：应用软件、系统软件、支撑软件（工具软件）
4. 软件危机：泛指在计算机软件的开发和维护过稈屮所遇到的一系列严重问题（成本、质量
和生产率等问题）
5. 软件工程：是应用于计算机软件的定义、开发和维护的一整套方法、工具、文档、实践标
准和工序，
&软件工稈包括三个要素：方法、工具、过程。
7. 软件工程包含四种基本活动：
（1） P（Plan）——软件规格说明书。 （2） D（Do）——软件开发。 （3） C（Check）——软件确认。
（4） --------------- A（Action） 软件演进。
8?软件生命周期：软件产品从提岀、实现、使用维护到使用退役的过稈。
（1） 定义阶段：可行性研究、需求分析；
（2） 开发阶段：概要设计、详细设计、实现、测试； （3） 维护阶段：使用、维护、退役。
9. 软件工稈的理论和技术性研究的内容主要包括：
（1） 软件开发技术：软件开发方法学（主体内容）、开发过程、开发工具、软件工程环境
（2） 软件工程管理：软件管理学、软件工程经济学、软件心理学
10. 软件工程的原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性、可验
证性
11. 软件开发环境：是全面支持软件开发全过稈的软件工具集合 3.2结构化分析方法
1. 软件开发方法包括：分析方法、设计方法、稈序设计方法 2. 需求分析方法：结构化分析方法、面向对彖的分析方法
3. 结构化分析：是指使用数据流图（DFD）、数据字典（DD）、结构化英语、判定表、判定
【精品】国二公共基础知识.doc
