2018年华北电力大学(北京)控制与计算机工程学院842数据结构与操作系统之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。
A. 单链表
B. 仅有头指针的单循环链表
C. 双链表
D. 仅有尾指针的单循环链表
【答案】D
【解析】仅有尾指针的单循环链表，在最后插入元素和删除第一个元素都会用到这个尾指针。
2． 下列因素中, 不会影响信道数据传输速率的是（ ）
A. 信噪比
B. 频率宽带
C. 调制速率
D. 信号传播速度
【答案】D
【解析】信道数据传输速率与信噪比、频率宽度、调制速率都有关。
3． 设二维数组(即m 行n 列) 按行存储在数组中，则二维数组元素A[i，j]在一维数组B 中的下标为（ ）。
A.(i﹣1)*n＋j
B.(i﹣1)*n＋j ﹣l
C.i*(j﹣1)
D.j*m＋i ﹣l
【答案】A
【解析】前i ﹣1的元素个数为(i﹣1)*n，所以二维数组元素A[i，j]在一维数组B 中的下标为(i﹣1)*n＋j 。需要注意数组B 的下标是从0开始，还是从1开始。
4． 某计算机存储器按字节编址, 采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位, 并且数据按边界对齐存储。某C 语言程序段如下:
若record 变量的首地址为0xC008, 则地址A. B. C. D.
【答案】D 。 中内容及的地址分别为（ ）。 32位整数a 需要占4个字节, 16位整数c 需要占2个字节, 而字符数据b 占一个字节。【解析】
a=273, 转换成十六进制是111H , 采用小端方式存放数据, 地址
边界对齐存储,
地址
中存放c 。
5． 设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。
A. 求子串
B. 判断是否相等
C. 模型匹配
D. 连接
【答案】C
【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。
6． n 个结点的线索二叉树上含有的线索数为（ ）。
A.2n
B.n ﹣1
C.n ＋1
D.n
【答案】C
【解析】线索二叉树是利用二叉树的空链域加上线索，n 个结点的二叉树有n ＋1个空链域。
7． 下列选项中, 不可能在用户态发生的事件是（ ）。
A. 系统调用
B. 外部中断
C. 进程切换
D. 缺页
【答案】C 。
【解析】我们在学习操作系统中知道, 任何一个进程在现代操作系统中为了共享和保护, 设定
中的内容为11H 。由于数据按中存放b ,
地址中空闲,
地址中存放a ,
地址
了用户态和内核态(可以通过设置软、硬件标志位来实现) , 在用户态运行用户的程序, 在内核运行系统的程序。所以, 从选项来看, 系统调用可以在任何态发生, 用户可以发起系统调用, 系统也可以; 外部中断是不可控的, 也会在任何时刻发生, 缺页的发生也是不可控的, 可以发生在用户代码之间; 而进程切换却不会在用户态发生。我们可以考虑一下情形, 进程切换是在什么时候发生的, 进程切换前必定运行的是进程调度, 只有进程调度选择了下一次被调度的进程, 进程切换才可以进行。进程调度是scheduler , 进程切换是dispather , 这体现了现代操作系统策略与机制分离的设计思想。所以, 进程切换必定不会在用户态发生(所谓发生指其起始的源头时刻) , 必定是在内核态(进程调度) 发生的。
8． —个栈的入栈序列为1, 2, 3, ……, n , 其出栈序列是
取值的个数是（ ） A. B. C.
D. 无法确定
【答案】C
【解析】除了3本身以外, 其他的值均可以取到, 因此可能取值的个数为n-1。
9． 设有数组A[i，j]，数组的每个元素长度为3字节，i 的值为1到8，j 的值为1到10，数组从内存首地址BA 开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为（ ）。
A.BA+141
B.BA+180
C.BA+222
D.BA+225
【答案】B
【解析】在计算中，可以考虑按照列存放时，A[5，8]在内存的位置，比较容易计算元素的首地址。比如A[5，8]顺序存放时，它是第7*8＋5＝61个元素，由于首地址为BA ，所以它的存储首地址为BA ＋(61﹣1)*3＝180+BA。
10．在虚拟存储管理中, 地址变换机构将逻辑地址变换为物理地址, 形成该逻辑地址的阶段是（ ）。
A. 编辑
B. 编译
C. 链接
D. 装载
【答案】B
【解析】程序的编辑阶段一般都是程序员能够识别的高级语言或低级语言的文本, 不涉及到任何与计算机运行相关的事; 编译是由编译程序将用户源代码编译成若干个目标模块, 源地址编译成
。若, 则, 则可能