《华师网络教育-本科-数据结构-期末复习资料.ppt》由会员分享,可在线阅读,更多相关《华师网络教育-本科-数据结构-期末复习资料.ppt(16页珍藏版)》请在三一办公上搜索。
1、数据结构期末考试复习提纲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、
2、若结点的存储地址与结点内容有某种确定的关系,则相应的存储结构应为散列存储。4、一种逻辑结构只能对应一种存储结构吗?错5、数值型和非数值型数据、原子类型和结构类型、加工型和引用型运算含义?6、数据结构可分为逻辑结构和非逻辑结构吗?错7、算法的正确性,一般不进行形式化的证明,而是用测试来验证。8、运算定义在逻辑结构上,算法定义在_结构上;运算指出“做什么”,算法指出_。9、线性结构可以顺序存储,也可以链接存储。非线性结构只能链接存储吗?10、程序设计的实质是:数据的表示和_,或者说,程序=数据结构_。,第二部分 复习提纲(不分题型),第1章 概论,1、顺序表、链表优缺点(存储、运算)?逻辑关系如何
3、表示?2、在顺序表中插入和删除结点时总要移动其它结点。(删尾结点、尾部添加时)3、顺序表插入和删除时,移动元素的个数与该元素的位置有关。4、顺序表中按值查找、按序号查找运算的复杂性分别为_、_。5、在链表的结点中,数据元素所占的存储量和整个结点所占的存储量之比称作_。6、链表的结点地址一定不连续。(可连续也可不连续)7、用尾指针表示单循环链表的好处是_。8、单链表中结点*p有且仅有一个后继结点的条件是_。,第2章 线性表,解:双向扫描:从前向后找一个正数,再从后向前找一个负数,然后交换两者位置。复杂性为O(n)。void moves(sqlist*L)int i,j;datatype x;i=
4、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、
5、栈和队列的共同特点是_。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
6、-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的下三角(含对角线)按行序存入一维数组B
7、1.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或1
8、4,即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
9、如何画中序、先序、后序线索二叉链表(线索二叉树)?解:以中序线索二叉链表为例,下列二叉树的中序线索二叉链表如图所示。详细过程见课本。,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,解:设二叉树结点类型为b
10、itree,函数名为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);/求
11、左子树中相应结点数 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条边的无向图的邻接矩阵中,表示边存在的
12、元素个数为_。10、对n个顶点和e条边的有向图,以邻接矩阵存储,则求图中某顶点入度的时间复杂度为_。11、有向图边数=邻接矩阵中1的个数;也=邻接表中的边表结点数。12、无向图边数=邻接矩阵中1的个数的一半;也=邻接表中的边表结点数的一半。,第6章 图,1、内排序是指_,稳定性是指_。2、可以将排序算法分为:插入排序、_、选择排序、_、分配排序。3、“就地排序”是指排序算法辅助空间的复杂度为_。O(1)4各种排序算法的结果总结。(好、坏、平均性能?稳定性?)5、不稳定的排序算法没有实际的应用价值吗?6、谁的空间复杂性为O(log2n)?7、时间复杂性为O(nlog2n)且空间复杂性为O(1)的
13、排序方法是_。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),请将关键字填到结点上。提示:中序序列递增。,