|
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 分]
（1）什么是堆？
（2）已知待排序文件为（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）中元素的先后顺序依次插入一棵初始为空的二叉查找树（即二叉排序树），插
入时关键词按英文词典的编排次序。试画出上述插入过程完成后的二叉查找树，并求其
在等概率情况下查找成功的平均查找长度（即平均比较次数）；
按表（1）中元素的先后顺序构造一棵高度平衡数（即二叉平衡树），试画出该高度平衡树，
标出树中每个平衡节点的平衡系数（即平衡因子），并求其在等概率情况下查找成功的平均
查找长度。
五．（10 分）设文件（R1，R2，。。。Rn）以单链表方式表式，指针变量 FIRST 指向表头结点，
表中的结点结构为
其中 KEY 为该结点的关键词域，LINK 为链接域，试给出该种线性表的直接选择排序算法，
要求算法的间复杂性为 O（n2）,且算法是稳定的。
六．[12 分]
图 1 中的两棵树可用嵌套括弧表示法分别表达如下：
A（B，C（K）） D（E（H），F（J），G）
其中的字母代表节点，紧接一字母后的左括号和与之配对的右括号所包含的字母都是该字母
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
