(完整word版)2011《数据结构》期末试卷_A卷(答案).pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《(完整word版)2011《数据结构》期末试卷_A卷(答案).pdf》由会员分享,可在线阅读,更多相关《(完整word版)2011《数据结构》期末试卷_A卷(答案).pdf(5页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1 一、(本题 10分)(1)线性表和广义表的主要区别是什么?(2)已知广义表:C=(a,(b,(a,b),(a,b),(a,b),则 tail(head(tail(C)=?答案:(1)线性表和广义表都是元素a1,a2,an组成的序列,其主要区别点在于:在线性表中,ai是单个元素(原子);在广义表中,ai 可以是单个元素(原子),也可以是广义表。(7 分)(2)tail(head(tail(C)=(a,b)(3 分)二、(本题 10 分)简述二叉树的两种存储结构(顺序存储和链式存储)的数据结构及主要优缺点。在哈夫曼树中,使用哪种存储结构,并说明理由。答案:顺序存储结构:typedef SqBi
2、TreeMax_Tree_Size;特点:使用数组存储二叉树上的结点元素,按照对应的完全二叉树的编号来存储二叉树。优点是适用于完全二叉树,访问方便。缺点是对于一般二叉树,较大地浪费了空间。(4分)链式存储结构:typedef strut BiTNode TElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;特点:使用结构体来表示结点元素,使用指针来指向结点的左右孩子。优点是插入与删除方便,节省空间,缺点是不能快速地随机访问结点元素。(4 分)在哈夫曼树中,使用静态三叉链表,这样可以方便地从根走到叶子,也可以从叶子走到根,而且可
3、以随机访问和节省空间。(2 分)三、(本题 10 分)一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来,试求出空格处的内容,并画出该二叉树。先序序列:_B_F_ICEH_G;中序序列:D_KFIA_EJC_;后序序列:_K_FBHJ_G_A。答案:先序序列:A B D F K I C E H J G 中序序列:D B K F I A H E J C G后序序列:D K I F B H J E G C A (11分)画出树得 4 分。厦门大学数据结构课程期末试卷信息科学与技术学院计算机科学系 2009 年级专业主考教师:陈怡疆庄朝晖 试卷类型:(A 卷)精品资料-欢迎下载-欢迎下
4、载 名师归纳-第 1 页,共 5 页 -2 四、(本题 10 分)分别使用普里姆算法和克鲁斯卡尔算法求出图G1的最小生成树,仅需画出最小生成树的成长过程即可。答案:(1)普里姆算法求最小生成树的过程如下:5 分0 1 2 3 4 5 1 0 1 2 3 4 5 1 3 0 1 2 3 4 5 1 4 3 A B C D E H J F G K I 0 1 2 3 4 5 1 4 5 2 5 6 6 6 3 7 图 G1 精品资料-欢迎下载-欢迎下载 名师归纳-第 2 页,共 5 页 -文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T
5、9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ
6、1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P
7、10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 Z
8、K2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6
9、R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文
10、档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS
11、5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A83(2)克鲁斯卡尔算法如下:5 分五、(本题 10分)有向图 G2 如上所示,(1)请写出图 G2 所有可能的拓扑序列:(2)请写出以顶点B 为起始点的深度优先遍历序列和广度优先遍历序列,并画出对应的生成树。遍历过程中当有多种选择时,编号小的结点优先。答案:(1)BACDE、B
12、ACED、BCADE、BCAED(5 分,少一个扣一分)(2)深度优先遍历序列:BADEC(3 分)0 1 2 3 4 5 1 4 5 2 3 0 1 2 3 4 5 1 4 2 3 0 1 2 3 4 5 1 2 3 0 1 2 3 4 5 1 2 0 1 2 3 4 5 1 0 1 2 3 4 5 1 4 5 3 0 1 2 3 4 5 1 4 5 2 3 A B C D E 图 G2 精品资料-欢迎下载-欢迎下载 名师归纳-第 3 页,共 5 页 -文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R
13、6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J
14、2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10
15、A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码
16、:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5
17、M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8
18、 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2L8P10R6 ZK2J2K6R10A8文档编码:CS5K5M6T9O8 HJ1K2
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 完整 word 2011 期末试卷 _A 答案
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内