2017年云南财经大学信息学院807数据结构考研仿真模拟题
● 摘要
一、填空题
1． 已知二维数组
为1000的连续存储区域时，
【答案】1196
【解析】设元素的行标为i ，列标为j 。则它的存储位置为：
2． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
3． 在一个无向图的的邻接表中，若表结点的个数是m , 则图中边的条数是_____条。
【答案】m/2
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
4． 空格串是指_____，其长度等于_____。
【答案】由空格字符（
值32）所组成的字符串；空格个数
5． 一个算法具有5个特性：_____、_____、_____、有零个或多个输入、有一个或多个输出。
【答案】有穷性；确定性；可行性
6． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。
【答案】左子树；右子树 【解析】二叉排序树
或者是一棵空树，或者是具有下列性质的二叉树：①若它
的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。
7． 检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按_____检索。也可以按_____检索；按_____检索又可以有_____检索和_____检索。
【答案】关键字；记录号；记录号；顺序；直接
8． 当广义表中的每个元素都是原子时，广义表便成了_____。
【答案】线性表
【解析】如果每个元素都是原子，则元素不可分。此时的元素是只有一对一的关系，所以广
第 2 页，共 26 页
中每个元素占4个单元，在按行优先方式将其存储到起始地址的地址是：_____。
义表变成了线性表。
9．
求REPLACE （S ，V , m ）=_____。
已
知
【答案】
10．VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
11．设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。
【答案】
，）则
的地址为_____。
若
12．设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若
则
的地址为
13．顺序栈用
【答案】
将
代入得33。
则的地址为
存储数据，栈顶指针是top ，则值为x 的元素入栈的操作是_____。
【解析】先判断栈是否满，如果不满，元素入栈。否则返回溢出信息。
14．—棵有个结点的满二叉树有_____个度为1的结点、有_____个分支（非终端）结点和_____个叶子，该满二叉树的深度为_____。
【答案】
或
【解析】满二叉树没有度为1的结点，度为0的结点等于度为2的结点个数+1。
15．线性表用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_____。
【答案】（n －1）/2
【解析】删除第一个元素需要移动n －i 次，以此类推，删除最后一个元素需要移动0次。平均次数为
二、判断题
16．栈和队列都是限制存取点的线性结构。（ ）
【答案】
第 3 页，共 26 页
17．有n 个数顺序（依次）入栈，出栈序列有Cn 种
，（ ）
【答案】
且处理只匹配一次的模式时，朴素的匹配（即
18．设模式串的长度为m , 目标串的长度为n ，当
【答案】
【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。
19．堆肯定是一棵平衡二叉树。（ ）
【答案】×
【解析】堆是n 个元素的序列，可以看成是完全二叉树，但相对于根并无左小右大的要求，故其既不是二叉排序树，更不会是平衡二叉树。
20．3阶的B-树是平衡的3路搜索树。反之，一棵平衡的3路搜索树是3阶B-树。（ ）
【答案】×
【解析】3路搜索树并不具有3阶B-树的性质。因此一棵平衡的3路搜索树不一定是3阶B-树。
21．在待排数据基本有序的情况下，快速排序效果最好。（ ）
【答案】×
【解析】在待排数据基本有序的情况下，插入排序效果最好。
22．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。（ ）
【答案】
【解析】算法的健壮性是指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果。
23．不同的求最小生成树的方法最后得到的生成树是相同的。（ ）
【答案】×
，生成树不同，每棵树的权也可能不同。若生【解析】对于一个带权连通无向图G=（V ，E ）
成树T 上的所有边的权值之和最小，则T 称为G 的最小生成树。因此可以看出，最小生成树不是唯一的，最小生成树的权值之和总是唯一的。
24．两分法插入排序所需比较次数与待排序记录的初始排列状态相关。（ ）
【答案】×
【解析】折半插入排序所需的附加存储空间和直接插入排序相同，从时间上比较，折半插入
第 4 页，共 26 页
子串定位函数）算法所花的时间代价可能会更为节省。（ ）
相关内容
相关标签