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

-数据结构复习解答-第 7 页问答题1.算法和程序的区别是什么呢？【参考答案】：算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。要设计一个好的算法通常要考虑以下的要求。正确。算法的执行结果应当满足预先规定的功能和性能要求。可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。高效。有效使用存储空间和有较高的时间效率。2. 抽象数据类型的定义由哪几部分组成？ 【参考答案】：数据对象、数据关系和基本操作三部分。 3. 按数据元素之间的逻辑关系不同，数据结构有哪几类？ 【参考答案】：线性结构、树型结构、图状结构和集合四类。 4. 你能举出几个你熟悉的"序列"的例子来吗？ 【参考答案】：如："0，1，2，9","A，B，C，Z"。 5. 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。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(“%dn”,n); 这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？【参考答案】：（1）是一个死循环，违反了算法的有穷性特征。（2）出现除零错误，违反了算法的可行性特征。9. 分析并写出下面的各语句组所代表的算法的时间复杂度。 (1) for (i=0; i<n; i+)for (j=0; j<m; 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）所以：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;i<j;i+,j- -)t=ai; ai= aj; ai=t;【参考答案】：基本语句共执行了n/2次，T(n)=O（n）10讨论线性表的逻辑结构和存储结构的关系，以及不同存储结构的比较。【答案】存储结构分为：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素间的逻辑关系链式存储结构：借助指示元素存储地址的指针表示数据元素间的逻辑关系 数据的逻辑结构只抽象反映数据元素的逻辑关系数据的存储（物理）结构数据的逻辑结构在计算机存储器中的实现数据的逻辑结构与存储结构密切相关： 算法设计 逻辑结构 算法实现 存储结构 顺序表：可以实现随机存取：O(1) 插入和删除时需要移动元素：O(n) 需要预分配存储空间; 适用于“不常进行修改操作、表中元素相对稳定”的场合。 链表：只能进行顺序存取：O(n) 插入和删除时只需修改指针：O(1) 不需要预分配存储空间; 适用于“修改操作频繁、事先无法估计最大表长”的场合。 应用问题的算法时间复杂度的比较 例如，以线性表表示集合进行运算的时间复杂度为O(n2), 而以有序表表示集合进行运算的时间复杂度为O(n)11判断下列概念的正确性(1) 线性表在物理存储空间中也一定是连续的。(2) 链表的物理存储结构具有同链表一样的顺序。(3) 链表的删除算法很简单，因为当删去链表中某个结点后，计算机会自动地将后继的各个单元向前移动。12试比较顺序存储结构和链式存储结构的优缺点。答：顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：（1）在做插入和删除操作时，需移动大量元素；（2）由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；（3）表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。13试写出一个计算链表中结点个数的算法，其中指针指向该链表的第一个结点。答：int linklist_num(linklist L,Lnode *p) int n=0;While(p)n+;p=p->next;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(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->dada<=q->dada)r=p;p=p->next;Elses=q;q=q->next;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出栈，部分输出序列变为：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”,说明其在朴素模式匹配算法中的匹配过程。答： 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、假定用于通信的电文由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，中序遍历序列是debac，能否确定唯一的二叉树？它的前序序列是什么？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）对一棵二叉树进行层次遍历时，应借助于一个栈。 （3）若已知二叉树的先序遍历序列和后序遍历序列，可确定唯一的一棵二叉树。27. 图遍历不唯一的因素有哪些？答：遍历的方法不同；开始遍历的顶点不同；存储结构不同。28. 证明：具有n个顶点和多于n-1条边的无向连通图G一定不是树。答：具有n个顶点n-1条边的无向连通图是自由树，即没有确定根结点的树，每个结点均可当根。（根结点不唯一）29 设一个有向图为G=(V,E),其中V= v1, v2, v3, v4,E=< v2, v1>,< v2, v3>,< v4, v1>,< v1, v4>,< v4, v2>,请画出该有向图,并求出每个顶点的入度和出度,画出相应的邻接矩阵、邻接链表答：有向图：顶点 入度 出度V1 2 1V2 1 2V3 1 0V4 1 2邻接距阵：邻接链表：30. 图的连通分量和最小生成树的区别是什么？答：图的连通分量是图的极大连通子图，不一定包含图中所有顶点；而最小生成树是连通网的带权路径长度最小的生成树，它包含了图中所有顶点和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)试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树。