文档介绍：专业资料参考首选 2011 计算机等考二级公共基础知识讲义汇总第一章数据结构与算法第1节算法第2节数据结构的基本概念第3节线性表及其顺序存储结构第4节栈和队列第5节线性链表第6节树与二叉树第 7/8 节查找技术与排序技术第二章程序设计基础第1节程序设计风格第2节结构化程序设计第3节面向对象的程序设计专业资料参考首选公共基础知识基本要求 1. 掌握算法的基本概念。 2. 掌握基本数据结构及其操作。 3. 掌握基本排序和查找算法。 4. 掌握逐步求精的结构化程序设计方法。 5. 掌握软件工程的基本方法,具有初步应用相关技术进行软件开发的能力。 6. 掌握数据库的基本知识,了解关系数据库的设计。考试内容一、基本数据结构与算法 1. 算法的基本概念; 算法复杂度的概念和意义( 时间复杂度与空间复杂度)。 2. 数据结构的定义; 数据的逻辑结构与存储结构; 数据结构的图形表示; 线性结构与非线性结构的概念。 3. 线性表的定义; 线性表的顺序存储结构及其插入与删除运算。 4. 栈和队列的定义; 栈和队列的顺序存储结构及其基本运算。 5. 线性单链表、双向链表与循环链表的结构及其基本运算。 6. 树的基本概念; 二叉树的定义及其存储结构; 二叉树的前序、中序和后序遍历。 7. 顺序查找与二分法查找算法; 基本排序算法( 交换类排序, 选择类排序, 插入类排序)。二、程序设计基础 1. 程序设计方法与风格。 2. 结构化程序设计。 3. 面向对象的程序设计方法,对象,方法,属性及继承与多态性。三、软件工程基础 1. 软件工程基本概念,软件生命周期概念,软件工具与软件开发环境。 2. 结构化分析方法,数据流图,数据字典,软件需求规格说明书。专业资料参考首选 3. 结构化设计方法,总体设计与详细设计。 4. 软件测试的方法, 白盒测试与黑盒测试, 测试用例设计, 软件测试的实施, 单元测试、集成测试和系统测试。 5. 程序的调试,静态调试与动态调试。四、数据库设计基础 1. 数据库的基本概念:数据库,数据库管理系统,数据库系统。 2. 数据模型,实体联系模型及 E-R 图,从 E-R 图导出关系数据模型。 3. 关系代数运算,包括集合运算及选择、投影、连接运算,数据库规范化理论。 4. 数据库设计方法和步骤:需求分析、概念设计、逻辑设计和物理设计的相关策略。考试方式公共基础知识有 10 道选择题和 5 道填空题共三十分。第一章数据结构与算法 算法算法:是指解题方案的准确而完整的描述。算法不等于程序,也不等计算机方法,程序的编制不可能优于算法的设计。算法的基本特征: 是一组严谨地定义运算顺序的规则, 每一个规则都是有效的, 是明确的,此顺序将在有限的次数下终止。特征包括: (1) 可行性; (2) 确定性,算法中每一步骤都必须有明确定义,不充许有模棱两可的解释,不允许有多义性; (3) 有穷性,算法必须能在有限的时间内做完,即能在执行有限个步骤后终止,包括合理的执行时间的含义; (4) 拥有足够的情报。算法的基本要素:一是对数据对象的运算和操作; 二是算法的控制结构。指令系统:一个计算机系统能执行的所有指令的集合。专业资料参考首选基本运算和操作包括:算术运算、逻辑运算、关系运算、数据传输。算法的控制结构:顺序结构、选择结构、循环结构。算法基本设计方法:列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度:算法时间复杂度和算法空间复杂度。算法时间复杂度是指执行算法所需要的计算工作量。算法空间复杂度是指执行这个算法所需要的内存空间。 数据结构的基本基本概念数据结构研究的三个方面: (1) 数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构; (2) 在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构; (3) 对各种数据结构进行的运算。数据结构是指相互有关联的数据元素的集合。数据的逻辑结构包含: (1) 表示数据元素的信息; (2) 表示各数据元素之间的前后件关系。数据的存储结构有顺序、链接、索引等。线性结构条件: (1) 有且只有一个根结点; (2) 每一个结点最多有一个前件,也最多有一个后件。非线性结构:不满足线性结构条件的数据结构。 线性表及其顺序存储结构线性表由一组数据元素构成, 数据元素的位置只取决于自己的序号, 元素之间的相对位置是线性的。在复杂线性表中, 由若干项数据元素组成的数据元素称为记录, 而由多个记录构成的线性表又称为文件。专业资料参考首选非空线性表的结构特征: (1) 且只有一个根结点 a1 ,它无前件; (2) 有且只有一个终端结点 an ,它无后件; (3) 除根结点与终端结点外,其他所有结点有且只有一个前件,也有且只有一个后件。结点个数 n 称为线性表的长度,当