上海海事大学数据结构1999考研试题研究生入学考试试题考研真题
● 摘要
上海海运学院1999年硕士研究生入学考试试题
考试科目：数据结构
一、〔本题10分，每小题1分〕判断下列叙述的正确性，将判断的结果写在答题纸上。 1 顺序存储方式的优点是存储密度大，且插入、删除效率高。
2 栈和队列的存储方式，即可是顺序方式，又可以是链式方式。
3 若输入序列为1，2，3，4，5，6，则通过栈可以输出序列1，5，4，6，2，3。 4 数组是同类型值的集合。
5 负载因子是散列存储的一个重要参数，它反映了散列表的装满程度。
6 用链表（llink-rlink ）存储包含n 个节点的二叉数时，节点的2n 个指针区域中有n+1个空指针。
7 用一维数组存储二叉数时，总是以它的前序遍列存储节点。
8 在查找数（二叉数排序数）中插入一个新节点，总是插入一个节点下面。
9 又邻接节点存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中节点个数有关，而有图的边数无关。
10 在外部排序时，理由悬这数方法在能容纳m 个记录的内存缓冲区中产生的初始段的平均长度为2m 个记录。
二、（本题20分，每小题5分 ）从供选择的答案中选出应填入下列叙述中的（）内的正确答案写在答题纸上
1 在作栈运算时，应先判别栈是否（A ），在作退栈操作时，应先判别是否（B ）。当栈中元素为n 个，作进栈运算时发生上溢，则说明该栈最大容量为（C ）。为了增加内存利用率和减少溢出的可能性，由两个栈共享一片连续的内存空间是，应将两栈的（D ）分别设在这片内存空间的两端，这样当（E ）时，才产生上溢。
供选择的答案：
A ， B ：（1）空 （2）满（3）上溢（4）下溢
C ：（1）n-1（2）n （3）n+1（4）n/2
D ：（1）长度（2）深度（3）栈顶（4）栈底
E ：（1）两个栈的栈底同时达到空间的中心点
（2）其中一个栈的栈底达到栈空间的中心点
（3）两个栈的栈顶在空间的某一位置相遇
（4）两个栈均不为空，且一个栈的栈顶达到另一个栈的栈底
2 数是节点的有限集合，他（A ）根节点，记为T 。其余节点分成m （m ）0）个（B ）的集合T1，T2， …Ｔm ，每个集合有都是树，此时节点Ti 称为T 的负节点，Tj 称为T 的子节点（1≤i ≤m ）。一个节点的之节点个数成为该节点的(C)。二叉树与树是两个不同的概念，二叉树又是节点的有限集合，他（D ）根节点。可以把树的根节点的成树定义为1，其他节点的层数等于其父节点层树加上1。令T 十一可二叉树，Ki 和Kj 是T 中子节点树小于2的节点中的任意两个，他们所占的层数分别为λKi 和λKj ，党关系是│λKi-λKj │≤一定成立时，则成T 为一棵（E ）。
供选择的答案：
A ， D ：1. 有0个或多个 2. 有1个或多个 3. 有其只有一个 4. 有1个或1一个以上
B:1.互不相交 2. 允许相交 3. 允许叶节点相交 4. 允许树枝节点相交