2000 年上海海事大学数据结构考研真题
一、(本题 15 分,每小题 1.5 分)判断下列叙述的正确性,将判断的结果写在答题纸上。
1 数据的逻辑结构说明数据元素之间的顺序关系、它依赖于计算机的存储结构。
2 顺序存储方式只能用于存储线性结构。
3 为了很方便地插入和删除数据,可以使用双向链表存放数据。
4 若输入序列为 1、2、3,4,5,6、则通过一个栈可以输出序列 3,2,5,6、4,1。
5 散列表的节点只包含数据元素自身的数据,不包含任何指针。
6 用链表(link-rlink)存储包含 n 个节点的二叉树时,节点的 2n 个指针区域中有 n+1 个
空指针。
7 每个节点的度数小于等于 2 的树是二叉树。
8 在查找树(二叉排序树)中插入一个新节点,总是插入到叶节点下面。
9 邻接矩阵适用于有向图和无向图的存储、但不能存储网络图(带权的有向图和无向
图)、而只能使用邻接表存储形式来存储它。
10 快速排序和归并排序在最坏情况下的比较次数都是 o(n log2 n)。
二、(本题 15 分、每小题 1.5 分)从供选择的答案中选出正确答案写在答题纸上
1 若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采
用____存储方式最节省运算时间。供选择的答案∶
A 单链表
B 仅有头指针的单循环链表
C 双向链表
D 仅有尾指针的单循环链表
2 对于有 n 个节点的二叉树,其高度为____。供选择的答案∶
3___,它的先序遍历和中序遍历具有同样的顺序。
供选择的答案∶
A 二叉树 B 完全二叉树 C 无左子树的二叉树 D 无右子树的二叉树
4 将数据以___结构存放、查找一个数据的时间不依赖数据个数。
供选择的答案∶
A 顺序 B 链表 C 散列表 D 二叉排序树
5 可以用__这种数据结构辅助实现图的广度优先遍历。供选择的答案∶
A 栈 B 队列 C 广义表 D 树
6 有一散列表,表的长度 m 为 100、采用除余法构造散列函数,即 H(k)=k MODp
(p≤m),为使散列函数具有较好的性能,P 的选择应是____。供选择的答案∶
A 99 B 97 C 93 D 91
8 各种排序算法都需要一些辅助空间暂存数据,插入排序、冒泡排序、选择排序和快速
排序四种算法中、_____所需的辅助空间最多。供选择的答案∶
A 插入排序 B 冒泡排序 C 选择排序 D 快速排序
9 对有 14 个元素的有序表 A【1.14】作二分法查找,查找元素 A【4】时的被比较元素依次
为供选择的答案∶
A A[1].A[2], A[3],A[4] B A[1, A[14],A[7], A[4]C A[7], A[3], A[5],A[4] D A[7],A[5],
A[3],A[4]
10 顺序文件采用顺序结构实现文件的存储,对大型顺序文件的少量修改要求重新复制整
个文件、代价很高。采用___的方法则可降低所需的代价。供选择的答案∶
A 附加文件 B 按关键字大小排序 C 按记录输入先后排序 D 连续存取