全国计算机等级考试二级(c语言)考点解析 第二部分_数据结构.doc

考点1算法的基本概念是对特定问题求解步骤的一种描述，算法是指令的有限序列，其中每一条指令表示一个或多个操作。基本特征：（1）可行性（2）确定性（3）有穷性（4）有足够的情报【（4）输入（5）输出】基本方法：（1）列举法（2）归纳法（3）递推法（4）递归（5）减半递推技术（6）回溯法设计要求：（1）正确性（2）可读性（3）健壮性（4）效率与低存储量要求时间复杂度：一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)空间复杂度：指算法在计算机内执行时所需存储空间的度量。记作 S(n)=O(f(n)考点2数据结构的基本概念数据的逻辑结构：集合、线性结构、树形结构和图（网）状结构。数据的存储结构：数据的逻辑结构在计算机中的映像，也称为数据的物理结构。通常有顺序、链接、散列和索引等结构。考点3线性表及顺序存储结构线性表：n（0）个数据元素的有限序列顺序存储结构：将线性表中的元素相继存放在一个连续的存储空间顺序存储方式：LOC(a i+1) = LOC( a i )+lLOC(a i) = LOC(a1)+(i-1)*l 顺序的插入：算法的复杂度E=n/2顺序的删除：算法的复杂度E=（n-1）/2考点4栈和队列栈：限定仅在表尾进行插入或删除操作的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)特点：后进先出 (LIFO)队列：只允许在表的一端进行插入，而在另一端删除元素的线性表。在队列中，允许插入的一端叫队尾（rear）允许删除的一端称为对头(front)。特点：先进先出 (FIFO)考点5树与二叉树树的定义：由 n (n 0) 个结点的有限集合。如果 n = 0，称为空树；如果 n 0，则有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n 1，除根以外的其它结点划分为 m (m 0) 个互不相交的有限集 T1,T2 ,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)二叉树：另一种树型结构，它是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。 特点：每个结点至多只有两棵子树（二叉树中不存在度大于2的结点）五种形态：LLRR性质1：在二叉树的第 i 层上至多有 2i 1个结点。性质2 ：深度为 k 的二叉树至多有 2 k-1个结点(k 1)。性质3：对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0n21.满二叉树 (Full Binary Tree) ：一棵深度为k且有2 k-1个结点的二叉树称为满二叉树。完全二叉树 (Complete Binary Tree)：若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层 (0 h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。621754389101112完全二叉树2154367非完全二叉树216543非完全二叉树考点6二叉树的遍历（重点）1、 前序遍历方法：若二叉树为空，则执行空操作。否则：（1） 访问根节点；（2） 前序遍历左子树；（3） 前序遍历右子树；2、 中序遍历方法：若二叉树为空，则执行空操作。否则：（1） 中序遍历左子树；（2） 访问根节点；（3） 中序遍历右子树；3、 后续遍历方法：若二叉树为空，则执行空操作。否则（1） 后序遍历左子树；（2） 后序遍历右子树；（3） 访问根节点；例：ABCDEF前序遍历：ABDECF中序遍历：DBEACF后序遍历：DEBFCA考试常出题型：给定二叉树的某两种遍历顺序，求另外一种遍历顺序。考点6查找技术顺序查找、二分法查找。考