2018年郑州大学944计算机学科专业基础综合[专业硕士]之数据结构考研强化五套模拟题
● 摘要
一、单项选择题
1． 某队列允许在其两端进行入队操作, 但仅允许在一端进行出队操作, 元素a , b , c , d , e 依次入此队列后再进行出队操作, 则不可能得到的出队序列是（ ）。
A.b , a , c , d , e B.d , b , a , c , e C.d , b , c , a , e D.e , c , b , a , d
【答案】C
【解析】根据题意, 队列两端都可以输入数据元素, 但是只能在一端输出数据元素, 这种队列为 输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队, 从而得出不可能的情况。
假设L 代表从左端入队, R 代表从右端入队, 出队都是从左端L 出。四个选项所给序列的进队操作序列分别为:
选项A.aL(或aR) , bL , cR , dR , eR 选项B.aL(或aR) , bL , cR , dL , eR 选项C. 不可能出现选项
D.aL(或aR) , bL , cL , dR , eL
2． 在一棵度为4的树T 中, 若有20个度为4的结点, 10个度为3的结点, 1个度为2的结点, 10个度为1的结点, 则树T 的叶结点个数是（ ）。
A.41 B.82 C.113 D.122
【答案】B
【解析】根据二叉树的性质3的推广公式:式, 即
。
树T 的叶子结点的个数是82。
3． 给定二叉树如下图所示. 设N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树. 若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）.
A.LRN B.NRL
第 2 页，共 73 页
可直接在将数据带入公
C.RLN
D.RNL
图
【答案】D
【解析】对“二叉树”而言，一般有三条搜索路径： ①先上后下的按层次遍历； ②先左(子树) 后右(子树) 的遍历； ③先右(子树) 后左(子树) 的遍历.
其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR 、中序遍历LNR 、后序遍历LRN ，第3种搜索路径方式则是不常使用的NRL 、RNL 、RLN. 本题考查的是第3种搜索路径方式的一种情况. 根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D.
4． 某数采用IEEE754单精度浮点数格式表示为C640 0000H, 则该数的值是（ ）
A. B. C. D. 【答案】A
【解析】IEEE754单精度浮点数格式为C640 0000H表示为二进制格式为 1100 01 10 0100 0000 0000 0000 0000 0000, 转换为标准的格式为:
因此, 浮点数的值为。
5． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。
两个操作完成后, 2的值（ ）。
第 3 页，共 73 页
A. 可能为-1或3 B. 只能为1 C. 可能为0、1或2 D. 可能为-1、0、1或2 【答案】C
【解析】这是在数据库中常有的操作。为保证数据的正确, 避免产生错误, 系统必须保证数据的同步。而保证数据的同步一般采取加锁的方法, 让进程P1和P2互斥访问共享变量X 。当然用信号量和P 、V 操作也是可以保证互斥操作, 达到数据同步的。
本例中, 由于没有采取保证数据同步的相应措施, 则最后结果就会出现差错。例如, 当正常情况下, 进程P1和P2先后对x 操作, 可以看到x 值的变化为初始则x 值的变化为初始
的过程, 若P2, P1先后操作,
, 这是正确的。若考虑一种并发的情况, 进程P1和P2先后执行了取数
load 的操作, 它们得到的x 值均为1, 运算后, P1和P2的x 值分别为2和0, 此时要看哪个进程后执行存数store 的操作了, 哪个进程后操作, 结果就是那个进程的x 值, 所以可能的结果为0或2, 加上前面正确的x 值1, 则可能的结果就有3种了。
6． 对于栈操作数据的原则是（ ）
A. 先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 【答案】B
【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。
7． 某文件占10个磁盘块, 现要把该文件磁盘块逐个读入主存缓冲区, 并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同,
把一个磁盘块读人缓冲区的时间为送到用户区的时间是
, CPU
对一块数据进行分析的时间为
下, 读人并分析完该文件的时间分别是（ ）。
A. B. C. D. 【答案】B
【解析】这是一个简单的缓冲区的问题。由于缓冲区的访问是互斥的, 所以对单一缓冲区, 从磁盘写入和读出到用户区的操作必须串行执行, 也就是要保证互斥操作。而CPU 对数据的分析与从用户区读数据也是需要互斥操作, 但是CPU 分析与从磁盘写入缓冲区的操作可以并行。从本题看, 由于分析所用的时间小于从磁盘写入缓冲区的时间, 因此, CPU 会空闲。
第 4 页，共 73 页
, 将缓冲区的数据传
。在单缓冲区和双缓冲区结构
相关内容
相关标签