您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 资本运营 > 数据结构03-04期末考试B答案
四川大学期末考试题解答(2003-2004学年第二学期)课程名:数据结构(B)计算机科学与技术专业适用人数:学院:专业:教师姓名:姓名:学号:成绩:一、设n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局;然后从出局的下一个人重新开始报数,数到第m个人,再让他出局,……,如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是:对于任意给定的n,s和m,求出这n个人的出局序列。请以n=9,s=1,m=5为例,人工模拟Josephus的求解过程以求得问题的解。(9分)【解答】出局人的顺序为5,1,7,4,3,6,9,2,8。二、列出右图所示二叉树的叶结点、分支结点和每个结点的层次。(9分)【解答】二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。结点①的层次为0;结点②、③的层次为1;结点④、⑤、⑥的层次为2;结点⑦、⑧的层次为3;结点⑨的层次为4。三.线性表可用顺序表或链表存储。试问:(9分)(1)两种存储表示各有哪些主要优缺点?(3分)(2)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自动改变、在此情况下,应选用哪种存储表示?为什么?(3分)(3)若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时,应采用哪种存储表示?为什么?(3分)【解答】(1)顺序存储表示是将数据元素存放于一个连续的存储空间中,实现顺序存取或(按下标)直接存取。它的存储效率高,存取速度快。但它的空间大小一经定义,在程序整个运行期间不会发生改变,因此,不易扩充。同时,由于在插入或删除时,为保持原有次序,平均需要移动一半(或近一半)元素,修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放,且只要存储器中还有空间,就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序,只需要保持原来的逻辑顺序,因此不必移动数据,只需修改它们的链接指针,修改效率较高。但存取表中的数据元素时,只能循链顺序访问,因此存取效率不高。(2)如果有n个表同时并存,并且在处理过程中各表的长度会动态发生变化,表的总数也可能自动改变、在此情况下,应选用链接存储表示。如果采用顺序存储表示,必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快,必须平均分配空间。在程序运行过程中,有的表占用的空间增长得快,有的表占用的空间增长得慢;有的表很快就用完了分配给它的空间,有的表才用了少量的空间,在进行元素的插入时就必须成片地移动其他的表的空间,以空出位置进行插入;在end1end2输出受限的双端队列end1end2输入受限的双端队列元素删除时,为填补空白,也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示,一个表的存储空间可以连续,可以不连续。表的增长通过动态存储分配解决,只要存储器未满,就不会有表溢出的问题;表的收缩可以通过动态存储释放实现,释放的空间还可以在以后动态分配给其他的存储申请要求,非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形,处理十分简便和快捷。所以选用链接存储表示较好。(3)应采用顺序存储表示。因为顺序存储表示的存取速度快,但修改效率低。若表的总数基本稳定,且很少进行插入和删除,但要求以最快的速度存取表中的元素,这时采用顺序存储表示较好。四、设有一个双端队列,元素进入该队列的顺序是1,2,3,4。试分别求出满足下列条件的输出序列。(9分)(1)能由输入受限的双端队列得到,但不能由输出受限的双端队列得到的输出序列;(3分)(2)能由输出受限的双端队列得到,但不能由输入受限的双端队列得到的输出序列;(3分)(3)既不能由输入受限的双端队列得到,又不能由输出受限的双端队列得到的输出序列。(3分)【解答】允许在一端进行插入和删除,但在另一端只允许插入的双端队列叫做输出受限的双端队列,允许在一端进行插入和删除,但在另一端只允许删除的双端队列叫做输入受限的双端队列。输出受限双端队列不能得到的输出序列有:41324231输人受限双端队列不能得到的输出序列有:42134231所以有:(1)4132(2)4213(3)4231五、使用(1)顺序表示和(2)二叉链表表示法,分别画出右图所示二叉树的存储表示。(9分)【解答】六、试分别找出满足以下条件的所有二叉树:(9分)(1)二叉树的前序序列与中序序列相同;(3分)(2)二叉树的中序序列与后序序列相同;(3分)(3)二叉树的前序序列与后序序列相同。(3分)【解答】(1)二叉树的前序序列与中序序列相同:空树或缺左子树的单支树;(2)二叉树的中序序列与后序序列相同:空树或缺右子树的单支树;(3)二叉树的前序序列与后序序列相同:空树或只有根结点的二叉树。七、已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。(9分)【解答】当前序序列为ABECDFGHIJ,中序序列为EBCDAFHIGJ时,逐步形成二叉树的过程如下图所示:八、给定权值集合{15,03,14,02,06,09,16,17},构造相应的霍夫曼树,并计算它的带权外部路径长度。(9分)【解答】①②③④⑤⑥⑦⑨⑧∧∧∧∧∧∧∧∧∧∧0123456789101112131415161718①②③④⑤⑥⑦⑧⑨顺序表示二叉链表表示EBCDFHIGJAABEFCDHIGJABEFCDGJHIABEFCDGJHI1503140206091617F:020315140609161705(Ⅰ)此树的带权路径长度WPL=229。九、画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中,边的条数为n(n-1)/2。(9分)【解答】02031514060916170511(Ⅱ)(Ⅲ)0203151409161705110620(Ⅳ)02031415091617051106202902031415091617051106202933(Ⅴ)1个顶点的无向完全图2个顶点的无向完全图3个顶点的无向完全图4个顶点的无向完全图5个顶点的无向完全图1503140206091617F:02031514060916170502031514060916170511(Ⅰ)(Ⅱ)(Ⅲ)0203151409161705110620(Ⅳ)02031415091617051106202902031415091617051106202933(Ⅴ)0203141509051106202916173349(Ⅵ)020315090511062029161733491482(Ⅶ)【证明】在有n个顶点的无向完全图中,每一个顶点都有一条边与其它某一顶点相连,所以每一个顶点有n-1条边与其他n-1个顶点相连,总计n个顶点有n(n-1)条边。但在无向图中,顶点i到顶点j与顶点j到顶点i是同一条边,所以总共有n(n-1)/2条边。十、有n个顶点的无向连通图至少有多少条边?有n个顶点的有向强连通图至少有多少条边?试举例说明。(9分)【解答】n个顶点的无向连通图至少有n-1条边,n个顶点的有向强连通图至少有n条边。例如:特例情况是当n=1时,此时至少有0条边。十一、以邻接表为存储结构,写一个基于DFS遍历策略的算法,求图中通过某顶点vk的简单回路(若存在)。(10分)解:算法思想,从给定顶点v4出发进行深度优先搜索,在搜索过程中判断当前访问的顶点是否为v4。若是,则找到一条回路。否则继续搜索。为此设一个顺序栈cycle记录构成回路的顶点序列,把访问顶点的操作改为将当前访问的顶点入栈;相应地,若从某一顶点出发搜索完再回溯,则做退栈操作,同时要求找到的回路的路径应大于2。另外还设置一个found,出值为0,当找到回路后为1。Voiddfscycle(ALGrph*G,intV4){inti,j,top=0,V=V4,found=0,w;intVisitde[100],cycle[100];EdgeNode*P;i=1;cycle[i]=Vi/*从V是开始搜索*/Visitde[v]==1;P=G[v]-firstedge;While(p!=NULL!!top0)&&!found){while(p!=NULL&&!found)if(p-adjvex==V4&&i2)found=1;/*找到回路*/elseif(visited[p-adjvex]==0)p=p-next;/*找到下一个邻接点*/elst{w=p-adjvex;/*记下路径,继续搜索*/visited[w]=1;i++;cycle[i]=w;top++;stack[top]=p;p=G[w]-firstedge;}if(!found&&top0)/*沿原路径退回后,另选路径进行搜索*/{p=attack[top];top--;p=p-next;i--;}}/*endwhile*/if(found){for(j=1;j=i;j++)printf(“%d,”,cycle[j]);/*打印回路的顶点序列*/printf(“%d,\n”,V);}elseprintf(“设有通过点V4的回路!\n”)}
本文标题:数据结构03-04期末考试B答案
链接地址:https://www.777doc.com/doc-2429082 .html