《数据结构03-04期末考试A评分标准》由会员分享，可在线阅读，更多相关《数据结构03-04期末考试A评分标准（8页珍藏版）》请在金锄头文库上搜索。
1、11111121110122222212011211111101020100000nnnnnnnnnnnnnbaaaabbaaabbbaabbbbaCLLLLLLLL 时当时当,jiijCjijiCjiA四川大学期末考试题解答评分标准四川大学期末考试题解答评分标准(2003-2004 学年第二学期)课程名: 数据结构(A) 计算机科学与技术专业适用 人数:学院: 专业: 教师姓名:姓名: 学号: 成绩:一. 【解答】评分标准评分标准: :错一个扣错一个扣 4 4 分分, , 仅给结论扣仅给结论扣 2 2 分。分。 若设顺序表中已有 n = last+1 个元素，last 是顺序表的数据成员，表
2、明最后表项的位置。 又设插入或删除表中各个元素的概率相等，则在插入时因有 n+1 个插入位置(可以在表中最 后一个表项后面追加)，每个元素位置插入的概率为 1/(n+1)，但在删除时只能在已有 n 个 表项范围内删除，所以每个元素位置删除的概率为 1/n。 插入时平均移动元素个数 AMN(Averagy Moving Number )为删除时平均移动元素个数 AMN 为二. 【解答】评分标准评分标准: :错一个扣错一个扣 4 4 分。分。计算公式2n 21)n(n 1n1)01)1n(n(1n1in1n1AMNn0i L1n0i21n 21)n(n n10)12)(n1)(nn11)i(nn1
3、AMNL111110111000nnnnaaaaaaALOLL111110111000nnnnbbbbbbBLOLL 时当时当,1,1jijiCjiijCjiB2132)16/(16 12C三. 【解答】评分标准评分标准: :错一个扣错一个扣 4 4 分。分。 (1) 可能的不同出栈序列有 种。 (2) 不能得到 435612 和 154623 这样的出栈序列。因为若在 4, 3, 5, 6 之后再将 1, 2 出栈， 则 1, 2 必须一直在栈中，此时 1 先进栈，2 后进栈，2 应压在 1 上面，不可能 1 先于 2 出栈。 154623 也是这种情况。出栈序列 325641 和 1354
4、26 可以得到。3562244 44111111113 32 32 325 325 3256 32564 32564153441222261 1 13 135 1354 13542 13542 135426四. 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。【解答】评分标准评分标准: : 叶结点对叶结点对 3 分，分支结点对分，分支结点对 3 分，结点的层次对分，结点的层次对 3 分。分。二叉树的叶结点有、。分支结点有、。结点的层 次为 0；结点、的层次为 1；结点、的层次为 2；结点、的层次为 3；结 点的层次为 4。五. 在结点个数为 n (n1)的各棵树中，高度最小的树的高度是多
5、少？它有多少个叶结点？ 多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 【解答】评分标准: 错一个扣一分。 结点个数为 n 时，高度最小的树的高度为 1，有 2 层；它有 n-1 个叶结点，1 个分支结 点；高度最大的树的高度为 n-1，有 n 层；它有 1 个叶结点，n-1 个分支结点。3六. 试分别画出具有 3 个结点的树和 3 个结点的二叉树的所有不同形态。【解答】评分标准评分标准: :具有具有 3 个结点的树个结点的树 4 分，具有分，具有 3 个结点的二叉树个结点的二叉树 5 分。分。 具有 3 个结点的树 具有 3 个结点的二叉树七. 写出向堆中加入数
6、据 4, 2, 5, 8, 3, 6, 10, 14 时，每加入一个数据后堆的变化。【解答】评分标准评分标准: : 错一个扣一分。错一个扣一分。以最小堆为例：八. 给定一组权值: 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路 径长度的扩充 4 叉树, 要求该 4 叉树中所有内部结点的度都是 4, 所有外部结点的度都是 0。这棵扩充 4 叉树的带权外部路径长度是多少?【解答】评分标准评分标准: :未考虑需未考虑需要补要补 2 个权值为个权值为 0 的外结点扣的外结点扣 5 分，构造分，构造 Huffman 树每错一步扣树每错
7、一步扣 1 分，求分，求此树的带权路径长度此树的带权路径长度 4 分分。 权值个数 n = 11，扩充 4 叉树的内结点的度都为 4，而外结点的度都为 0。设内结点个数 为 n4，外结点个数为 n0，则可证明有关系 n0 = 3 * n4 + 1。由于在本题中 n0 = 113 * n4 +1，需要补 2 个权值为 0 的外结点。此时内结点个数 n4 = 4。 仿照霍夫曼树的构造方法来构造扩充 4 叉树，每次合并 4 个结点。此树的带权路径长度 WPL = 375 + 82 + 169 + 18 = 644。4444422255522884352834528346528346105283461
8、014007 0111523263339455258665866821691523261833394552375007 0114010000000000010010100000010100001010Edge九. 给出右图的邻接矩阵、邻接表和邻接多重表表示。【解答】评分标准评分标准: : 邻接矩阵、邻接表和邻接多重表各邻接矩阵、邻接表和邻接多重表各 3 分。分。 (1) 邻接矩阵ABCDEF5 或 (2) 邻接表(3) 邻接多重表（十字链表）十.对于如右图所示的有向图，试写出： (1) 从顶点出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点出发进行广度优先搜索所得到的广度优先生成树
9、； 【解答】评分标准评分标准: :错一个扣错一个扣 4 分。分。 (1) 以顶点为根的深度优先生成树（不唯一）： (2) 以顶点为根的广度优先生成树：0A1B2C3D4E5F10A1B2C3D4E5F324514403101352（出边表）（入边表）0A1B2C3D4E5Fdata fin fouti j ilink jlink0 1 (A, B)0 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)6十一.设在 4 地(A, B, C, D)之间架设有 6 座桥，如图所示：要求从某一地出发，经过每座桥恰巧一
10、次，最后仍回到原地。 (1) 试就以上图形说明：此问题有解的条件什么？（3 分） (2) 设图中的顶点数为 n，试用 C+描述与求解此问题有关的数据结构并编 写一个算法，找出满足要求的一条回路。（7 分）【解答】评分标准评分标准: : 有解的充要条件有解的充要条件 3 分，算法分，算法 dfs 给给 4 分，主函数分，主函数 3 分。分。将下图改为无向图，城市为结点，桥为边：(1) 此为欧拉问题。有解的充要条件是每一个结点的度为偶数。 （5 分）(2) 数据结构采用邻接表，每个边结点有 3 个域，分别记录相关边号、邻接顶点号和链指针。另外，设置一个边的访问标志数组 visited ，当 vis
11、itedi = 0 表示第 i 条边未访问过，一旦访问了第 i 条边，即将 visitedi改为 1。ABCDABCDABCD EdgeNo AdjNo link7struct edgenode /顶点结点int edgeno;/相关边号int adjvertex;/邻接顶点号edgenode * link;/链接指针;struct vertex /顶点int city;/顶点数据edgenode * first;/出边表指针;Typedef vertex * nodelist;/邻接表数组下面给出按深度优先搜索方法求解欧拉问题的递归算法。（5 分）void dfs ( nodelist eu
12、ler, int start, int n, int visited ) cout ;/输出顶点数据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;nodeli
13、st euler= new vertexn;/创建邻接表数组 2 2 2 2 2 2 2 2 2 2 2 2 1A2B3C4Dvisited nodelist8for ( 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;e
14、dgenode * 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;/创建访问标志数组for ( i = 0; i link;/查下一条关联的边;/计算该顶点的度if ( count % 2 != 0 ) cout “顶点的度不为偶数, 此题无解！” endl; exit(1); dfs ( euler, 0, n, visited );/从 0 号顶点开始delete visite
