二级C语言基础知识.doc

第1章数据结构与算法
算法复杂度、数据结构的概念、栈、二叉树的遍历、二分法查找
、算法时间复杂度及空间复杂度的概念
、数据逻辑结构及物理结构的定义
、线性链表的存储方式
、二叉树的基本性质、完全二叉树的概念、二叉树的遍历



考点1 算法的基本概念
:可行性、确定性、有穷性、拥有足够的情报。
:
(1)算法中对数据的运算和操作
一个算法由两种基本要素组成:一是对数据对象的运算和操作;二是算法的控制结构。
在一般的计算机系统中,基本的运算和操作有以下4类:算术运算、逻辑运算、关系运算和数据传输。
(2)算法的控制结构:算法中各操作之间的执行顺序称为算法的控制结构。
描述算法的工具通常有传统流程图、N-S结构化流程图、算法描述语言等。一个算法一般都可以用顺序、选择、循环3种基本控制结构组合而成。
考点2 算法复杂度

算法的时间复杂度是指执行算法所需要的计算工作量。
算法的工作量=f(n)其中n是问题的规模

算法的空间复杂度是指执行这个算法所需要的内存空间。
数据结构的基本概念
考点3 数据结构的定义
三个方面:
(1)数据的逻辑结构;
(2)数据的存储结构;
(3)对各种数据结构进行的运算。
数据的逻辑结构有两个要素:一是数据元素的集合,通常记为D;二是D上的关系,它反映了数据元素之间的前后件关系,通常记为R。一个数据结构可以表示成 B=(D,R)
在数据的存储结构中,不仅要存放各数据元素的信息,还需要存放各数据元素之间的前后件关系的信息。
一种数据的逻辑结构根据需要可以表示成多种存储结构,采用不同的存储结构,其数据处理的效率是不同的。因此选择合适的存储结构是很重要的。

考点5 栈及其基本运算

栈是限定只在一端进行插入与删除的线性表。
通常称插入、删除的这一端为栈顶,另一端为栈底。
当表中没有元素时称为空栈。
"先进后出"

用一维数组S(1∶m)作为栈的顺序存储空间,其中m为最大容量,S(bottom)为栈底元素,S(top)为栈顶元素。top=0表示栈空;top=m表示栈满。
栈的基本运算有三种:入栈、退栈与读栈顶元素。
(1)入栈运算:入栈运算是指在栈顶位置插入一个新元素。首先将栈顶指针加一(即top加1),然后将新元素插入到栈顶指针指向的位置。当栈顶指针已经指向存储空间的最后一个位置时,说明栈空间已满,不可能再进行入栈操作。这种情况称为栈"上溢"错误。
(2)退栈运算:退栈是指取出栈顶元素并赋给一个指定的变量。首先将栈顶元素(栈顶指针指向的元素)赋给一个指定的变量,然后将栈顶指针减一(即top减1)。当栈顶指针为0时,说明栈空,不可进行退栈操作。这种情况称为栈的"下溢"错误。
(3)读栈顶元素:读栈顶元素是指将栈顶元素赋给一个指定的变量。这个运算不删除栈顶元素,只是将它赋给一个变量,因此栈顶指针不会改变。当栈顶指针为0时,说明栈空,读不到栈顶元素。
考点6 线性链表的基本概念
链式存储方式既可用于表示线性结构,也可用于表示非线性结构。
(1)线性链表
线性表的链式存储结构称为线性链表。
(2)带链的栈
栈也是线性表,也可以采用链式存储结构。
疑难解答:在链式结构中,存储空间位置关系与逻辑关系是什么?
在链式存储结构中,存储数据结构的存储空间可以不连续,各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致,而数据元素之间的逻辑关系是由指针域来确定的。

考点7 树与二叉树及其基本性质
误区警示:
满二叉树也是完全二叉树,而完全二叉树一般不是满二叉树。应该注意二者的区别。
1、树的基本概念
树(tree)是一种简单的非线性结构。在树结构中,每一个结点只有一个前件,称为父结点,没有前件的结点只有一个,称为树的根结点。每一个结点可以有多个后件,它们称为该结点的子结点。没有后件的结点称为叶子结点。
在树结构中,一个结点所拥有的后件个数称为该结点的度。叶子结点的度为0。在树中,所有结点中的最大的度称为树的度。
2、二叉树及其基本性质
(1)二叉树的定义
二叉树是一种很有用的非线性结构,
两个特点:
①非空二叉树只有一个根结点;
②每一个结点最多有两棵子树,且分别称为该结点的左子树和右子树。
每一个结点的度最大为2,即所有子树(左子树或右子树)也均为二叉树,而树结构中的每一个结点的度可以是任意的。
(2)二叉树的基本性质
二叉