上海海事大学数据结构1995考研试题研究生入学考试试题考研真题
● 摘要
上海海运学院1995年硕士研究生入学考试试题
考试科目：数据结构
一 判断下列叙述的正确性，将判断的结果填在括号中，正确的填√，不正确的填×。 （本题满分11分，每小题1分）
1 为了很方便的插入和删除数据，可以使用双向链表存放数据。……… （ ） 2 若输入序列为1，2，3，4，5，6，则通过一个栈可以输出序列3，2，5，6，
4，1。……………………………………………………………………… （ ）
3 散列存储的基本思想是由关键码的值决定数据的存储地址…………… （ ） 4 一个数形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现（ ） 5 二叉树中每个结点至多有两个子结点，而对一般树则无此限制，因此二叉树
是树的特殊情况。………………………………………………………… （ ）
6 二叉树的前序遍历并不能唯一确定这棵树，但是，如果我们还知道这棵树的
根结点是那一个，则可以确定这棵二叉树。………………………… （ ）
7 线索二叉树的优点是便于是在中序下查找前驱结点和后继结点。…… （ ） 8 用一维数组存储二叉树时，总是以前序遍历顺序存储接点。………… （ ） 9 邻接矩阵适用于有向图和无向图的存储，但不能存储带权的有向图和无向图， 而只能使用邻接表存储形式来存储它。………………………………… （ ） 10 交换排序法是对序列中的元素进行一系列比较，当被比较的两个元素逆向时 进行交换。冒泡排序和快速排序是基于这类方法的两种排序方法，冒泡排序算
2法的最坏时间复杂性是0(n),而快速排序算法的最坏时间复杂性是0(nlog2n)，
所以快速排序比冒泡排序效率更高。……………………………………… （ ）
11 对大小均为n 的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。……………………………………………………………………… （ ）
二 从供选择的答案中选出应填如下列叙述中的_____内的正确答案，把遍号写在对应栏
内。（本题满分25分，每小题5分） 1 线性表的表元存储方式有___A___和链接两种。试指出下列个表中使用的是何种存储
表二是___C____存储方式；表三是___D___存储方式； 方式：表一是___B___存储方式； 表四是____E____存储方式。表左的元素指向起始表元。
表一 表元编号
s→ 1
2
3
4
5
6
表元编号
1
2
s→ 3 货号 618 205 103 501 781 910 货号 618 205 103 数量 40 2 15 20 17 24 数量 40 2 15 表元间联系 2 3 4 5 6 0 5 1 4 表二