《数据结构复习》由会员分享，可在线阅读，更多相关《数据结构复习（7页珍藏版）》请在金锄头文库上搜索。
1、下数据构造复习提纲第1章 绪论有关术语；算法、算法复杂度的分析和计算措施例题: 1下面算法的时间复杂度为O( n )。int f( uniged int ）if ( n= = | 1 ） retrn 1;el returen n*f ( n 1 )； 2.o（i=1，s=0； i=； +）t=1;or(j=1；et=s； s-x=)；注旨在某个已知结点前插需要执行的语句？注意循环(链）队列的判空和判满的条件?（看书理解！)3.对于一种具有n个结点的单链表，在已知的结点p后插入一种新结点的时间复杂度为 O(1),在给定值为x的结点后插入一种新结点的时间复杂度为 O(）。4在具有n个单元的顺序存储
2、的循环队列中，假定ront和ea分别为队头指针和队尾指针,则判断队满的条件为 (rr+l）n= fot。执行出队操作后其头指针frnt如何?5. 线性表采用链式存储时，结点的存储地址持续与否均可; 链式栈删除栈顶元素的操作序列为tp=onet.7.在单链表中，指针p指向元素为的结点,实现“删除的后继”的语句是p-ne=p-nt-next.8. 鉴定“带头结点的链队列为空”的条件是rt=Q.ear.9.假设以数组seqm寄存循环队列的元素,设变量rar和uelen分别批示循环队列中队尾元素的位置和元素的个数。则队满的条件体现式为quele = ;队空的条件体现式qule = 0；队头元素位置的体
3、现式 ( rear- queen+ ) m第6章 树和二叉树 树和二叉树的定义、完全二叉树及其性质、存储表达及遍历算法(递归和非递归）、哈夫曼树的概念。例题:1.在一棵二叉树中，度为0的结点个数为n0,度为2的结点个数为2，则n0= n21。（完全二叉树性质）例：二叉树上叶结点数等于（双分支结点数加1)；对于一棵具有n个结点的二叉树,当进行链接存储时，其二叉链表中的指针域的总数为2n个,其中 1个用于链接孩子结点, n+1个空闲着。. n 个权构成一棵Hufmn树，其节点总数为n-1.3. 设用权6,10,13,4，2,37构造Hufan树,则该Huffmn树的根结点的权值为100. (仔细验
4、算构造Hffman树） 一棵深度为k的满二叉树的结点总数为 2-,一棵深度为k的完全二叉树的结点总数的最小值为2k1，最大值为2-1。5深度为的完全二叉树的结点个数不不小于或等于深度相似的满二叉树6. 设一棵完全二叉树的顺序存储构造中存储数据元素为ABDF，则该二叉树的前序遍历序列为DECF ，中序遍历序列为DEAFC，后序遍历序列为DEBFA7 一棵完全二叉树中共有78结点,则该树中共有384个叶子结点。. 深度为k的完全二叉树中至少有2k1个结点。二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条件是任一结点无右孩子第章 图 图的存储及遍历算法，图的有关概念，最短途径，（最小）
5、生成树例题：1由一种具有个顶点的连通图生成的最小生成树中,具有n-1 条边。2.有向图的存储构造用邻接矩阵来表达,则中第行中所有非零元素个数之和等于顶点i的出度，第i列中所有非零元素个数之和等于顶点i的入度。3. 若要把n个顶点连接为一种连通图,则至少需要n-1 条边。4.连通图中有n个顶点e条边，则相应的最小生成树上有n1条边5.在一种图中，所有顶点的度数之和等于所有边数的 倍。6.在一种具有n个顶点的无向完全图中,包具有n(n-)/条边，在一种具有n个顶点的有向完全图中,包具有n（n1)条边。无向图G中有n个顶点条边,则用邻接矩阵作为图的存储构造进行深度优先或广度优先遍历时的时间复杂度为O
6、(n）; 用邻接表作为图的存储上述复杂度O(n+)在含个顶点和e条边的无向图的邻接矩阵中，零元素的个数为n22e.9.设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为,则e和的关系为=.10. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=d/211掌握最小生成树算法例如使用普里姆(rim）算法以为源点,构造下图的最小代价生成树,画出各步的成果。AFGDBCAFADFACDFAGCDFABGCDFAE12. 已知有向图G如下所示，根据迪杰斯特拉算法求顶点v0到其她顶点的最短距离。终点从0到各终点的d值和最短途径的求解过程i=1i=23i=4v (v0,v1)12(
7、v0，v）7 (v,v4,）v24 （v0，2)（v0,)8 （v0,v，3）7 (v0,4,v)7(0,v,3)4（v0，）5 （v，v)jv2v4v1v3v0,vv0,v4v0，4,v1v0,v3第9章 查找 掌握二分（折半）查找,二叉排序树的概念及其上的插入和删除有何特点，掌握哈希查找。例题：1. 对于顺序存储的有序表(5,1，20，26,37,42,50,6)，若采用折半查找，则查找元素26的比较次数为4。2.有序表中进行二分查找,则比较一次查找成功的结点数有1个，比较两次查找成功有结点数有2个,比较三次3.理解并掌握二叉排序树的概念，会构造二叉排序树及查找、插入和删除操作。4中序遍历
8、二叉排序树可以得到一种从小到大的有序序列。5.设哈希表HT表长m为3,哈希函数为H(k)=kMOD m，给定的核心值序列为9,4，23,0,68,2，8,27,55,1。试求出用线性探测法解决冲突时所构造的哈希表，并求出在等概率的状况下查找成功的平均查找长度ASL。()表形态:()平均查找长度:AS(0)(1*+*4+*1)/10=1.66. 设一组初始记录核心字序列为（20，12，2，31，1，14，28)，则根据这些记录核心字构造的二叉排序树的平均查找长度是9/7.第1章 内部排序 掌握基本排序措施的实现思想。例题：1. 假定对元素序列（7, 3, 5, ，1, 1， 8, ）进行迅速排序
9、，则进行第一次划分后，得到的左区间中元素的个数为3。.设一组初始记录核心字序列为(6,8，55，40，42，85)，则以第一种核心字5为基准而得到的一趟迅速排序成果是42,40，55,60,80，5考试题型：一.单选题（152分=30分）二.填空题（102分=20分)1.实现数据x进栈程序填空；. 二叉树中各类结点个数及关系；3 有关无向图的度;4. 无向图邻接矩阵中找邻接点;5. 二叉树遍历;顺序循环队列元素个数;7 二叉排序树平均查找长度； . 哈夫曼树构造和哈夫曼树的高度； 9. 最小生成树构造及其上权值之和; .二叉排序树中插入一种新结点算法填空。三.解答题（6分=30分） 1.循环队列在特定设立下判满判空,计算元素位置;2.给出邻接矩阵,画出该图,画出深度优先生成树；3. 填写出散列表和平均查找长度;.求某顶点到其他各顶点的最短途径; 5.构造一棵二叉排序树，画出删去结点之后的二叉排序树. 四算法阅读题（26分1分）. 在带头结点的单链表中,删除数据元素的算法; .中序遍历二叉树过程中实现对某些节点的其她操作.五、算法设计题（8分)1. 将一种简朴的递归程序改写成非递归,实现相似功能 以上各例题中的答案并不保证完全对的,但愿自己亲自验证。找到并对照课本上的相应内容仔细阅读3遍以上。切实理解和掌握每个知识点的实质，决不可以似是而非,侥幸过关。祝同窗们考出好成绩！
