2017年大连理工大学管理与经济学部810数据结构和计算机组成原理之数据结构考研仿真模拟题
● 摘要
一、选择题
1． 假设栈初始为空，将中缀表达式
当扫描到f 时，栈中的元素依次是（ ）
A.
B. C. D. 【答案】B
【解析】中缀表达式转后缀表达式遵循以下原则： （1）遇到操作数，直接输出； （2）栈为空时，遇到运算符，入栈； （3）遇到左括号，将其入栈；
（4）遇到右括号，执行出栈操作，并将出桟的元素输出，直到弹出栈的是左括号， 左括号不输出； （5）遇到其他运算符运算符入栈；
（6）最终将栈中的元素依次出栈，输出。 所以扫描到优先级比
入栈‘描到
由于
优先级比
低，所以将
弹出，
入栈；扫描到
，
高，入栈；扫描到
入栈; 扫描到
将栈中优先级更高的
弹出，入栈; 扫描到
时，弹出所有优先级大于或等于该运算符的栈顶元素，然后将该
转换为等价后缀表达式的过程中，
优先级比高，入栈。所以扫描到f 的时候，栈中元素为
2． 算法的计算量的大小称为计算的（ ）。
A. 效率 B. 复杂性 C. 现实性 D. 难度 【答案】B
【解析】算法复杂度通常分为时间复杂度和空间复杂度，算法的计算量的大小可以用时间复杂度衡量，即可以称为计算的复杂度。
3． 下列选项中，在用户态执行的是（ ）。
A. 命令解释程序 B. 缺页处理程序 C. 进程调度程序 D. 时钟中断处理程序 【答案】A
【解析】题目是问用户态执行，可见是有关操作系统基本概念的问题。四个选项中，用户唯一能面对的是命令解释程序，缺页处理程序和时钟中断都属于中断，在核心态执行，而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口，可以运行在用户态，接受用户的命令操作控制。
4． 一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（ ）个不同的码字。
A.107 B.108 C.214 D.215
【答案】B
【解析】此题可转化为一棵哈夫曼树共有215个结点，共有多少叶子结点。又有以
所
也就是说若对其进行哈夫曼编码，共能得到108个码字。
5． 若查找每个记录的概率均等，则在具有n 个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度
【答案】C
【解析】最快查找一次成功，最慢查找n
次成功。平均查找次数为
那么
6． 已知序列25, 13, 10, 12, 9是大根堆，在序列尾部插入新元素18, 将其再调整为大根堆，调整过程 中元素之间进行的比较次数是（ ）。
A.1 B.2 C.4 D.5
【答案】B
【解析】对堆插入或删除一个元素，有可能不满足堆的性质，堆被破坏，需要调整为新堆。 （1）为原堆， （2）为插入18后，
（3）比较10与18，交换后，
（4）比较25与18, 不交换，即为调整后的新的大根堆。 因此调整过程中元素之间进行的比较次数为2。
为（ ）。
7． 下列选项中，属于多级页表优点的是（ ）
A .加快地址变换速度 B. 减少缺页中断次数 C. 减少页表项所占字节数 D. 减少页表所占的连续内存空间 【答案】D
【解析】多级页表避免了把所有的页表一直保存在内存中
8． 某磁盘的转速为10, 000转/分，平均寻道时间是磁盘传输速率是为
读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms B.9.4ms C.12ms D.12.4ms 【答案】B
【解析】磁盘转速是10 000转/分钟，平均转一转的时间是6ms ，因此平均查询扇区的时间是3ms ，平均寻道时间是6ms ，读取4KB 扇区信息的时间为0.2ms ，信息延迟的时间为0.2ms ，总时 间为
9． 元素a , b , c , d , e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d 开头的序列个数是（ ）。
A.3 B.4 C.5 D.6
【答案】B
【解析】d 首先出栈后的状态如下图所示。
磁盘控制器延迟
相关内容
相关标签