2014数据结构复习

1、2014 （下）数据结构复习2014下数据结构复习提纲第1章绪论有尖术语；算法、算法复杂度的分析和计算方法例题：1下面算法的时间复杂度为0( n) oint f( unsigned int n )if(n = = 0|n = = 1 ) return 1;else reture n n *f ( n T );2 for(i=1 、s=0 ； iv=n ； i+ ) t=1 ； for(j=1 ； j<=i ； j+) t=t*j ； s=s+t ； 时间复杂度为0()第2-3章线性表，栈和队列线性表的概念、存储结构、插入与删除操作；栈和队列的概念，理 解栈顶指针、队首、队尾指针的意义和作

2、用，特别是循环队列的头、尾指针 的设置。为什么要这样设置。它们基本操作的实现。判空和判满？了解有尖应用。例题：1 -在一个单链表中，若q所指结点是P所指结点的前驱结点，若在q与P 之间插入一个s所指的结点，则执行的语句?(答：q>next=s; s->next=p):注意在某个已知结点前插需要执行的语句？ 2注意循 环(链)队列的判空和判满的条件？(看书理解! ) 3对于一个具有n个结点 的单链表，在已知的结点P后插入一个新结点的时间复杂度为0(1)，在给定 值为x的结点后插入一个新结点的时间复杂度为O(n)。4. 在具有n个单元的顺序存储的循环队列中，假定front和rear分别

3、为 队 头指针和队尾指针'则判断队满的条件为(®r+l) %n= = front。执行出队操 作后其头指针front如何？5. 线性表采用链式存储时，结点的存储地址连续与否均可；6链式栈删除栈顶元素的操作序列为top=top->next.7. 在单链表中，指针P指向元素为x的结点，实现“删除x的后继”的 语句是 p->next=p->next>next.8. 判定“带头结点的链队列为空”的条件是Q.front=Q.rear.9. 假设以数组seqn m 存放循环队列的元素，设变量rear和quelen分别指 示循环队列中队尾元素的位置和元素的个数。则队

4、满的条件表达式为quelen = m ；队空的条件表达式quelen = 0 ；队头元素位置的表达式 (rear quelen + m ) % m第6章树和二叉树树和二叉树的定义、完全二叉树及其性质、存储表示及遍历算法（递 归和非递归）、哈夫曼树的概念。例题：1 -在一棵二叉树中，度为0的结点个数为n。,度为2的结点个数为氐，则 no= H24-1 o （完全二叉树性质）例：二叉树上叶结点数等于（双分支结点数 加1 ）；对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链 表中的指针域的总数为勿个，其中个用于链接孩子结点，n+1个空闲 着。2. n个权构成一棵Huffman树，其节点总数为

5、2n-1.3. 设用权 6，10，13，14, 20 » 37 构造 Huffman 树、则该 Huffman 树的 根结点的权值为100.（仔细验算构造Huffman树）4. 一棵深度为k的满二叉树的结点总数为2<1，一棵深度为k的完全二叉树 的结点总数的最小值为2k'1，最大值为2<1。5深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树6设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二 叉树的前序遍历序列为ABDECF，中序遍历序列为DBEAFC ，后序 遍历序 列为 DEBFCA.7一棵完全二叉树中共有768结点，则该树中共有38

6、4个叶子结点。8深度为k的完全二叉树中最少有2k-1个结点。9.二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的 条件是任一结点无右孩子第7章图图的存储及遍历算法，图的有尖概念，最短路径，（最小）生成树例 题：1由一个具有n个顶点的连通图生成的最小生成树中，具有条边。2 有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个 数之和等于顶点i的出度，第i列中所有非零元素个数之和等于顶点i的入 度。3. 若要把n个顶点连接为一个连通图，则至少需要条边。4. 连通图G中有n个顶点e条边，则对应的最小生成树上有条边5 在 一个图中，所有顶点的度数之和等于所有边数的2倍。6.

7、在一个具有n个顶点的无向完全图中，包含有n （n-1） /2条边， 在一个具有n个顶点的有向完全图中，包含有n(n1)条边。7无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行 深度优先或广度优先遍历时的时间复杂度为 0(乎)；用邻接表作为图的存 储上述复杂度O(n+e).8. 在含n个顶点和e条边的无向图的邻接矩阵中，零元素的个数为n2- 2e.9. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和 d的尖系为d=e.10. 设某无向图中顶点数和边数分别为n和e,所有顶点的度数之和为d,则 e=d/211. 掌握最小生成树算法例如使用普里姆(Prim)算法以A为源

8、点，构造下图 的最小代价生成树，画出各步的结果。也已知有向图G如下所示，根据迪杰斯特 拉算法求顶点v0到其他顶点的最短距离终占乙八、从VO到各终点的d值和最短路径的求解过 程i=1i=2i=3i=4V112(v0,v1)12 (vO,v1)7(vO,v4,v1)v24 (v0,v2)v39 (v0,v3)8(v0,v2,v3)7(v0,v4,v3)7(v0,v4,v3)v45 (vO,v4)5 (v0,v4)vjv2v4v1v3sv0,v2vO,v4vO,v4,v1v0,v4,v3第9章查找掌握二呑(折半)查找，二叉排序树的概念及其上的插入和删除有何特点，掌握哈希查找。 例题：1. 对于顺序存

9、储的有序表(5,12, 20, 26, 37, 42, 46, 50, 64)，若采用折半查找，则查找元素 26的比较次数为4。2. 有序表中进行二分查找，则比较一次查找成功的结点数有1个，比较两次查找成功有结点数有2个，比较三次3 理解并掌握二叉排序树的概念，会构造二叉排序树及查找、插入和删除操作。4. 中序遍历二叉排序树可以得到一个从小到大的有序序列。5. 设哈希表HT表长m为13,哈希函数为H(k)=k MOD m给定的尖键值序列为19,14,23,10,68,20,84,27,55,11。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL(1

10、)表形态:0123456789101112142768551920842310111212113122平均查找长度：ASL(10)=(1 *5+2*4+3*1)/10=1.66设一组初始记录尖键字序列为(20，12, 42, 31，18，14，28)，则根 据这些记录尖键字构造的 二叉排序树的平均查找长度是19/7.第10章内部排序掌握基本排序方法的实现思想。例题：4假定对元素序列(7, 3, 5, 9,1,12, 8, 15进行快速排序，则进行第一次划分 后，得到的左区间中元素的个数为3。2 设一组初始记录尖键字序列为(60，80, 55, 40，42, 85)，则以第一个尖键字45为基准而

11、得到的一趟快速排序结果是42, 40, 55, 60, 80,85考试题型：一.单项选择题(15X2分=30分)二填空题(10X2分=20分1 实现数据x进栈程序填空；2二叉树中各类结点个数及尖系；3尖于无向图 的度；4无向图邻接矩阵中找邻接点；5二叉树遍历；6顺序循环队列元素 个数；7二叉排序树平均查找长度；8哈夫曼树构造和哈夫曼树的高度；9. 最小生成树构造及其上权值之和；10.二叉排序树中插入一个新结点算法填 空。三解答题（5八6分=30分）1 循环队列在特定设置下判满判空，计算元素位置；2.给出邻接矩阵，画 出该图，画出深度优先生成树；3.填写出散列表和平均查找长度;4.求某顶 点到其余各顶点的最短路径；5.构造一棵二叉排序树，画出删去结点之后的 二叉排序树.四算法阅读题（2X6分=12分