2018年鲁东大学信息与电气工程学院828计算机科学与技术专业基础之数据结构考研核心题库
● 摘要
一、填空题
1． 设T 是一棵结点值为整数的二叉排序树，A 是一个任意给定的整数。在下面的算法中，free_tree(T)在对二叉排序树丁进行后序遍历时释放二又排序树T 的所有结点
；
，首先在二叉排序树T 中查找值为A 的结点，根据查找情况分别进行如下
处理:(1)若找不到值为A 的结点，则返回根结点的地址(2)若找到值为A 的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A 的结点是查找树的根结点，删除后变成空的二叉树，则返NULL ; 否则返回根结点的地址。
【答案】
2． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长(也称增 量序列) 依次是4， 2， 1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。
【答案】3; (10，7，-9，0，47，23，1，8，98，36)
3． 已知一循环队列的存储空间为则此循环队列判满的条件是_____
【答案】
4． VSAM(虚拟存储存取方法) 文件的优点是:动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
，其中n ＞m ，队头和队尾指针分别为front 和rear ，
5． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉树。故结点个数为。
6． 在n 个顶点的非空无向图中，最多有_____个连通分量。
【答案】n
【解析】当n 个顶点之间没有边，都是孤立的顶点时，有n 个连通分量。
7． 栈是_____的线性表，其运算遵循_____的原则。
【答案】操作受限(或限定仅在表尾进行插入和删除操作) ；后进先出 8． 假定查找有序表
【答案】
表
平均查找次数为。
9． 阅读下列程序，指出其功能，并写出空格处应填上的语句。
【答案】
中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。
【解析】折半查找时每个的次数如表所示:
【解析】本题是在哈希表中插入值为item 的元素，如该元素已在哈希表中，报告出错。
10．在一个无向图的的邻接表中，若表结点的个数是m ，则图中边的条数是_____条。
【答案】
【解析】对于无向图，在邻接表中，如果存在n 条边，则会有2n 个表结点。
二、单项选择题
11．引入二叉线索树的目的是（ ）。
A. 加快查找结点的前驱或后继的速度 B. 为了能在二叉树中方便地进行插入与删除 C. 为了能方便地找到双亲 D. 使二叉树的遍历结果唯一 【答案】A
【解析】二叉线索树有指向前驱和后继的指针，因此加快了查找前驱和后继结点的速度。
12．已知一个长度为16的顺序表L , 其元素按关键字有序排列。若采用折半查找法查找一个L 中不存在的元素, 则关键字的比较次数最多是（ ）。
A.4 B.5 C.6 D.7
【答案】B
【解析】
折半查找法在查找不成功时和给定值进行比较的关键字个数最多为题中, n=16, 故比较次数最多为5。
13．
将一个的三对角矩阵，
按行优先存入一维数组A 6665(即该元素下标i ＝66，j ＝65) ，在B 数组中的位置K 为（ ）。
A.198 B.195 C.197
【答案】B
【解析】将对角矩阵a[i][j]存入b[k]，三对角矩阵压缩地址计算公式如下:k ＝2i ＋j ﹣2。
14．一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）.
A.28字节 B.216字节 C.224字节 D.232字节 【答案】C
【解析】段内位移的最大值就是最大段长. 段号长度占了8位，剩下32﹣8＝24位是段内位移空间，因此最大段长为2B.
15．设有一个10阶的对称矩阵A ，采用压缩存储方式，以行序为主存储，a 11为第一元素，其存
24
, 在本
中，A 中元素
储地址为1，每个元素占一个地址空间，则a 85的地址为（ ）。
A.13 B.33 C.18