发布时间 : 星期三 文章全国计算机二级教案更新完毕开始阅读
全国计算机二级教案 计算机等级考试二级公共基础
第1章：数据结构与算法
1.1算法
1:算法的基本概念
算法: 是指解题方案的准确而完整的描述.
算法的可解: 对于一个问题,如果可以通过一个-计算机程序,在有限的存储空间内运行有限长的时间而得到正确的结果. 通常,程序的编制不可能优于算法的设计.
算法的基本特征:①可行性 ② 确定性 ③ 有穷性 ④ 拥有足够的情报
算法的基本要素:① 算法中对数据的运算和操作:算术运算,逻辑运算,关系运算,数据传输
② 算法的控制结构:顺序结构,选择结构,循环结构
算法的基本方法:① 列举法 ② 归纳法 ③ 递推法 ④ 递归法 ⑤ 减半递推技术 ⑥ 回溯法 2 算法的复杂度
算法的复杂度:主要包括时间和空间复杂度
算法的时间复杂度:是指执行算法所要的计算工作量.
有两种方法分析算法的工作量:① 平均性态 ② 最坏情况复杂性 算法的空间复杂度:是指执行这个算法所要的内存空间大小.
1.2数据结构的基本概念
数据结构主要研究如下三个方面的内容:
㈠ 各数据元素之间的固有的逻辑关系,即数据的逻辑结构 ㈡ 各数据元素在计算机中的存储关系,即数据的存储结构
㈢ 对各种数据结构进行运算
数据结构主要研究的目的:提高数据处理的效率.(① 数据处理速度 ② 节省处理过程中的存储空间) 1．2．1什么是数据结构
数据结构是指对数据集合中的各元素以以各种方式进行运算，（插入、删除、查找、更改）等。 （简单说：数据结构是指相互有关联的数据元素的集合） 例：无序表的顺序查找与有序表的对分查找。 1：无序表 3 5 1 2：有序表（查词典） 5 7 8 4 42 53 45 2 65 56 75 0 84 由此可看出数据元素在表中的排列顺序对查效率是有很大的影响。 数据元素：现实世界中客观存在的一切个体都可以是数据元素。 一年四季（春、夏、秋、冬） 一年12月（1、2、3、4。。。。。） 数值
家庭成员（父亲、儿子、女儿）
客观存在的事件（一次演出、一次借书、一次比赛。。。。）
各数据元素一般具有某种共同特征、人们不会同时处理特征完全不同的没有任何关系和各类元素。
1：数据的逻辑结构
数据结构是是带有结构的数据元素的集合，结构实际上是数据元素之间的前后件关系。 一个数据结构应包含两个方面的信息：
1：数据元素的信息 2：数据元素之间的前后件关系（逻辑关系） 数据逻辑结构有两个要素：
一是数据元素的集合，通常记为D
二是D上的关系即元素之间的前后件的关系，通常记为R。 一个数据结构可以表示成：B=（D，R）
一年四季的数据结构可以表示成：
B=（D，R）
D=（春、夏、秋、冬）
R={（春、夏），（夏、秋），（秋、冬）} 家庭成员：
B=（D，R）
D=（父亲、儿子、女儿）
R={（父亲，儿子），（父亲，女儿）}
2：数据的存储结构
概念：数据的逻辑结构在计算机的表示。
一个数据结构中的各数据元素在计算机存储空间中的位置关系与逻辑关系有可能不同
例：在家庭成员中“儿子”，“女儿”都是“父亲”的后件，但在计算机存储空间中根本不可能将 “儿子”，“女儿”放在父亲的后面的。
常用的数据存储结构有：顺序、链接、索引等。采用不同的存储结构，其数据处理效率是不同的。 1．2．2数据结构的图形表示
一个数据结构除了用二元关系表示外，还可以直观用图形表示。 例：一年四季：
根结点
春□夏□秋□冬 □父亲 终结点
儿子 女儿
在数据结构中，没有前件的结点称为根结点；没有后件的结点称为终端结点（也称叶子结点）
1.2.3线性结构与非线性结构
空的数据结构:在一个数据结构中一个元素都有没有
根据数据结构中各数据元素之间前后件的复杂程序,一般将数据结构分为:线性与非线性结构. 1:线性结构:
如果一个非空的数据结构满足以下条件:
A:有且只有一个根结点,B:每一个结点最多有一个前件,也最多有一个后件 所以”一个四季”是线性结构,”家庭成员”则是非线性结构 1.3 线性表及其顺序存储结构
1.3.1线性表的基本概念
线性表是最简单、最常用的一种数据结构 一个线性表可表示成：（A1，A2，A3，…….An） 显然线性表是一种线性结构。 非空线性表有如下一些特征：
A：有且只有一个根结点，它无前件
B：有且只有一个终端结点，它无后件
C：除根结点与终端结点外，其他所有结点有且只有一个前件，也有且只有一个后件。 线性表中结点的个数N称为线性表的长度。当N=0时，称为空表
1．3．2 线性表的顺序存储结构
线性表的存储结构具有以下两个特点 A：所有元素所占的存储空间是连续的
B：各数据元素在存储空间中是按逻辑顺序依次存放的。
假设线性表中的第一个数据元素存储地址为：a1，每个元素占用k个字节，则第i个元素ai在计算机 中的存储地址为：a1+(i-1)k
可以对线性表作以下处理：
插入、删除、查找、排序、分解、合并、复制、逆转等 1.3.3 顺序表的插入与删除运算
12 32 13 14 15 32 42 33 35 插入则有”溢出”
12 可 插 入 以
32 元素
13 14 15 32 42
线性表的顺序存储结构对于小线性表或者其中元素不常动的线性表来说是合适的.
但这咱顺序存储的方式对经常要变动的大线性表就不适合了,因为插入与删除效率比较低.
栈和队列
1:什么是栈
栈实际上也是线性表,只不过是一种特殊的线性表.在这种线性表中, 其插入与删除运算只能 在线性表的一端进行.
栈是限定在一端进行插入与删除的线性表 入栈:往栈中插入一个元素 退栈:从栈中删除一个元素
2:队列
队列:加入的元素总是插入到线性表的末尾,并且又总是从线性表的头部出(删除)元素 队尾:允许插入的一端,尾指针总是指向最后被插入的元素. 队头:允许删除一端.
退队 A B C D E F G 入队 队头 队尾 入队：往队列的队尾插入一个元素
退队：从队列的排头删除一个元素
循环队列：是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。 1．5线性链表
1：线性链表：线性表的存储结构
为了存储线性表中的每个元素，一方面要存储数据元素的值，另一方面要存储各数据元素之间的前后件关系。
存储序 1 2 3 HEAD 数据1 数据2 数据域 指针域 号
NULL
这种线性表为单链表。在这种链表中，每一个结点只有一个指针域，由这个指针只能找到后件结点，不能找到前面的结点。为了弥补单链表的这个缺点，在某些应用中采用双向链表。 2：带链的栈
栈的链式存储结构基本上和线性表的链式存储结构相同。只是线性链表的链式存储结构的头指针变成了栈的链式结构的栈顶指针。
3：带链的队列
队列的链式存储结构基本上和线性表的链式存储结构也基本相同。只不过队列的链式结构保持有两个指针：一个指向队列头的头指针和一个指向队列尾的尾指针。 4：线性链表的基本运算