资源描述：
《数据结构A卷答__》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、华南农业大学期末考试试卷（A卷）答案2006学年第1学期 考试科目： 数据结构 考试类型：（闭卷） 考试时间： 120 分钟学号姓名年级专业题号一二三四总分得分评阅人一、选择题（单选，每题2分，共50分）1C2B3C4C5A6B7A8D9C10B11A12D13B14D15D16D17C18C19A20C21B22D23C24A25A二、填空题（每题2分，共14分）1Head->next=NULL2n-132254455562526三、解答题（以下有6题，除了特别申明外每题必答共30分）1(5分)已经带权无向图如图1所示，
2、利用克鲁斯科尔(Kruskal)算法，画出该无向图的最小生成树的每一步52(6分)如图2所示的有向图,请分别给出该图的邻接矩阵表示(1分),逆邻接表表示(2分)和十字链表表示(3分)（1）邻接矩阵表示(1分)3(6分)如图3所示的二叉树[1]该二叉树的深度是多少,结点B,E的平衡因子分别是多少.[2]画出该二叉树的先序线索化树解：【1】该二叉树的深度是5;(1分)；结点B,E的平衡因子分别是2,-2(2分)5【2】先序线索化二叉树如下图（3分）4(7分)（04级应数同学必做，05级同学可以不答）对于待排序序列{12,11,13
3、,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,49[2]平衡二叉树为;(3分)搜索成功的平均查找长度ASL＝(1+2x2+3x4+1x4)/8=21/8(1分)5(7分)（05级同学必做，
4、04级应数同学可不答)有序表按关键码排列如下：{7，14，18，21，23，29，31，35，38，42，46，49，52}[1]写出在表中用折半查找关键码为14的数据元素的过程，[2]并且画出有序表折半查找的判断树,并且求出等概率查找成功的平均查找长度ASL。解;[1]:折半查找关键码为14的数据元素的过程如下(3分)50123456789101112137141821232931353842464952↑↑low=1①设置初始区间high=13────────────────────────────↑mid=7↑↑low=
5、1high=6high=mid-1，调整到左半区────────────────────────────↑mid=3↑↑low=1high=2high=mid-1，调整到左半区────────────────────────────↑mid=1↑↑low=2high=2low=mid+1，调整到右半区────────────────────────────↑mid=2查找成功，返回找到的数据元素位置为2[2]有序表折半查找的判断树(3分)等概率查找成功的平均查找长度ASL=1/13(1+2x2+3x4+4x6)=3.15(1分
6、)6(6分)如图4所示AOE是某个工程的计划图,各个顶点表示事件,边表示活动,边上的权值表示各活动所需要的时间[1]分别计算事件v4和活动a5的最早发生时间和最晚发生时间.[2]求该AOE图的关键路径解：[1]l(v4)=e(v4)=6(2分)l(a5)=4e(a5)=3(2分)[2]关键路径：v1,v2,v5,v7和v1,v4,v5,v7或者a1,a2,a4,a8,a9(2分)四，（共6分）算法设计(下面2题必须任意选择一题作为设计)1．5已知带头结点的单链线性表La和Lb中的元素都是按值非递减排列，现归并La和Lb得到新单
7、链线性表Lc,使得Lc中的元素也是按值非递减排列，用La的头结点作为Lc的头结点，归并完了释放Lb的头结点。解答;定义线性表的单链表结点：typedefstructLNode{ElemTypedata;structLNode*next;}*LinkList;算法:voidmergeList(LinkListLa,LinkListLb,LinkListLc){pa=La->next;pb=Lb->next;Lc=pc=La；//用La的头结点作为Lc的头结点。while(pa&&pb){if(pa->data<=pb->data
8、){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．设计一个算法分别统计出二叉树的叶子结点，
