上海海事大学数据结构1996考研试题研究生入学考试试题考研真题
● 摘要
一九九六年上海海运学院攻读硕士学位研究生入学考试试题
数据结构
一 判断下列叙述的正确性，将判断的结果填在括号中，正确的填√，不正确的填×。（本题满分10分，每小题1分）。
1 顺序存贮方式的优点是存储密度大，且插入删除效率高。 （ ） 2 栈和队列的存储方式，既可以是顺序方式，有可是链式方式。 （ ） 3 数组是同类型的集合。 （ ） 4 负载因子是散存储的一个重要参数，它反映散列表的装满程度。 （ ）
5 用链表(llink-rlink) 存储包含几个结点的二叉树，结点的2n 个指针区域中有n-1
个空指针。 （ ）
6 一棵一般树的结点的前序遍历和后序遍历分别于它相应二叉树的结点前序遍历和后序
遍历是一致的。 （ ） 7 线索二叉树的优点是便于在中序下查找前驱结点和后继结点。 （ ）
8 用邻接矩阵存储一个图时，再不考虑压缩存储的情况下，所占用的存储空间大小与图
中结点个数有关，而与图的边数无关。 （ ） 9 快速排序和归并排序在最坏情况下的比较次数都是O(nlog2n). （ ）
10 任意查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性
表的平均查找时间。 （ ）
二 从供选择的答案中选出应填入下列叙述中____内的正确答案。
（本题满分25分，每小题5分）
1 有一个二维数组A[0..8,1..5],每个数组元素用相邻的四个字节存储，存储器按字节
编址，假设存储数组元素A[0,1]的第一个字节的地址是0，存储数组A 的最后一个元素的第一个字节的地址是____。若按行存储，则A[3,5]和 A[5,3]的第一个字节的地址是 ____ 和_____。若按列存储，则A[7,1]和A[2,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