下数据结构复习

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

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

3、环队列中，假定 front 和 rear 分别为队头指针和队尾指针，则判断队满的条件为(rear+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 nrj存放循环队列的元素，设变量 rear和quelen分别

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

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

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

7、通图G中有n个顶点e条边，则对应的最小生成树上有 n-1条边5 .在一个图中，所有顶点的度数之和等于所有边数的2倍。6 .在一个具有n个顶点的无向完全图中，包含有 n(n-1)/2条边，在一个具有n个顶点的有向完全图中，包含有n(n-1)条边。7 .无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为O(n2)；用邻接表作为图的存储上述复杂度O(n+e).8 .在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为n2- 2e.9 .设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d,则e和d的关系为d=e.10 .设某无向图中顶点数和边

8、数分别为n和e,所有顶点的度数之和为 d,则e=d/211 .掌握最小生成树算法.例如使用普里姆(Prim)算法以 乱源点，构造下图 的最小代价生成树，画出各步的结果。OQC12.已知有向图G如下所示，根据迪短距离。.oCOOA R Q上入特拉算法求顶点?0到其他顶点的最OO OQ > 再终点从v0到各终点的d值和最短路径的求解过程i=1i=2i=3i=4v112 (v0,v1)12 (v0,v1)7 (v0,v4,v1)v24 (v0,v2)v39 (v0,v3)8 (v0,v2,v3)7 (v0,v4,v3)7 (v0,v4,v3)v45 (v0,v4)5 (v0,v4)vjv2v4

9、v1v3sv0,v2v0,v4v0,v4,v1v0,v4,v3第9章查找掌握二分（折半）查找，二叉排序树的概念及其上的插入和删除有何特 点，掌握哈希查找。例题:1. 对于顺序存储的有序表(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,给定的关键

10、值序列为 19,14,23,10,68,20,84,27,55,11。 试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的情况下查找成功的平均查找长度ASL。(1) 表形态：(2) 平均查找长度：ASL(10)=(1*5+2*4+3*1)/10=1.66. 设一组初始记录关键字序列为(20， 12， 42， 31， 18， 14， 28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是19/7.第 10章 内部排序掌握基本排序方法的实现思想。例题 ：1. 假定对元素序列（7, 3, 5, 9, 1, 12, 8, 15 ）进行快速排序，则进行第一次划分后，得到的左区间中元素的个

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