2016年云南财经大学信息学院算法与数据结构之数据结构复试笔试最后押题五套卷
● 摘要
目录
2016年云南财经大学信息学院算法与数据结构之数据结构复试笔试最后押题五套卷（一） . .... 2 2016年云南财经大学信息学院算法与数据结构之数据结构复试笔试最后押题五套卷（二） . .. 10 2016年云南财经大学信息学院算法与数据结构之数据结构复试笔试最后押题五套卷（三） . .. 17 2016年云南财经大学信息学院算法与数据结构之数据结构复试笔试最后押题五套卷（四） . .. 24 2016年云南财经大学信息学院算法与数据结构之数据结构复试笔试最后押题五套卷（五） . .. 31
一、选择题
1． 若
A.x+y B.-x+y C.x-y D.-x-y 答:C
则下列表达式采用8位定点补码运算实现时，会发生溢出的是（ ）
【解析】8位定点补码能表示的数的范围为：码能表示的数的范围，会发生溢出
2． —个具有1025个结点的二叉树的高h 为（ ）。
A.11 B.10
C.11至1025之间
D.10至1024之间 答:C
A 结果为78, B结果为-128, D结果为-78都在此范围内，只有C 结果128超过了8位定点补
【解析】当一棵树是完全二叉树时，其高度最低，此时高度为11，当一棵树的结点在一条线上时，此时最高，这时二叉树的高度是1025。
3． 下列关于AOE 网的叙述中，不正确的是（ ）。
A. 关键活动不按期完成就会影响整个工程的完成时间 B. 任何一个关键活动提前完成，那么整个工程将会提前完成 C. 所有的关键活动提前完成，那么整个工程将会提前完成 D. 某些关键活动若提前完成，那么整个工程将会提前完成 答:B
【解析】关键路径是指从有向图的源点到汇点的最长路径。某些关键活动提前完成，那么整个工程将会提前完成，但不是任何一个关键活动提前完成，就能保证整个工程将会提前完成。
4． 用海明码对长度为8位的数据进行检/纠错时，若能纠正一位错，则校验位数至少为（ ）
A.2 B.3 C.4 D.5 答:C
【解析】设校验位的位数为k ，数据位的位数为n ，根据海明码编码k 和n
应满足下述关系。
当k=4时，
符合要求，校验位至少是4位，故答案为C 。
5． 某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，
把一个磁盘块读人缓冲区的时间为传送到用户区的时间是
CPU 对一块数据进行分析的时间为
构下，读人并分析完该文件的时间分别是（ ）。
A. B. C. D. 答:B
【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的，所以对单一缓冲区，从磁盘写入和读 出到用户区的操作必须串行执行，也就是要保证互斥操作。而CPU 对数据的分析与从用户区读数据也是需要互斥操作，但是CPU 分析与从磁盘写入缓冲区的操作可以并行。从本题看，由于分析所用的时间小于从磁盘写入 缓冲区的时间，因此，CPU 会空闲。单缓冲区的总时间=（磁盘写入缓冲区时间+缓冲区读出时间
）
处理最后一块数据的时
间
当采用双缓冲区时，每块缓冲区的操作也必须满足互斥操作，但是，
对两块缓冲区的操作却可以并行，所以，当第一个缓冲区写满以后，磁盘紧接着写另一个缓冲区，同时，前一个已经满了的缓冲区被读出到用户区，并立即进行CPU 的数据分析。读出操作和数据分析必须互斥进行，故从时间上看，当数据被读出并分析后，恰好另一个缓冲区也写满了，可以立即进行读出数据到用户区并 进行数据分析。两块缓冲区交替进行读写，直到数据分析完毕，因此，总时间=（磁盘写入缓冲区时间）
表示对
级中断进行
读出最后一块数据时间+CPU分析最后一块数据时间=
6． 某计算机有五级中断的顺序为
A.11110 B.01101 C.00011 D.01010 答:D
【解析】由于
则
中断屏蔽字为
屏蔽。若中断响应优先级从高到低的顺序是
将缓冲区的数据
，在单缓冲区和双缓冲区结
且要求中断处理优先级从高到低
的中断处理程序中设置的中断屏蔽字是（ ）。
B
排除掉。的中断处理优先级下降，屏蔽字中需要3个0, 所以可以将选项A 、
需要对开放，所以相应位应该为即为01010。
7． 下列关于虚拟存储的叙述中，正确的是（ ）。
A. 虚拟存储只能基于连续分配技术 B. 虚拟存储只能基于非连续分配技术
C. 虚拟存储容量只受外存容量的限制 D. 虚拟存储容量只受内存容量的限制 答:D 。
【解析】所谓虚拟存储，是指运行的进程不必全部装入内存，只需要部分装入便可以开始运行的一种技术，在运行过程中，当所需要的代码部分不在内存时，通过一种技术（例如缺页中断，技术）将所需要的页面调入内存，从而继续运行。虚拟存储可以在较少的内存中运行较大的程序。但是需要有较大的外存以及相应的软、硬件 机制配合才能实现。虚拟存储器可以连续分配也可以非连续分配，虚拟存储器和外存大小没有关系，所以选项中 的A ，B ，C 都是错误的，所以答案是D 项。
8． 下列选项中，操作系统提供的给应用程序的接口是（ ）。
A. 系统调用 B. 中断 C. 库函数 D. 原语 答:A
【解析】操作系统提供给用户应用程序的接口只有两种：命令输入和系统调用。其中，命令输入又有不同的形式，例如常规的命令行、图形化人机交互接口复杂调用（例如多种
，
以及包含在）
自然命令用户接口
等，而系统调用中除了常规的一些传统的系统调用（例如read （ ））以外，还有经过扩展的
库中的各种封装好的过程调用（最终都是通过系统调
用陷入到操作系统中去的）等。
9． 若线性表最常用的操作是存取第I 个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（ ）。
A. 单链表 B. 双向链表 C. 单循环链表 D. 顺序表 答:D
【解析】线性表采用顺序表，便于进行存取任一指定序号的元素。
10．在系统内存中设置磁盘缓冲区的主要目的是（ ）。
A. 减少磁盘I/O次数 B. 减少平均寻道时间 C. 提高磁盘数据可靠性 D. 实现设备无关性