2011《数据结构》期末试卷 A卷(答案).doc

2011《数据结构》期末试卷_A卷(答案)厦门大学《_数据结构_》课程期末试卷信息科学与技术学院计算机科学系2009年级___专业主考教师:陈怡疆庄朝晖试卷类型:(A卷)一、(本题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分)简述二叉树的两种存储结构(顺序存储和链式存储)的数据结构及主要优缺点。在哈夫曼树中,使用哪种存储结构,并说明理由。答案:顺序存储结构:typedefSqBiTree[Max_Tree_Size];特点:使用数组存储二叉树上的结点元素,按照对应的完全二叉树的编号来存储二叉树。优点是适用于完全二叉树,访问方便。缺点是对于一般二叉树,较大地浪费了空间。(4分)链式存储结构:typedefstrutBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;特点:使用结构体来表示结点元素,使用指针来指向结点的左右孩子。优点是插入与删除方便,节省空间,缺点是不能快速地随机访问结点元素。(4分)在哈夫曼树中,使用静态三叉链表,这样可以方便地从根走到叶子,也可以从叶子走到根,而且可以随机访问和节省空间。(2分)三、(本题10分)一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来,试求出空格处的内容,并画出该二叉树。先序序列:__B__F__ICEH__G;中序序列:D__KFIA__EJC__;后序序列:__K__FBHJ__G__A。答案:先序序列:ABDFKICEHJG中序序列:DBKFIAHEJCG后序序列:DKIFBHJEGCA(11分)画出树得4分。ABCDEHJFGKI四、(本题10分)分别使用普里姆算法和克鲁斯卡尔算法求出图G1的最小生成树,仅需画出最小生成树的成长过程即可。图G10123451452566637答案:(1)普里姆算法求最小生成树的过程如下:5分012345101234513012345143012345145301234514523(2)克鲁斯卡尔算法如下:5分012345101234512012345123012345142301234514523五、(本题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)在等概率的情况下,求出该二叉排序树查找成功的平均查找长度。(3)针对上述10个键值,在不同的排列次序下所构造出