|
吉林大学 2000 年硕士研究生试题
一． 回答下列问题（22 分）
1． 已知一棵二叉数的中序（或中根）遍历节点排序为 DGBAECHIF，后序（或中根）
遍历节点排序为 GDBEIHFCA，
（1） 试画出该二叉树。
（2） 试画出该二叉树的中序穿线（或线索）树。
（3） 试画出该二叉树（自然）对应的森林。（5 分）
2． 给定一组权值 2，3，5，7，11，13，17，19，23，29，31，37，41，试画出用 Huffman
算法建造的 Huffman 树。（4 分）
3． 试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。
（3 分）
4． （1）什么是堆？
（2）试写出把序列{503 87 512 61 908 170 897 275 653 462} 建成
（或调整为）一个堆的过程。（4 分）
5． 给定关键词输入序列{CAP AQU PIS ARI TAU GEM CAN LIB VIR
LEO SCO}，假定关键词比较按英文字典序，
（1） 试画出从一棵空树开始，依上述顺序（从左到右）输入关键词，用高度平
衡树的查找和插入算法生成一棵度平衡树的过程，并说明生成过程中采用
了何种转动方式进行调整，标出树中各节点的平衡系数；
（2） 试画出在上述生成的高度平衡树中，用高度平衡树的删除算法先后删除节
点 CAN 和 AQU 后的树形，要求除后的树形仍为一棵高度
平衡树，并说明删除过程中采用了何种转动方式进行平衡调整，标出树中
各节点的平衡系数。（6 分）
二、按要求编写算法（28 分）（注意：不限制算法的写法，请尽量写出详尽的解释过程）
1．设一个连通无向图 G=(V , E)采用邻接表的方式存储，V={1,2,…,n},一维数组
HEAD[1..n]用来存放每个单链表的头指
针 ，单链表中结点结构为 VER LINK ，其中 LINK 是链接字段，VER 字段表示顶点
内容，一维数组 MARK[1..n]用于相应顶点加标号，MARK[i]=0 表示顶点 i 未被访问到，
MARK[i]=1 表示顶点 i 已经被访问过，试写出对上述图 G 进行广度（或宽度）优先遍历（或
访问）的非递归算法 BFS(HEAD , n , s , MARK , MARK),其中 s 为任一遍历起始顶点。（7 分）
2．（1）设待排序文件（R1，R2，…,Rn）以数组方式表示，每个记录对应的关键词域为
（K1，K2，…，Kn），试写出对该线性表的直接插入排序法 INSERT(R,n),要求算法是稳定的，
并说明算法的时间复杂性；
(2)待排序文件以单链表方式表示，指针变量 FIRST 指向表头结点，表中结点结构为
KEY LINK ， 其中 KEY 为结点的关键词域，LINK 为链接域，试写出对该线性表的
直接插入排序算法 INSERT2（FIRST），要求算法是稳定的，并说明算法的时间复杂性。
，更多更新年份持续更新，请在本站的考博信息网|www.kaoboinfo.com中的“考研试卷库”学校栏目中查询下载。
|
您现在的位置： 
