|
友情提示：本站提供全国400多所高等院校招收硕士、博士研究生入学考试历年考研真题、考博真题、答案，部分学校更新至2012年，2013年；均提供收费下载。 下载流程： 考研真题 点击“考研试卷””下载; 考博真题 点击“考博试卷库” 下载
吉林大学 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），要求算法是稳定的，并说明算法的时间复杂性。
免责声明：本文系转载自网络，如有侵犯，请联系我们立即删除，另：本文仅代表作者个人观点，与本网站无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
|
文章搜索
您现在的位置： 
