杭州电子科技大学 数据结构 期末复习 大纲 习题.doc

第一章第一章绪论绪论 杭州电子科技大学杭州电子科技大学一．一． 基本概念和术语基本概念和术语数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科术语：数据、数据元素、数据对象、数据结构、抽象数据类型、算法数据结构的形式定义（二元组）数据的逻辑结构：线性结构 非线性结构数据的存储结构（物理结构）：主要有顺序存储结构 链式存储结构抽象数据类型（三元组）算法（5 个重要特性）二．二． 算法的时间复杂度和空间复杂度算法的时间复杂度和空间复杂度算法的评价：正确性、可读性、健壮性、高效率、低存储量第二章第二章线性表线性表一．一． 线性表的定义线性表的定义线性结构的特点二．二． 线性表的存储结构线性表的存储结构1． 顺序存储结构（顺序表）插入/删除元素时，需移动元素2． 链式存储结构（链表，分为单向链表、双向链表）带头结点的链表和不带头结点的链表；循环链表；链表空与非空的情况3． 两种存储结构的优缺点比较，各适合那些场合三．三． 线性表操作的实现（算法描述）线性表操作的实现（算法描述）插入元素、删除元素、查找、判表是否满足某种特性例：例：判断题：1. 线性表的逻辑顺序与存储顺序总是一致的。

F2. 线性结构的基本特征是：每个结点有且仅有一个直接前驱和一个直接后继F3. 线性表的链式存储结构优于顺序存储结构F选择题：线性表 L 在( B )情况下适于使用链表结构实现A. 不需修改 L 的结构 B. 需不断对 L 进行删除、插入C. 需经常修改 L 中结点值 D. L 中含有大量结点填空题：1. 对于顺序表中，在第 i 个元素前插入一个元素需移动 n-i+1 个元素，要删除第 i 个元素，需移动 n-i 个元素2. 在双向循环链表中某结点（由指针 p 指示）之后插入 s 指针所指结点的操作是：； ； ； ；第三章第三章栈和队列栈和队列一．一． 栈栈1． 栈的定义2． 栈的存储结构：顺序存储结构 链式存储结构3． 栈的应用：二叉树的先序、中序、后序遍历算法 图的深度优先遍历算法（将递归算法改写为非递归算法可借助栈来完成；递归算法的执行需用栈来实现）二．二． 队列队列1． 队列的定义2． 队列的存储结构：顺序存储结构（循环队列） ，链式存储结构3． 队列的应用：二叉树层序遍历 图的广度优先遍历算法4． 循环队列：·队空、队满的判断条件·求队列的长度·循环队列通常用 front 和 rear 来指示队头和队尾的位置来表示一个队列；如果用 front 指示队头，用 length 表示队列的长度，也可以表示一个队列。

相应的有关操作怎样实现？例：例：判断题：因为栈是特殊的线性表，所以对线性表的所有操作都可以用于对栈操作填空题：循环队列队满的条件是 rear->front 第四章第四章串串一．一． 串的定义串的定义二． 串的术语串的术语：长度、子串三． 串的基本操作串的基本操作：求串的长度、求子串、串联接、串替换、串匹配（子串定位）例：例：已知下列字符串：a='THIS', b=' '（一个空格）, c='GOOD', d='NE', f='A SAMPLE',执行如下操作：s=Concat (a , Concat (Concat (b , SubString (a ,3 ,2)) , SubString (f , 2 , SubLength(f))));t=Replace (f , SubString (f ,3 ,6) , c);u=Concat (SubString (c ,3 ,1) , d);v=Concat (s , Concat (b ,Concat (t , Concat (b , u))));试问：s，t，u，v，LENGTH(s)各是什么？第五章第五章数组和广义表数组和广义表一．一． 数组数组数组的顺序存储：行主顺序法，列主顺序法。

元素存储地址计算特殊矩阵的压缩存储 元素存储地址计算二．二． 广义表广义表1. 广义表的概念：广义表，长度，深度，表头，表尾；2. 广义表的头尾链表存储结构第六章第六章树和二叉树树和二叉树一．一． 树、二叉树的定义树、二叉树的定义二．二． 二叉树二叉树1． 二叉树的性质（5 条）2． 二叉树的存储结构：顺序存储结构（按层序存放）链式存储结构（二叉链表、三叉链表） （空指针域的个数）3． 遍历二叉树：先序、中序、后序、层序应用：给定二叉树的先序和中序（或后序和中序）序列，画出相应的二叉树4． 线索二叉树：先序、中序、后序线索化三．三． 树和森林树和森林1． 树的存储结构：双亲表示法 孩子表示法 孩子-兄弟（二叉树）表示法2． 树（森林）与二叉树的相互转换3． 树的遍历：先根、后根次序遍历4． 森林的遍历：先序、中序遍历四．四． 赫夫曼树及其应用赫夫曼树及其应用1． 最优二叉树（赫夫曼树） ，求 WPL2． 赫夫曼编码五．五． 各种二叉树概念的区分各种二叉树概念的区分1． 满二叉树2． 完全二叉树3． 正则二叉树（严格二叉树）4． 最优二叉树5． （折半查找的）判定树6． 二叉排序树7． 平衡二叉树8． 堆六．六． 二叉树有关的递归算法二叉树有关的递归算法例：例：判断题：1. 已知二叉树的先序序列和后序序列并不能唯一地确定这棵二叉树，因为不知道二叉树的根结点是哪一个。

