一九九六年上海海运学院攻读硕士学位研究生入学考试试题

1、一九九六年上海海运学院攻读硕士学位研究生入学考试试题数据结构一判断下列叙述的正确性，将判断的结果填在括号中，正确的填，不正确的填X。（本题满分 10 分，每小题 1 分）。1 顺序存贮方式的优点是存储密度大，且插入删除效率高。（）2 栈和队列的存储方式，既可以是顺序方式，有可是链式方式。（）3 数组是同类型的集合。（）4 负载因子是散存储的一个重要参数，它反映散列表的装满程度。（）5 用链表 （llink-rlink） 存储包含几个结点的二叉树，结点的 2n 个指针区域中有 n-1个空指针。（）6 一棵一般树的结点的前序遍历和后序遍历分别于它相应二叉树的结点前序遍历和后序遍历是一致的。（）7

2、线索二叉树的优点是便于在中序下查找前驱结点和后继结点。（）8 用邻接矩阵存储一个图时，再不考虑压缩存储的情况下，所占用的存储空间大小与图中结点个数有关，而与图的边数无关。（）9 快速排序和归并排序在最坏情况下的比较次数都是O（nlog 2n）.（ ）10 任意查找树 （二叉分类树 ） 的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。（ ）二 从供选择的答案中选出应填入下列叙述中 内的正确答案。（本题满分 25 分，每小题 5 分）1 有一个二维数组 A0.8,1.5,每个数组元素用相邻的四个字节存储，存储器按字节编址，假设存储数组元素 A0,1的第一个字节的地址是 0,存储

3、数组A的最后一个元素 的第一个字节的地址是 。若按行存储，则 A3,5 和 A5,3 的第一个字节的地址是 和。若按列存储，则 A7,1 和 A2,4 的第一个字节的地址是 和 。 供选择的答案：A- E: 28 44 76 92 108 116 132 176 184 1882 只能在一端删除结点， 另端插入结点的线索表是 ；只能在端点对结点进行删除，插入操作的线性表是 , 所有插入和删除均在一端进行， 而另端不允许插入或删除的线性表是 , 其中的结点已按中序次序分类好的树是 , 其中每个结点的左右子树的高度差都不大于 1 树是; 所有后件数小于 2的结点均在最下面二层的树是 。供选择的答案

4、：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、 （5）3D: (1)27 (2)30 (3)45 (4)51 (5)614如下图所示的网络表示的工程中，这个工程由 个作业构成，各个作业所需天数由箭头先上的树子给出。另外，各作业都可能缩短一天，而且所需要的费用由()中的数字给出。这项工程需要 天可以全部完成，关键路径是 。同时，为了将工程所用的天数缩短一天，可以将作业 缩短一天，这样可以用最低费用缩短工期，这是以关键路径为,将它已经可能少的费用在缩短一天时，则可以将作业 缩短。供选择的答案：A,B: (1) 8 (2) 9 (3) 10 (4) 11 (5) 13 (6) 14 (7) 15 (8) 16(9) 20 (10) 23C,E:

6、 (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-8D,F: (1) (2,4)(2) (2,5)(3,5)(3,7)(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时，此方法的查找次数接近于 。供选择的答案