2017年厦门大学自动化系845数据结构考研冲刺密押题
● 摘要
一、填空题
1． 循环队列的引入，目的是为了克服_____。
【答案】假溢出时大量移动数据元素
【解析】用数组实现队列时，如果不移动，随着数据的不断读写，会出现假满队列的情况。即尾数组已满但头数组还是空的。循环队列也是一种数组，引入循环队列，有效克服假溢出大量移动数据元素的问题。
2． 遍历图的过程实质上是_____，广度优先遍历图的时间复杂度_____; 深度优先遍历图的时间复杂度_____, 两者不同之处在于_____, 反映在数据结构上的差别是_____。
【答案】查找顶点的邻接点的过程；0（n+e）; 0（n+e）; 访问顶点的顺序不同；队列和栈 【解析】广度优先遍历图使用队列这种数据结构，深度优先遍历图使用栈这种数据结构。
3． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
4． 在哈希函数
中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
5．
给定一组数据以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
的值为_____。 【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
6． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为
7． 在下面的程序段中，对X 的赋值语句的时间复杂度为_____（表示为n 的函数）。
【答案】1＋（1＋2）＋（1＋2＋3）＋"•＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6，即
【解析】当i=l时，赋值语句就被执行了一次。当i=2时，赋值语句被执行了1＋2次。当i=3时，赋值语句被执行了1＋2＋3次。可以推出赋值语句总共被执行了1＋（1＋2）＋（1＋2＋3）＋…＋（l ＋2＋... ＋n ）=n（n ＋1）（n ＋2）/6次。
8． 在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
9． 已知一循环队列的存储空间为环队列判满的条件是（ ）
【答案】
，）则
的地址为_____。
若
10．设有一个10阶对称矩阵A 采用压缩存储方式（以行为主序存储：
【答案】33
【解析】设存储的元素的行标为i ，列标为j 。若则
的地址为
11．设广义表
将则
代入得33。
是_____tail（L ）是_____；L 的长度是_____；深度是_____。
则
的地址为
其中
队头和队尾指针分别为front 和rear , 则此循
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
12．组成串的数据元素只能是_____。
【答案】字符
二、选择题
13．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是（ ）。
A. 存在，且唯一 B. 存在，且不唯一不唯一 C. 存在，可能不唯一 D. 无法确定是否存在 【答案】C 。
【解析】图的基本应用——拓扑排序，用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，说明该图为有向无环图，所以其拓扑序列存在，但不一定唯一，如图的邻接矩阵为则存在两个拓扑序列。
14．若则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）
A.x+y B.-x+y C.x-y D.-x-y
【答案】C
【解析】8位定点补码能表示的数的范围为：
A 结果为78, B结果为-128, D结果为-78都在此范围内，只有C 结果128超过了8位定点补码能表示的数的范围，会发生溢出
15．用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为趟排序采用的增量（间隔）可能是（ ）
A.2 B.3 C.4 D.5
【答案】B
【解析】对于A , 增量为2, 那么9, 4, 7, 20, 15是一组，而它们是无序的，所以A 错误 对于C , 增量为4, 那么9, 7，15是一组，而它们是无序的，所以C 错误
对于D , 增量为5, 那么9, 8是一组，降序，1，20是一组，而它们是升序，所以D 也错误。对于B ，分为3组：都是升序有序，所以B 正确
16．对给定的关键字序列110, 119, 007, 911，114，120, 122进行基数排序，则第2趟分配收集后得到的关键字序列是（ ）
A. B. C. D.
【答案】C
则该
相关内容
相关标签