杭州电子科技大学

1、杭州电子科技大学-数据结构- 期末复习-大纲-习题第一章 绪论杭州电子科技大学一. 基本概念和术语数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。术语：数据、数据元素、数据对象、数据结构、抽象数据类型、算法。数据结构的形式定义（二元组）数据的逻辑结构：线性结构非线性结构数据的存储结构（物理结构）:主要有顺序存储结构链式存储结构抽象数据类型（三元组）算法（5个重要特性）二. 算法的时间复杂度和空间复杂度算法的评价：正确性、可读性、健壮性、高效率、低存储量第二章 线性表一. 线性表的定义线性结构的特点二. 线性表的存储结构1. 顺序存储结构（顺序表）插

2、入/删除元素时，需移动元素2. 链式存储结构（链表，分为单向链表、双向链表）带头结点的链表和不带头结点的链表；循环链表； 链表空与非空的情况。3. 两种存储结构的优缺点比较，各适合那些场合。三. 线性表操作的实现（算法描述）插入元素、删除元素、查找、判表是否满足某种特性例：判断题：1.线性表的逻辑顺序与存储顺序总是一致的。F2. 线性结构的基本特征是：每个结点有且仅有一个直接前驱和一个直接后继。F3. 线性表的链式存储结构优于顺序存储结构。F选择题：线性表L在（B ）情况下适于使用链表结构实现。A.不需修改L的结构B.需不断对L进行删除、插入C.需经常修改L中结点值D. L中含有大量结点填空题

3、：1.对于顺序表中，在第i个元素前插入一个元素需移动n-i+1个元素，要删除第i个元素,需移动 n-i个元素。2. 在双向循环链表中某结点（由指针 p指示）之后插入s指针所指结点的操作是：第三章栈和队列栈1.栈的定义2.栈的存储结构：顺序存储结构链式存储结构3.栈的应用：二叉树的先序、中序、后序遍历算法图的深度优先遍历算法（将递归算法改写为非递归算法可借助栈来完成; 递归算法的执行需用栈来实现）二.队列1. 队列的定义2. 队列的存储结构：顺序存储结构(循环队列)，链式存储结构3. 队列的应用：二叉树层序遍历图的广度优先遍历算法4. 循环队列：队空、队满的判断条件求队列的长度循环队列通常用 f

