数据结构-1996.doc

一九九六年上海海运学院攻读硕士学位研究生入学考试试题考试科目：数据结构一 判断下列叙述的正确性，将判断的结果填在括号中，正确的填，不正确的填。（本题满分10分，每小题1分）。 1 顺序存贮方式的优点是存储密度大，且插入删除效率高。 （ ） 2 栈和队列的存储方式，既可以是顺序方式，有可是链式方式。 （ ） 3 数组是同类型的集合。 （ ） 4 负载因子是散存储的一个重要参数，它反映散列表的装满程度。 （ ） 5 用链表(llink-rlink)存储包含几个结点的二叉树，结点的2n个指针区域中有n-1个空指针。 （ ） 6 一棵一般树的结点的前序遍历和后序遍历分别于它相应二叉树的结点前序遍历和后序遍历是一致的。 （ ） 7 线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 （ ） 8 用邻接矩阵存储一个图时，再不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。 （ ） 9 快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n). （ ） 10 任意查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。 （ ）二 从供选择的答案中选出应填入下列叙述中_内的正确答案。 （本题满分25分，每小题5分） 1 有一个二维数组A0.8,1.5,每个数组元素用相邻的四个字节存储，存储器按字节编址，假设存储数组元素A0,1的第一个字节的地址是0，存储数组A的最后一个元素的第一个字节的地址是_。若按行存储，则A3,5和 A5,3的第一个字节的地址是 _ 和_。若按列存储，则A7,1和A2,4的第一个字节的地址是_和_。 供选择的答案：A- E: 28 44 76 92 108 116 132 176 184 188 2 只能在一端删除结点，另端插入结点的线索表是_ ；只能在端点对结点进行删除，插入操作的线性表是_,所有插入和删除均在一端进行，而另端不允许插入或删除的线性表是_,其中的结点已按中序次序分类好的树是_,其中每个结点的左右子树的高度差都不大于1树是_; 所有后件数小于2的结点均在最下面二层的树是_。供选择的答案：A- F: (1) 队列 (2) 数组 （3）十字链表 （4）双向队列 （5） 循环链表（6）栈 （7） 双向链表 （8） 有序树 （9） 丰满二叉树 （10）完全二叉树 （11）平衡树 （12） 分类二叉树 3 设T是正则二叉树（完全二叉树），它具有6片树叶，那么树T的高度最多可以是_， 最小可以是_;树的内结点数是_.如果T是哈夫曼树（Hoffman）最优树，且各片树叶的权（频率）分别是1，2，3，4，5，6，则最优树T的非叶结点的权之和是 _;权为1的树叶的高度是_. 注：树的根结点高度为1。 供选择的答案： A,B,C,E:(1)7 (2)5 (3)6 (4)4 (5)3 D: (1)27 (2)30 (3)45 (4)51 (5)61 4 如下图所示的网络表示的工程中，这个工程由_个作业构成，各个作业所需天数由箭头先上的树子给出。另外，各作业都可能缩短一天，而且所需要的费用由（ ）中的数字给出。 这项工程需要_天可以全部完成，关键路径是_。 同时，为了将工程所用的天数缩短一天，可以将作业_缩短一天，这样可以用最低费用缩短工期，这是以关键路径为 _ ,将它已经可能少的费用在缩短一天时，则可以将作业_缩短。 供选择的答案： A,B: (1) 8 (2) 9 (3) 10 (4) 11 (5) 13 (6) 14 (7) 15 (8) 16 (9) 20 (10) 23 C,E: (1) 1-2-4-5-6-7-8 (2) 1-2-4-6-7-8 (3) 1-2-5-6-7-8 (4) 1-3-5-6-7-8 (5)1-2-7-8 (6) 1-2-4-6-7-8和1-2-5-6-7-8 (7) 1-2-4-6-7-8和1-2-4-5-6-7-8 (8) 1-2-4-5-6-7-8和1-2-5-6-7-8 (9) 1-3-5-6-7-8和1-3-7-8 D,F: (1) (2,4) (2) (2,5) (3) (3,5) (4) (3,7) (5) (4,6) (6) (5,6) (7) (7,8) (8) (2,4)和(2,5) (9) (2,4)和(4,6) (10) (2,4)和(5,6)5 某顺序存储的表格，其中有90000个元素，以按关键项的值的上升顺序排列。现假定对各个元素进行查找的概率是相同的，并且各个元素的关键项的值皆不相同。用顺序查找法时，平均比较次数是_,最大比较次数是_。现把90000个元素按排列顺序划分成若干组，使每组有g个元素(最后一组可能不是g个)。查找时，先从头一组开始，通过比较各组的最后一个元素的关键项的值，找到欲查找的元素所在的组，然后再用顺序查找法找到欲查找的元素。在这种查找法中，使总的平均比较次数最小的g是_，此时的平均比较数是_。当g的值大于等于90000时，此方法的查找次数接近于_。供选择的答案： A,B:(1) 2500 (2) 30000 (3)4500 (4)9000 C,D:(1) 100 (2)200 (3) 300 (4) 400 E:(1) 快速分类法 (2) 斐波那契查找法 (3) 二分法 (4) 顺序查找法三 试用过程或函数使现有序表的两种操作：INSERT DELETE 有序表的表示法是基于如下结构 (1)数组 (2)指针(链表) (本题满分16分)四 假设一个二叉树的两种遍历如下：前序：ABFGCHDEIJLK 中序：FGBHCDILJKEA(1) 画出这棵二叉树及它的中序线索树；(2) 写出在中序线索树的情况下，找到结点N的前驱结点的算法INORDER-PRIOR(N,X)(本题满分10分，第一小题4分，第二小题6分)五 已知长度为12 的表(Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oct,Nov,Dec)(1) 试按表中元素的顺序依次插入一棵初始为空的分类二叉树，是画出插入完成之后的分类二叉树，并计算其在等概率查找情况下，查找成功的平均查找长度。(2) 试用以下两种方法构造两个Hash表，Hash函数H(K)=i/2,其中i为关键字K中第一个字母在字母表中的序号， 表示取整数。1 用线性探测开放定址法处理冲突(散列地址空间为0-16)2 用链地址法处理然后分别求出这两个Hash表在等概率查找情况下，查找成功的平均查找长度。(本题满分15分，第一小题5分，第二小题10分)六 下面是冒泡排序算法，请阅读并完成该程序，并回答以下问题：PROCEDURE bubblesort (r,n) BEGIN i:=1; m:=n-1; flag:=1; while (irj+1.key then begin flag:=_; t:=rj; rj:=rj+1; rj+1:=t end; i:=i+1;m:=m-1 end; end.1 请在上面横线上填上适当的语句，完成该算法程序。2 设计标志flag的作用是什么？3 该算法结点的最大比较次数和最大移动次数是多少？4 该分类算法稳定吗？（本题满分12分，每小题3分）七 （本题满分12分）阅读下列程序说明和PASCAL程序，把应填入其中处字句写在答案的对应栏内。程序说明：本程序根据输入的等价对，形成并输出相应的等价类。等价对（a,b）表示等价元a与b等价，若存在等价对（a,b）和(b,c)(或c,b)则表示a,b,c属于同一个等价类。算法分为两个部分：（1） 由输入的等级对建立若干个链表，数组元素Seg(i)用来指向与I有直接等价关系的等价元链表。当输入的等价对中第一个元素小于或等于0时，表示输入结束。例如，输入的等价对是1，5；4，2；7，11；9，10；8，5；7，9；4，6；8，12；12，1时，建立的数组Seg是（2） 扫描数组元素segi，i=1,2,输出相应的等价类程序： program equo (input,output);const nmax=50;type pointer=node; node=record data:1nmax; link:pointer end;var seg:array1nmax of pointer; out:array1nmax of Boolean; I,j,n:integer; X,y,top:pointer; Done:Boolean;Begin Writerln(input the number n=); Read(n); For I:=1 to n do Begin(1) outI:=true end; writeln(input the equivnlent pairs); readln(I,j); while I0 do begin new(x); x.data:=j; x.link:=segI; segI:=x; new(x); x.data:=I;x.link:=segj; segj:=x;readln(I,j); end; for I:=1 to n do if (2) then writeln(A nem class,I); outI:=false;(2) top:=nil;done:=false;repeat while