数据结构03-04期末考试A评分标准

2-1 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局， 四川大学期末考试题解答评分标准 (2003-2004学年第二学期) 课程名: 数据结构(A) 计算机科学与技术专业适用 人数: 学院: 专业: 教师姓名: 姓名: 学号: 成绩: 一. 【解答】评分标准:错一个扣4分, 仅给结论扣2分。 若设顺序表中已有n = last+1个元素，last是顺序表的数据成员，表明最后表项的位置。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。 插入时平均移动元素个数AMN(Averagy Moving Number )为 删除时平均移动元素个数AMN为 二. 【解答】评分标准:错一个扣4分。 计算公式 三. 【解答】评分标准:错一个扣4分。 (1) 可能的不同出栈序列有 种。 (2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。 3 5 6 2 2 4 4 4 4 1 1 1 1 1 1 1 1 3 32 32 325 325 3256 32564 325641 5 3 4 4 1 2 2 2 2 6 1 1 13 135 1354 13542 13542 135426 四. 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。 【解答】评分标准: 叶结点对3分，分支结点对3分，结点的层次对3分。 二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。 结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、⑧的层次为3；结点⑨的层次为4。 五. 在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 【解答】评分标准: 错一个扣一分。 结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。 六. 试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 【解答】评分标准:具有3个结点的树 4分，具有3个结点的二叉树5分。 具有3个结点的树 具有3个结点的二叉树 七. 写出向堆中加入数据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树每错一步扣1分，求此树的带权路径长度4分。 权值个数n = 11，扩充4 叉树的内结点的度都为4，而外结点的度都为0。设内结点个数为n4，外结点个数为n0，则可证明有关系n0 = 3 * n4 + 1。由于在本题中n0 = 11≠3 * n4 +1，需要补2个权值为0的外结点。此时内结点个数n4 = 4。 仿照霍夫曼树的构造方法来构造扩充4叉树，每次合并4个结点。 此树的带权路径长度WPL = 375 + 82 + 169 + 18 = 644。 九. 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】评分标准: 邻接矩阵、邻接表和邻接多重表各3分。 (1)​ 邻接矩阵 (2)​ 邻接表 (3) 邻接多重表（十字链表） 十..对于如右图所示的有向图，试写出： (1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树； 【解答】评分标准:错一个扣4分。 (1) 以顶点①为根的深度优先生成树（不唯一）：② ③ ④ ⑤ ⑥ (2) 以顶点②为根的广度优先生成树： 十一.设在4地(A, B, C, D)之间架设有6座桥，如图所示： 要求从某一地出发，经过每座桥恰巧一次，最后仍回到原地。 (1) 试就以上图形说明：此问题有解的条件什么？ （3分） (2) 设图中的顶点数为n，试用C++描述与求解此问题有关的数据结构并编写一个算法，找出满足要求的一条回路。 （7分） 【解答】评分标准: 有解的充要条件3分，算法dfs给4分，主函数3分。 将下图改为无向图，城市为结点，桥为边： (1) 此为欧拉问题。有解的充要条件是每一个结点的度为偶数。 （5分） (2) 数据结构采用邻接表，每个边结点有3个域，分别 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 相关边号、邻接顶点号和链指针。 另外，设置一个边的访问标志数组visited[ ]，当visited[i] == 0表示第i条边未访问过，一旦访问了第i条边，即将visited[i]改为1。 struct 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 << euler[start].city << ‘ -> ’; //输出顶点数据 edgenode * p = euler[start].first; //找第一条关联的边 while ( p != NULL ) { //有 int j = p->edgeno; //边号 if ( visited[j] == 0 ) { //未走过 visited[j] = 1; //作边访问标记 dfs ( euler, p->adjvertex, n, visited ); //按邻接顶点递归下去 } p = p->link; //查下一条关联的边 } } 主程序 （5分） void main { int count, n, i, j, k; cout << “输入顶点数 ：” ; cin >> n; nodelist euler= new vertex[n]; //创建邻接表数组 for ( int i = 0; i < n; i++) { //输入顶点数据, 指针置空 cin >> euler[i].city; euler[i].first = NULL; } cout << “输入各条边！” << endl; //输入各边数据 count = 0; //边计数 cin >> i >> j >> k >>; //i是边号码，j, k是顶点 while ( i != 0 ) { //i为0, 表示输入结束 edgenode * p = new edgenode; //链入第j号链表 p->edgeno = i; p->adjvertex = k; p->link = euler[j].first; euler[j].first = p; edgenode * p = new edgenode; //链入第k号链表 p->edgeno = i; p->adjvertex = j; p->link = euler[k].first; euler[k].first = p; cin >> i >> j >> k >>; count++; } int *visited = new int[count]; //创建访问标志数组 for ( i = 0; i < count; i++) visited[i] = 0; for ( i = 0; i < n; i++ ) { //判断各个顶点的度是否偶数 count = 0; p = euler[start].first; //找第一条关联的边 while ( p != NULL ) { //有 count++; p = p->link; //查下一条关联的边; } //计算该顶点的度 if ( count % 2 != 0 ) { cout << “顶点的度不为偶数, 此题无解！” << endl; exit(1); } } dfs ( euler, 0, n, visited ); //从0号顶点开始 delete [ ] visited; }