4、ront和rear来指示队头和队尾的位置来表示一个队列；如果用front指示队头，用length表示队列的长度，也可以表示一个队列。相应 的有关操作怎样实现？例：判断题：因为栈是特殊的线性表，所以对线性表的所有操作都可以用于对栈操作。 填空题：循环队列队满的条件是rear-front。第四章串一. 串的定义二. 串的术语：长度、子串三. 串的基本操作：求串的长度、求子串、串联接、串替换、串匹配(子串定位)例：已知下列字符串：a=THIS, b=(一个空格)，c=GOOD, d=NE, f=A SAMPLE,执行如下操作：s=Concat (a , Concat (Concat (b , Sub

5、String (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. 广义表

6、的头尾链表存储结构第六章树和二叉树一. 树、二叉树的定义二. 二叉树1. 二叉树的性质(5条)2. 二叉树的存储结构：顺序存储结构(按层序存放)链式存储结构(二叉链表、三叉链表)(空指针域的个数)3. 遍历二叉树：先序、中序、后序、层序应用：给定二叉树的先序和中序(或后序和中序)序列，画岀相应的二叉树4. 线索二叉树：先序、中序、后序线索化三. 树和森林1. 树的存储结构：双亲表示法孩子表示法 孩子-兄弟（二叉树）表示法2. 树（森林）与二叉树的相互转换3. 树的遍历：先根、后根次序遍历4. 森林的遍历：先序、中序遍历四. 赫夫曼树及其应用1. 最优二叉树（赫夫曼树），求 WPL2. 赫夫曼编

7、码五. 各种二叉树概念的区分1. 满二叉树2. 完全二叉树3. 正则二叉树（严格二叉树）4. 最优二叉树5. （折半查找的）判定树6. 二叉排序树7. 平衡二叉树8. 堆六. 二叉树有关的递归算法例：判断题：1.已知二叉树的先序序列和后序序列并不能唯一地确定这棵二叉树，因为不知道二叉树的根结 点是哪一个。fi-1k2.一般二叉树的第i层上有2 个结点，深度为k的二叉树有2 -1个结点。f选择题：1.下列二叉树中，（a ） 可用于实现符号不等长高效编码。A.最优二叉树B.二叉查找树C.平衡二叉树 ？D.二叉排序树2结点数为n的二叉树高度至多为 （b）。A.不定B. nC. |llog2n +1D

8、. log?填空题：1.将满二叉树（含 n个结点）中各结点从上到下，从左到右进行编号，并采用顺序存储表示，则编号为i的结点，其双亲编号为i/2，其左孩子编号为2i（2in），其右孩子编号为2i+1（2i+1n）。2.对树的遍历有先根次序遍历树和后根次序遍历树。若以二叉链表作树的存储结构，则树的先根遍历可借用二叉树的先序遍历算法来实现，而树的后根遍历可借用二叉树的 中序遍历算法来实现。应用题：1.已知某二叉树的先序遍历序列是ABCDEFGHI，中序遍历序列是BDCEAGHFI，画出该二叉树。2.以数据集（4,5,6,7,10,12,18）为叶结点权值，构造一棵赫夫曼树，并求其带权路径长度。第七章

9、 图一. 图的定义和术语无向图、有向图、（无向/有向）完全图、子图、（强）连通图、（强）连通分量、生成树二. 图的存储结构无向图：邻接矩阵、邻接表、邻接多重表有向图：邻接矩阵、邻接表、逆邻接表、十字链表三. 图的遍历（针对具体的存储结构进行）深度优先搜索遍历图（利用栈）广度优先搜索遍历图（利用队列）四. 图的遍历的应用求无向图的连通分量、生成树（生成森林）五. 图的应用求最小生成树（无向网）：Prim算法、Kruskal算法拓扑排序（AOV-网）关键路径（AOE-网）概念最短路径：Dijkstra算法例：判断题：一个连通图的连通分量是包含该图中的所有（n个）顶点和任意n-1条边的子图。f应用题

10、：已知图G如下，画岀该有向图的邻接矩阵和邻接表，并根据你的邻接表分别写岀深度优先遍历和 广度优先遍历的顶点序列。BD第九章 查找一. 静态查找表1. 顺序查找表（设置岗哨）2. 有序查找表（折半/二分查找） 要求：元素值有序的顺序表3. 索引顺序查找表二. 动态查找表1. 二叉排序树（二叉查找树）定义、查找、插入、删除从空树开始创建一棵二叉排序树2. 平衡二叉树定义、查找、插入 从空树开始创建一棵平衡的二叉排序树3. n个元素的二叉排序树、平衡二叉树的深度4. 8-树（B+树）（常用于文件系统）定义、查找、插入、删除从空树开始创建一棵 3阶B-树（2-3树）二.哈希表1.哈希表的定义2.哈希函

11、数的构造方法3.处理冲突的方法4.四.哈希表的造表、查找平均查找长度的计算1.等概率情况下，查找成功时的平均查找长度ASL2.查找不成功时的查找长度例：判断题：1.任一个二叉排序树的平均查找长度都小于用顺序查找法查找同样结点的线性表的平均查找长度。2.当二叉排序树是一棵平衡树时，其平均查找长度为O(log2n)。选择题：1.折半查找算法要求被查找的表是(c )。A.键值有序的链表B.键值不一定有序的链表C.键值有序的顺序表D.键值不一定有序的顺序表2.若查找表是一个有序的单链表，则应采用(a ) 方法。A.顺序查找B.折半查找C.分块查找D.哈希查找3 .设线性表中元素的关键字序列为(8,16

12、,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 mod13,用开放定址法的二次探测再散列处理冲突。 依次存入10个元素：17,24,36,21,83,96,13,34,57,46，请画出它们在表中的分布情形。第十章 内部排序一. 内部排序的方法1. 直接插入排序2. 希尔排序3. 起泡排序4. 快速排序5. 简单选择排序6. 堆排序7. 归并排序8. 基数排序二. 各种内部排序方法的比较(最好、最坏、平均)时间复杂度平均空间复杂度例：判断题：归并排序和堆排序的平均时间和最坏情况下的时间