第1-7章习题答案版

一.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。解答：●数据：指能够被计算机识别、存储和加工处理的信息载体。●数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。●数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。●数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。●逻辑结构：指数据元素之间的逻辑关系。●存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。●线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。●非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。2-4顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下,对有127个元素的顺序表进行插入,平均需要移动多少个元素?删除一个元素,又平均需要移动多少个元素?【解答】若设顺序表中已有n=last+1个元素，last是顺序表的数据成员，表明最后表项的位置。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。插入时平均移动元素个数AMN(AveragyMovingNumber)为127/2删除时平均移动元素个数AMN为126/22-6线性表可用顺序表或链表存储。试问：(1)两种存储表示各有哪些主要优缺点?1n0i21n21)n(nn10)12)(n1)((nn11)i(nn1AMN(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？(3)若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？【解答】(1)顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。(2)如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。(3)应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。5-1设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。【解答】设数组元素A[i][j]存放在起始地址为Loc(i,j)的存储单元中。∵Loc(2,2)=Loc(0,0)+2*n+2=644+2*n+2=676.∴n=(676-2-644)/2=15∴Loc(3,3)=Loc(0,0)+3*15+3=644+45+3=692.5-2设有一个nn的对称矩阵A，如图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问：(1)存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？(2)若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。(3)若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存下三角部分的情形下(图(c))应存于一维数组的什么下标位置？给出计算公式。【解答】(1)数组B共有n+(n-1)++1=n*(n+1)/2个元素。(2)只存上三角部分时，若ij，则数组元素A[i][j]前面有i-1行（1i-1，第0行第0列不算)，第1行有n个元素，第2行有n-1个元素，，第i-1行有n-i+2个元素。在第i行中，从对角线算起，第j号元素排在第j-i+1个元素位置（从1开始），因此，数组元素A[i][j]在数组B中的存放位置为n+(n-1)+(n-2)++(n-i+2)+j-i+1=(2n-i+2)*(i-1)/2+j-i+1=(2n-i)*(i-1)/2+j若ij，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。在数组B的第(2n-j)*(j-1)/2+i位置中找到。如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为当ij时，=(2n-i+1)*i/2+j-i=(2n-i-1)*i/2+j当ij时，=(2n-j-1)*j/2+i(3)只存下三角部分时，若ij，则数组元素A[i][j]前面有i-1行（1i-1，第0行第0列不算)，第1行有1个元素，第2行有2个元素，，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素A[i][j]在数组B中的存放位置为1+2++(i-1)+j=(i-1)*i/2+j若ij，数组元素A[i][j]在数组B中没有存放，可以找它的对称元素A[j][i]。在数组B的第(j-1)*j/2+i位置中找到。如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素A[i][j]在数组B中的存放位置可以改为当ij时，=i*(i+1)/2+j当ij时，=j*(j+1)/2+i6-2列出右图所示二叉树的叶结点、分支结点和每个结点的层次。【解答】二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、⑧的层次为3；结点⑨的层次为4。6-3使用(1)顺序表示和(2)二叉链表表示法，分别画出右图所示二叉树的存储表示。6-4在结点个数为n(n1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？【解答】结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。6-5如果一棵树有n1个度为1的结点,有n2个度为2的结点,…,nm个度为m的结点,试问有多少个度为0的结点?试推导之。【解答】总结点数n=n0+n1+n2+…+nm总分支数e=n-1=n0+n1+n2+…+nm-1=m*nm+(m-1)*nm-1+…+2*n2+n1则有1)1(20miinin6-6试分别找出满足以下条件的所有二叉树:(1)二叉树的前序序列与中序序列相同;(2)二叉树的中序序列与后序序列相同;(3)二叉树的前序序列与后序序列相同。【解答】(1)二叉树的前序序列与中序序列相同：空树或缺左子树的单支树；(2)二叉树的中序序列与后序序列相同：空树或缺右子树的单支树；(3)二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。6-11请画出右图所示的树所对应的二叉树。【解答】6-14已知一棵二叉树的前序遍历的结果是ABECDFGHIJ,中序遍历的结果是EBCDAFHIGJ,试画出这棵二叉树。①②③④⑤⑥⑦⑨⑧∧∧∧∧∧∧∧∧∧∧0123456789101112131415161718①②③④⑤⑥⑦⑧⑨顺序表示二叉链表表示1对应二叉树122334455667788【解答】当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示：6-16给定权值集合{15,03,14,02,06,09,16,17},构造相应的霍夫曼树,并计算它的带权外部路径长度。【解答】此树的带权路径长度WPL=229。6-17假定用于通信的电文仅由8个字母c1,c2,c3,c4,c5,c6,c7,c8组成,各字母在电文中出现的频率分别为5,25,3,6,10,11,36,4。试为这8个字母设计不等长Huffman编码,并给出该电文的总码数。【解答】已知字母集{c1,c2,c3,c4,c5,c6,c7,c8}，频率{5,25,3,6,10,11,36,4}，则Huffman编码为c1c2c3c4c5c6c7c801101000000111001010110001电文总码数为4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257EBCDFHIGJAABEFCDHIGJABEFCDGJHIABEFCDGJHI1503140206091617F：02031514060916170502031514060916170511(Ⅰ)(Ⅱ)(Ⅲ)0203151409161705110620(Ⅳ)02031415091617051106202902031415091617051106202933(Ⅴ)0203141509051106202916173349(Ⅵ)020315090511062029161733491482(Ⅶ)010000000000010010100000010100001010Edge7-1画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n个顶点的无向完全图中，边的条数为n(n-1)/2。【解答】【证明】在有n个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有n-1条边与其他n-1个顶点相连，总计n个顶点有n(n-1)条边。但在无向图中，顶点i到顶点j与顶点j到顶点i是同一条边，所以总共有n(n-1)/2条边。7-3给出右图的邻接矩阵、邻接表和邻接多重表表示。【解答】(1)邻接矩阵10061393625221771011114365C3C8C5C6C1C4C2C7000000011111111个顶点的无向完全图2