计算机2级C语言笔试部分分为数据结构软件工程数据库面向程序设计很详细.doc

如你想要拥有完美无暇的友谊，可能一辈子找不到朋友。 二级C语言公共基础知识之 数据结构 考点1 算法的复杂度 1．算法的基本概念 算法的基本特征：可行性、确定性、有穷性、输入（可为0）、输出(不能为0) 2．算法复杂度 包括时间复杂度和空间复杂度 名称 描述 时间复杂度 是指执行算法所需要的计算工作量 空间复杂度 是指执行这个算法所需要的内存空间 考点2 逻辑结构和存储结构 1．逻辑结构 2．存储结构 考点3 线性结构和非线性结构 根据数据结构中各数据元素之间前后件关系的复杂程度 一般将数据结构分为两大类型：线性结构与非线性结构 如果一个非空的数据结构满足下列两个条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件 也最多有一个后件 则称该数据结构为线性结构 线性结构又称线性表 在一个线性结构中插入或删除任何一个结点后还应是线性结构 栈、队列、串等都线性结构 如果一个数据结构不是线性结构 则称之为非线性结构 数组、广义表、树和图等数据结构都是非线性结构 考点4 栈 1．栈的基本概念 栈（stack）是一种特殊的线性表 是限定只在一端进行插入与删除的线性表 在栈中 一端是封闭的 既不允许进行插入元素 也不允许删除元素；另一端是开口的 允许插入和删除元素 通常称插入、删除的这一端为栈顶 另一端为栈底 当表中没有元素时称为空栈 栈顶元素总是后被插入的元素 从而也是最先被删除的元素；栈底元素总是最先被插入的元素 从而也是最后才能被删除的元素 先进后出或后进先出 2．栈的顺序存储及其运算 栈的基本运算有三种：入栈、退栈与读栈顶元素 （1）入栈运算：入栈运算是指在栈顶位置插入一个新元素 （2）退栈运算：退栈是指取出栈顶元素并赋给一个指定的变量 （3）读栈顶元素：读栈顶元素是指将栈顶元素赋给一个指定的变量 考点5 队列 1．队列的基本概念 队列是只允许在一端进行删除 在另一端进行插入的顺序表 通常将允许删除的这一端称为队头 允许插入的这一端称为队尾 当表中没有元素时称为空队列 队列的修改是依照先进先出的原则进行的 因此队列也称为先进先出的线性表 或者后进后出的线性表 例如：火车进遂道 最先进遂道的是火车头 最后是火车尾 而火车出遂道的时候也是火车头先出 最后出的是火车尾 若有队列：Q =（q1 q2 ... qn） 那么 q1为队头元素（排头元素） qn为队尾元素 队列中的元素是按照q1 q2 ... qn的顺序进入的 退出队列也只能按照这个次序依次退出 即只有在q1 q2 ... qn-1 都退队之后 qn才能退出队列 因最先进入队列的元素将最先出队 所以队列具有先进先出的特性 体现先来先服务的原则 队头元素q1是最先被插入的元素 也是最先被删除的元素 队尾元素qn是最后被插入的元素 也是最后被删除的元素 先进先出 入队运算为往队列队尾插入一个数据元素 退队运算为从队列的队头删除一个数据元素 考点6 链表 在链式存储方式中 要求每个结点由两部分组成：一部分用于存放数据元素值 称为数据域 另一部分用于存放指针 称为指针域 其中指针用于指向该结点的前一个或后一个结点（即前件或后件） 链式存储方式既可用于表示线性结构 也可用于表示非线性结构 （1）线性链表 线性表的链式存储结构称为线性链表 在某些应用中 对线性链表中的每个结点设置两个指针 一个称为左指针 用以指向其前件结点；另一个称为右指针 用以指向其后件结点 这样的表称为双向链表 在线性链表中 各数据元素结点的存储空间可以是不连续的 且各数据元素的存储顺序与逻辑顺序可以不一致 在线性链表中进行插入与删除 不需要移动链表中的元素 （2）带链的栈 栈也是线性表 也可以采用链式存储结构 带链的栈可以用来收集计算机存储空间中所有空闲的存储结点 这种带链的栈称为可利用栈 考点7 二叉树及其基本性质 1、二叉树及其基本概念 二叉树是一种很有用的非线性结构 具有以下两个特点： ①非空二叉树只有一个根结点； ②每一个结点最多有两棵子树 且分别称为该结点的左子树和右子树 在二叉树中 每一个结点的度最大为2 即所有子树（左子树或右子树）也均为二叉树 另外 二叉树中的每个结点的子树被明显地分为左子树和右子树 在二叉树中 一个结点可以只有左子树而没有右子树 也可以只有右子树而没有左子树 当一个结点既没有左子树也没有右子树时 该结点即为叶子结点 父结点（根） 　　在树结构中 每一个结点只有一个前件 称为父结点 没有前件的结点只有一个 称为树的根结点 简称树的根 例如 在图1-1中 结点A是树的根结点 子结点和 叶子结点 　　在树结构中 每一个结点可以有多个后件 称为该结点的子结点 没有后件的结点称为叶子结点 例如 在图1-1中 结点D E F均为叶子结点 度 　　在树结构