f2. 一般二叉树的第 i 层上有 2i-1个结点，深度为 k 的二叉树有 2k-1 个结点f选择题：1. 下列二叉树中，(a )可用于实现符号不等长高效编码A.最优二叉树 B.二叉查找树 C. 平衡二叉树  D.二叉排序树2．结点数为ｎ的二叉树高度至多为( b )A. 不定 B.ｎ C. log2n+1 D. log2n填空题：1. 将满二叉树（含 n 个结点）中各结点从上到下，从左到右进行编号，并采用顺序存储表示，则编号为 i 的结点，其双亲编号为 i/2 ，其左孩子编号为 2i(2i>n) ，其右孩子编号为 2i+1(2i+1>n) 2. 对树的遍历有先根次序遍历树和后根次序遍历树若以二叉链表作树的存储结构,则树的先根遍历可借用二叉树的 先序 遍历算法来实现,而树的后根遍历可借用二叉树的 中序 遍历算法来实现应用题：1. 已知某二叉树的先序遍历序列是 ABCDEFGHI，中序遍历序列是 BDCEAGHFI，画出该二叉树。

2. 以数据集(4,5,6,7,10,12,18)为叶结点权值，构造一棵赫夫曼树，并求其带权路径长度第七章第七章 图图一一. 图的定义和术语图的定义和术语无向图、有向图、 （无向/有向）完全图、子图、 （强）连通图、 （强）连通分量、生成树二．二． 图的存储结构图的存储结构无向图：邻接矩阵、邻接表、邻接多重表有向图：邻接矩阵、邻接表、逆邻接表、十字链表三． 图的遍历图的遍历（针对具体的存储结构进行）深度优先搜索遍历图（利用栈） 广度优先搜索遍历图（利用队列）四．四． 图的遍历的应用图的遍历的应用求无向图的连通分量、生成树（生成森林）五．五． 图的应用图的应用求最小生成树（无向网）：Prim 算法、Kruskal 算法拓扑排序（AOV-网）关键路径（AOE-网）概念最短路径：Dijkstra 算法例：例：判断题：一个连通图的连通分量是包含该图中的所有（n 个）顶点和任意 n-1 条边的子图f应用题：已知图 G 如下，画出该有向图的邻接矩阵和邻接表，并根据你的邻接表分别写出深度优先遍历和广度优先遍历的顶点序列AB CD E第九章第九章查找查找一．一． 静态查找表静态查找表1. 顺序查找表（设置岗哨）2. 有序查找表（折半/二分查找） 要求：元素值有序的顺序表3. 索引顺序查找表二．二． 动态查找表动态查找表1． 二叉排序树（二叉查找树）定义定义、查找、插入、删除从空树开始创建一棵二叉排序树2． 平衡二叉树定义定义、查找、插入从空树开始创建一棵平衡的二叉排序树3． n 个元素的二叉排序树、平衡二叉树的深度4． B-树（B+树） （常用于文件系统）定义定义、查找、插入、删除从空树开始创建一棵 3 阶 B-树（2-3 树）三．三． 哈希表哈希表1． 哈希表的定义2． 哈希函数的构造方法3． 处理冲突的方法4． 哈希表的造表、查找四．四． 平均查找长度的计算平均查找长度的计算1． 等概率情况下，查找成功时的平均查找长度 ASL2． 查找不成功时的查找长度例：例：判断题： 1. 任一个二叉排序树的平均查找长度都小于用顺序查找法查找同样结点的线性表的平均查找长度。

2. 当二叉排序树是一棵平衡树时，其平均查找长度为 O(log2n)选择题：1. 折半查找算法要求被查找的表是( c )A. 键值有序的链表 B. 键值不一定有序的链表C. 键值有序的顺序表 D. 键值不一定有序的顺序表2. 若查找表是一个有序的单链表，则应采用( a )方法A.顺序查找 B.折半查找 C.分块查找 D.哈希查找3．设线性表中元素的关键字序列为（8,16,24,29,35,40,46,58,66,73,87,98） ，用折半查找法查关键字等于 87 的元素时，需依次比较关键字（ c ） A. 40,58,87 B. 46,87 C. 40,66,87 D. 46,66,87应用题：1. 已知如下所示长度为 8 的表: (12，71，36，45，47，50，2，9)，按表中元素顺序构造一棵平衡的二叉排序树，请画出该树 （二叉排序树，2-3 树）2. 设哈希表长为 16，哈希函数为 H(key)=key mod 13，用开放定址法的二次探测再散列处理冲突依次存入 10 个元素：17,24,36,21,83,96,13,34,57,46，请画出它们在表中的分布情形。

第十章第十章内部排序内部排序一．一． 内部排序的方法内部排序的方法1． 直接插入排序2． 希尔排序3． 起泡排序4． 快速排序5． 简单选择排序6． 堆排序7． 归并排序8． 基数排序二．二． 各种内部排序方法的比较各种内部排序方法的比较（最好、最坏、平均）时间复杂度 平均空间复杂度例：例：判断题：归并排序和堆排序的平均时间和最坏情况下的时间性能都是 O(nlogn),因此，它们在最坏情况下的时间性能比快速排序好应用题：若要按升序对关键字序列(36,45,85,16,23,16,58,22,59,74,12,46)进行排序，请写出：(1). 堆排序初始建堆(大顶堆)的结果；(2). 以第一个元素为枢轴的快速排序一趟扫描的结果；(3). 起泡排序第一趟的结果；(4). 希尔排序第一趟（增量 5）的结果(5). 基数排序第一趟的结果。