下数据结构复习

《下数据结构复习》由会员分享，可在线阅读，更多相关《下数据结构复习（7页珍藏版）》请在装配图网上搜索。

1、2014（下）数据结构复习2014下数据结构复习提纲第1章绪论有关术语；算法.算法复杂度的分析和计算方法 例题：1. 下面算法的时间复杂度为0( n )。int f( unsigned int n )if(n = = 0lln = =l) return 1;else returen n ( n - 1); 2- for (i=l, s=0； i=n； i+) t=l； for(J=l； jnext二s; s-next=p)；注意在某个已知结点前插需要执行的语句？2. 注意循环(链)队列的判空和判满的条件？(看书理解!)3. 对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点 的时间复

2、杂度为0(1),在给定值为x的结点后插入一个新结点的时间复 杂度为0 (n) o4在具有n个单元的顺序存储的循环队列中，假定front和rear分别为 队头指针和队尾指针，则判断队满的条件为(rear+1) %n= = fronto 执行出队操作后其头指针front如何？5. 线性表采用链式存储时，结点的存储地址连续与否均可；6链式栈删除栈顶元素的操作序列为top=top-next.7.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的 语句是 p-next=p-next-next&判定“带头结点的链队列为空”的条件是Q. front=Q. rear.9假设以数组seqn in存放循

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

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

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

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

7、的度数之和为d, 则 e=d/211掌握最小生成树算法例如使用普里姆(Prim)算法以A为源点，构造 下图的最小代价生成树，画出各步的结果。12.已知有向图G如下所示,根据迪杰斯特拉算法求顶点v0到其他顶点的最短距离。终点从vO到各终点的d值和最短路径的求解过 程i=li=2i=3i=4V112 (vO,vl)12 (vO,vl)7(v0,v4,vl)v24 (v0,v2)v39 (v0,v3)8(v0,v2,v3)7(v0，v4，v3)7(v0，v4，v3)v45 (v0,v4)5 (v0，v4)Vjv2v4vlv3sv0,v2v0,v4v0，v4，vlv0，v4，v3第9章査找掌握二分(折

8、半)査找，二叉排序树的概念及其上的插入和删除有 何特点，掌握哈希査找。例题：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,给定的关键值 序列为19,14, 23, 10, 68, 20, 84, 27, 55,1

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

10、元素的个数为3。2. 设一组初始记录关键字序列为(60, 80, 55, 40, 42, 85),则以第一 个关键字45为基准而得到的一趙快速排序结果是42, 40, 55, 60, 80, 85考试题型：一.单项选择题(15X2分=30分)二填空题(10X2分=20分)1.实现数据x进栈程序填空；2.二叉树中各类结点个数及关系；3.关 于无向图的度；4.无向图邻接矩阵中找邻接点；5.二叉树遍历;6顺序 循环队列元素个数；7.二叉排序树平均査找长度；8.哈夫曼树构造和 哈夫曼树的高度；9.最小生成树构造及其上权值之和；10.二叉排序树 中插入一个新结点算法填空。三解答题（5x6分=30分）1.

11、循环队列在特定设置下判满判空，计算元素位置；2.给出邻接矩阵， 画出该图，画出深度优先生成树；3.填写出散列表和平均査找长度;4 求某顶点到其余各顶点的最短路径;5构造一棵二叉排序树，画出删去 结点之后的二叉排序树.四. 算法阅读题（2X6分=12分）1.在带头结点的单链表中，删除数据元素的算法;2.中序遍历二叉树过程 中实现对一些节点的其他操作.五、算法设计题（8分）1.将一个简单的递归程序改写成非递归，实现相同功能.以上各例题中的答案并不保证完全正确，希望自己亲自验证。找到 并对照书本上的相应内容仔细阅读3遍以上。切实理解和掌握每个知识 点的实质，决不可以似是而非，侥幸过关。祝同学们考出好成绩!