华师大数据结构复习题.pptx

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,#,1,、四种基本逻辑结构是：,_,？,2,、算法区别于程序的主要地方是,_,。,3,、算法评价一般考虑四个方面：,_,、,_,、,_,、,_,；其中在数据结构里主要考虑,_,。,4,、时间和空间性能往往是一对矛盾吗？,5,、空间耗费包括代码部分吗？,6,、程序段时间复杂性的简单判断？,7,、算法的时间复杂性越高，则从计算机速度提高得到的收益就越大吗？,第二部分 复习提纲,(,不分题型,),1,、顺序表和链表哪个可以按序号随机存取？按值能否随机存取？,2,顺序表和链表中的逻辑关系分别用什么表示？,3,链表中结点物理地址一定不连续吗？,4,、寻找单链表中当前结点的后继和前趋的时间复杂度分别是,_,。,5,、单链表中插入、删除结点的执行步骤？,6,、何谓存储密度？顺序表、链表分别如何？,L,a,1,a,2,a,n,7,、例：将顺序表中所有负数移动到表的前端，要求移动次数小。,解：双向扫描：从前向后找一个正数，再从后向前找一个负数，然后交换两者位置。复杂性为,O,（,n,）。,void moves(sqlist*L),int i,j;,datatype x;,i=1;j=L-n;/,设数组下标从,1,开始,while(idataidataj=0/,从后向前找负数,if(idatai;L-datai=L-dataj;L-dataj=x;,i+;j;,+-+-+-+-+-,8,、例：删除顺序表中所有的正数，要求移动次数小。,解：搜索顺序表，对每一个正数，先不删除，而是累计当前正数个数,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;/,调整表长,+-+-+-+-+-,1,、什么问题需要用栈或队列来描述？,2,怎样克服假溢出？,3,、已知进栈序列，怎样判断哪些出栈序列可能或不可能？,4,、,C,语言中，串的存储方式是,_,。,5,、,空串、空白串、串相等、模式匹配含义？,6,、,strcmp(),、,strlen(),、,strcat(),、,strcpy(),函数功能？,1,、数组的基本运算是,读、写,。没有插入删除等运算,2,、为什么说数组是随机存储结构？,3,、对称矩阵、稀疏矩阵，谁压缩存储后还可以随机存取？,4,、十字链表中的结点需存储非零元素的哪五个信息？,5,、广义表的分类，图形表示与识别？,6,、广义表不仅是线性表的推广，也是树的推广。,7,、用,head(),和,tail(),函数在广义表,A=(a,(x,y,z),b),中取出原子,b,。,1,、,3,个结点可构成,_,个不同形态的二叉树。,2,、,二叉树的先根遍历序列和后根遍历序列相同，则该二叉树的特征是,_,。,3,、能否,有二叉树，其任何遍历次序都相同？,4,、,某完全二叉树有,5,个叶子，则其结点总数为,_,。,(10,或,9,，一般,2n,或,2n-1),5,、,某完全二叉树的第,5,层只有,6,个结点，则其叶子结点数是,_,。,6,、树的先根遍历需要借助,_,来实现、层次遍历需要借助,_,来实现。,(,栈,队列,),7,、,线索二叉树上，求结点的,(,遍历,),前趋和后继时可利用线索得到，是否就不必进行遍历了？,8,、,线索二叉树中，线索的含义？,9,、哈夫曼树的特点？,10,、如何画中序、先序、后序线索二叉链表（线索二叉树）？,解：以中序线索二叉链表为例，下列二叉树的中序线索二叉链表如图所示。详细过程见课本。,A,B,C,D,E,F,C,B,D,E,A,0,0,0,0,0,F,1,1,1,1,1,1,1,NULL,NULL,中序：,D B E F A C,A,B,C,D,E,F,NULL,NULL,中序线索二叉树,中序线索二叉链表,11,如何由先序中序、后序中序还原出二叉树？,解：,对前序序列，序列的第一个点就是整个二叉树的根；,对后序序列，序列的最后一个点就是整个二叉树的根；,对中序序列，以根为界，序列的前一部分为根的左子树，后一部分为根的右子树；并且，前一部分是左子树的中序序列，后一部分是右子树的中序序列。,若给定了前序和中序序列，反复利用上面的和，即由前序序列找到根，由中序序列得到左、右子树；再对每个子树由前序序列找到子树的根，由中序序列得到子树的左、右子树，等等类推，每次得到一个点,(,子树的根,),，从而逐渐还原和构造出该二叉树。,例 由先根和中根序列构造二叉树,G,先根序列,中根序列,A,B,H,F,D,E,C,K,G,H,B,D,F,A,E,K,C,H,F,D,K,G,B,C,E,A,后根,+,中根,呢？,12,、例：判断二叉树是否所有结点都为正数。,解：设二叉树根指针类型为,bitree,，函数名为,detect,，函数返回判断结果,int detect(bitree t),if(t=NULL)return 1;/,空树返回真，递归出口,if(t-datalchild),/,由左右子树共同决定真或假,13,、例：判断是否二叉树,t,否满足小根堆的特点,。,解：设二叉树结点类型为,bitree,，函数名为,detect,，函数返回判断结果。,int detect(bitree t),if(t=NULL)return 1;/,空树返回真,if(t-lchild!=NULL&t-lchild-datadata)|,(t-rchild!=NULL,return detect(t-lchild),1,n,个顶点及,e,条边的无向图，邻接表中的边结点数为,_,，邻接矩阵中,1,的个数为,_,。若是有向图呢？,2,、,n,个顶点的无向图、有向图，边数范围分别是多少？,3,、图的,DFS,遍历类似树的,_,遍历，是其推广。,4,、,在邻接矩阵和邻接表上进行,BFS,或,DFS,遍历时，时间复杂性分别为多少？,5,、某图有,3,个连通分量，则要访问所有顶点时，必须调用,_,次,DFS,遍历算法。,6,、,若有向图的邻接矩阵中，主对角线以下的元素均为零，则该图可拓扑排序吗？,7,、拓扑排序可用以分析工程能否顺利进行。,8,、何谓,关键路径？,0 1 0 1 0,1 0 1 0 1,0 1 0 1 1,1 0 1 0 0,0 1 1 0 0,V1,1,V2,2,V3,3,V4,4,m,2,4,1,3,1,各种排序算法的复杂度如何？,(,好、坏、平均,?),(1),、哪些最好和最坏时间复杂度都为,O(nlog,2,n),？,(2),、趟数最少和最多情况如何？,(3),、哪些,空间复杂性为,O(n),？,2,、初始序列基本有序时，哪些排序方法好？,3,、,n,个数据直接插入排序，可能的最少比较次数是,_,。,4,、希尔排序的增量序列中，最后一个增量为,_,。,5,、,堆的定义？,6,、,基数排序的排序趟数？,练习：,(49,38,13,76,65,97,27,49,),7,各种排序方法步骤如何？（会写每趟结果，冒泡、选择、快速排序等）,1,、顺序查找法既可用于顺序表，也可用于链表吗？,2,、二分查找对数据的要求？,3,、分块查找如何分块较好？效率如何？,4,、二叉排序树按,_,遍历结果递增有序。,5,、,散列表中要解决的两个主要问题是：,_,、,_,。,6,、,解决散列引起的冲突问题，常采用的方法有哪些？,7,、何谓,堆积现象？开散列表会出现吗？,8,、数据量越多，散列表的查找效率就越低吗？,i,i+1,i+2,i+k,i+k+1,#,#,#,#,#,