吉大数据结构11994.docVIP

15．什么是EULER函数？并求成过急（11）=？ 二．设R，S，T是集合A上的三个关系，证明或反驳下列等式：[每题5分，共10分] （1）R．（S T）=（R。S） （R。T） （2）R．（S T）=（R。S） （R。T） 三 1．[15分]用演绎法证明{P Q，P R， }共同蕴涵P Q 2．[5分]点数为8的非HAMILTON图最多有多少条边？并证明你的结论。 第二部分：数据结构 四．按要求回答下列问题：[16分] 1[6分] 什么是堆？ 已知待排序文件为（27，4，78，2，60，10，58，16，49，18）。试把该文件建成一个堆，写出结果。 2[10分]已知如下的关键词表： （JAN，FEB，MAR，APR，MAY，JUN，JUL，AUG，SEP，OCT，NOV，DEC） （1） 按表（1）中元素的先后顺序依次插入一棵初始为空的二叉查找树（即二叉排序树），插入时关键词按英文词典的编排次序。试画出上述插入过程完成后的二叉查找树，并求其在等概率情况下查找成功的平均查找长度（即平均比较次数）； 按表（1）中元素的先后顺序构造一棵高度平衡数（即二叉平衡树），试画出该高度平衡树，标出树中每个平衡节点的平衡系数（即平衡因子），并求其在等概率情况下查找成功的平均查找长度。 五．（10分）设文件（R1，R2，。。。Rn）以单链表方式表式，指针变量FIRST指向表头结点，表中的结点结构为 其中KEY为该结点的关键词域，LINK为链接域，试给出该种线性表的直接选择排序算法，要求算法的间复杂性为O（n2）,且算法是稳定的。 六．[12分] 图1中的两棵树可用嵌套括弧表示法分别表达如下： A（B，C（K）） D（E（H），F（J），G） 其中的字母代表节点，紧接一字母后的左括号和与之配对的右括号所包含的字母都是该字母的子树的节点。逗号把不同的子树分开。 试写一算法，把任一棵树用嵌套括弧表示法表达出来，规定节点的格式为： 其中，INFO表示一节点的信息字段（域）LINKi(I=1,2…..,J)表示指向该节点的第I个节点的指针；NUM表示该节点的子节点数目。 七．[12分]设PERT网（即AOE网或加权的有向无环图）以邻接表方式存储，表头数组为HEAD[1：n]链表中的节点结构为： 其中WEIGHT是该节点相应边上的权值，VERTEX是该节点的内容，LINK是链接字段。试给出一个算法，该算法为每个顶点V赋予一个最早时间et[v]和一个最迟时间lt[v]，并给出算法的时间复杂性。