2017年北京师范大学研究生院珠海分院879程序设计与数据结构考研冲刺密押题

目录

2017年北京师范大学研究生院珠海分院879程序设计与数据结构[专业硕士]考研冲刺密押题（一） (2)

2017年北京师范大学研究生院珠海分院879程序设计与数据结构[专业硕士]考研冲刺密押题（二） (13)

2017年北京师范大学研究生院珠海分院879程序设计与数据结构[专业硕士]考研冲刺密押题（三） (20)

2017年北京师范大学研究生院珠海分院879程序设计与数据结构[专业硕士]考研冲刺密押题（四） (30)

2017年北京师范大学研究生院珠海分院879程序设计与数据结构[专业硕士]考研冲刺密押题（五） (39)

第1 页，共46 页

第 2 页，共 46 页 2017年北京师范大学研究生院珠海分院879程序设计与数据结构[专业硕士]考研冲刺

密押题（一）

注意：①本试题所有答案应写在答题纸上，不必抄题，写清题号，写在试卷上不得分；

②答卷需用黑色笔（钢笔，签字笔，圆珠笔）书写，用铅笔、红色笔等其他颜色笔答题，试题作废；

③答卷上不得做任何与答题无关的特殊符号或者标记，否则按零分处理；

④考试结束后试题随答题纸一起装入试题袋中交回。

————————————————————————————————————————

一、填空题

1． 二进制地址为011011110000，大小为和块的伙伴地址分别为：_____ 【答案】011011110100；011011100000

【解析】011011110000是块的起始地址，

大小分别为和其伙伴块的起始地址计算公式如下：

当大小为4时，起始地址

为

当大小为16时，起始地址为

：

2． 建立索引文件的目的是_____。

【答案】提高查找速度

3． VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。

【答案】分配和释放存储空间；重组；对插入的记录

4． 文件由_____组成；记录由_____组成。

【答案】记录；数据项

5． 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称

增量序列）依次是4，2，1则排序需_____趟，写出第一趟结束后，数组中数据的排列次序_____。

【答案】3;（10，7，-9，0，47，23，1，8，98，36）

6． 下面描述的是一种构造最小生成树算法的基本思想。设要处理的无向图包括n

个顶点

用相邻矩阵A 表示，边的权全是正数。请在下列划线处填上正确叙述。

（1）若是边，则的值等于_____，若不是边，则的值是一个比任何边的权_ ，矩阵的对角线元素全为0。

第 3 页，共 46 页 （2）构造最小生成树过程中，若顶点Vi 已包括进生成树，就把相邻矩阵的对角线元素A （i ,i ）置成__ ，若

已包括进生成树，就把矩阵元素A （i ，j ）置成_ 。 （3）算法结束时，相邻矩阵中_ 的元素指出最小生成树的_ 。

【答案】（1）边上的权值；都大的数；（2）1;负值；（3）为负；边

7． 已知二叉排序树的左右子树均不为空，则_____上所有结点的值均小于它的根结点值，_____上所有结点的值均大于它的根结点的值。

【答案】左子树；右子树

【解析】二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：①若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；②若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；③它的左、右子树也分别为二叉排序树。

8． 在一棵m 阶树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是_____；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是_____。 【答案】

【解析】m 阶树除根结点和叶子结点外，结点中关键字个数最多是最少

9． 无用单元是指_____，例_____

【答案】用户不再使用而系统没有回收的结构和变量；

10．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】

【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。

11．试利用下列栈和串的基本操作完成下述填空题。

initstack （S ） 置S 为空找；

push （S ,X ） 元素X 入找；

pop （S ） 出栈操作；

gettop （S ） 返回栈顶元素；

sempty （S ） 判找空函数；

置串

为空串； length （st ） 返回串st 的长度；

判串

是否相等的函数；

返回联接之后的串；

第 4 页，共 46 页

sub （S ,i ,1） 返回S 中第i 个字符； empty （st ） 判串空函数

{若给定的表达式的前缀式pre 正确，本过程求得和它相应的表达式exp 并返回true ,否则exp 为空串，并返回false 。已知原表达式中不包含括弧，opset 为运算符的集合。）

注意：毎个空格只填一个语句。 【答案】（1）栈S 初始化为空栈 （2）串exp 初始化为空串 （3）判取出字符是否是操作符

（4）如ch 是运算符，则入操作符栈s （5）判栈8是否为空

（6）若读出ch 是操作数且栈为空，则按出错处理

（7）exp （8）若ch 是操作数且栈非空，则形成部分中缀表达式

（9）exp （10）取栈顶操作符 （11）操作符取出后，出栈

（12）

将pre 的最后一个字符（操作数）加入到中缀式exp 的最后

12．对n 个记录的表r[l..n]进行简单选择排序，所需进行的关键字间的比较次数为_____。

【答案】n （n-1）/2

【解析】第一次需要n-1次比较，第i 此需要n-i 此比较，所以共需要、n-l+n-2+...+l=n （n-l ）

本文来源：https://www.bwwdw.com/article/bwke.html