华师网络教育-本科-数据结构-期末复习资料.ppt

数据结构期末考试复习提纲2013年6月,考试时间 90 分钟,第一部分 题型1单选题：2分15=30分概述1、线性表2、栈队串2、数组广义表1、树3、图2、排序2、查找22判断题：2分10=20分概述1、线性表1、栈队串1、数组广义表1、树2、图2、排序1、查找13填空题：2分11=22分概述1、线性表1、栈队串1、数组广义表2、树2、图2、排序1、查找14应用题：8分 2=16分树1、排序15程序题：6分 2=12分二叉链表1、顺序表1,1、四种基本存储结构是：顺序、链式、索引、散列；其中最基本的是：顺序、链式。2、若结点的存储地址可以反映数据间的逻辑关系，则相应的存储结构应为顺序存储。3、若结点的存储地址与结点内容有某种确定的关系，则相应的存储结构应为散列存储。4、一种逻辑结构只能对应一种存储结构吗？错5、数值型和非数值型数据、原子类型和结构类型、加工型和引用型运算含义？6、数据结构可分为逻辑结构和非逻辑结构吗？错7、算法的正确性，一般不进行形式化的证明，而是用测试来验证。8、运算定义在逻辑结构上，算法定义在_结构上；运算指出“做什么”，算法指出_。9、线性结构可以顺序存储，也可以链接存储。非线性结构只能链接存储吗？10、程序设计的实质是：数据的表示和_，或者说，程序=数据结构_。,第二部分 复习提纲(不分题型),第1章 概论,1、顺序表、链表优缺点（存储、运算）？逻辑关系如何表示？2、在顺序表中插入和删除结点时总要移动其它结点。（删尾结点、尾部添加时）3、顺序表插入和删除时，移动元素的个数与该元素的位置有关。4、顺序表中按值查找、按序号查找运算的复杂性分别为_、_。5、在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作_。6、链表的结点地址一定不连续。（可连续也可不连续）7、用尾指针表示单循环链表的好处是_。8、单链表中结点*p有且仅有一个后继结点的条件是_。,第2章 线性表,解：双向扫描：从前向后找一个正数，再从后向前找一个负数，然后交换两者位置。复杂性为O（n）。void moves(sqlist*L)int i,j;datatype x;i=1;j=L-n;/删除A1到An的所有零元素,设数组下标从1开始 while(idataidataj=0,9例：将顺序表中所有负数移动到表的前端，要求移动次数小。,解：搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数s，于是，对每个非正数，将它一次性前移s位。算法复杂性为O（n）。void dels(sqlist*L)int s,i;s=0;/正数计数器 for(i=0;in;i+)if(L-datai0 s+;/累计当前正数 else if(s0)L-datai-s=l-datai;/向前移动s位 L-n=L-n-s;/调整表长,10例：删除顺序表中所有的正数，要求移动次数小。,1、栈和队列的共同特点是_。2、栈操作的原则是_。3、设进栈顺序为A，B，C，D，E和F，出栈顺序为C，E，D，F，B，A，则栈的容量至少为_。4、若进栈序列为a,b,c，则通过入出栈操作能得到的a,b,c的不同排列个数为_。5、设入栈序列为A,B,C,D，则可能的出栈序列有哪些？（哪些不可能？）6、顺序栈在进行_运算时，可能发生栈的上溢，在进行_运算时，可能发生栈的下溢。7、顺序栈、链栈上进行进栈操作时，谁可不需判断栈满？8、链栈一般不需要头结点，因为无头结点的链栈运算也很方便。9、设链栈结点结构为(data,next)，top为栈顶指针，当执行入栈操作时需执行下列语句：p=new node;p-data=x;p-next=top;_;,第章 栈、队列和串,1数组的基本运算是_。（读、写，没有插入删除运算）2、多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为_(一维储存？)。3、数组各元素在内存中连续存放，故前后相邻的两元素物理地址相差为1或-1。4、多维数组可以顺序储存，所以实际上是一种顺序表？5、设C数组A2010每个元素占2个存储单元，且第1个元素的首地址为2000，则元素A89的存储地址为_。6、数组A1.81.10中，每个元素占3个单元，从首地址SA开始存放，若该数组按列存放，则元素A85的地址是_7、将对称矩阵A1.n1.n的下三角(含对角线)按行序存入一维数组B1.n(n+1)/2中，设Aij对应位置Bk，则k=_。8、稀疏矩阵常用的压缩存储方法有两种，即_、_。9、十字链表中的结点需存储非零元素的五个信息：行号、列号、值、_、_。10、稀疏矩阵的三元组表示中，三元组是指非零元素的_、_和_三项。,第4章 多维数组和广义表,1、某树所有结点的度数之和为100，则树中边数为_。2、树上每个结点都可有多个孩子、一个双亲吗？3、3个结点可构成_个不同形态的二叉树。4、何谓完全二叉树？（会识别）5、二叉树必须有结点的度为2吗？可否所有点的度都小于2？6、树的度是指树中结点的最大度数，所以二叉树的度为2。7、某完全二叉树有7个叶子，则其结点总数为_。（13或14,即2n-1或2n）8、若二叉树中没有度为1的结点，则为满二叉树？9、满二叉树是一种特殊的完全二叉树吗？10、深度为k的二叉树，结点数至多为_，结点数至少为_。11、深度为k的二叉树，叶子数至多为_，叶子数至少为_。12、高度为n、结点数也为n的二叉树，共有 2n-1 棵。(即等于满二叉树最底层叶子数)13、200个结点的二叉树，深度至多为 200，深度至少为 8。14、在深度为7的二叉树中，第5层上的结点数最少为_，最多为_。15、有无可能某二叉树的任何遍历次序都相同？16、某二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是_。17、二叉树、森林相互转换。,第5章 树形结构,18如何画中序、先序、后序线索二叉链表（线索二叉树）？解：以中序线索二叉链表为例，下列二叉树的中序线索二叉链表如图所示。详细过程见课本。,C,B,D,E,A,F,中序：D B E F A C,中序线索二叉链表,19例：求二叉树高度。,解：设二叉树结点类型为bitree，函数名为high，函数返回高度。int high(bitree t)int L,R;if(t=NULL)return 0;/空树高度为0，递归出口L=high(t-lchild);/求左子树高度R=high(t-rchild)/求右子树高度return(LR?L:R)+1;/当前高度=左右子树高度较大者+1,解：设二叉树结点类型为bitree，函数名为sum1，函数返回结点数。int sum1(bitree t)int L,R;if(t=NULL)return 0;/当前树为空，递归出口 L=sum1(t-lchild);/求左子树中相应结点数 R=sum1(t-rchild)/求右子树中相应结点数 if(t-lchild=NULL,20例：求二叉树中度为1的结点数。,22例：求二叉树中度为2的结点数。解：设二叉树结点类型为bitree，函数名为sum2，函数返回结点数。int sum2(bitree t)int L,R;if(t=NULL)return 0;/当前树为空，递归出口 L=sum2(t-lchild);/求左子树中相应结点数 R=sum2(t-rchild)/求右子树中相应结点数 if(t-lchild!=NULL,1、n个顶点的有向图，最少有_条边；最多有_条边。2、n个顶点的无向图，最少有_条边，最多有_条边。3、某无向图有28条边，则其顶点数最少为_。4、某图所有顶点的度数之和为200，则边数为_条。5、n个顶点的强连通图若只有n条边，则该有向图的形状是()。6、n个结点的有向图，若它有n(n1)条边，则它一定是强连通的。7、有向图出度、入度关系？（出度总和=入度总和）8、含n个顶点的无向图，其邻接矩阵中非零元素的个数就是图中的边数。9、在n个顶点和e条边的无向图的邻接矩阵中，表示边存在的元素个数为_。10、对n个顶点和e条边的有向图，以邻接矩阵存储，则求图中某顶点入度的时间复杂度为_。11、有向图边数=邻接矩阵中1的个数；也=邻接表中的边表结点数。12、无向图边数=邻接矩阵中1的个数的一半；也=邻接表中的边表结点数的一半。,第6章 图,1、内排序是指_，稳定性是指_。2、可以将排序算法分为：插入排序、_、选择排序、_、分配排序。3、“就地排序”是指排序算法辅助空间的复杂度为_。O(1)4各种排序算法的结果总结。(好、坏、平均性能？稳定性？)5、不稳定的排序算法没有实际的应用价值吗？6、谁的空间复杂性为O(log2n)？7、时间复杂性为O(nlog2n)且空间复杂性为O(1)的排序方法是_。8、Shell排序稳定吗？其时间性能与增量序列的选取关系大不大？9各种排序方法步骤。（会写每趟结果，归并、小根堆、直选、快速、希尔）,练习：(49,38,13,76,65,97,27,49),第7章 排序,1、查找表的逻辑结构是_。2、哪些方法属于静态查找、动态查找？（会区分）二者根本区别？3、对长度为100的顺序表，在等概率情况下，查找成功时的平均查找长度为_，在查找不成功时的平均查找长度为_。50.5、100(或101)4、对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为()。5、二分查找对数据的存储要求？有序且顺序存储6、二分查找的判定树是否是理想平衡的二叉排序树？7、在150个结点的有序表中二分法查找，不论成功与否，键值比较次数最多为_。8、如果根结点的左子树和右子树高度差不超过1，则该二叉树是平衡二叉树吗？9、二叉排序树的形态与关键字的输入序列有关，但平衡二叉排序树是相同的。,第8章 查找表,第7题：,或：,27=12828=256,log2151=7.x,即与完全二叉树高度相同,10例：已知右图为二叉排序树，关键字为（2,1,7,6,9,8），请将关键字填到结点上。提示：中序序列递增。,