下载文档原格式
全国计算机等级考试——二级公共基础知识辅导讲义目录第一章数据结构与算法11.1 算法11.2 数据结构的基本概念11.3 线性表与其顺序存储结构21.4 栈和队列21.5 线性链表21.6 树与二叉树41.7 查找技术51.8 排序技术6本章应考点拨6第二章程序设计基础62.1 程序设计风格62.2 结构化程序设计（面向过程的程序设计方法）72.3 面向对象的程序设计7本章应考点拨8第三章软件工程基础83.1 软件工程基本概念83.2 结构化分析方法103.3 结构化设计方法113.4 软件测试123.5 程序的调试14本章应考点拨15第四章数据库设计基础154.1 数据库系统的基本概念154.2 数据模型174.3 关系代数194.4 数据库设计方法和步骤20本章应考点拨20第一章数据结构与算法1.1 算法1骤的一种描述。
*：算法不等于程序，也不等于计算方法。
程序的编制不可能优于算法的设计。
2、算法的基本特征（1）可行性。
针对实际问题而设计的算法，执行后能够得到满意的结果。
（2）确定性。
每一条指令的含义明确，无二义性。
并且在任何条件下，算法只有唯一的一条执行路径，即一样的输入只能得出一样的输出。
（3）有穷性。
算法必须在有限的时间完成。
有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间完成。
（4）拥有足够的情报。
算法中各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据。
因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。
当输入不够或输入错误时，算法将无法执行或执行有错。
一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。
*：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。
3、算法复杂度主要包括时间复杂度和空间复杂度。
全国计算机等级考试——二级公共基础知识辅导讲义第一章数据结构与算法1.1 算法1描述。
*:算法不等于程序,也不等于计算方法。
程序的编制不可能优于算法的设计。
2、算法的基本特征(1可行性。
针对实际问题而设计的算法,执行后能够得到满意的结果。
(2确定性。
每一条指令的含义明确,无二义性。
并且在任何条件下,算法只有唯一的一条执行路径,即相同的输入只能得出相同的输出。
(3有穷性。
算法必须在有限的时间内完成。
有两重含义,一是算法中的操作步骤为有限个,二是每个步骤都能在有限时间内完成。
(4拥有足够的情报。
算法中各种运算总是要施加到各个运算对象上,而这些运算对象又可能具有某种初始状态,这就是算法执行的起点或依据。
因此,一个算法执行的结果总是与输入的初始数据有关,不同的输入将会有不同的结果输出。
当输入不够或输入错误时,算法将无法执行或执行有错。
一般说来,当算法拥有足够的情报时,此算法才是有效的;而当提供的情报不够时,算法可能无效。
*:综上所述,所谓算法,是一组严谨地定义运算顺序的规则,并且每一个规则都是有效的,且是明确的,此顺序将在有限的次数下终止。
3、算法复杂度主要包括时间复杂度和空间复杂度。
(1算法时间复杂度是指执行算法所需要的计算工作量,可以用执行算法的过程中所需基1.2 数据结构的基本概念12、数据结构主要研究和讨论以下三个方面的问题:(1数据集合中各数据元素之间所固有的逻辑关系,即数据的逻辑结构。
数据的逻辑结构包含:1表示数据元素的信息;2表示各数据元素之间的前后件关系。
(2在对数据进行处理时,各数据元素在计算机中的存储关系,即数据的存储结构。
数据的存储结构有顺序、链接、索引等。
1顺序存储。
它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里,结点间的逻辑关系由存储单元的邻接关系来体现。
由此得到的存储表示称为顺序存储结构。
2链接存储。
它不要求逻辑上相邻的结点在物理位置上亦相邻,结点间的逻辑关系是由附加的指针字段表示的。
目录全国计算机等级考试——二级公共基础知识辅导讲义 (1)第一章数据结构与算法 (1)第二章程序设计基础 (7)第三章软件工程基础 (9)第四章数据库设计基础 (16)任课教师：田密作者介绍：田密，男，延安职业技术学院计算机等级考试二级辅导主讲教师。
联系方式：Email：tianmizr@QQ：6009265欢迎大家多多与我交流，提出你们对课程的意见和建议！第一章数据结构与算法1.1算法1步骤的一种描述。
G：算法不等于程序，也不等于计算方法。
程序的编制不可能优于算法的设计。
2、算法的基本特征（1）可行性。
针对实际问题而设计的算法，执行后能够得到满意的结果。
（2）确定性。
每一条指令的含义明确，无二义性。
并且在任何条件下，算法只有唯一的一条执行路径，即相同的输入只能得出相同的输出。
（3）有穷性。
算法必须在有限的时间内完成。
有两重含义，一是算法中的操作步骤为有限个，二是每个步骤都能在有限时间内完成。
（4）拥有足够的情报。
算法中各种运算总是要施加到各个运算对象上，而这些运算对象又可能具有某种初始状态，这就是算法执行的起点或依据。
因此，一个算法执行的结果总是与输入的初始数据有关，不同的输入将会有不同的结果输出。
当输入不够或输入错误时，算法将无法执行或执行有错。
一般说来，当算法拥有足够的情报时，此算法才是有效的；而当提供的情报不够时，算法可能无效。
G：综上所述，所谓算法，是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。
3、算法复杂度主要包括时间复杂度和空间复杂度。
（1）算法时间复杂度是指执行算法所需要的计算工作量，可以用执行算法的过程中所需基本运算的执行次数来度量。
（21.2数据结构的基本概念12、数据结构主要研究和讨论以下三个方面的问题：（1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构。
数据的逻辑结构包含：1）表示数据元素的信息；2）表示各数据元素之间的前后件关系。
公共基础在所有的二级考试科目中都占30分。
在试卷当中，前十道选择题和前五道填空题均是公共基础内容。
公共基础讲义数据结构与算法（约占10分）程序设计基础（约占4分）软件工程基础（约占8分）数据库设计基础（约占8分）第一章数据结构基础本章内容提要●算法:算法的基本概念、算法复杂度●数据结构的基本概念：什么是数据结构、数据结构的图形表示、线性结构与非线性结构●线性表及其顺序存储结构：线性表的基本概念、顺序存储结构、插入运算、删除运算●栈和队列：栈及其基本运算、队列及其基本运算●线性链表：基本概念、基本运算、循环链表及其基本运算●树与二叉树：树的基本概念、二叉树及其基本性质、二叉树的存储结构、二叉树的遍历●查找技术：顺序查找、二分法查找●排序技术：交换类排序法、插入类排序法、选择类排序法算法1.算法的基本概念：算法是解题方案的准确而完整的描述。
算法规定了解决某类问题所需的操作语句以及执行顺序，使其能够通过有限的指令语句，在一定时间内解决问题。
算法是一个操作序列，有限长度，目的是解决某类问题。
注意：（1）算法不等同于程序：因为程序的编制不可能由于算法的设计；（2）算法也不等同于数学上的计算方法：因为很多数学计算公式也许无法在计算机上实现。
2.算法的基本特征（算法具有动态性）：可行性、确定性、有穷性、拥有足够的情报（指的是有输入有输出）在设计一个算法时，必须要考虑算法的执行过程保证结果的可靠性。
3.算法的基本要素：第一要素：对数据对象的运算和操作1)算术运算 + - * /2)逻辑运算 NOT AND OR3)关系运算 > < <>4)数据传输赋值，输入与输出第二要素：算法的控制结构（决定了算法中各操作的执行顺序）顺序、选择、循环4.算法设计的基本方法（计算机解题的过程实际上是在实施某种算法）1)列举法（列举所有解决方案）根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。
