二级C语言复习资料.doc

第一章 数据结构与算法（占10分，共5小题）1、算法是指解题方案的准确而完整的描述。（是问题处理方案的正确而完整的描述）2、算法的特点：可行性、确定性、有穷性、拥有足够的情报。3、算法的两要素：对数据对象的运算和操作算法的控制结构算法4、算法的控制结构：顺序、选择（分支）、循环（重复）。5、算法的基本设计方法：列举法、归纳法、递推、递归、减半递推技术和回溯法6、算法的复杂度分：算法的时间复杂度和算法的空间复杂度7、算法的时间复杂度是指执行算法所需要的计算工作量。（是指算法执行所需要的基本运算次数）1、数据结构分为数据的逻辑结构和数据的存储结构（数据的物理结构）2、对分查找只适用于有序表，而对于无序表是无法进行对分查找的。3、一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率。4、数据的逻辑结构是指反映数据元素之间逻辑关系（即前后件关系）的数据结构数据结构5、数据的存储结构（数据的物理结构）是指数据的逻辑结构在计算机存储空间中的存放方式（是指数据的逻辑结构在计算机中的表示）6、数据存储方式分：顺序存储结构和链式存储结构，它们都属于线性结构。7、数据结构分两大类：线性结构（线性表）和非线性结构，它们都可以是空的数据结构。线性表及顺序存储结构1、非空线性表特征：只有一个根结点和只有一个叶子结点（终端结点）。2、线性表的顺序存储结构特点：它里面的所有元素所占的存储空间是连续的，而且是按逻辑顺序依次存放的。1、栈的基本运算有：入栈、退栈和读栈顶元素。2、栈的原则是“先进后出”或“后进先出”3、栈具有记忆作用；栈只能在一端插入元素或删除元素，在操作时不需要改变栈底指针。栈和队列4、队列的原则是“先进先出”或“后进后出”5、循环队列的基本运算：入队运算和退队运算。6、队列允许在一端插入元素，而在另一端删除元素。7、栈和队列都可以采用：顺序方式和链式方式来存储，并且它们也属于线性表8、栈和队列都会产生“上溢”（不能插入时）和“下溢”（不能退出时）的错误。1、线性链表是指线性表的链式存储结构。线性链表2、线性表存储方式：顺序存储和链式存储3、存储结点分：数据域和指针域4、线性链表的存储空间不一定是连续的，且各元素的存储顺序是任意的1、树是非线性结构2、树的第一层的结点就是“根结点”，一棵树有且仅有一个根结点；没有后件的结点称为叶子结点（终端结点）；每个结点只有一个前件叫父结点。树3、某个结点所拥有的后件个数，称为该结点的度，而结点中最大的度称为树的度；树的最大层称树的深度（即树的总共层数）。如下图：该树的度为3，A的度为2，树的深度为3，A为树的根结点，D、E、F、G是树的叶子结点，B、C是树的子结点。AB CD E F G1、二叉树，有且仅有一个根结点，每个结点最多有两棵子树（左子树和右子树）2、满二叉树（满满的，没有任何缺省的子树）AB CD E F G满二叉树、完全二叉树性质在二叉树第K层上，最多有2K-1（K=1）个结点。性质深度为m的二叉字最多有2M-1个结点。例：若深度为5的二叉树，最多有31个结点，深度为5的二叉树，叶子结点个数为16个。（251=16）性质：在二叉树中，度为0 的结点（叶子结）总比度为2的结点多1 个Eg: 若二叉树的度为2的结点有18 个、则该二叉树的叶子结点有19个性质：具有n个结点的二叉树，其深度至少为log2n+1性质：是有n个结点的完全2叉树深度为log2n+1性质：完全二叉树有n个结点当k=1时，该结点为根结点当k1时，父结点编号为lnt(k/2)从特点上看，满二叉树也是完全二叉树，而完全二叉树不一定是满二叉树。例：完全二叉树共699个结点，它的叶子结点为350个。（699Int(699/2)）；而父结点为349个。 （int(699/2)=349）二叉树：二叉树的元素存储结点由数据域和指针域组成。 二叉树通常采用链式存储结构，满二叉树和完全二叉树也能顺序存储。二叉树遍历：前序遍历、中序遍历和后序遍历前序：ABDECF （根左右）中序：DBEACF （左根右）后序：DEBFCA （左右根）该树的宽度（度）为2，树的深度为3例： A B C D E F查找1、对于长度为n的有序线性表，最坏情况下，顺序查找需要比较n次，而二分查找比较log2n次。2、当线性表为有序表时，不管是顺序存储还是链式存储，都只能用顺序查找。排序技术交换类排序法：昌泡排序法：对于长度n的有序线性表，最坏情况下比较次数为n (n-1)/2快速排序法插入类排序法：简单插入排序法:：最坏情况下比较次数为n (n-1)/2 堆排序法：最坏情况下比较次数O (nlog2n)第二章 程序设计基础（约占4分，共2小题）程序设计方法和风格设计风格：“清晰第一、效率第二”程序注释分；序言性注释和功能性注释 原则：自顶向下、逐步求精、模快化和限制使用goto语句。结构化程序设计基本结构：顺序结构、选择结构（分支结构）和重复结构（循环结构）以上的结构都只允许有一个入口和出口结构化程序设计主要强调的是程序的易读性。 面向对象的方法的优点：与人类思维方法一致 稳定性好 可重用性好 易开发 可维护性好 易测试和调试 对象是面向对象方法中最基本的概念，对象是类的实例面向对象的程序设计对象特点：标识唯一性 分类性 多态性 封装性 模块独立好信息隐藏的概念与模块独立性直接相关，信息隐藏是通过对象的封装性来实现，对象的操作也叫方法或服务。“任何对象都必须有继承性”这句话是错误的。 在面向对象方法，类之间共享属性和操作的机制称为继承。类描述是具有相似属性和操作的一组对象第三章 软件工程基础（约占6分，共3小题）软件分两部分：机器执行的程序和数据 机器不执行的，使用有关的方法软件=程序+数据+文档软件按功能分：应用软件 系统软件 支撑软件软件工程的核心思想是强调在软件开发过程中需要应用工程化原则。软件工程的主要思想是把软件产品看作是一个工程产品来处理软件工程概念软件工程原则：抽象、信息隐蔽、模块化、局部化、确定性、一致性、完备性和可 验证性软件生命周期：将软件产品从提出、实现、使用维护到停止退役的过程。软件生命周期分：软件定义：初步计划、需求分析 软件开发：概要设计、详细设计、实现、测试 软件运行和维护：使用、维护、退役设计、编码和测试都属于软件开发阶段软件工程研究包括：软件开发技术和软件工程原理需求分析阶段工作：需求获取 需求分析 编写规格说明书 需求评审结构化分析方法需求分析法：结构化分析方法:是面向数据流的结构化分析方法，是面向数据结构Jackson方法。面向对象的分析法 静态分析法 动态分析法结构化分析常用工具：数据流图（DFD）数据字典（DD）判断树 判定表软件设计（工程角度）：概要设计（结构设计或总体设计）和详细设计软件设计（技术观点分）：结构设计、数据设计、接口设计、过程设计软件设计原理：抽象、模块化、信息隐藏和模块独立性内聚性：模块内部元素之间的紧密程度结构化设计方法耦合性：模块间互相连接的紧密程度“高内聚，低耦合”来提高模块的独立性模块为矩形表示。面向数据流的设计法，其数据流类型：变换型和事务型过程设计工具：程序流程图（PFD）、 N-S图、PAD（问题分析图）PDL（伪码或过程设计语言）它是尽可能多的发现软件中的错误软件测试方法：静态测试（人的思维）和动态测试（计算机）白盒测试：（结构测试或逻辑驱动测试）：逻辑覆盖、路径覆盖软件测试黑盒测试：（功能测试或数据驱动测试）：等价类划分法、边界值分析法、错误推测法和因果图。软件测试4步：单元测试集成测试、验收测试（确认测试）和系统测试程序调试的任务是诊断和改正程序的错误软件调试分：静态调试、动态调试软件调试方法：强行排错法 、回溯法、原因排除法 第四章 数据库设计基础（约占10分，共5小题）数据库中数据两大特点：“集成”与“共享”数据库管理系统是一个系统软件（关系数据库系统）数据库管理系统是数据库系统的核心数据库管理系统的数据语言：数据定义语言（DDL）、数据操纵语言（DML）和数据操作语言（DCL）数据库经历的3 个阶段：人工管理阶段、文件系统阶段和数据库系统阶段数据库的特点：数据集成性 数据的共享性，冗余度低 数据的独特性高数据库 数据统一管理与控制数据独立性分：物理独立性和逻辑独立性物理独立性是指当数据的存储结构（物理结构）改变时，其逻辑结构可以不变，基于逻辑结构的应用程序不必修改。逻辑独立性是指数据库的总体逻辑结构的改变，不会影响应用程序的改变。数据独立性是数据与程序间的不相互依赖性，数据的逻辑结构、存储结构与存取方式的改变不影响应用程序。数据库的三级模式：概念模式、内模式（物理模式）和外模式（子模式或用户模式） 外模式是用户的数据视图,索引属于内模式。数据库的两个级映射：概念模式到内模式的映射、外模式到概念模式的映射数据模型分三部分：数据结构、数据操作和数据约束数据模型分三类型：概念模型、逻辑模型和物理模型E-R图：实体集 属性 联系数据模型层次模型的结构是树形结构；一个二维表就是一个关系。关系模型有：查询、增加、删除和修改关系的数据约束：实体完整性约束、参照完