吉林大学数据结构2000考研试题研究生入学考试试题考研真题
● 摘要
吉林大学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]用来存放每个单链表的头指
针 ，单链表中结点结构为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）设待排序文件（R 1，R 2，…,Rn ）以数组方式表示，每个记录对应的关键词域为
，试写出对该线性表的直接插入排序法INSERT(R,n),要求算法是稳定的，（K 1，K 2，…，K n ）
并说明算法的时间复杂性； (2)待排序文件以单链表方式表示，指针变量FIRST 指向表头结点，表中结点结构为 ， 其中KEY 为结点的关键词域，LINK 为链接域，试写出对该线性表的 直接插入排序算法INSERT2（FIRST ），要求算法是稳定的，并说明算法的时间复杂性。