2017年杭州电子科技大学数字媒体与艺术设计学院851数据结构考研仿真模拟题
● 摘要
一、填空题
1． 设m 、n 均为自然数，m 可表示为一些不超过n 的自然数之和，f （m , n ）为这种表示方式的 数目。例f （5, 3）=5，有5种表示方式：3＋2, 3＋1＋1，2＋2＋1，2＋1＋1＋1, 1＋1＋1＋1＋1。
①以下是该函数的程序段，请将未完成的部分填入，使之完整。
②执行程序，f （6，4）=_____。 【答案】①1; 1; f （m ，n －1）; n ②9
2． 实现字符串拷贝的函数strcpy 为：
【答案】
在B
3． 假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵
，将
4． 高度为4的3阶B-树中，最多有_____个关键字。
【答案】26
【解析】第4层是叶结点，1层至3层每个结点两个关键字，每个节点的关键字达到最大时，关键字最多。
5．
【答案】5
代入得93。
=_____
6． 一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
7． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
8． 如某二叉树有20个叶结点，有30个结点仅有一个孩子，则该二叉树的总结点数为_____。
【答案】69
【解析】二叉树叶结点数为20, 则度为2的结点数为19, 所以总的结点数为20+19+30=69。
9． 在一棵m 阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。
【答案】
【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是最少
10．设广义表
则是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
11．设有个结点的完全二叉树顺序存放在向量中，其下标值最大的分支结点为_____。
【答案】
【解析】最大的分支结点是最后一个叶子结点的父结点。
12．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。
【答案】视哨。
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监
二、选择题
13．单链表中，增加一个头结点的目的是为了（ ）。
A. 使单链表至少有一个结点 B. 标识表结点中首结点的位置 C. 方便运算的实现
D. 说明单链表是线性表的链式存储 【答案】C
【解析】单链表中增加一个头结点的目的是为了方便运算的实现，使得对第一个元素的操作与其它元素的操作相同。
14．将一个（即该元素下标
A.198 B.195 C.197
【答案】B
的三对角矩阵，按行优先存入一维数组在B 数组中的位置K 为（ ）。
中，A 中元素
【解析】将对角矩阵存入三对角矩阵压缩地址计算公式如下：
15．下列二叉排序树中查找效率最高的是（ ）。
A. 平衡二叉树 B. 二叉查找树
C. 没有左子树的二叉排序树 D. 没有右子树的二叉排序树 【答案】A
【解析】平衡二叉树的左子树和右子树的深度之差的绝对值不超过1。这就保证了二叉树的深度是
级别的。二叉查找树或者是一颗空数；或者是具有下列性质的二叉树：①若左子树不
空，则左子树上所有结点的值均小于它的根结点的值；②若右子树不空，则右子树上所有结点的值均大于它的根结点的值；③左、右子树也分别为二叉排序树。B 、C 、D 三项均不能保证左子树和右子树的深度之差的绝对值不超过1，甚至很大，因此查找效率低。
16．设系统缓冲区和用户工作均采单，从外读入1个数据块到系统缓冲区的时间为100, 从系统缓冲区读入1个数据块到用户工作区的时间为5, 对用户工作区中的1个数据块行分析的时间为90 （如下图所示）。进程从外设读入并分析2个数据块的最短时间是（ ）
A.200
B.295 C.300 D.390
相关内容
相关标签