资源简介：吉林大学数据结构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]用来存放每个单链表的头指
针 ，单链表中结点结构为 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），要求算法是稳定的，并说明算法的时间复杂性。

 

说明：本站提供的《吉林大学数据结构2000年考研真题考研试题 》源自权威渠道，为历年考过（被使用过）的真题试卷，除标注有“回忆版”字样的试题外，其余均为原版扫描，权威可靠；回忆版试题由当年参加全国硕士、博士研究生入学考试考生回忆，内容完整。