数据结构A卷答__

华南农业大学期末考试试卷（A卷）答案2006学年第1学期 考试科目：数据结构考试类型：（闭卷）考试时间：120 分钟学号 姓名 年级专业 题号一二三四总分得分评阅人一、 选择题（单选，每题2分，共50分）1C2B3 C 4C5A6B7A8D9C10B11A12D13B14D15D16D17C18C19A20C21B22D23C24A25A二、 填空题（每题2分，共14分）1Head-next=NULL2n-1322544555625 26三、 解答题（以下有6题，除了特别申明外每题必答共30分）1 (5分)已经带权无向图如图1所示，利用克鲁斯科尔(Kruskal)算法，画出该无向图的最小生成树的每一步2 (6分) 如图2所示的有向图,请分别给出该图的邻接矩阵表示(1分),逆邻接表表示(2分)和十字链表表示(3分)（1）邻接矩阵表示(1分) 3 (6分)如图3所示的二叉树 1该二叉树的深度是多少, 结点B,E的平衡因子分别是多少. 2画出该二叉树的先序线索化树解：【1】该二叉树的深度是5;(1分)；结点B,E的平衡因子分别是2,-2 (2分)【2】先序线索化二叉树如下图（3分）4 (7分) （04级应数同学必做，05级同学可以不答）对于待排序序列12,11,13,49,26,14,8,7 1以快速排序算法来将该序列进行排序，写出各趟排序后的结果。2以该序列为输入序列来建立平衡二叉排序树，并求出其搜索成功的平均查找长度ASL;解 (1)快速排序算法中各趟排序的结果（3分。）第一趟排序结果：7,11,8,12,26,14,49,13第二趟排序结果：7,11,8,12,13,14,26,49第三趟排序结果：7,8,11,12,13,14,26,492平衡二叉树为;(3分)搜索成功的平均查找长度ASL(1+2x2+3x4+1x4)/8=21/8(1分)5(7分)（05级同学必做，04级应数同学可不答) 有序表按关键码排列如下：7，14，18，21，23，29，31，35，38，42，46，49，521写出在表中用折半查找关键码为14的数据元素的过程， 2并且画出有序表折半查找的判断树,并且求出等概率查找成功的平均查找长度ASL。解;1: 折半查找关键码为14的数据元素的过程如下(3分) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 7 141821232931353842464952 low=1 设置初始区间 high=13 mid=7 low=1 high=6 high=mid-1，调整到左半区 mid=3 low=1 high=2 high=mid-1，调整到左半区 mid=1 low=2 high=2 low=mid+1，调整到右半区 mid=2 查找成功，返回找到的数据元素位置为22 有序表折半查找的判断树(3分)等概率查找成功的平均查找长度ASL=1/13(1+2x2+3x4+4x6)=3.15 (1分)6 (6分)如图4所示AOE是某个工程的计划图,各个顶点表示事件,边表示活动,边上的权值表示各活动所需要的时间1分别计算事件v4和活动a5的最早发生时间和最晚发生时间.2求该AOE图的关键路径解：1l(v4)=e(v4)=6 (2分) l(a5)=4 e(a5)=3 (2分) 2关键路径：v1,v2,v5,v7和v1,v4,v5,v7或者a1,a2,a4,a8,a9 (2分)四，（共6分）算法设计 (下面2题必须任意选择一题作为设计) 1已知带头结点的单链线性表La和Lb中的元素都是按值非递减排列，现归并La和Lb得到新单链线性表Lc,使得Lc中的元素也是按值非递减排列，用La的头结点作为Lc的头结点，归并完了释放Lb的头结点。解答;定义线性表的单链表结点：typedef struct LNode ElemType data; struct LNode *next;*LinkList;算法:void mergeList(LinkList La, LinkList Lb, LinkList Lc)pa=La-next;pb=Lb-next; Lc=pc=La；/用La的头结点作为Lc的头结点。while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;/插入剩余段free(Lb);/释放Lb的头结点。2设计一个算法分别统计出二叉树的叶子结点，度为1的结点和度为2的结点个数。解答：定义树的结点类型为：typedef struct node ElemType data; struct node *lchild; struct node *rchild; BTree; static int a3;/定义全局静态变量数组，a0,a1,a2分别用来保存度为0,1,2的结点个/数。算法：void countnode(BTree *b) if(b=NULL)return; if(b-lchild