数据结构03-04期末考试A答案.doc

四川大学期末考试题解答(2003-2004学年第二学期)课程名: 数据结构(A) 计算机科学与技术专业适用 人数:学院: 专业: 教师姓名:姓名: 学号: 成绩:一. 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?【解答】若设顺序表中已有n = last+1个元素，last是顺序表的数据成员，表明最后表项的位置。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。插入时平均移动元素个数AMN(Averagy Moving Number )为删除时平均移动元素个数AMN为 二. 设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n(n+1)/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。【解答】计算公式三. 铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出进栈或出栈的序列)。【解答】(1) 可能的不同出栈序列有 种。(2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。3562244 4411111111 3 32 32 325 325 3256 32564 3256415344122226 1 1 13 135 1354 13542 13542 135426 四. 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。【解答】二叉树的叶结点有、。分支结点有、。结点的层次为0；结点、的层次为1；结点、的层次为2；结点、的层次为3；结点的层次为4。五. 在结点个数为n (n1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 【解答】结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。六. 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。【解答】具有3个结点的树 具有3个结点的二叉树七. 写出向堆中加入数据4, 2, 5, 8, 3, 6, 10, 14时，每加入一个数据后堆的变化。【解答】以最小堆为例：2224445552444238822223535533510648104864848614八. 给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充4叉树, 要求该4叉树中所有内部结点的度都是4, 所有外部结点的度都是0。这棵扩充4叉树的带权外部路径长度是多少?【解答】权值个数n = 11，扩充4 叉树的内结点的度都为4，而外结点的度都为0。设内结点个数为n4，外结点个数为n0，则可证明有关系n0 = 3 * n4 + 1。由于在本题中n0 = 113 * n4 +1，需要补2个权值为0的外结点。此时内结点个数n4 = 4。仿照霍夫曼树的构造方法来构造扩充4叉树，每次合并4个结点。6658524539332623151170000011 705239334518231526169826658375此树的带权路径长度WPL = 375 + 82 + 169 + 18 = 644。画出对其进行折半搜索时的二叉搜索树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。【解答】509677154897553275017908765612512503170094九. 给出右图的邻接矩阵、邻接表和邻接多重表表示。DA【解答】(1) 邻接矩阵EBFC310 A1 B2 C3 D4 E5 F(2) 邻接表42（出边表）54140 A1 B2 C3 D4 E5 F（入边表）30105312data fin fout(3) 邻接多重表（十字链表）i j ilink jlink0 1 (A, B)0 A1 B2 C3 D4 E5 F0 3 (A, D)1 2 (B, C)1 4 (B, E)2 5 (C, F)3 1 (D, B)3 4 (D, E)5 4 (F, E)十.对于如右图所示的有向图，试写出：(1) 从顶点出发进行深度优先搜索所得到的深度优先生成树；(2) 从顶点出发进行广度优先搜索所得到的广度优先生成树； 【解答】(1) 以顶点为根的深度优先生成树（不唯一）： 或 (2) 以顶点为根的广度优先生成树：十一.设在4地(A, B, C, D)之间架设有6座桥，如图所示：ACDB要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。(1) 试就以上图形说明：此问题有解的条件什么？（3分）(2) 设图中的顶点数为n，试用C或Pascal描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。（7分）【解答】将下图改为无向图，城市为结点，桥为边：ACDBBADC(1) 此为欧拉问题。有解的充要条件是每一个结点的度为偶数。（5分）EdgeNo AdjNo link(2) 数据结构采用邻接表，每个边结点有3个域，分别记录相关边号、邻接顶点号和链指针。另外，设置一个边的访问标志数组visited ，当visitedi = 0表示第i条边未访问过，一旦访问了第i条边，即将visitedi改为1。1 A2 B3 C4 D 2 2 2 2 2 2 2 2 2 2 2 2 nodelist visitedstruct edgenode /顶点结点int edgeno;/相关边号int adjvertex;/邻接顶点号edgenode * link;/链接指针;struct vertex /顶点int city;/顶点数据edgenode * first;/出边表指针;Typedef vertex * nodelist;/邻接表数组下面给出按深度优先搜索方法求解欧拉问题的递归算法。（5分）void dfs ( nodelist euler, int start, int n, int visited ) cout eulerstart.city ;/输出顶点数据edgenode * p = eulerstart.first;/找第一条关联的边while ( p != NULL ) /有int j = p-edgeno;/边号if ( visitedj = 0 ) /未走过visitedj = 1;/作边访问标记dfs ( euler, p-adjvertex, n, visited ); /按邻接顶点递归下去p = p-link;/查下一条关联的边主程序（5分）void main int count, n, i, j, k;cout n;nodelist euler= new vertexn;/创建邻接表数组for ( int i = 0; i euleri.city; euleri.first = NULL;cout “输入各条边！” i j k ;/i是边号码，j, k是顶点while ( i != 0 ) /i为0, 表示输入结束edgenode * p = new edgenode;/链入第j号链表p-edgeno = i; p-adjvertex = k;p-link = eulerj.first; eulerj.first = p;edgenode * p = new edgenode;/链入第k号链表p-edgeno = i; p-adjvertex = j;p-link = eulerk.first; eulerk.first = p;cin i j k ;count+;int *visited = new intcount;/创建访问标