2017年北京服装学院计算机信息中心917程序设计与算法考研题库
● 摘要
一、填空题
1． 在一个具有n 个单元的顺序栈中，假定以地址高端（即下标为n 的单元）作为栈底，以top 作为栈顶指针，则当向栈中压入一个元素时，top 的变化是top=_____。 【答案】
【解析】由于栈底在地址高端，栈中压入一个元素时，栈顶向地址底端移动一个单位，
所以
2． 设T 和P 是两个给定的串，在T 中寻找等于P 的子串的过程称为_____，又称P 为_____。
【答案】模式匹配；模式串
3． 设正文串长度为n ，模式串长度为m ，则串匹配的KMP 算法的时间复杂度为_____。 【答案】
4．
给定一组数据
的值为_____。
【答案】5；96
【解析】每次找两个最小的权值构建哈夫曼树：
以它构造一棵哈夫曼树，则树高为_____，
带权路径长度
5． 文件可按其记录的类型不同而分成两类，即_____和_____文件。
【答案】操作系统文件；数据库
6． 如下的算法分别是后序线索二叉树求给定结点node 的前驱结点与后继结点的算法，请在算法
，其空格处填上正确的语句。设线索二叉树的结点数据结构为（lflag ，lcft ，data ，right ，rflag ）
中：lflag=0，lcft 指向其左孩子，lflag=1，left 指向其前驱：rflag=0，right 指向其右孩子，rflag=1，right 指向其后继。
Prior （node , x ）
{ if（node !=null）
If （ （1） ） *x=node->right；else * x-node->left;
}
next （bt , node, x ）/*bt是二叉树的树根*/
{ （2） ;
if （node->rflag）（3）;
else {do t=*x；;
while （*x==node ）;
*x=t;
}
}
【答案】nodc->rflag==O; *x=ht; *x=nodc->right; prior （t , X ）
7． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
8． 设单链表的结点结构为为指针域，已知指针px 指向单链表中data 为x 的结
_____；点，指针py 指向data 为y 的新结点，若将结点y 插入结点x 之后，贝懦要执行以下语句：
_____; 【答案】
9． N 个顶点的连通图用邻接矩阵表示时，该矩阵至少有_____个非零元素。
【答案】2（N-1）
【解析】所谓连通图一定指的是无向图，有向图会称作强连通图。连接N 个顶点，至少需要N-1条边就可 以了。由于无向图的每一条边同时关联了两个顶点。因此用邻接矩阵表示时，该矩阵至少有2（N-1）个非零元素。
10．在哈希函数中，P 值最好取_____。
【答案】小于等于表长的最大素数或不包含小于20的质因子的合数
【解析】在使用除留余数法时，对除数P 的选择很重要。若P 选的不好，容易产生同义词。一般情况下，可以选P 为质数或不包含小于20的质因素的合数。
11．假设一个15阶的上三角矩阵A 按行优先顺序压缩存储在一维数组B 中，则非零元素中的存储位置k=_____。（注：矩阵元素下标从1开始）
【答案】93
【解析】对于上三角矩阵，将
12．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
在B 代入得93。
二、选择题
13．在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法
B. 孩子链表表示法
C. 孩子兄弟表示法
D. 顺序存储表示法
【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为：双亲表示法、孩子链表示法、孩子兄弟表示法。
14．动态存储管理系统中，通常可有（ ）种不同的分配策略。
【答案】C
【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给用户。则系统在分配前首先要对可利用空间表从头到尾扫视一遍，然后从中找出一块不小于n 且最接近n 的空闲块进行分配。③最差拟合法，将可利用空间表中不小于n 且是链表中最大的空闲块的一部分分配给用户。
15．为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A. 栈
B. 队列
C. 树
D. 图
【答案】B
【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。