2017年济南大学信息科学与工程学院846数据结构[专业硕士]考研仿真模拟题
● 摘要
一、选择题
1． 在系统总线的数据线上，不可能传输的是（ ）。
A. 指令 B. 操作数
C. 握手（应答）信号 D. 中断类型号型号 【答案】C
【解析】握手（应答）信号属于通信联络控制信号应该在通信总线上传输，不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。
2． 已知序列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。
3． 下列有关总线定时的叙述中，错误的是（ ）。
A. 异步通信方式中，全互锁协议最慢 B. 异步通信方式中，非互锁协议的可靠性最差 C. 同步通信方式中，同步时钟信号可由多设备提供 D. 半同步通信方式中，握手信号的采样由同步时钟控制 【答案】C
【解析】A 项正确，异步通信方式中，全互锁协议最慢，主从模块都需要等待确认后才能撤销其信号；B 项正确，异步通信方式中，非互锁协议没有相互确认机制，因此可靠性最差；C 项错误，同步通信要遵循统一的时钟信号，不能由多设备提供；D 项正确，半同步通信方式中，握手信号的采样由同步时钟控制。
4． 在双向链表指针P 的结点前插入一个指针q 的结点操作是（ ）。
A. B. C. D. 【答案】C
5． float 型整数据常用IEEE754单精度浮点格式表示，假设两个float 型变量x 和y 分别在32为寄存器
和中，若
A. B. C. D.
且符号相同 且符号不同 且符号相同 且符号不同
则x 和y 之间的关系为：（ ）
【答案】A
【解析】两个数对应的IEEE754的标准形式为；
将IEEE754
单精度形式的二进制转化为浮点数公式为由于
的符号位都是1, 所以fl ，f2符号相同，而阶码上
所以fl 的绝对
值比f2大，而他们都是负数，所以所以选A
6． 某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段。假定取指令时，每取一个字节PC 自动加1。若某转移指令所在主存地址为2000H ，相对位移量字段的内容为06H , 则该转移指令成功转移后的目标地址是（ ）。
A.2006H B.2007H
C.2008H D.2009H 【答案】C
【解析】相对寻址方式的有效地址EA=（PC ）+D, 其中PC 为程序计数器，D 为相对偏移量。主存按字节编址，取指令时，每取一个字节PC 值自动加1。由于转移指令由两个字节组成，取出这条转移指令之后的PC 值自动加2，为2002H ，故转移的目标地址为2002H+06H=2008H。
7． 假设某计算机按字编址，Cache 有4个行，Cache 和主存之间交换的块大小为1个字。若Cache 的内容初始为空，采用2路组相联映射方式和LRU 替换算法，当访问的主存地址依次为0, 4, 8, 2, 0, 6, 8, 6, 4， 8时，命中Cache 的次数是（ ）。
A.1 B.2 C.3 D.4
【答案】C 。
【解析】Cache 有4个行，2路组相联，即Cache 被分成2组，每组2行。主存地址为0〜1、4〜5、8〜9 可映射到第0组Cache 中，主存地址为2〜3、6〜7可映射到第1组Cache 中。Cache 初始为空，采用LRU 替换算法，当访问主存的10个地址依次为0, 4，8, 2, 0, 6，8, 6, 4, 8时，命中Cache 的次数共有3次，分别发生在第7、8和10步时。
8． 以下说法错误的是（ ）。
（1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n 下，复杂度
的算法在时间上总是优于复杂度
的算法
（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A. （1） B. （1）, （2） C. （1）, （4） D. （3） 【答案】A
【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。
9． 动态存储管理系统中，通常可有（ ）种不同的分配策略。
【答案】C
【解析】动态存储管理系统中有以下三种：首次拟合法、最佳拟合法、最差拟合法。①首次拟合法，从表头指针开始查找可利用空间表，将找到的第一个大小不小于n 的空闲块的一部分分配给用户。②最佳拟合法，将可利用空间表中一个不小于n 且最接近n 的空闲块的一部分分配给