2017年吉林省培养单位长春光学精密机械与物理研究所866计算机原理之数据结构考研导师圈点必考题汇编
● 摘要
一、填空题
1． —棵深度为k 的平衡二叉树， 其每个非终端结点的平衡因子均为0，则该树共有_____个结点。
【答案】
【解析】每个非终端结点都是0表示该平衡二叉树没有高度落差。也就是说它是一棵满二叉 树。故结点个数为
2． 在单链表中设置头结点的作用是_____。
【答案】方便运算
3． 执行顺序查找时，存储方式可以是_____，折半查找时，要求线性表_____，分块查找时要求线性表_____，而哈希表的查找，要求线性表的存储方式是_____。
【答案】顺序存储或链式存储；顺序存储且有序；块内顺序存储，块间有序；散列存储
4．
【答案】5
5． VSAM 系统是由_____、_____、_____构成的。
【答案】索引集；顺序集；数据集
6． 设有一个空找，栈顶指针为1000H （十六进制），现有输入序列为1，2，3, 4, 5，经过PUSH ，PUSH , POP , PUSH , POP ，PUSH ，PUSH 之后，输出序列是_____，而栈顶指针值是_____。设栈为顺序栈，每个元素占4个字节。
【答案】23; 100CH
7． 数据结构中评价算法的两个重要指标是_____。
【答案】算法的时间复杂度和空间复杂度
8． 建立索引文件的目的是_____。
【答案】提高查找速度
9． 模式串
第 2 页，共 61 页 =_____ 的next 函数值序列为_____。 【答案】01122312
10．VSAM （虚拟存储存取方法）文件的优点是：动态地_____，不需要文件进行_____，并能较快地_____进行查找。
【答案】分配和释放存储空间；重组；对插入的记录
11．顺序查找n 个元素的顺序表，若查找成功，则比较关键字的次数最多为_____次；当使用监视哨时，若查找失败，则比较关键字的次数为_____。 【答案】
【解析】最多的情况就是把整个表遍历了一遍。使用监视哨时，需要多一个存储空间来存监视哨。
12．数据结构是研讨数据的_____和_____以及它们之间的相互关系，并对与这种结构定义相应的_____，设计出相应的_____。
；算法 【答案】逻辑结构；物理结构；操作（运算）
二、选择题
13．—个进程的读磁区操作完成后，操作系统针对该进程必做的是（ ）
A. 修改进程状态为就绪态
B. 降低进程优先级
C. 进程分配用户内存空间
D. 增加进程的时间片大小
【答案】A
【解析】进程等待的操作完成便会从等待状态转移到就绪状态。
14．单级中断系统中，中断服务程序内的执行顺序是（ ）。
I 保护现场；II 开中断；III 关中断；IV 保存断点；V 中断事件处理；VI 恢复现场；VII 中断返回
【答案】A
【解析】程序中断有单级中断和多级中断之分，单级中断在CPU 执行中断服务程序的过程中不能被打断， 即不允许中断嵌套。保存断点与关中断的任务是由硬件（中断隐指令）完成的，所以在单级中断系统中，中断服 务程序内应完成的任务有：①保存现场；②中断事件处理；③恢复现场；④开中断；⑤中断返回。
15．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A.257
B.258
第 3 页，共 61 页
C.384
D.385
【答案】C
【解析】由
：
_
则和
__可知
，
即显然
384, 所以二叉树的叶结点个数是384。还可以根据完全二叉树的另一个性质：最后一个分支结点的序号为[768/2], 故非叶子结点数为384, 而叶子结点的个数为768-384=384。（[x]表示不大于x 的最大整数，比如[3.14] =3）。
16．广义表则式子
【答案】D
head 操作就是得到广义表中第一个的原子。【解析】 的值为（ ）。
操作就是得到除第一个原子外剩下元
素构成的表。也就是toil 得到的元素需要在外层再加一个（ ）。
17．下列选项中，用于设备和控制器（’接口）之间互连的接口标准是（ ）
A.PCI
B.USB
C.AGP
D.PCI-Express
【答案】B
【解析】设备和设备控制器之间的接口是USB 接口，其余选项不符合，故答案为B 。
18．下列选项中，在总线的数据线上传输的信息包括（ ）。
I. 接口中的命令字
II. 接口中的状态字III. 中断类型号
A. 仅 I 、II
B. 仅 I 、III
C. 仅 II 、III
D.I 、II 、III
【答案】D 。
【解析】
在
总线的数据线上传输的信息包括接口中的命令字、状态字以及真正的数据，而中断类型号也是通过数据线传输的。
19．在含有n 个关键字的小根堆（堆顶元素最小）中，关键字最大的记录有可能存储在（ ）位置上。
【答案】D
【解析】小根堆中，关键字最大的记录只能在叶结点上，故不可能在小于等于
上。
第 4 页，共 61 页 的结点