当前位置：问答库＞考研试题

上海海运学院1997年硕士研究生入学考试试题

考试科目：数据结构

一. 判断下列叙述的正确性, 将判断结果写在答题纸上.(本题满分15分, 每小题1,5分)

1. 顺序存储方式只能用于存储线性结构.

2. 为了方便地插入和删除数据, 可以使用双向链表存放数据.

3. 若输入序列为1,2,3,4,5,6, 则通过一个栈可以输出序列3,2,5,6,4,1.

4. 散列表的结点中只包含数据元数自身的数据, 不包含任何指针.

5.二叉数树中每个结点至多有两个子结点, 而对一般二叉树则无此限制. 因此, 二叉树是树的特殊情形.

6. 用指针的方式存储一棵有n 各结点的二叉树, 最少要用n+1个结点.

7. 线索二叉树的优点是便于左中序下查找前序结点和后序结点.

8.邻接矩阵适用于有向图和无向图的存储, 但不能存储带权的有向图和五向图, 而只能使用邻接表存储形式来存储它.

9.冒泡排序和快速排序都是基于交换两个逆序元素的排序方法, 冒泡排序算法的最坏时间复杂性是o(n的平方), 而快速排序算法的最坏时间复杂性是o(n以二为底的n 的对数), 所以快速排序比冒泡排序算法效率更高.

10.任一查找树(二叉分类树) 的平均查找时间都小于用于顺序查找法查找同样结点的选线性表的平均查找时间.

二. 从供选择的答案中选出正确答案写在答案纸上(本题满分23分, 第1,2,3,5小题5分, 第4小题 3分)

1.在作进栈运算时, 应先判断栈是否( ),在退栈运算时应先判断栈是否( ).当栈中元素为n 个, 作进栈运算时发生上溢, 则说明该栈的最大容量为( ).为了增加存储空间的利用率和减少溢出的可能性, 有两个栈共享一片连续的存储空间时, 应增加两栈的( )分别设在这片内存空间的两端, 这样, 当( )时才产生上溢.

供选择的答案

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,B,C:1.二叉树中每个结点的两棵子树的高度差不大于1.

2. 二叉树中每个结点的两棵子树的高度差等于 1

3. 二叉树中每个结点的两棵子树是有序的.

4. 二叉树中每个结点有两棵非空子树, 或有两棵非空子树.

5. 二叉树中每个结点的关键字值大于其非空左子树(如果存在的话) 所有结点的关