天大2016年12月《数据结构》期末大作业考核要求.doc

数据结构要求: , 作答时要按照模版信息.... 填写完整,写明题型、题号; :手写作答或电脑录入,使用学院统一模版(模版详见附件); :以下两种方式任选其一, 1)手写作答的同学可以将作业以图片形式打包压缩上传; 2)提交电子文档的同学可以将作业以 word 文档格式上传; “中心-学号-姓名- ”或“中心-学号-姓名- ”; :不得超过 10MB 。请在以下几组题目中,任选一组题目作答,满分 100 分。第一组: 一、编程题(每小题 30 分,共 60分) (一) 设顺序表 L 是一个递增有序表,试写一算法,将 x 插入 L 中,并使 L 仍是一个有序表。(二) 用标准 C 语言实现 Hanoi 塔问题二、解答题( 20分) (一) 对下面的带权无向图采用 prim 算法从顶点①开始构造最小生成树。( 写出加入生成树顶点集合S 和选择 Edge 的顺序) ① 9 10 ②7③ 567 ④⑤⑥ 118 S: 顶点号 Edge : (顶点,顶点,权值) ①(,,) ①(,,) ①(,,) ①(,,) ①(,,) 1 三、画图题( 20分) (一) 将给定的图简化为最小的生成树,要求从顶点 1 出发。第二组: 一、编程题(每小题 30 分,共 60分) (一) 对于二维整数数组 A[m][n] ,对下列三种情况,分别编写相应的函数。 1. 求数组所有边缘元素的数值和。 int sum1(int A[M][N],int m ,int n) {2. 求从 A[0][0] 开始的互不相邻的所有元素的和注:一个元素的八个方向上的第一个元素均为相邻元素。 int sum2 (int A[M][N] , int m, int n) { 3. 假定 m=n ,并为偶数,请分别计算正、反两条对角线上的元素值之和。 int sum3(int A[M][N] , int n) { 1325476 8 5 15 3 10 122 79 6 (二) 1. 设计在单链表中删除值相同的多余结点的算法。 2. 设计一个求结点 x 在二叉树中的双亲结点算法。二、解答题( 20分) (一) 已知一棵二叉树的先序序列是 ABCDEFGHIJK ,中序序列是 CDBGFEAHJIK ,请构造出该二叉树。三、画图题( 20分) (一) 已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ, 中序遍历的结果是 EBCDAFHIGJ, 试画出这棵二叉树,并给出这棵二叉树的后序遍历序列。第三组: 一、编程题(每小题 30 分,共 60分) (一) 对于二维整数数组 A[m][n] ,对下列三种情况,分别编写相应的函数。 1. 求数组所有边缘元素的数值和。 int sum1(int A[M][N],int m ,int n) {2. 求从 A[0][0] 开始的互不相邻的所有元素的和注:一个元素的八个方向上的第一个元素均为相邻元素。 int sum2 (int A[M][N] , int m, int n) { 3. 假定 m=n ,并为偶数,请分别计算正、反两条对角线上的元素值之和。 int sum3(int A[M][N] , int n) {(二) 设顺序表 L 是一个递增有序表,试写一算法,将 x