第 3 次作业一、填空题（本大题共 20 分，共 10 小题，每小题 2 分）若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的和记录的。具有  个顶点的无向图，边的总数最多为。树在计算机内的表示方式有 ， ， 。三维数组 （下标从  开始计， 有  个元素），每个元素的长度是 ，则 的地址是。设 的地址是 数据以行为主方式存储直接插入排序用监视哨的作用是。 网中结点表示边表示。 网中结点表示边表示。非空的单循环链表  的尾结点（由  指针所指）满足条件。 构造最小生成树过程如下：（下图也可选代替代替）+!!解题方案：评分标准：参考答案：度为 2 的树从形式上看与二叉树很相似，但它的子树是无序的，而二叉树是有序的。即，在一般树中若某结点只有一个孩子，就无需区分其左右次序，而在二叉树中即使是一个孩子也有左右之分。解题方案：评分标准：参考答案：例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。　　这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。　　在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。解题方案：评分标准：参考答案：（）+ !    （）前序序列：ＡＢＣＥＤＦＨＧＩ 2中序序列：  3!24后序序列： ＥＣＨＦＪＩＧＤＢＡ（）+   C解题方案：评分标准：四、程序设计题（40 分，共 4 题，每小题 10 分）参考答案：由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树有深度。对每一结点，找其双亲，双亲的双亲，直至（根）结点双亲为  为止。0"11+1&1==求以双亲表示法为存储结构的树的深度，+1& 的定义参看教材>0"1$91:6<D&0:60G:1"60II>1$:6<:06E0*<#>1$II6<:1"D(<&"16A==深度加 并取新的双亲 0<1$#$91$91:1$6==最大深度更新A&1'&"$916==返回树的深度A==结束 1C解题方案：评分标准：参考答案：1;</&1,;6==定义 1,; 类型　1;<(1&'/1"D>　　　　1,;16　　　　(1&'/1"D*/0*&/0*6==左右孩子子树　　A0",MD6==结点类型1;<0",MD0",&6==二叉树类型 0"1.<0",&,　　>==算叶子数　　　0<,　　　　0<,7#*/0*::MN..HH,7#&/0*::MN..　　　　　&1'&"6　　　　*(&1'&".<,7#*/0*IMD,7#&/0*6　　　*(&1'&"6　　A解题方案：评分标准： 参考答案：KS".0(180@==假定表空间大小为 1;<0"11,;6==假定 1,; 的类型为 0"1 型1;<(1&'/1>CCC1,;1.0(180@6==向量 1 用于存放表结点CCC0"1*"?16==当前的表长度CA8B*0(16C==以上为定义表结构FD04"(&1.0(18B*0(1.11;90"10>==将新结点 9 插入 . 所指的顺序表的第 0 个结点 0 的位置上，即插入的合法位置为：G:0G:.7#*"?10"1J60<0GTT0#.7#*"?1CCC&&D&PD(010D"&&D&P6==非法位置，退出，该函数定义见教材 +0<.7#*"?1#:.0(180@CCC&&D&UDF&VDEP6<D&J:.7#*"?176J#:06J77CCC.7#1JI:.7#1J6.7#10:96.7#*"?1II6A解题方案：评分标准：参考答案：1;<(1&'/1>　　　%;,;);；　　　4"<D,;D1&0"<D； ==此类型依赖于应用 　　AMD,;；　1;<MD,;8B.0(1"I； ==" 号单元用作哨兵　0"18B8&/8B*0(15，%;,;%　　　>==在关键字递增有序的顺序表 5"7中顺序查找关键字为 % 的结点，　　　　==成功时返回找到的结点位置，失败时返回7　　　　0"10；　　　　5");:%； ==设置哨兵　　　　<D&0:；50);G:%6077； ==从表前往后找　　　　0<0G"HH50);::%&1'&"06==50是要找的结点　　　　*(&1'&"7　　　A==8B8&/等概率情况下查找成功 8.:IIIWI"="　　等概率情况下查找失败时的 8.:IIIWI"I"I="I解题方案：评分标准： 一棵深度为  的满二叉树有个分支结点和个叶子。已知二叉树前序为  !，中序为  !，则后序一定是 。在哈希文件中，处理冲突的方法通常有、、和四种。二、算法设计题（本大题共 20 分，共 2 小题，每小题 10 分）设有一个线性表采用顺序存储结构，表中的数据元素值为正整数（" 个）。设在 "时间内，将线性表分成两为两部分，其中左半部分每个元素都小于原表的第一个元素，而右半部分则相反。约瑟夫问题：设编号为 ，，…，" 的 "（"#）个人按顺时针方向围坐一圈，每人持有一正整数密码。开始时任选一个正整数作为报数上限值 $，从第一个人开始顺时针方向自  起顺序报数，报到 $ 时停止报数，报 $ 的人出列，将他的密码作为新的 $ 值，从他在顺时针方向上的下一个人起重新从  报数。如此下去，直到所有人全部出列为止。令 " 最大值取 。要求设计一个程序模拟此过程，求出出列编号序列（采用循环单链表结构）。三、简答题（本大题共 20 分，共 4 小题，每小题 5 分）已知一个无向图如下图所示，要求用 %&'()* 算法生成最小树（假设以①为起点，试画出构造过程）。+! !!  一棵度为  的树与一棵二叉树有何区别？ 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 设二叉树 , 的存储结构如下-./0*          1 2 3 !       45/0*          其中 , 为树根结点的指针，其值为 ./0*5/0* 分别为结点的左、右孩子指针域1 为结点的数据域。试完成下列各题-（*）（ 分）画出二叉树 , 的逻辑结构6（）（ 分）写出按前序、中序、后序遍历该二叉树所得到的结点序列6（）（ 分）画出二叉树的后序线索树。四、程序设计题（本大题共 40 分，共 4 小题，每小题 10 分）假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。（注-已知树中结点数）以二叉链表为存储结构，写出求二叉树叶子总数的算法 设线性表的 " 个结点定义为"7，重写顺序表上实现的插入算法：4"(&1.0(1 设顺序表中关键字是递增有序的，试写一顺序查找算法，将哨兵设在表的高下标端。然后求出等概率情况下查找成功与失败时的 8.。答案：一、填空题（20 分，共 10 题，每小题 2 分）参考答案：比较；移动解题方案：评分标准：参考答案：解题方案：评分标准：参考答案：双亲链表表示法，孩子链表表示法，孩子兄弟表示法解题方案：评分标准： 参考答案：解题方案：评分标准：参考答案：免去查找过程中每一步都要检测整个表是否查找完毕，提高了查找效率。解题方案：评分标准：参考答案：活动（）活动间的优先关系（）事件（）活动边上的权代表活动持续时间解题方案：评分标准：参考答案：7#"91::解题方案：评分标准：参考答案： n1+n2=0+ n2= n0-1=31，26-1 =32解题方案：评分标准：参考答案：! 解题方案：评分标准：参考答案：开放地址法、再哈希法、链地址法、建立一个公共溢出区解题方案：评分标准：二、算法设计题（20 分，共 2 题，每小题 10 分）参考答案：算法思想是：以第一个元素为轴，开始时设置  个指针（一个在最左端【不包括第一个元素】，一个在最右端）若两个指针没有重合，从右向左扫描每个元素，若遇到比轴小的元素则记录位置并停止向左扫描，开始从左向右扫描每个元素，若遇到比轴大的元素，则记录位置并停止扫描，将两个位置的记录交换，然后再从右向左扫描，重复上述过程，直到两个指针重合。1;<(1&'/1==> *$,;*$6==存储空间首地址0"1*"?16==线性表的当前长度 0"1*0(1(0@6==当前分配的存储单元数A8B.0(16C0"1+&1010D"8B.0(1.CCC>0"1*DE:，0"10?:.7#*"?17CCCCC*$,;0FD1:.7#*$； ==用区间的第  个记录作为基准 CCCCCE0**DEG0?>==从区间两端交替向中间扫描，直至 *DE:0? 为止CCCCCCCE0**DEG0?HH.7#*$0?#:0FD1==0FD1 相当于在位置*DE 上CCCCCCCCC0?77； ==从右向左扫描，查找第  个关键字小于 0FD1 的记录 .*$0?CCCCCCCC0<*DEG0?==表示找到的 .*$0?的关键字G0FD1CCCCCCCCCCC.7#*$*DEII:.7#*$0?； ==相当于交换 .*$*DE和 .*$0?，交换后 *DE 指针加 CCCCCCCE0**DEG0?HH.7#*$*DEG:0FD1==0FD1 相当于在位置0? 上CCCCCCCCCCC*DEII； ==从左向右扫描，查找第  个关键字大于 0FD1 的记录.*$0CCCCCCC0<*DEG0?J==表示找到了 .*$*DE，使 .*$*DE);#0FD1CCCCCCCCCCC.7#*$0?77:.7#*$*DE6==相当于交换 .*$*DE和.*$0?，交换后 0? 指针减 CCCCCCCA=="E0*CCCCC.7#*$*DE:0FD1； ==基准记录已被最后定位CCCCC&1'&"*DE；CCCA==&1010D"解题方案：评分标准： 参考答案：K0"/*'G(10D#K0"/*'G$**D/#K0"/*'G(1*0L#(1&'/1*0")"D>CCCC0"116CCCC(1&'/1*0")"D"916A61;<(1&'/1*0")"D"D1;6"D1;/&10"1"==建立一个单向循环链表且不带头节点节点长度为 ">CC0"10:6CC"D1;:MN..(:MN..16CC:"D1;$**D/(0@D<"D1;6CC0<O901P分配失败P6CC&0"1<P输入第  个节点的 1 域-P6CC(/"<PQPH7#16CC1:6<D&0:60G:"60IICC>CCCCCC(:"D1;$**D/(0@D<"D1;6CCCCCC0<O(901P分配失败P6CCCCCC&0"1<P输入第Q 个节点的 1 域-P06CCCCCC(/"<PQPH(7#16CCCCCC(7#"91:MN..6CCCCCC17#"91:(6CCCCCC1:(6==1 始终指向最后一个节点CCCCCCCCACC17#"91:6==1 指向最后一个节点 CC&1'&"16AFD00(*;"D1;10"1"0"1(0"1$>CCCC"D1;:1B:MN..6CCCC0"10J)6CCCC<D&0:60G(60II:7#"916CCCC==使  指向开始出列节点的前驱CCCC<D&J:6JG:"6JIICCCC>CCCCCCCC<D&):6)G:$76)II:7#"916==使  指向要出列的节点的前驱CCCCCCCCB:7#"916CCCCCCCC&0"1<P第Q 个报数的节点元素是：QR"PJB7#16CCCCCCCC7#"91:B7#"916==使 B 节点出列CCCCCCCC<&B6CCCCAAFD0$0">CCCC"D1;/&10"16CCCCFD00(*;"D1;0"10"10"16CCCC"D1;&&6CCCC&&:/&16CCCC0(*;&&6CCCC(;(1$P'(P6A解题方案：评分标准：三、简答题（20 分，共 4 题，每小题 5 分）参考答案：