吉大数据结构12000.docVIP

吉林大学2000年硕士研究生试题 回答下列问题（22分） 已知一棵二叉数的中序（或中根）遍历节点排序为DGBAECHIF，后序（或中根）遍历节点排序为GDBEIHFCA， 试画出该二叉树。 试画出该二叉树的中序穿线（或线索）树。 试画出该二叉树（自然）对应的森林。（5分） 给定一组权值2，3，5，7，11，13，17，19，23，29，31，37，41，试画出用Huffman算法建造的Huffman树。（4分） 试写出用克鲁斯卡尔（Kruskal）算法构造下图的一棵最小支撑（或生成）树的过程。（3分） （1）什么是堆？ （2）试写出把序列{503 87 512 61 908 170 897 275 653 462} 建成（或调整为）一个堆的过程。（4分） 给定关键词输入序列{CAP AQU PIS ARI TAU GEM CAN LIB VIR LEO SCO}，假定关键词比较按英文字典序， 试画出从一棵空树开始，依上述顺序（从左到右）输入关键词，用高度平衡树的查找和插入算法生成一棵度平衡树的过程，并说明生成过程中采用了何种转动方式进行调整，标出树中各节点的平衡系数； 试画出在上述生成的高度平衡树中，用高度平衡树的删除算法先后删除节点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），要求算法是稳定的，并说明算法的时间复杂性。 3．设一棵二叉树的结点结构为 LLINK INFO RLINK ，ROOT为指向该二叉树 根结点的指针，p和q问别为指向该二叉树中任意两个结点的指针，试编写一算法ANCESTOR（ROOT，p，q，r），该算法找到p和q的最近的共同祖先结点r。（12分）