《数据结构与算法复习提纲》由会员分享，可在线阅读，更多相关《数据结构与算法复习提纲（15页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法复习提纲线性表部分：1、顺序表的基本操作：创建、插入、删除、查找、修改、遍历、 输出2、带头结点单链表的基本操作：创建、插入（头插、尾插、任意 位置插入）、删除（头删、尾删、任意位置删除）、查找、修改、 定位、输出、求表长、遍历的基本应用3、带头结点的循环单链表的基本操作：创建、插入（头插、尾插、 任意位置插入）、删除（头删、尾删、任意位置删除）、查找、 修改、定位、输出、求表长、遍历的基本应用4、线性表的应用：有序顺序表的插入；有序单链表的插入；顺序表的逆置、单链表的逆置；顺序表归并、单链表归并栈和队列部分：1、顺序栈的基本操作：创建、入栈、出栈、取得栈顶元素（注意top 变量
2、的取值）、判栈空、判栈满、遍历2、链栈的基本操作：创建、入栈、出栈、判栈空、遍历3、循环队列的基本操作：创建、入队、出队、队空队满的判定条 件、求队列长度、遍历；4、链队列的基本操作：创建、入队、出队、队空、遍历5、表达式求值：栈中数据的变化过程树和二叉树1、二叉树的 5个基本性质2、二叉树的顺序存储结构3、二叉链表存储，相关的基本操作：前中后三种遍历、层次遍历、 创建、求结点个数、求叶子个数、求深度、基于遍历的应用4、树的孩子兄弟链表存储结构，相关的基本操作：创建、查找某 个结点的孩子、插入一个结点、遍历输出5、树的孩子兄弟链表存储结构，相关的基本操作：创建、求深度、 先根遍历、插入结点6、
3、二叉树、树与森林的应用：由两种遍历序列确定一棵二叉树； 二叉树的三种遍历序列；由两种遍历序列确定一棵树；树（森 林）与二叉树之间的相互转换；7、哈夫曼树及其应用：构造哈夫曼树、哈夫曼编码、求wpl；注意：构造哈夫曼树过程相关存储结构的变化图的部分1、图的基本概念2、图的邻接矩阵存储结构：创建、深度遍历、广度遍历3、图的邻接表存储结构：创建、深度遍历、广度遍历4、最小生成树： prim 算法、 kruscal 算法5、最短路径：迪杰斯特拉算法、 floyd 算法6、拓扑排序、关键路径查找与排序部分1、带哨兵的顺序查找：算法、 ASL2、折半查找：算法、查找判定树、成功与不成功的 ASL3、二叉排
4、序树的构造、平衡二叉树的构造、成功与不成功的 ASL4、哈希表：构造、线性探测、二次探测、拉链法；成功与不成功 的 ASL5、直接插入排序、希尔排序、冒泡排序、快速排序， 一趟排序 的结果。试卷样题1、假设通信电文使用的字符集为a,b,c,d,e,f，字符在电文中出现的频率分别为 34，5，12，23，8，18。请构造哈夫曼树（要求树中左孩子结点的权值小于 右孩子结点的权值），并设计哈夫曼编码（10 分）。2、设一棵二叉树的前序序列为 1， 2， 3， 4， 5， 6， 7， 8， 9，其中序序列为 2， 3， 1， 5， 4， 7， 8， 6， 9，试画出该二叉树（10 分）。3、已知无向图
5、 G， V（G）=1， 2， 3， 4， E（G）=（1， 2）， （1， 3）， （2， 3）， （2， 4）， （3, 4），试画出G的邻接表。并简述，已知点i时，如何在邻接表上找到与i 点相邻的所有点（10 分）。4、 给定关键字序列 55， 31， 11， 37， 46， 73， 63， 02， 07 （1）构造平衡二叉树，画出每加入一个新结点时二叉树的形态。若发生不平 衡，指明需做的平衡调整类型及调整的结果（8 分）。（2）计算该平衡二叉树在等概率下查找成功的平均查找长度（2分）。5、设散列表的长度为13,散列函数为H （h） = k%13,给定的关键字序列为19，14， 23， 0
6、1， 68， 20， 84， 27。试画出用线性探测法解决冲突时所构成的散 列表（10 分）。6、设待排序序列为10， 18， 4， 3， 6， 12， 1， 9， 15， 8，请给出希尔排序一 趟的结果。增加量序列为5。（5分）7、图示为有向图，用Dijkstra算法求出从源点1到其它各顶点的最短路径。8、试简述一种判定有向图 G 中是否有环（回路、圈）的方法（5 分）。9、给定如下有向图，完成问题（15 分）。a4=43a6-l-a8=&|a0=38a?=lla3=501）从顶点V1出发的深度优先遍历序列；2）从顶点 V1 出发的广度优先遍历序列；3）求从 V1 到 V8 的关键路径。要求
7、过程：计算每个顶点的最早、最晚发生时间； 每项活动最早、最迟开始时间。10、以顺序表为存储结构，写一算法，删除线性表中从第i个元素开始的k个元 素（10 分）。11、用带头结点的循环链表作为队列的存储表示，不设头指针而只设一个尾指针 rear指向队尾结点。试写出该链式队列的入队和出队算法（10分）。复习题目：练习题1一、 应用题1、画出满足以下条件的二叉树形态1) 前序和中序遍历序列相同2) 中序和后序遍历序列相同3) 前序和后序遍历序列相同2、 已知一棵含有n个结点的树中，只有度为0和度为k的结点，求叶结点 的个数？要求写出求解过程。3、一棵度为3的树中，度为3的结点数为2个，度为2的结点数
8、为1个，度 为1的结点数为2个，求度为0的结点数？写出求解过程。4、设权W=(0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10)(1) 构造哈夫曼树，求WPL(8分)。(2) 写出这8个字母的哈夫曼编码(2分)。5、对森林做以下操作：(1) 转换成二叉树(2) 给出二叉树的三种遍历序列6、假设用于通讯的电文由8个字母组成，字母在电文中出现的频率分别为7， 19， 2， 6， 32， 3， 21， 10，7、已知一棵树的先根遍历序列为GFKDAIEBCHJ，后根遍历序列为 DIAEKFCJHBG，画出该树。& 假设一棵二叉树的中序序列为cbedahgijf和后序序列
9、为cedbhjigfa。(1) 请画出该二叉树(2) 给出其先序遍历序列9、已知无向图如下所示，回答问题：1) 写出邻接矩阵；(4分)2) 在邻接矩阵存储上，写出以顶点1作为源点的深度优先遍历序列；(3 分)3）在邻接矩阵存储上，写出以顶点1作为源点的广度优先遍历序列。（3 分）二、程序设计1、有向连通图采用邻接表存储结构，写一个根据给定值进行查找的算法（基 于遍历做）。（10分）2、写一个在单链表上查找最大值的算法。（10分）3、写一个求单链表长度的算法（10分）。4、写出建立无向图的邻接矩阵存储的算法（10分）。练习题2一、应用题1、请对下图的无向带权图：（1）写出它的邻接矩阵，并按普里姆
10、算法求其最小生成树；（2）写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树2. 【类似严题集6.27】给定二叉树的两种遍历序列，分别是：前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A， G， I， F，试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树 B 的思想方法。3、把如图所示的树转化成二叉树。4.【严题集6.21】画出和下列二叉树相应的森林。5假定对有序表：（3， 4， 5， 7， 24， 30， 42， 54， 63， 72， 87， 95）进行折半查找，试回答下列问题：（1） 画出描述折半查找过程的判定树；（2） 若查找
11、元素 54，需依次与哪些元素比较？（3）若查找元素 90，需依次与哪些元素比较？（4）假定每个元素的查找概率相等，求查找成功时的平均查找长度。二、算法设计1、写出循环队列初始化、入队和出队操作，并用存储示意图描述每一种操作的 变化。2、写出带头结点单链表的逆置算法。3、写一个求二叉树叶子结点个数的算法。注：二叉树采用二叉链表存储。习题3一应用分析题.1、给定一组关键字序列36, 75, 83, 54, 12, 67, 60, 40, 92, 72，按照关 键字顺序构造一个平衡二叉树AVL,并求等概率情况下查找成功的平均查找长 度 ASL。（10 分）3、设有一组关键字（32, 75, 29,
12、63, 48, 94, 25, 46, 18, 70）,采用哈希函 数：H（key）=key%13。采用链地址法处理冲突，设计出链表结构，并计算查找成 功时的平均查找长度。（10分）4、已知一组关键字为46, 74, 16, 53, 14, 26, 40, 38, 86, 65, 27, 34, 利用希尔排序的方法写出增量d每取一个值后所得到的排列结果，假定d依次取5、3, 1（5 分）二程序设计1、写一个建立有向图邻接表存储结构的算法。（10分）2、写一个带岗哨的顺序查找算法。（10分）习题4一、分析设计题。1. 设哈希（Hash）表的地址范围为017,哈希函数为：H（K）=K MOD 17
13、。K为关键字，用线性探测再散列法处理冲突，输入关键字序列：（10， 24， 32， 17， 31， 30， 46， 47， 40， 63， 49）造出Hash表，试回答下列问题：（1）画出哈希表的示意图；（2）若查找关键字63，需要依次与哪些关键字进行比较？（3）若查找关键字60，需要依次与哪些关键字比较？（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。（5）2. 【严题集9.3】画出对长度为10的有序表进行折半查找的判定树，并求其 等概率时查找成功的平均查找长度。3. 在一棵空的二叉查找树中依次插入关键字序列为12, 7, 17, 11，16, 2, 13，9, 21, 4,
14、请画出所得到的二叉平衡树，并求ASL.4、选取散列函数H （key） = （3*key） %11，用线性探测法和链地址法两种方法 处理冲突，分别对下列关键码序列构造一个散列地址空间为010,表长为11 的散列表，22, 41, 53, 08, 46, 30, 01, 31, 66。并求各自的 ASL5、关键字序列为（7,4,5,9,1,2,8,10,6,5），写出一趟快速排序，画出排序中比较交换 的过程。6、关键字序列 4938659776132749550410, 画出一趟希尔排序的过程。d1=5二、算法1、写一个单链表求长度的算法。2、写一个根据给定值在二叉树中进行查找的算法。二叉树采用二叉链表存储结 构。3、【严题集7.14】编写算法，由依次输入的顶点数目、弧的数目、各顶点的信 息和各条弧的信息建立有向图的邻接表。习题5(1)ASL=(1+2*2+3*3+4*3+5*2+6)/12= 42/12(2)判定树如下：ASL=(1+2*2+3*4+4*5)/12=37/12012345678910226741305346130113121126
