数据结构与算法复习提纲

数据结构与算法复习提纲 线性表部分： 1、 顺序表的基本操作：创建、插入、删除、查找、修改、遍历、输出 2、 带头结点单链表的基本操作：创建、插入（头插、尾插、任意位置插入）、删除（头删、尾删、任意位置删除）、查找、修改、定位、输出、求表长、遍历的基本应用 3、 带头结点的循环单链表的基本操作：创建、插入（头插、尾插、任意位置插入）、删除（头删、尾删、任意位置删除）、查找、修改、定位、输出、求表长、遍历的基本应用 4、 线性表的应用：有序顺序表的插入；有序单链表的插入；顺序表的逆置、单链表的逆置；顺序表归并、单链表归并 栈和队列部分： 1、 顺序栈的基本操作：初始化、入栈、出栈、取得栈顶元素（注意top变量的取值）、判栈空、判栈满、遍历 2、 链栈的基本操作：初始化、入栈、出栈、判栈空、遍历 3、 循环队列的基本操作：初始化、入队、出队、队空队满的判定条件、求队列长度、遍历； 4、 链队列的基本操作：初始化、入队、出队、队空、遍历 5、 表达式求值：栈中数据的变化过程 树和二叉树 1、 二叉树的5个基本性质 2、 二叉树的顺序存储结构 3、 二叉链表存储，相关的基本操作：前中后三种遍历、层次遍历、创建、求结点个数、求叶子个数、求深度、基于遍历的应用 4、 树的孩子兄弟链表存储结构，相关的基本操作：创建、查找某个结点的孩子、插入一个结点、求深度、先根、后根遍历输出 5、 二叉树、树与森林的应用：由两种遍历序列确定一棵二叉树；二叉树的三种遍历序列；由两种遍历序列确定一棵树；树（森林）与二叉树之间的相互转换； 6、 哈夫曼树及其应用：构造哈夫曼树、哈夫曼编码、求wpl；注意：构造哈夫曼树过程相关存储结构的变化 图的部分 1、 图的基本概念 2、 图的邻接矩阵存储结构：创建、深度遍历、广度遍历 3、 图的邻接表存储结构：创建、深度遍历、广度遍历 4、 最小生成树：prim算法 查找与排序部分 1、 折半查找：算法、查找判定树、成功与不成功的ASL 2、 二叉排序树的构造、平衡二叉树的构造、成功与不成功的ASL 3、 哈希表：构造、线性探测、二次探测、拉链法；成功与不成功的ASL 4、 直接插入排序、希尔排序、冒泡排序、快速排序，一趟排序的结果。 试卷样题 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、已知无向图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，01，68，20，84，27。试画出用线性探测法解决冲突时所构成的散列表(10分)。 6、设待排序序列为{10，18，4，3，6，12，1，9，15，8}，请给出希尔排序一趟的结果。增加量序列为5。（5分） 8、试简述一种判定有向图G中是否有环（回路、圈）的方法(5分)。 9、给定如下有向图，完成问题（15分）。

1）从顶点V1出发的深度优先遍历序列； 2）从顶点V1出发的广度优先遍历序列； 10、以顺序表为存储结构，写一算法，删除线性表中从第i个元素开始的k个元素(10分)。 11、用带头结点的循环链表作为队列的存储表示，不设头指针而只设一个尾指针rear指向队尾结点。试写出该链式队列的入队和出队算法(10分)。

复习题目： 练习题1 一、 应用题 1、 画出满足以下条件的二叉树形态 1） 前序和中序遍历序列相同 2） 中序和后序遍历序列相同 3） 前序和后序遍历序列相同

2、 设权W=（0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10） (1) 构造哈夫曼树，求WPL(8分)。 (2) 写出这8个字母的哈夫曼编码（2分）。 3、 对森林做以下操作： (1)转换成二叉树 (2)给出二叉树的三种遍历序列 4、 假设用于通讯的电文由8个字母组成，字母在电文中出现的频率分别为7，19，2，6，32，3，21，10， 5、 已知一棵树的先根遍历序列为GFKDAIEBCHJ，后根遍历序列为DIAEKFCJHBG，画出该树。 6、 假设一棵二叉树的中序序列为cbedahgijf和后序序列为cedbhjigfa。

(1)请画出该二叉树 (2)给出其先序遍历序列 7、 已知无向图如下所示，回答问题： 1）写出邻接矩阵；（4分） 2）在邻接矩阵存储上，写出以顶点1作为源点的深度优先遍历序列；（3分） 3）在邻接矩阵存储上，写出以顶点1作为源点的广度优先遍历序列。（3分）

二、 算法设计 1、 有向连通图采用邻接表存储结构，写一个根据给定值进行查找的算法（基于遍历做）。（10分） 2、 写一个在单链表上查找最大值的算法。（10分） 3、 写一个求单链表长度的算法（10分）。

4、写出建立无向图的邻接矩阵存储的算法 (10分)。

练习题2 一、应用题

1 2 3

4 5 6

7

8 1、请对下图的无向带权图： （1） 写出它的邻接矩阵，并按普里姆算法求其最小生成树；

2.给定二叉树的两种遍历序列，分别是： 前序遍历序列：D，A，C，E，B，H，F，G，I；中序遍历序列：D，C，B，E，H，A，G，I，F， 试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。

3、把如图所示的树转化成二叉树。

4.画出和下列二叉树相应的森林。 5．假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题： （1） 画出描述折半查找过程的判定树； （2） 若查找元素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，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分）

习题4 一、算法应用题。 1. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K MOD 17。 K为关键字，用线性探测再散列法处理冲突，输入关键字序列： （10，24，32，17，31，30，46，47，40，63，49） 造出Hash表，试回答下列问题： （1） 画出哈希表的示意图； （2） 若查找关键字63，需要依次与哪些关键字进行比较？ （3） 若查找关键字60，需要依次与哪些关键字比较？ （4） 假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

2. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。

3. 在一棵空的二叉查找树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉平衡树，并求ASL.

4、选取散列函数H（key）=（3*key）%11，用线性探测法和链地址法两种方法处理冲突，分别对下列关键码序列构造一个散列地址空间为0～10，表长为11的散列表，{22，41，53，08，46，30，01，31，66}。并求各自的ASL

5、关键字序列为(7,4,5,9,1,2,8,10,6,5)，写出一趟快速排序，画出排序中比较交换的过程。 6、关键字序列49 38 65 97 76 13 27 49 55 04 10，画出一趟希尔排序的过程。d1=5

二、算法设计 1、写一个单链表求长度的算法。 2、写一个根据给定值在二叉树中进行查找的算法。二叉树采用二叉链表存储结构。 3、编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信