数据结构复习解答(7页).doc

《数据结构复习解答(7页).doc》由会员分享，可在线阅读，更多相关《数据结构复习解答(7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构复习解答-第 7 页问答题1.算法和程序的区别是什么呢？【参考答案】：算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执

2、行来体现。要设计一个好的算法通常要考虑以下的要求。正确。算法的执行结果应当满足预先规定的功能和性能要求。可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。高效。有效使用存储空间和有较高的时间效率。2. 抽象数据类型的定义由哪几部分组成？ 【参考答案】：数据对象、数据关系和基本操作三部分。 3. 按数据元素之间的逻辑关系不同，数据结构有哪几类？ 【参考答案】：线性结构、树型结构、图状结构和集合四类。 4. 你能举出几个你熟悉的序列的例子来吗？ 【参考答案】：如：0，1，2，9,A，B，C，Z。 5. 简述下列术语：数据、数据元素

3、、数据对象、数据结构、存储结构、数据类型和抽象数据类型。6.数据结构和数据类型两个概念之间有区别吗？【参考答案】：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。7. 简述线性结构与非线性结构的不同点。【参考答案】：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。8. 有下列两段描述：（1）void pro1( ) (2)void pro2( )n=2; y=0; While(n%2=0) x=5/y; n=n+2; printf(“%d,%dn,x,y); printf(“%d

4、n”,n); 这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？【参考答案】：（1）是一个死循环，违反了算法的有穷性特征。（2）出现除零错误，违反了算法的可行性特征。9. 分析并写出下面的各语句组所代表的算法的时间复杂度。 (1) for (i=0; in; i+)for (j=0; jm; j+)Aij=0;【参考答案】：O（m*n）(2) k=0; for( i=1; i=n; i+) for (j=i ; j=n; j+) k+;【参考答案】：O（n2）(3) i=1; while(i=n) i=i*3;【参考答案】：3 T(n)n即：T(n) log3n =O（log3n）

5、所以：T(n)= O（log3n） (4) k=0; for( i=1; i=n; i+) for (j=i ; j=n; j+) for (k=j ; k=n; k+) x += delta;【参考答案】：O（n3）(5) for(i=0,j=n-1;inext;Return n:14试设计实现在单链表中删去值相同的多余结点的算法。 (a)为删除前，(b)为删除后。1015181510H(a) 删除前181510H(b) 删除后答：void Deletaz(Linklist L) Lnode *p,*q,*r,*s; P=l-next;while (p) q=p;r=q-next;while

6、(r)if(r-data!=p-data)q=r;r=r-next;elses=r-next;q-next=s;free(r);r=s; P=p-next;15. 设有两个单链表A、B，其中元素递增有序，编写算法将A、B归并成一个按元素值递减（允许有相同值）有序的链表C，要求用A、B中的原结点形成，不能重新申请结点。答：void unit(Linklist A,Linklist B,Linklist C)Lnode *p,*q,*r,*s;P=A-next;q=next;C=A;r=C;While(p&q)if(p-dadadada)r=p;p=p-next;Elses=q;q=q-next;

7、s-next=r-next;r-next=s;r=s;16. 如果输入序列为1 2 3 4 5 6,试问能否通过栈结构得到以下两个序列:4 3 5 6 1 2和1 3 5 4 2 6;请说明为什么不能实现或如何才能得到。17. 设输入序列为2，3，4，5，6，利用一个栈能得到序列2，5，3，4，6吗？栈可以用单链表实现吗？【答案】1、输入序列为123456，不能得出435612，其理由是，输出序列最后两元素是12，前面4个元素（4356）得到后，栈中元素剩12，且2在栈顶，不可能栈底元素1在栈顶元素2之前出栈。 得到135426的过程如下：1入栈并出栈，得到部分输出序列1；然后2和3入栈，3出

8、栈，部分输出序列变为：13；接着4和5入栈，5，4和2依次出栈，部分输出序列变为13542；最后6入栈并退栈，得最终结果135426。2、不能得到序列2，5，3，4，6。栈可以用单链表实现，这就是链栈。由于栈只在栈顶操作，所以链栈通常不设头结点。18填空（1）一个字符串相等的充要条件是 和 。（2）串是指 的序列；空串是指 的串；空格串是指 的串。（3）设s=“IAMATEACHER”,其长度是_。（4）若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为 。19设s=”00001000010100001”, t =”0001”,说明其在朴素模式匹配算法中的匹配过程。

9、答： i=3第一趟匹配 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1(1)0 0 0 1 j=3 i=5 第二趟匹配0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 1(2) 0 0 0 1 j=420、已知一个二叉树的先序和中序序列，能否唯一确定一棵二叉树？并举例。若给定先序遍历序列和后序遍历序列，能否唯一确定，说明理由（或举例说明）。【参考答案】：前一个可以唯一确定一个二叉树，前序abdghcefi 中序 gdhbaecif若只知道前序和后序序列是不能确定唯一的二叉树的，如图中为二棵不同的二叉树，其先序和后序的序列相同，分别为：ba和ab：21、假定用于

10、通信的电文由8个字母A，B，C，D，E，F，G，H组成，各字母在电文中出现的概率为5，25，3，7，10，12，30，8，试为这8个字线设计哈夫曼编码。【参考答案】：954157818927124325473010022、对于图6.23中的树回答下列问题： （1）哪些结点是树叶？（2）哪个结点树根？（3）哪个结点是C双亲结点？ （4）哪个结点是C孩子结点？（5）哪些结点是F祖先结点？（6）哪些结点是B子孙结点？（7）这棵树的高度是多少? （8）结点J的深度是多少？23、请分别画出有3个结点的树和3个结点的二叉树的所有不同形态。24、已知某二叉树的后序遍历序列是dabec，中序遍历序列是deba

11、c，能否确定唯一的二叉树？它的前序序列是什么？25、选择题1）一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足下面 条件？A所有结点均无左孩子B所有结点均无右孩子C只有一个叶子结点D是任意一棵二叉树2）设n、m为一棵二叉树上的两个结点，在中序遍历时，n在m前面的条件是（ ）。An在m右方Bn是m祖先 Cn在m左方 Dn是m子孙3）在一棵非空二叉树的中序遍历中，根结点的右边_. A只有右子树上的所有结点 B只有右子树上的部分结点 C只有左子树上的所有结点 D只有左子树上的部分结点26、判断题 （1）完全二叉树一定存在度为1的结点。 （2）对一棵二叉树进行层次遍历时，应借助

12、于一个栈。 （3）若已知二叉树的先序遍历序列和后序遍历序列，可确定唯一的一棵二叉树。27. 图遍历不唯一的因素有哪些？答：遍历的方法不同；开始遍历的顶点不同；存储结构不同。28. 证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。答：具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。（根结点不唯一）29 设一个有向图为G=(V,E),其中V= v1, v2, v3, v4,E=,请画出该有向图,并求出每个顶点的入度和出度,画出相应的邻接矩阵、邻接链表答：有向图：顶点 入度 出度V1 2 1V2 1 2V3 1 0V4 1 2邻接距阵：邻接链表：30.

13、 图的连通分量和最小生成树的区别是什么？答：图的连通分量是图的极大连通子图，不一定包含图中所有顶点；而最小生成树是连通网的带权路径长度最小的生成树，它包含了图中所有顶点和n-1条边。31. 根据图7.26：（1）假设指定从v1出发，用普里姆方法画出最小生成树的过程。 （2）用克鲁斯卡尔方法画出最小生成树的过程。答：（1）假设指定从v1出发，用普里姆方法画出最小生成树的过程：（2）用克鲁斯卡尔方法画出最小生成树的过程：33. 写出图7.28的三种可能的拓朴排序结果。答:5,2,1,3,4,6,7,85,2,4,3,1,7,6,87,5,2,1,3,4,6,833若二叉排序树中的一个结点存在两个孩子，那么它的中序后继结点是否有左孩子？它的中序前驱结点是否有右孩子？【参考答案】：若p是给定的二叉排序树中的某个结点，且p有左、右孩子。按照中序遍历的思想，先中序遍历p的左子树，再访问根结点p，最后遍历p的右子树。左子树最后访问的结点x为p的前驱结点，x一定没有右子树，否者x不是左子树上中序遍历中最后访问的结点。因而，p的前驱结点x没有右孩子。同理，p的中序后继结点x没有左孩子。34设有一记录集合，集合中各记录的关键字分别为：90，31，12，40，74，94，14，26，35，85，64，9，55，60。(1)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树。