文档介绍：Forpersonaluseonlyinstudyandresearch;mercialuse绪论基本概念和术语数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。术语:数据、数据元素、数据对象、数据结构、抽象数据类型、算法。数据结构的形式定义(二元组)数据的逻辑结构:(四类基本结构)线性结构、树型结构、图状结构、集合它们各自的特性?数据的存储结构(物理结构):主要有顺序存储结构(以存储地址相邻来表示逻辑上的相邻关系),链式存储结构(用指针来指示逻辑上的相邻关系)抽象数据类型(三元组)算法的定义,算法的5个重要特性。算法的时间复杂度和空间复杂度算法的评价:正确性、可读性、健壮性、高效率、低存储量求语句频度、时间复杂度线性表线性表的定义线性结构的特点线性表的存储结构顺序存储结构(顺序表):随机存取插入/删除元素时,需移动元素的次数。链式存储结构(链表,分为单(向)链表、双(向)链表):非随机存取(顺序存取)带头结点的链表和不带头结点的链表;循环/非循环的链表;链表空与非空的情况(判断条件)。两种存储结构的优缺点比较,各适合那些场合。线性表操作的实现(算法描述)插入元素、删除元素、查找、判表是否满足某种特性、逆置等。例:判断题:。:每个结点有且仅有一个直接前驱和一个直接后继。。选择题:线性表L在()情况下适于使用链表结构实现。、:,在第i个元素前插入一个元素需移动个元素,要删除第i个元素,需移动个元素。(由指针p指示)之后插入s指针所指结点的操作是:;;;;。栈和队列栈栈的定义、特点(后进先出)栈的存储结构:顺序存储结构链式存储结构栈的应用:二叉树的先序、中序、后序遍历算法图的深度优先遍历算法(将递归算法改写为非递归算法可借助栈来完成;递归算法的执行需用栈来实现。)队列队列的定义、特点(先进先出)队列的存储结构:顺序存储结构(循环队列),链式存储结构队列的应用:二叉树层序遍历算法图的广度优先遍历算法循环队列:·队空、队满的判断条件·求队列的长度例:判断题:因为栈是特殊的线性表,所以对线性表的所有操作都可以用于对栈操作。填空题:循环队列队满的条件是。串数组和广义表树和二叉树树、二叉树的定义二叉树二叉树的性质(5条)二叉树的存储结构:顺序存储结构(按完全二叉树层序存放)链式存储结构(二叉链表、三叉链表)(空链域的个数)遍历二叉树:先序、中序、后序、层序应用:给定二叉树的先序和中序(或后序和中序)序列,画出相应的二叉树。树和森林树的存储结构:双亲表示法孩子表示法孩子-兄弟(二叉树)表示法树(森林)与二叉树的相互转换树的遍历:先根、后根次序遍历森林的遍历:先序、中序遍历赫夫曼树及其应用构造最优二叉树(赫夫曼树),求WPL赫夫曼编码各种二叉树概念的区分满二叉树(若深度为k,结点数?)完全二叉树(若深度为k,结点数至多、至少?)正则二叉树(严格二叉树)(若深度为k,结点数至多、至少?)最优二叉树(折半查找的)判定树二叉排序(二叉查找树)树平衡二叉树堆二叉树有关的递归算法例:判断题: