《数据结构》2015年12月考试期末大作业

数据结构 要求: 1. 独立完成,作答时要写明所选题型、题号 2. 题目要用 A4 大小纸张,手写作答后将每页纸张拍照或扫描为图片形式 3. 提交方式:请以图片形式打包压缩上传,请确保上传的图片正向显示 4. 上传文件命名为“中心-学号-姓名-科目.rar” 5. 文件容量大小:不得超过 10MB。

一、编程题(请在以下题目中任选 2 题作答,每题 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) { (二) 程序编写题 已知某哈希表的装载因子小于 1,哈希函数 H(key)为关键字(标识符)的第一个字母在字母 表中的序号, 处理冲突的方法为线性探测开放定址法。 试编写一个按第一个字母的顺序输出 哈希表中所有关键字的算法。

(三)

程序编写题

设顺序表 L 是一个递增有序表,试写一算法,将 x 插入 L 中,并使 L 仍是一个有序表。

(四) 程序编写题 用标准 C 语言实现 Hanoi 塔问题

(五)

程序编写题

1.设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符),要求利用原单链表 中结点空间设计出三个单链表的算法,使每个单链表只包含同类字符。

2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。

(六)

程序编写题

1.设有一组初始记录关键字序列(K1,K2,?,Kn) ,要求设计一个算法能够在 O(n)的时间 复杂度内将线性表划分成两部分,其中左半部分的每个关键字均小于 Ki,右半部分的每个 关键字均大于等于 Ki。 2. 设有两个集合 A 和集合 B,要求设计生成集合 C=A∩B 的算法,其中集合 A、B 和 C 用 链 式存储结构表示。

(七)

程序编写题

1. 设计在单链表中删除值相同的多余结点的算法。 2. 设计一个求结点 x 在二叉树中的双亲结点算法。

二、 解答题(请在以下题目中任选 1 题作答,共 20 分)
(八) 解答题 设待排序记录的关键字序列为{46, 55, 13, 42, 94, 05, 17, 70}写出其第一趟快速排 序过程。 (要求写出每次交换后的序列,并且枢轴记录到位也算一次交换) 初始关键字: 46 1 次交换后: 2 次交换后: 3 次交换后: 4 次交换后: 5 次交换后: 55 13 42 94 05 17 70

(九) 解答题 对下面的带权无向图采用 prim 算法从顶点①开始构造最小生成树。 (写出加入生成树顶点集 合 S 和选择 Edge 的顺序) ① 9 ② 5 ④ 11 S: 顶点号 ① ① ① ① ① ① 10 7 6 ⑤ 8 Edge: (顶点,顶点,权值) (, , ) (, , ) (, , ) (, , ) (, , ) ③ 7 ⑥

(十)

解答题

若二叉树中各结点的值均不相同, 则由二叉树的前序序列和中序序列, 或由其后序序列和中 序序列均能唯一地确定一棵二叉树, 但由前序序列和后序序列却不一定能唯一地确定一棵二 叉树。 (1)已知一棵二叉树的前序序列和中序序列分别为 ABDGHCEFI 和 GDHBAECIF, 请画出此二叉 树。 (2)已知一棵二叉树的在序序列和后序序列分别为 BDCEAFHG 和 DECBHGFA, 请画出此二叉树。 (3)已知一棵二叉树的前序序列和后序序列分别为 AB 和 BA,请画出这两棵不同的二叉树。 (十一) 解答题 已知一棵二叉树的先序序列是 ABCDEFGHIJK, 中序序列是 CDBGFEAHJIK, 请构造出该二叉树。 (十二) 解答题 写出下图所示的 AOV 网的可能拓扑序列,要求至少写出五个

B A C

D

E

F

(十三) 解答题 设有一个求解汉诺塔(Hanoi)的递归算法 voidHANOI (int n , int peg1 , int peg2 , int peg3) { if (n= =1) printf(”move %d to %d\n”,peg1,peg3); else { HANOI (n-1, peg1, peg3, peg2); printf(”move %d to %d\n”,peg1,peg3); HANOI (n-1, peg2, peg1, peg3) ; } } 假定采用 HANOI(3,1,2,3)去调用上述算法,则写出整个输出结果的前四行内容。

三、 画图题(请在以下题目中任选 1 题作答,共 20 分)
(十四) 画图题 已知二维数组表示的图的邻接矩阵如下图所示。 试分别画出自顶点 1 出发进行遍历所得的深 度优先生成树和广度优先生成树。

(十五) 画图题 将给定的图简化为最小的生成树,要求从顶点 1 出发。

8 2 10 12 6 6 9

1 3

5 3 15 7 2 7 5

4

(十六) 画图题 某子系统在通信联络中只可能出现 8 种字符, 其出现的概率分别为 0.05, 0.29, 0.07, 0.08, 0.14,0.23,0.03,0.11 试设计赫夫曼编码

0 23 0 11 0 5

0 1 1 1 3

1 0 29 0 14 7 0 1 1 1 8

(十七) 画图题 已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ, 中序遍历的结果是 EBCDAFHIGJ, 试 画出这棵二叉树,并给出这棵二叉树的后序遍历序列。 (十八) 画图题 设有序顺序表中的元素依次为 017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和 搜索不成功的平均搜索长度。 (十九) 画图题 将下面的森林变换成二叉树

A B C D

E F H

G I J K

(二十) 画图题 已知一树的双亲表示法如下,其中各兄弟结点是依次出现的,画出该树对应的二叉树。 1 data paren t A 0 2 B 1 3 C 1 4 D 1 5 E 2 6 F 2 7 G 3 8 H 3 9 I 4 10 J 4 11 K 5 12 L 6 13 M 6 14 N 7 15 O 8


相关文档

2015-2016学年第二学期期末考试《数据结构》大作业
《管理信息系统》2015年12月考试期末大作业
2015年数据结构期末考试题及答案
《会计学》2015年12月考试期末大作业
《网络经济》2015年12月考试期末大作业
天大《数据结构》2017年12月考试期末大作业
《工程造价管理》2015年12月考试期末大作业
《经济法》2015年12月考试期末大作业
《资产评估学》2015年12月考试期末大作业
5 2015年数据结构期末考试题及答案
电脑版