2017年北方民族大学计算机技术833C语言程序设计与数据结构之数据结构考研冲刺密押题
● 摘要
一、填空题
1． 二进制地址为011011110000，大小为【答案】011011110100；011011100000
011011110000是块的起始地址，
【解析】大小分别为式如下：
当大小为4时，起始地址
为
2． 在单链表中设置头结点的作用是_____。
【答案】方便运算
3． 外排序的基本操作过程是_____和_____。
；归并 【答案】生成有序归并段（顺串）
4． 索引顺序文件既可以顺序存取，也可以_____存取。
【答案】随机
5． 抽象数据类型的定义仅取决于它的一组_____，而与_____无关, 即不论其内部结构如何变化，只要它的_____不变，都不影响其外部使用。
【答案】逻辑特性；在计算机内部如何表示和实现；数学特性
6． 空格串是指_____，其长度等于_____。
【答案】由空格字符（值32）所组成的字符串；空格个数
7． 对于一个具有n 个结点的二叉树，当它为一棵_____二叉树时具有最小高度，当它为一棵_____ 时. 具有最大高度
【答案】完全；只有一个叶结点的二叉树
第 2 页，共 41 页 和块的伙伴地址分别为：_____ 和其伙伴块的起始地址计算公当大小为16时，起始地址为
：
8． 模式串的next 函数值序列为_____。
【答案】01122312
9． 顺序存储结构是通过_____表示元素之间的关系的；链式存储结构是通过_____表示元素之间的关系的。
【答案】物理上相邻；指针
【解析】顺序存储结构是通过物理位置表示元素之间的关系的，链式存储结构通过指针表示元素之间的关系。
10．一个有2001个结点的完全二叉树的高度是_____。
【答案】11
【解析】
完全二叉树的高度
二、判断题
11．一般来说，若深度为k 的n 个结点的二叉树只有最小路径长度，那么从根结点到第
的最多结点数为【答案】√
【解析】求最小路径长度，即构成哈夫曼树，当哈夫曼树为层全满时，
此时从根结点到第 层具有最大的结点数为
12．平衡二叉树中，若某个结点的左、右孩子的平衡因子为零，则该结点的平衡因子一定是零。（ ）
【答案】×
【解析】平衡因子定义为该结点的左子树的深度减去右子树的深度，一个平衡二叉树中，某节点的左右孩子的平衡因子为0，说明左孩子的左子树和右子数的深度相同，而且右子树的左子树和右子数的深度相同，但这不能说明该节点的左子树和右子树的深度相同。
13．串是一种数据对象和操作都特殊的线性表。（ ） 【答案】
【解析】串是一种操作特殊的线性表，其特殊性主要体现在数据元素是一个字符。在内存中，一份文本都可以看做是一个字符串，而每一行都可以看做是其子串。
14．若一个广义表的表头为空表，则此广义表亦为空表。（ ）
【答案】×
【解析】广义表的表头就是广义表的第一个元素。只有非空广义表才能取表头。
第 3 页，共 41 页 层具有余下的个结点在第k 层的任一位置上。（ ）
15．如果完全二叉树从根结点开始按层次遍历的输序列为1，2，3，4，5，6，7，则该完全二叉树是二叉排序树。（ ）
【答案】×
【解析】不是，2，3作为1的左右孩子，由于左节点2比1大，所以不具有二叉排序树的性质。
16．排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（ ）
【答案】×
【解析】排序的稳定性指：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，且ri 在rj 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。
17．设模式串的长度为m , 目标串的长度为n ，当且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（ ） 【答案】
【解析】因为两个字符串的长度几乎相等，因此，在进行相应的匹配时，只需要定位父串的前几位即可。
18．稀疏矩阵压缩存储后，必会失去随机存取功能。（ ）
【答案】√
【解析】稀疏矩阵在压缩存储后，必回失去随机存储的功能。因为在这个矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。
19．负载因子（装填因子）是哈希表的一个重要参数，它反映哈希表的装满程度。（ ）
【答案】√
【解析】查找过程中需和给定值进行比较的关键字的个数取决于三个因素：哈希函数，处理冲突的方法和哈希表的装填因子。其中装填因子标志哈希表的装满程度。
20．若中序遍历平衡的二叉排序树，可得到排好序的关键码序列。（ ）
【答案】√
【解析】二叉排序树对于每一个结点，它的左子树的所有结点的值都小于这个结点的值，而它的右子树的所有结点的值都大于这个结点的值。而采用中序遍历，遍历顺序为左根右，因此可以得到按增序排列的关键码序列。
三、算法设计题
第 4 页，共 41 页