2018年兰州交通大学电子与信息工程学院828数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 在下列存储形式中，哪一个不是树的存储形式？（ ）
A. 双亲表示法 B. 孩子链表表示法 C. 孩子兄弟表示法 D. 顺序存储表示法 【答案】D
【解析】顺序存储就是利用一段连续的存储单元依次存储线性表中的元素。树中某个结点的孩子可以有多个，这就意味着，无论用哪种顺序将树中所有的结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此简单的顺序存储表示不能满足树的基本要求。常用的三种树的表示法为:双亲表示法、孩子链表示法、孩子兄弟表示法。
2． 某磁盘的转速为10, 000转/分, 平均寻道时间是6ms , 磁盘传输速率是为
, 读取一个4KB 的扇区所需平均时间约为（ ）
A.9ms B. C.12ms D. 【答案】B
【解析】磁盘转速是10000转/分钟, 平均转一转的时间是6ms , 因此平均查询扇区的时间是3ms , 平均寻道时间是6ms , 读取4KB
扇区信息的时间为
。
3． 已知有向图G=(V，E) , 其中
,
G 的拓扑序列是（ ）。 A. B. C. D.
【答案】A 拓扑序列的条件:若
能被称为必须排
, 信息延迟的时间为0.2ms ,
总时间为
, 磁盘控制器延迟
【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列
是图中的边(即从顶点
到有一条路径) ，则在序列中顶点
在顶
点之前。根据上面拓扑序列的定义，就可以得出G 的拓扑序列
是
。
4． 有两个并发执行的进程P1和P2, 共享初值为1的变量x 。P1对x 加1, P2对x 减1。加1和减1操作的指令序列分别如下所示。
两个操作完成后, 2的值（ ）。 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种了。
5． 已知序列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。
6． 和顺序栈相比，链栈有一个比较明显的优势是（ ）。
A. 通常不会出现栈满的情况 B. 通常不会出现栈空的情况 C. 插入操作更容易实现 D. 删除操作更容易实现 【答案】A
7． 某计算机主存容量为64KB ，其中ROM 区为4KB ，其余为RAM 区，按字节编址. 现要用2K ×8位的ROM 芯片和4K ×4位的RAM 芯片来设计该存储器，则需要上述规格的ROM 芯片数和RAM 芯片数分别是（ ）
A.1、15 B.2、15 C.1、30 D.2、30 【答案】D
【解析】主存储器包括RAM 和ROM 两部分，由于ROM 区为4KB ，则RAM 区为60KB. 存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种. 选用2Kx8位的ROM 芯片，只需采用2片芯片进行字扩展便可得到4KB 的ROM 区；选用4Kx4位的RAM 芯片，需采用(60)/4*2片芯片进行字和位同时扩展便可得60KB 的RAM 区.
8． 在支持多线程的系统中, 进程P 创建的若干个线程不能共享的是（ ）。
A. 进程P 的代码段 B. 进程P 中打开的文件 C. 进程P 的全局变量 D. 进程P 中某线程的栈指针 【答案】D