上海交通大学1996年研究生考试数据结构及程序设计技术试题
一（7分） 设加权树G=(V,E)是一连通图，回答： （1）何谓图G的最小生成树？ （2）设G为试找出所有的最小生成树。 二（8分） 已知一棵五次树，其结点数据场为一英文字母，现给出该五次树的前序周游结果（按前序打印数据场之值）及每个结点的次数如下： 前序：A,X,B,C,F,G,D,H,J,K,L,M,N,E,I 次数：5,0,0,2,0,0,1,1,3,0,0,1,0,1,0 试画出表示该五次树的示意图。 三（8分） 哈希（hashing）查找法有何特点？何谓冲突？试给出两种解决冲突的方法。 四（8分） 一个算法所需时间由下述递归方程表示，试求出该算法的时间复杂度的级别。 T(n)=1(ifn=1) 2T(n/2) nn>1 其中：n是问题的规模，为简单起见，设n是2的整数幂。 五（8分） 已知a,b,c,d,e,f,g,,h字符出现的百分比分别为45%,15%,10%,8%,5%,5%,4%;试给出它们的huffuman编码。 六（8分） 从额外空间使用，平均情况下的时间复杂性，最坏情况下的时间复杂性三个方面来分析堆分类法和快速分类法的各自特性。若分裂对象已排好序，采用堆分类法还是快速分类法进行排序快？为什么？ 七（8分） 在进行磁带文件分类时，通常用置换一选择分类法生成最初合并段。若内存缓冲区只能存放m个记录，则平均情况下的最初合并段长度为多少？并请进行简单的分析。有无可能只生成一个最初合并段，即该合并段的记录总数和被分类的磁带文件记录总数相等？为什么？ 八（15分） 编写一个非递归的过程，将r数组整理为一个合乎最大化要求的堆。其中，r的说明为 r:array[I…n]ofinteger 要求：1、额外空间的需求为O(1) 2、时间复杂度必须为O(n),并且还要加以简单的证明。 九（15分） 设分类二叉树中的结点的结构为： leftdataright
其中，left,right分别给出本结点的左右儿子结点的地址。Data类型为整数。 已知分类二叉树根结点地址为root，且它的所有结点的data域之值互不相等。设计一个程序，删除data域之值为T的结点，且保持删除后的二叉树仍为分类二叉树。 十（15分） 设中序穿线二叉树结点结构为： leftltagdatartagright
其中： ltag=0，则left中存放的是该结点的左儿子结点地址 1则left中存放的是该结点的按中序次序的前驱结点地址 rtag=0，则right中存放的是该结点的右儿子的结点地址 1则right中存放的是该结点的按中序次序的后继结点地址 现已知中序穿线二叉树的根结点地址root。设计一个程序，打印出该穿线二叉树的中序结构。注意，不得再使用0(n)级及其0(n)级以上的辅助空间，否则作零分处理。（这里N指穿线二叉树的结点规模。）
页:
[1]