二级基础知识数据结构与算法.ppt

**二级基础知识第一章数据结构与算法全国计算机等级考试1.1算法一、算法的概念解决问题准确而完整的描述。特征：可行性、确定性、有穷性、拥有足够的情报。要素：对数据运算操作（算术、逻辑）通过指令序列程序来实现、算法的控制结构（执行顺序）。算法设计方法：列举法：列举所有可能归纳法：从特殊到一般递推：从条件到结论递归：函数的自调用减半递推：中间分冶回溯:反证二、算法复杂度1、时间复杂度（工作量）平均性态（平均值）；最坏情况（最大值）2、空间复杂度（资源）内存资源1.2数据结构的基本概念研究数据结构——逻辑结构、物理结构、运算的实现1、数据结构数据逻辑结构：数据元素及元素间的关系，B=(D,R)存储结构：内存中的存放形式线性与非线性结构：有且仅有一个根结点；一个前件，一个后件只有一个根结点不是线性结构1.3线性表及其顺序存储结构线性表：连续顺序存储，逻辑结构与存储结构一致。插入运算：插入点起所有元素后移删除运算：删除点后所有元素前移1.4栈和队列1、栈只有一个出入口仅有一个元素宽度的巷道， 先进后出入栈、退栈、读栈顶元素2、队列一个出口一个入口仅有一个元素宽度的巷道，先进先出队列移动，循环标志s0空入队；上溢、退队；下溢1.5线性链表线性表的缺点：插入删除上的复杂性、空间的连续性（预留、不够）结点：元素+指针Head---a1*a2---a2*a3…annull双链表栈与队列的链表实现链表的插入删除改变前后元素的指针指向，可以不改变位置循环链表：增加一个表头结点数据不定,最后一指针指向表头1.6树与二叉树1、树层次结构根结点、叶子结点、子结点、深度（层数）、节点的度（分叉数）了解表达式的树表示2、二叉树分叉数少于等于2（左右子树）,一个根节点是二叉树性质A、k层节点少于2^(k-1)B、m深度的树节点总数为2^m-1C、度为2的比度为0节点多一个d、节点为n，则深度为int(log2N)+13、满二叉树与完全二叉树满二叉树不缺枝完全二叉树：仅缺右子树注意完全二叉树节点编号间关系4、二叉树的存储采用双链表5、二叉树的遍历遍历：不重复访问所有结点前序：根、左、右中序：左、根、右后序：左、右、根注意从上到下均按上述顺序例1.33b左前：abdhiejkcflg；中:hdibjekalfcg后:hidjkeblfgca**