2017年天津城建大学计算机学院815数据结构考研强化模拟题
● 摘要
一、选择题
1．
已知操作符包括的后缀表达式
将中缀表达式
转换为等价
时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为
空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。
A.5 B.7 C.8 D.11
【答案】A 。
【解析】基本思想是：采用运算符栈是为了比较运算符的优先级，所有运算符必须进栈。只将大于栈顶元素优先级的运算符直接进栈，否则需要退栈栈顶运算符（先出栈的运算符先计算，同优先级的运算符在栈中的先计算）
。表达式所列：
产生后缀表达式的过程如下表
通过上表可以看出，显然转换过程中同时保存在栈中的操作符的最大个数是5。
2． 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz , 则总线带宽是（ ）。
A.lOMB/s B.20MB/S C.40MB/S D.80MB/S 【答案】B
【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz , 时钟周期为0.1押，总线周期占用2个时钟周期，为0.2两。一个总线周期中并行传输4=20MB/s。 字节信息, 则总线带宽是4B ÷
3． 单级中断系统中，中断服务程序内的执行顺序是（ ）。
I 保护现场；II 开中断；III 关中断；IV 保存断点；V 中断事件处理；VI 恢复现场；VII 中断返回
【答案】A
【解析】程序中断有单级中断和多级中断之分，单级中断在CPU 执行中断服务程序的过程中不能被打断， 即不允许中断嵌套。保存断点与关中断的任务是由硬件（中断隐指令）完成的，所以在单级中断系统中，中断服 务程序内应完成的任务有：①保存现场；②中断事件处理；③恢复现场；④开中断；⑤中断返回。
4． 串的长度是指（ ）。
A. 串中所含不同字母的个数 B. 串中所含字符的个数 C. 串中所含不同字符的个数 D. 串中所含非空格字符的个数 【答案】B
【解析】串中字符的数目n 称为字符的长度，不必考虑其中单个字符是否相等。
5． 分别以下列序列构造二叉排序树，与用其他三个序列所构造的结果不同的是（ ）。
【答案】C
【解析】二叉排序树：左右子树都是二叉排序树，且保证右子树都比根结点大，左子树都比根结点小。据以上两点建立二叉排序树。
6． 设二维数组（即m 行n 列）按行存储在数组
中，
则二维数组元素
在一维数组B 中的下标为（ ）。
【答案】A 【解析】
前
的元素个数为
所以二维数组元素
在一维数组B
中的下标为
需要注意数组B 的下标是从0开始，还是从1开始。
7． 在一个有N 个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为（ ）。
【答案】B
【解析】二分查找的时间复杂度为
在一个用N 个元素的有序单链表中查找具有给定
关键字的结点，因为查找是从头结点开始的，需要使用指针顺序往下查找，
因此时间复杂度为
8． 输入序列为ABC ，可以变为CBA 时，经过的栈操作为（ ）。
【答案】B
【解析】根据输入序列和输出序列可知，输入序列全部进栈，然后再出栈。从中可以看出，push 的数目始终大于等于pop 的数目。
9． 下列命中组合情况中，一次访存过程中不可能发生的是（ ）。
A.TLB 未命中，Cache 未命中，Page 未命中 B.TLB 未命中，Cache 命中，Page 命中 C.TLB 命中，Cache 未命中，Page 命中 D.TLB 命中，Cache 命中，Page 未命中 【答案】D
【解析】TLB （快表）和慢表（页表，Page ）构成二级存储系统，若TLB 命中，则Page 必命中。因此不可能发生的是D 选项。
10．下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（ ）。
A. 先来先服务 B. 高响应比优先 C. 时间片轮转
D. 非抢占式短任务优先 【答案】B
【解析】分析该题目可以看到，本题所提到的问题是涉及短任务调度也就是属于作业调度，