电大法学专科-刑法学1-考试包过

《电大法学专科-刑法学1-考试包过》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、三、综合题1．（1）对给定权值3，1，4，4，5，6，构造深度为5的哈夫曼树。(设根为第1层)。(2)求树的带权路径长度。65435423418145197896434531213（3）链接存储上述哈夫曼树，结点中共有多少个个指针域为空,说明理由.答：（2)WPL=3*4+1*4+4*3+6*2+4*2+5*2=58(3)共11个结点,22个指针域,除根结点外,每个结点对应一个指针域.,共10个指针域非空,故有22-10=12个空指针域,2．(1)以2，3，4，7，8，9作为叶结点的权，构造一棵哈夫曼树(要求每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权

2、重值叶结点的哈夫曼编码。(2)一棵哈夫曼树有n个叶结点，它一共有多少个结点？简述理由？答：(1)2：11103:11114：1107：008：019：10（2）2n-1个，因为非叶结点数比叶结点数少一个。3.(1)如下的一棵树,给出先序遍历序列(2)把1,2,3,4,5,6,7,8,9填人,使它成为一棵二叉排序树提示：设图中的树是二叉排序树，找出中序遍历序列与1，2，…9的对应关系(3)请在该树中再插入一个结点3.5作为叶结点，并使它仍然是一棵二叉排序树答：1A1A2A4A7A8A5A9A3A6（2）如图17421563893.5A1A2A43A7A5A9A8A3A6图1

3、图24．一组记录的关键字序列为（46，79，56，38，40，84）（1）利用快速排序的方法，给出以第一个记录为基准得到的一次划分结果（给出逐次交换元素的过程，要求以升序排列）（2）对上述序列用堆排序的方法建立大根堆，要求以二叉树逐次描述建堆过程。(1)初始序列46，79，56，38，40，8440，79，56，38，40，8440，79，56，38，79，8440，38，56，38，79，8440，38，56，56，79，8440，38，46，56，79，845．设查找表为(5,6,7,8,9,10,11,12,13,14)（1）画出对上述有序表进行折半查找所对应的判定

4、树(要求以数据元素作为树结点)(2)给出二叉排序树的定义,针对上述折半查找所对应的判定树的构造过程,说明判定树是否是二叉排序树(设树中没有相同结点)？(3)为了查找元素5.5，经过多少次元素间的比较才能确定不能查到？971014118512136971014118512136答：(1)如图(2)二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子树的所有结点的值都大于（若允许结点有相同的值，则大于等于）它的根结点的值;左,右子树也是一棵二叉排序树，按定义判定树是二叉排序树。(3).

5、3次6．设查找表为(50,60,75,85,96,98,105,110,120,130)(1)说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？(2)为了折半查找元素95，经过多少次元素间的比较才能确定不能查到？（3）画出对上述有序表进行折半查找所对应的判定树(要求以数据元素作为树结点)96759813010585501100512060答：(1)3次(2)4次abcd1.(1)说明什么是顶点活动网(AOV网)和拓扑序列（2）设有向图G如下，写出3种拓扑序列，（3）在图G中增加一条边，使图G仅有一条拓扑序列答：（1）顶点活动网(AOV网)：顶点表示活动，边表

6、示活动间先后关系的有向图叫做顶点活动网(AOV网)。拓扑序列：在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，此序列叫做拓扑序列。（2）3种拓扑序列：a,b,d,ca,d,b,cd,a,b,c（3）仅有一条拓扑序列为：a,b,d,c2．设查找表为(16,15,20,53,64,7),(1)用冒泡法对该表进行排序（要求升序排列），写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？(2)在排序后的有序表的基础上，画出对其进行折半查找所对应的判定树.(要求以数据元素作为树结

7、点)71520641653(1)原序列（2）1615205364715162053764n-1趟15162075364n-j次151672053641571620536471516205364A1A2A4A7A5A9A8A3A6(3)平均查找长度=（1*1+2*2+3*3）/6=14/63．如下是一棵二叉排序树，A1,A2,…A9代表1，2，3,…9中各个不同数字，（1）给出对该树中序遍历的结果（2）A3,A5,A7的值各为多少？（3）请在该树中再插入一个结点9.5作为叶结点，并使它仍然是一棵二叉排序树答(1)中序A7,A4,