2016年北京交通大学软件学院10101数据结构考研复试题库
● 摘要
一、选择题
1． 单链表中，增加一个头结点的目的是为了（ ）。
A. 使单链表至少有一个结点
B. 标识表结点中首结点的位置
C. 方便运算的实现
D. 说明单链表是线性表的链式存储
答:C
【解析】单链表中增加一个头结点的目的是为了方便运算的实现，使得对第一个元素的操作与其它元素的操作相同。
2． 若无向图G= （V , E）中含7个顶点，则保证图G 在任何情况下都是连通的，则需要的边数最少是（ ）。
A.6
B.15
C.16
D.21
答:C
【解析】要保证无向图G 在任何情况下都是连通的，即任意变动图G 中的边，G 始终保持连通。首先需要图G 的任意6
个结点构成完全连通子图然后再添加一条边将第7个结点与需条边，连接起来，共需16条边。本题非常容易错误地选择选项A ，主要原因是对“保证图G 在任何情况下都是连通的”的理解，分析选项A ，在图G 中，具有7个顶点6条边并不能保证其一定是连通图，即有n-1 条边的图不一定是连通图。分析选项D ，图G 有7个顶点21条边，那么图G —定是无向完全图，无向完全图能 保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。
3． 某容量为256M 的存储器，由若干位的DRAM 芯片构成，该DRAM 芯片的地址引脚和数据引脚总数是：（ ）
A.19
B.22
C.30
D.36
答:A
【解析】DRAM 地址线复用，4M 为2的22次方，因此除2为11根，数据线8根。因此地址引脚和数据引脚总数为19根
4． 某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，
把一个磁盘块读人缓冲区的时间为
传送到用户区的时间是CPU 对一块数据进行分析的时间为
构下，读人并分析完该文件的时间分别是（ ）。 A. B. C. D.
答:B
【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的，所以对单一缓冲区，从磁盘写入和读 出到用户区的操作必须串行执行，也就是要保证互斥操作。而CPU 对数据的分析与从用户区读数据也是需要互斥操作，但是CPU 分析与从磁盘写入缓冲区的操作可以并行。从本题看，由于分析所用的时间小于从磁盘写入 缓冲区的时间，因此，CPU 会空闲。单缓冲区的总时间=（磁盘写入缓冲区时间+缓冲区读出时间
）处理最后一块数据的时
间
当采用双缓冲区时，每块缓冲区的操作也必须满足互斥操作，但是，
对两块缓冲区的操作却可以并行，所以，当第一个缓冲区写满以后，磁盘紧接着写另一个缓冲区，
同时，前一个已经满了的缓冲区被读出到用户区，并立即进行CPU 的数据分析。读出操作和数据分析必须互斥进行，故从时间上看，当数据被读出并分析后，恰好另一个缓冲区也写满了，可以立即进行读出数据到用户区并 进行数据分析。两块缓冲区交替进行读写，直到数据分析完毕，因此，总时间=（磁盘写入缓冲区时间）
转换为等价后缀表达式的过程中，读出最后一块数据时间+CPU分析最后一块数据时间= 5． 假设栈初始为空，将中缀表达式
当扫描到f 时，栈中的元素依次是（ ） A.
B.
C.
D.
答:B
【解析】中缀表达式转后缀表达式遵循以下原则：
（1）遇到操作数，直接输出；
（2）栈为空时，遇到运算符，入栈；
（3）遇到左括号，将其入栈；
（4）遇到右括号，执行出栈操作，并将出桟的元素输出，直到弹出栈的是左括号，
左括号不输出；
（5）遇到其他运算符
运算符入栈；
将缓冲区的数据，在单缓冲区和双缓冲区结 时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该