数据结构例题详解PPT课件.ppt

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,.,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,.,*,数据结构,考研辅导,例题详解,浙江大学计算机学院,内容提纲,自测题解答,1,分类测试,2,线性表、堆栈、队列、数组,A,树与图,B,查找与排序,C,自测题解答,单项选择题：在每小题给出的四个选项中，请选出一项最符合题目要求的。,从一个具有,n,个结点的单链表中查找其值等于,x,结点时，在查找成功的情况下，需平均比较多少个结点？,n,n/2,(n-1)/2,(n+1)/2,自测题解答,某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？,单链表,仅有头指针的单循环链表,双链表,仅有尾指针的单循环链表,自测题解答,设一个栈的输入序列是,1,，,2,，,3,，,4,，,5,则下列序列中，是栈的合法输出序列的是？,5 1 2 3 4,4 5 1 3 2,4 3 1 2 5,3 2 1 5 4,自测题解答,三叉树中，度为,1,的结点有,5,个，度为,2,的结点,3,个，度为,3,的结点,2,个，问该树含有几个叶结点？,8,10,12,13,N1=5;N2=3;N3=2,N=N0+10,N 1=5*1+3*2+2*3,自测题解答,对二叉排序树进行什么遍历可以得到从小到大的排序序列？,前序遍历,中序遍历,后序遍历,层次遍历,自测题解答,12,个结点的,AVL,树的最大深度是？,3,4,5,6,等价问题：深度为,h,的,AVL,树的最少结点数是？,自测题解答,对于一个共有,n,个结点、,k,条边的森林，共有几颗树？,n,k,n,k+1,n,k,1,不能确定,每棵有,m,个结点的树必有,m-1,条边,n=m,k=m t,（,t,是树的个数）,t=?,自测题解答,已知有向图,G=(V,E),，其中,V=v1,v2,v3,v4,v5,v6,，,E=,。,G,的拓扑序列是,?,v3,v4,v1,v5,v2,v6,v1,v3,v4,v5,v2,v6,v3,v1,v4,v5,v2,v6,v1,v4,v3,v5,v2,v6,1,2,3,4,5,6,自测题解答,任何一个带权无向连通图的最小生成树,是唯一的,是不唯一的,有可能不唯一,有可能不存在,自测题解答,判定一个有向图是否存在回路，除了拓扑排序，还可以用,图的遍历,求最小生成树,最短路径,求关键路径,自测题解答,在图中自,a,点开始进行深度优先遍历算法可能得到的结果为,a,b,e,c,d,f,a,e,d,f,c,b,a,c,f,e,b,d,a,e,b,c,f,d,a,b,e,c,d,f,自测题解答,以下哪个命题是正确的？,对于带权无向图,G=(V,E),，,M,是,G,的最小生成树，则,M,中任意两点,V1,到,V2,的路径一定是它们之间的最短路径。,P,是顶点,s,到,t,的最短路径，如果该图中的所有路径的权值都加,1,，,P,仍然是,s,到,t,的最短路径。,深度优先遍历也可用于完成拓扑排序。,以上都不是。,自测题解答,假定有,k,个关键字互为同义词，若用线性探测法把这,k,个关键字存入散列表中，至少要进行多少次探测？,k-1,k,k+1,k(k+1)/2,自测题解答,就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是,堆排序,快速排序,归并排序,堆排序,归并排序,归并排序,快速排序,堆排序,快速排序,归并排序,自测题解答,下面四种排序算法中，稳定的算法是,快速排序,归并排序,堆排序,希尔排序,自测题解答,综合应用题,树中任意两结点之间都存在一条路径，两结点的距离即定义为路径的长度。距离最远的两个结点的距离定义为树的“直径”。给定一棵用二叉链表存储的二叉树，其结点构造为如图。,指针,Root,指向根结点。请设计时间复杂度为,O(n,),的算法（,n,为树中结点的个数）求二叉树的直径。,Left_Child,Data,Right_Child,直径,=max(,左树深度,+,右树深度,),自测题解答,int BinaryTreeHeight(tree T,int,自测题解答,考研大纲中例题（,15,分）,已知一棵二叉树采用二叉链表存储。现定义二叉树中结点,X0,的根路径为从根结点到,X0,的一条路径，请编写算法输出该二叉树中最长的根路径（多条最长根路径中只输出一条即可。算法可用,C,或,C+,或,JAVA,语言实现）。,参考答案：,计算树的深度，同时记住最深的结点,p,。,然后用非递归先序遍历找到,p,，此时路径上的结点都在堆栈中。,自测题解答,下图中每个顶点表示一个岛，每条边表示岛屿间建桥的成本，找到一个算法计算正确的造桥方法，使得所有的岛屿都能连通，并且总的造价最小，给出这个算法的名字，并给出求解过程。,12,15,30,35,25,17,15,7,20,10,5,12,A,B,C,G,F,E,D,求最小生成树：,普里姆,(Prim),算法 或克鲁斯卡尔,(Kruskal),算法。,自测题解答,假设有,n,个值不同数据元素存储在顺序表中，要求不经过完全排序就从中选出自小到大顺序的前,m(mn,),个元素，试问要如何进行才能使最坏情况下的元素间所作的比较次数最少？,改造堆排序，建立最小堆。,分类测试,线性表、堆栈、队列、数组,树与图,查找与排序,23,自测题,令,P,代表入栈，,O,代表出栈。则将一个字符串,3*a+b/c,变为,3 a*b c/+,的堆栈操作序列是哪个？（例如将,ABC,变成,BCA,的操作序列是,PPOPOO,。）,PPPOOOPPOPPOOO,POPOPOPPOPPOOO,POPPOOPPOPPOOO,POPPOOPPOPOOPO,线性表、堆栈、队列、数组,自测题,从一个栈顶指针为,ST,的链栈中删除一个结点时，用,x,保存被删结点的值，则执行,：,x=ST;ST=,ST,-next;,x=ST-data;,ST=,ST,-next;x=ST-data;,x=ST-data;ST=,ST,-next;,线性表、堆栈、队列、数组,ST,x,自测题,线性表在什么情况下适用于使用链式结构实现,?,需经常修改中的结点值,需不断对进行删除插入,中含有大量的结点,中结点结构复杂,线性表、堆栈、队列、数组,自测题,若已知一个栈的入栈序列是,1,，,2,，,3,，,，,n,，其输出序列为,p1,，,p2,，,p3,，,，,pn,。若,p1=n,，则,pi,为,：,i,n i,n i+1,不确定,线性表、堆栈、队列、数组,自测题,链表不具有的特点是,：,插入、删除不需要移动元素,可随机访问任一元素,不必事先估计存储空间,所需空间与线性长度成正比,线性表、堆栈、队列、数组,自测题,若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间,？,单链表,双链表,单循环链表,带头结点的双循环链表,线性表、堆栈、队列、数组,自测题,若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间,？,顺序表,双链表,单循环链表,带头结点的双循环链表,线性表、堆栈、队列、数组,自测题,数组,A1.5,1.6,每个元素占,5,个单元，将其按行优先次序存储在起始地址为,1000,的连续的内存单元中，则元素,A5,5,的地址为,1140,1145,1120,1125,线性表、堆栈、队列、数组,1000+(29 1)*5,自测题,设高为,h,的二叉树只有度为,0,和,2,的结点，则此类二叉树的结点数至少为,_,，最多为,_,？,2,h-1,+1,2,h,1,2h,2,h,1,2h 1,2,h,1,2h 1,2,h-1,1,树与图,自测题,设每个,d,叉树的结点有,d,个指针指向子树，有,n,个结点的,d,叉树有多少,空链域？,n(d-1),n(d-1)+1,nd,以上都不是,树与图,n,个结点有,nd,个指针,除了根，每个结点被,1,个指针所指,nd (n 1),自测题,哪种树，树中任何结点到根结点路径上的各结点值是有序的？,堆,二叉排序树,完全二叉树,以上都不是,树与图,自测题,某二叉树的中序序列和后序序列正好相反，则该二叉树一定是,空或只有一个结点,高度等于其结点数,任一结点无左孩子,任一结点无右孩子,树与图,自测题,下面是某二叉树三种遍历的部分结果，请画出相应的二叉树。,前序,:_B_F_ICEH_G,中序,:D_KFIA_EJC_,后序,:_K_FBHJ_G_A,树与图,A,B,C,D,F,K,I,E,H,J,G,A,B,D,K,D,I,H,J,G,E,C,自测题,请设计算法求二叉树中叶结点的个数。,树与图,void countLeaf(Tree T,int&leafNum),if(!T-left&!T-right),/,如果,T,是叶结点,leafNum+;,/,则叶结点的数量,+1,else,/,如果,T,是中间结点，则继续先序遍历二叉树,if(T-left!=NULL),countLeaf(T-left,leafNum);,if(T-right!=NULL),countLeaf(T-right,leafNum);,自测题,一棵二叉排序树结构如下,各结点的值从小到大依次为,1-8,，请标出各结点的值。,树与图,1,2,3,4,5,6,7,8,自测题,给定一个整数,x,，以及一个可能的查找的关键字序列,K0,KN-1,，请设计算法判别一个序列是否是一个可能的二叉排序树上进行的查找序列。（例如：,1,4,2,3,就是查找,3,的序列，对应二叉排序树如图。而,2,4,1,3,就不可能是。）要求算法时间复杂度为,O(N),。,树与图,1,2,3,4,答案,1,：先构造树，再判断是否二叉排序树,树与图,bool Is_BST_sequence(int K,int N),if(N=2)return true;,Create root for K0;,Parent=root;,for(i=1;ikey key),Parent-rightchild=node;,else,Parent-leftchild=node;,Parent=node;,return IS_BST(root,可以用简单的后序遍历吗？,4,3,2,7,5,1,6,树与图,bool IS_BST(Tree T,int*min,int*max),if(!T-leftchild&!T-rightchild),(*min)=(*max)=T-key;,return true;,Left_flag=Right_flag=false;,if(T-leftchild&IS_BST(T-leftchild,&lmin,&lmax)&T-key lmax),|!T-leftchild),Left_flag=true;,if (T-rightchild&IS_BST(T-rightchild,&rmin,&rmax)&T-key rightchild),Right_flag=true;,if(Left_flag&Right_flag),if(T-leftchild)(*min)=lmin;,else (*min)=T-key;,if(T-rightchild)(*max)=rmax;,else (*max)=T-key;,return true;,else return false;,树与图,答案,2,：,bool Is_BST_sequence(int K,int N),if(NK1)max=K0;min=MIN_ELEMENT;,else max=MAX_ELEMENT;min=K0;,for(i=1;i=max|Ki+1=max|Ki+1 Ki+1)max=Ki;,else min=Ki;,if(KN-1=KN-2)return FALSE;,return TRUE;,min,max,Ki+1,max,min,Ki+1,自测题,递归地从大到小输出二叉排序树,T,中所有关键字不小于,x,的元素。,树与图,SortBST(tree T,int x),if(T-RightChild),SortBST(T-RightChild,x);,if(T-data data);,if(T-LeftChild),SortBST(T-LeftChild,x);,自测题,在有,N,个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。,O(logN,),O(N),O(NlogN,),O(N,2,),树与图,自测题,给定链表表示的二叉树，判断其是否为完全二叉树。,答案,1,：使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。,树与图,树与图,bool JudgeComplete(BiTree T),if(!T)return true;,QueueIn(Q,T);/,初始化队列，根结点指针入队,while(!QueueEmpty(Q),T=QueueOut(Q);/,出队,if(T-lchild,/,左子女入队,else if(T-lchild)return flase;,/,前边已有结点为空，本结点不空,else tag=1;,/,首次出现结点为空,if(T-rchild,/,右子女入队,else if(T-rchild)return false;,else tag=1;,/,while,return true;,自测题,森林的二叉树用,T,表示。已知,T,的前序和中序遍历结果，请画出对应的森林,前序：,A B C D E F G H I J K L,中序：,C B E F D G A J I K L H,树与图,A,B,C,D,E,F,G,H,I,J,K,L,A,H,B,D,G,C,E,F,I,K,L,J,自测题,设一段文本中包含字符,a,b,c,d,e,，其出现频率相应为,3,2,5,1,1,。则经过哈夫曼编码后，文本所占字节数为,40,36,25,12,树与图,12,7,4,2,5,3,2,1,1,自测题,给定字符出现频率以及哈夫曼编码的正确长度，现对于任一套输入的编码，判断其是否哈夫曼编码。,树与图,树与图,核心部分：,while(codeij!=0),if(codeij=0),if(!tmp-left_child)tmp-left_child=new_node();,else if(tmp-left_child-data 0)ok=false;,tmp=tmp-left_child;,if(codeij=1),if(!tmp-right_child)tmp-right_child=new_node();,else if(tmp-right_child-data 0)ok=false;,tmp=tmp-right_child;,j+;,if(!tmp-left_child,else ok=false;,Length+=fi*j;/,计算编码长度,自测题,在,AOE,网中，什么是关键路径？,最短回路,从第一个事件到最后一个事件的最短路径,最长回路,从第一个事件到最后一个事件的最长路径,树与图,自测题,用,DFS,遍历一个无环有向图，并在,DFS,算法退栈返回时打印相应的顶点，则输出的顶点序列是？,逆拓扑有序,拓扑有序,无序的,以上都不对,树与图,1,2,3,4,DFS:4,3,2,1,自测题,某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。要解决这个问题，问：,(1),可用什么数据结构表示城镇和道路？,(2),请描述效率最高的算法。,树与图,答案：最小生成树；,Prim,自测题,某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可），并要求增设的道路条数为最少。要解决这个问题，问：,(1),可用什么数据结构表示城镇和道路？,(2),请用伪码描述效率最高的解法。,树与图,答案：,DSF,数连通集个数,1,自测题,给定,n,个村庄之间的交通图，若村庄,i,和,j,之间有道路，则将顶点,i,和,j,用边连接，边上的,Wij,表示这条道路的长度，现在要从这,n,个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短,?,树与图,答案：,先用,Floyd,求任意,2,点间最短路；,对每个村庄，求它到其他村庄的最短路中最长的；,找所有,n,条最长路中最短的，那个村庄就建医院。,自测题,给定现有城镇道路统计表，表中列出了每条道路直接连通的城镇以及距离。现有一镇受灾，指定另一镇救援，要求设计算法使得救援队以最快速度到达。另外，救援队每经过一镇，可以得到一个单位的救援物资。要求在最快到达的同时带去最多的救援物资。,树与图,树与图,修改,Dijkstra,：,if(Tv.Dist+Cvw Tw.Count,),Tw.Count=Tv.Count+1;,Tw.Path=v;,/*DO NOT forget this*/,自测题,设有,100,个元素的有序序列，如果用折半插入排序再插入一个元素，则最大比较次数是,（）,25,50,10,7,查找与排序,自测题,对线性表进行二分查找时，要求线性表必须,（）,以顺序方式存储,以顺序方式存储,且数据元素有序,以链接方式存储,以链接方式存储,且数据元素有序,查找与排序,自测题,散列表的地址区间为,0-16,散列函数为,H(K)=K mod 17,。采用线性探测法处理冲突，并将关键字序列,26,，,25,，,72,，,38,，,8,，,18,，,59,依次存储到散列表中。元素,59,存放在散列表中的地址是（）,8,9,10,11,查找与排序,自测题,127,阶,B-,树中除根结点外所有非终端结点至少有多少棵子树？,2,64,126,63,查找与排序,自测题,给出关键字序列,321,，,156,，,57,，,46,，,28,，,7,，,331,，,33,，,34,，,63,，下面哪个选择是按,LSD,链式基数排序进行了一趟分配和收集的结果？,3313213363341564657728,1562832133133344657637,3213313363341564657728,5746287333463156321331,查找与排序,自测题,输入,N10,个只有,1,位数字的整数，试设计,O(N),复杂度的算法将其排序。,答案：基数排序,查找与排序,自测题,借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于,key,的记录。设此组记录存放于数组,rl.h,中。若查找成功，则输出该记录在,r,数组中的位置及其值，否则显示“,not find”,信息。请编写出算法并简要说明算法思想。,答案：将,key,看做支点，用快速排序中找支点位置的方法。,查找与排序,自测题,借助于快速排序的算法思想，在一组无序的记录中查找第,k,大元。请编写出算法并简要说明算法思想。,答案：,首先选支点将集合划分为,2,部分；,S1,和,S2,若,k|S2|,，则第,k,大元必在,S1,中，并且是第,(|S1|-N+k),大元。递归,查找与排序,其他可能的题目,实现指定的排序法并略做修改,双向冒泡,二路插入排序,表排序,+,任何一种排序,查找与排序,预祝大家,取得好成绩！,