数据结构例题详解ppt课件

数据结构考研辅导例题详解,浙江大学计算机学院,1,内容提纲,2,自测题解答,单项选择题：在每小题给出的四个选项中，请选出一项最符合题目要求的。从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较多少个结点？nn/2(n-1)/2(n+1)/2,3,自测题解答,某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？单链表仅有头指针的单循环链表双链表仅有尾指针的单循环链表,4,自测题解答,设一个栈的输入序列是1，2，3，4，5,则下列序列中，是栈的合法输出序列的是？51234451324312532154,5,自测题解答,三叉树中，度为1的结点有5个，度为2的结点3个，度为3的结点2个，问该树含有几个叶结点？8101213,N1=5;N2=3;N3=2N=N0+10N1=5*1+3*2+2*3,6,自测题解答,对二叉排序树进行什么遍历可以得到从小到大的排序序列？前序遍历中序遍历后序遍历层次遍历,7,自测题解答,12个结点的AVL树的最大深度是？3456,等价问题：深度为h的AVL树的最少结点数是？,8,自测题解答,对于一个共有n个结点、k条边的森林，共有几颗树？nknk+1nk1不能确定,每棵有m个结点的树必有m-1条边n=mk=mt（t是树的个数）t=?,9,自测题解答,已知有向图G=(V,E)，其中V=v1,v2,v3,v4,v5,v6，E=,。G的拓扑序列是?v3,v4,v1,v5,v2,v6v1,v3,v4,v5,v2,v6v3,v1,v4,v5,v2,v6v1,v4,v3,v5,v2,v6,10,自测题解答,任何一个带权无向连通图的最小生成树是唯一的是不唯一的有可能不唯一有可能不存在,11,自测题解答,判定一个有向图是否存在回路，除了拓扑排序，还可以用图的遍历求最小生成树最短路径求关键路径,12,自测题解答,在图中自a点开始进行深度优先遍历算法可能得到的结果为a,b,e,c,d,fa,e,d,f,c,ba,c,f,e,b,da,e,b,c,f,d,13,自测题解答,以下哪个命题是正确的？对于带权无向图G=(V,E)，M是G的最小生成树，则M中任意两点V1到V2的路径一定是它们之间的最短路径。P是顶点s到t的最短路径，如果该图中的所有路径的权值都加1，P仍然是s到t的最短路径。深度优先遍历也可用于完成拓扑排序。以上都不是。,14,自测题解答,假定有k个关键字互为同义词，若用线性探测法把这k个关键字存入散列表中，至少要进行多少次探测？k-1kk+1k(k+1)/2,15,自测题解答,就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是堆排序归并排序快速排序堆排序快速排序归并排序,16,自测题解答,下面四种排序算法中，稳定的算法是快速排序归并排序堆排序希尔排序,17,自测题解答,综合应用题树中任意两结点之间都存在一条路径，两结点的距离即定义为路径的长度。距离最远的两个结点的距离定义为树的“直径”。给定一棵用二叉链表存储的二叉树，其结点构造为如图。指针Root指向根结点。请设计时间复杂度为O(n)的算法（n为树中结点的个数）求二叉树的直径。,直径=max(左树深度+右树深度),18,自测题解答,intBinaryTreeHeight(treeT,int,19,自测题解答,考研大纲中例题（15分）已知一棵二叉树采用二叉链表存储。现定义二叉树中结点X0的根路径为从根结点到X0的一条路径，请编写算法输出该二叉树中最长的根路径（多条最长根路径中只输出一条即可。算法可用C或C+或JAVA语言实现）。参考答案：计算树的深度，同时记住最深的结点p。然后用非递归先序遍历找到p，此时路径上的结点都在堆栈中。,20,自测题解答,下图中每个顶点表示一个岛，每条边表示岛屿间建桥的成本，找到一个算法计算正确的造桥方法，使得所有的岛屿都能连通，并且总的造价最小，给出这个算法的名字，并给出求解过程。,求最小生成树：普里姆(Prim)算法或克鲁斯卡尔(Kruskal)算法。,21,自测题解答,假设有n个值不同数据元素存储在顺序表中，要求不经过完全排序就从中选出自小到大顺序的前m(mn)个元素，试问要如何进行才能使最坏情况下的元素间所作的比较次数最少？,改造堆排序，建立最小堆。,22,分类测试,线性表、堆栈、队列、数组树与图查找与排序,23,自测题令P代表入栈，O代表出栈。则将一个字符串3*a+b/c变为3a*bc/+的堆栈操作序列是哪个？（例如将ABC变成BCA的操作序列是PPOPOO。）PPPOOOPPOPPOOOPOPOPOPPOPPOOOPOPPOOPPOPPOOOPOPPOOPPOPOOPO,线性表、堆栈、队列、数组,24,自测题从一个栈顶指针为ST的链栈中删除一个结点时，用x保存被删结点的值，则执行：x=ST;ST=ST-next;x=ST-data;ST=ST-next;x=ST-data;x=ST-data;ST=ST-next;,线性表、堆栈、队列、数组,25,自测题线性表在什么情况下适用于使用链式结构实现?需经常修改中的结点值需不断对进行删除插入中含有大量的结点中结点结构复杂,线性表、堆栈、队列、数组,26,自测题若已知一个栈的入栈序列是1，2，3，n，其输出序列为p1，p2，p3，pn。若p1=n，则pi为：inini+1不确定,线性表、堆栈、队列、数组,27,自测题链表不具有的特点是：插入、删除不需要移动元素可随机访问任一元素不必事先估计存储空间所需空间与线性长度成正比,线性表、堆栈、队列、数组,28,自测题若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？单链表双链表单循环链表带头结点的双循环链表,线性表、堆栈、队列、数组,29,自测题若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用哪种存储方式最节省时间？顺序表双链表单循环链表带头结点的双循环链表,线性表、堆栈、队列、数组,30,自测题数组A1.5,1.6每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A5,5的地址为1140114511201125,线性表、堆栈、队列、数组,1000+(291)*5,31,自测题设高为h的二叉树只有度为0和2的结点，则此类二叉树的结点数至少为_，最多为_？2h-1+1,2h12h,2h12h1,2h12h1,2h-11,树与图,32,自测题设每个d叉树的结点有d个指针指向子树，有n个结点的d叉树有多少空链域？n(d-1)n(d-1)+1nd以上都不是,树与图,n个结点有nd个指针除了根，每个结点被1个指针所指nd(n1),33,自测题哪种树，树中任何结点到根结点路径上的各结点值是有序的？堆二叉排序树完全二叉树以上都不是,树与图,34,自测题某二叉树的中序序列和后序序列正好相反，则该二叉树一定是空或只有一个结点高度等于其结点数任一结点无左孩子任一结点无右孩子,树与图,35,自测题下面是某二叉树三种遍历的部分结果，请画出相应的二叉树。前序:_B_F_ICEH_G中序:D_KFIA_EJC_后序:_K_FBHJ_G_A,树与图,A,B,D,K,D,I,H,J,G,E,C,36,自测题请设计算法求二叉树中叶结点的个数。,树与图,voidcountLeaf(TreeT,int,37,自测题一棵二叉排序树结构如下,各结点的值从小到大依次为1-8，请标出各结点的值。,树与图,1,2,3,4,5,6,7,8,38,自测题给定一个整数x，以及一个可能的查找的关键字序列K0,KN-1，请设计算法判别一个序列是否是一个可能的二叉排序树上进行的查找序列。（例如：1,4,2,3就是查找3的序列，对应二叉排序树如图。而2,4,1,3就不可能是。）要求算法时间复杂度为O(N)。,树与图,答案1：先构造树，再判断是否二叉排序树,39,树与图,boolIs_BST_sequence(intK,intN)if(Nkeykey)Parent-rightchild=node;elseParent-leftchild=node;Parent=node;returnIS_BST(root,可以用简单的后序遍历吗？,40,树与图,boolIS_BST(TreeT,int*min,int*max)if(!T-leftchild,41,树与图,答案2：boolIs_BST_sequence(intK,intN)if(NK1)max=K0;min=MIN_ELEMENT;elsemax=MAX_ELEMENT;min=K0;for(i=1;i=max|Ki+1=max|Ki+1Ki+1)max=Ki;elsemin=Ki;if(KN-1=KN-2)returnFALSE;returnTRUE;,42,自测题递归地从大到小输出二叉排序树T中所有关键字不小于x的元素。,树与图,SortBST(treeT,intx)if(T-RightChild)SortBST(T-RightChild,x);if(T-datadata);if(T-LeftChild)SortBST(T-LeftChild,x);,43,自测题在有N个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。O(logN)O(N)O(NlogN)O(N2),树与图,44,自测题给定链表表示的二叉树，判断其是否为完全二叉树。答案1：使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。,树与图,45,树与图,boolJudgeComplete(BiTreeT)if(!T)returntrue;QueueIn(Q,T);/初始化队列，根结点指针入队while(!QueueEmpty(Q)T=QueueOut(Q);/出队if(T-lchild,46,自测题森林的二叉树用T表示。已知T的前序和中序遍历结果，请画出对应的森林前序：ABCDEFGHIJKL中序：CBEFDGAJIKLH,树与图,A,A,H,47,自测题设一段文本中包含字符a,b,c,d,e，其出现频率相应为3,2,5,1,1。则经过哈夫曼编码后，文本所占字节数为40362512,树与图,48,自测题给定字符出现频率以及哈夫曼编码的正确长度，现对于任一套输入的编码，判断其是否哈夫曼编码。,树与图,49,树与图,核心部分：while(codeij!=0)if(codeij=0)if(!tmp-left_child)tmp-left_child=new_node();elseif(tmp-left_child-data0)ok=false;tmp=tmp-left_child;if(codeij=1)if(!tmp-right_child)tmp-right_child=new_node();elseif(tmp-right_child-data0)ok=false;tmp=tmp-right_child;j+;if(!tmp-left_child/计算编码长度,50,自测题在AOE网中，什么是关键路径？最短回路从第一个事件到最后一个事件的最短路径最长回路从第一个事件到最后一个事件的最长路径,树与图,51,自测题用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是？逆拓扑有序拓扑有序无序的以上都不对,树与图,DFS:4,3,2,1,52,自测题某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。要解决这个问题，问：(1)可用什么数据结构表示城镇和道路？(2)请描述效率最高的算法。,树与图,答案：最小生成树；Prim,53,自测题某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可），并要求增设的道路条数为最少。要解决这个问题，问：(1)可用什么数据结构表示城镇和道路？(2)请用伪码描述效率最高的解法。,树与图,答案：DSF数连通集个数1,54,自测题给定n个村庄之间的交通图，若村庄i和j之间有道路，则将顶点i和j用边连接，边上的Wij表示这条道路的长度，现在要从这n个村庄中选择一个村庄建一所医院，问这所医院应建在哪个村庄，才能使离医院最远的村庄到医院的路程最短?,树与图,答案：先用Floyd求任意2点间最短路；对每个村庄，求它到其他村庄的最短路中最长的；找所有n条最长路中最短的，那个村庄就建医院。,55,自测题给定现有城镇道路统计表，表中列出了每条道路直接连通的城镇以及距离。现有一镇受灾，指定另一镇救援，要求设计算法使得救援队以最快速度到达。另外，救援队每经过一镇，可以得到一个单位的救援物资。要求在最快到达的同时带去最多的救援物资。,树与图,56,树与图,修改Dijkstra：if(Tv.Dist+CvwTw.Count)Tw.Count=Tv.Count+1;Tw.Path=v;/*DONOTforgetthis*/,57,自测题设有100个元素的有序序列，如果用折半插入排序再插入一个元素，则最大比较次数是（）2550107,查找与排序,58,自测题对线性表进行二分查找时，要求线性表必须（）以顺序方式存储以顺序方式存储,且数据元素有序以链接方式存储以链接方式存储,且数据元素有序,查找与排序,59,自测题散列表的地址区间为0-16,散列函数为H(K)=Kmod17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素