2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研冲刺密押题
● 摘要
目录
2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研冲刺密押题（一）.... 2 2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研冲刺密押题（二）.... 8 2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研冲刺密押题（三）.. 17 2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研冲刺密押题（四）.. 23 2017年军事医学科学院卫生装备研究所836计算机应用之数据结构考研冲刺密押题（五）.. 29
第 1 页，共 34 页
一、填空题
1． 实现字符串拷贝的函数strcpy 为：
【答案】
2． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为
3． 在双向循环链表中，向P 所指的结点之后插入指针f 所指的结点，其操作是_____、_____、_____、_____。
【答案】
4． 无用单元是指_____，例_____
【答案】用户不再使用而系统没有回收的结构和变量； 5．
【答案】5
6． 对于给定的元素，可以构造出的逻辑结构有_____，_____，_____，_____四种。
【答案】集合；线性结构；树形结构；图状结构（网状结构）
7． 按LSD 进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用_____的排序方法。
【答案】稳定
第 2 页，共 34 页
=_____
8． 设广义表则 是_____tail（L ）是_____；L 的长度是_____；深度是_____。
；；2；2 【答案】（ ）（（ ））
【解析】广义表的表头是表的第一个元素，表尾是除了第一个元素外其余的所有的元素构成的表；表的长度指表中元素的个数；表的深度指展开后括号的层数。
9． 属于不稳定排序的有_____。
【答案】希尔排序、简单选择排序、快速排序、堆排序等
10．起始地址为480，大小为8的块，其伙伴块的起始地址是_____；若块大小为32，则其伙伴块的起始地址为_____。
【答案】
【解析】起始地址为P ，大小为的内存块，其伙伴块的起始地址计算公式如下：
根据上述公式起始地址就为488。
11．在基于关键字比较且时间为O （nl 〇g2n ）的排序中，若要求排序是稳定的，则可选用_____，则可选用_____排序。 排序；若要求就地排序（及辅助空间为0（1））
【答案】归并；堆
12．对单链表中元素按插入方法排序的C 语言描述算法如下，其中L 为链表头结点指针。请填充算法中标出的空白处，完成其功能。
【答案】（1）（2）（3）（4）（5）
第 3 页，共 34 页
置空链表，然后将原链表结点逐个插入到有序表中
当链表尚未到尾，p 为工作指针
查P 结点在链表中的插入位置，这时q 是工作指针
将P 结点链入链表中
是q 的前驱，u 是下个待插入结点的指针
13．已知链队列的头尾指针分别是f 和r , 则将值x 入队的操作序列是_____。
【答案】
【解析】队列采用链式存储结构，先分配一个节点的内存，然后在队尾添加该节点。
14．VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
15．设有个结点的完全二叉树顺序存放在向量
【答案】
中，其下标值最大的分支结点为_____。
【解析】最大的分支结点是最后一个叶子结点的父结点。
二、选择题
16．组内的所有元素和小于后一组内的所有元素，若采用基于比较的排序，其时间下界应为（ ）。
A. B. C. D.
【答案】B
【解析】因组与组之间已有序，故将
个组分别排序即可，基于比较的排序方法每组的时
间下界为
0全部时间下界为
17．系统为某进程分配了4个页框，该进程已访问的页号序列为2, 0, 2, 9, 3, 4, 2, 8, 2, 3, 8, 4, 5, 若进程要访问的下一页的页号为7，依据LRU 算法，应淘汰页的页号是（ ）。
A.2 B.3 C.4 D.8
【答案】B
【解析】LRU 置换算法是选择最近最久未使用的页面予以淘汰。进程有4个页框，题中访问过程中页框的变化如下：
序列：页框：
淘汰：3。
第 4 页，共 34 页
访问页号为7的页时，内存中存在的页的页号是：3、8、4和5，根据LRU 定义应淘汰的是