1、2011数据结构期末试卷_A卷2011数据结构期末试卷_A卷编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心 ， 本文档内容是由我和我的同事精心编辑整理后发布的 ， 发布之前我们对文中内容进行仔细校对 ， 但是难免会有疏漏的地方 ， 但是任然希望（2011数据结构期末试卷_A卷）的内容能够给您的工作和学习带来便利 。
同时也真诚的希望收到您的建议和反馈 ， 这将是我们进步的源泉 ， 前进的动力 。
本文可编辑可修改 ， 如果觉得对您有帮助请收藏以便随时查阅 ， 最后祝您生活愉快 业绩进步 ， 以下为2011数据结构期末试卷_A卷的全部内容 。
11(完整word版)2011数据结构期末试卷_A卷（答案）亲爱的读者:本文内容由我和我的同事精 。

2、心收集整理后编辑发布到文库,发布之前我们对文中内容进行详细的校对,但难免会有错误的地方 ， 如果有错误的地方请您评论区留言,我们予以纠正,如果本文档对您有帮助 ， 请您下载收藏以便随时调用 。
下面是本文详细内容 。
最后最您生活愉快 O(_）O 厦门大学数据结构课程期末试卷信息科学与技术学院计算机科学系2009年级专业主考教师：陈怡疆 庄朝晖 试卷类型：（A卷）一、（本题10分）（1）线性表和广义表的主要区别是什么？（2）已知广义表： C=(a ， （b, (a ， b)）, （(a ， b), (a,b) ，则tail（head(tail(C)） =？答案：（1)线性表和广义表都是元素a1 ， a2,an组成的序列 ， 其主 。

3、要区别点在于：在线性表中 ， ai是单个元素（原子)；在广义表中 ， ai可以是单个元素（原子） ， 也可以是广义表 。
（7分）（2）tail(head（tail(C）) = (a,b)（3分)二、（本题10分）简述二叉树的两种存储结构（顺序存储和链式存储）的数据结构及主要优缺点 。
在哈夫曼树中 ， 使用哪种存储结构 ， 并说明理由 。
答案：顺序存储结构：typedef SqBiTreeMax_Tree_Size； 特点：使用数组存储二叉树上的结点元素 ， 按照对应的完全二叉树的编号来存储二叉树.优点是适用于完全二叉树,访问方便 。
缺点是对于一般二叉树 ， 较大地浪费了空间 。
（4分）链式存储结构：typedef strut Bi 。

4、TNode TElemType data;
struct BiTNode lchild, *rchild;
BiTNode, BiTree;
特点：使用结构体来表示结点元素 ， 使用指针来指向结点的左右孩子 。
优点是插入与删除方便,节省空间,缺点是不能快速地随机访问结点元素.(4分）在哈夫曼树中 ， 使用静态三叉链表 ， 这样可以方便地从根走到叶子 ， 也可以从叶子走到根 ， 而且可以随机访问和节省空间 。
（2分）三、（本题10分）一棵二叉树的先序、中序和后序序列分别如下 ， 其中有一部分未显示出来 ， 试求出空格处的内容 ， 并画出该二叉树 。
先序序列：__B__F__ICEH__G；中序序列：D__KFIA__EJC__ ；后序序 。

5、列:__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分 。
ABCDEHJFGKI四、（本题10分） 分别使用普里姆算法和克鲁斯卡尔算法求出图G1的最小生成树,仅需画出最小生成树的成长过程即可 。
图G10123451452566637答案：(1)普里姆算法求最小生成树的过程如下：5分012345101234513012345143012345145301234514523（2）克鲁斯卡尔算法如下：5分01234510123451201 。

6、2345123012345142301234514523五、（本题10分）有向图G2如上所示 ， （1）请写出图G2所有可能的拓扑序列: （2)请写出以顶点B为起始点的深度优先遍历序列和广度优先遍历序列 ， 并画出对应的生成树.遍历过程中当有多种选择时,编号小的结点优先 。
图G2ABCDE答案：（1)BACDE、BACED、BCADE、BCAED （5分 ， 少一个扣一分）(2）深度优先遍历序列：BADEC (3分）广度优先遍历序列:BACDE （3分）六、（本题15分）已知键值序列为45,56,83 ， 31,72,35,14 ， 47 ， 89,19 ， 要求给出：(1）按键值排列次序构造一棵二叉排序树.（2）在等概率 。

【数据结构|2011《数据结构》期末试卷_A卷】7、的情况下 ， 求出该二叉排序树查找成功的平均查找长度 。
（3)针对上述10个键值,在不同的排列次序下所构造出的不同形态的二叉排序树中 ， 在最坏和最好情况下 ， 二叉排序树的高度各是多少？答案： （1）455315614354783197289(2）在等概率情况下 ， 该二叉排序树的平均检索长度是：ASL=（1+2*2+3*4+4*3）/10=29/10=2.9(3）对于上述10个键值,在最坏情况下 ， 每个结点（除了叶子结点)只有右孩子（或者只有左孩子） ， 高度为10.在最好情况下 ， 高度为log210+1=4 。

来源：(未知)

【学习资料】网址：/a/2021/0321/0021739336.html

标题：数据结构|2011《数据结构》期末试卷_A卷