2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研仿真模拟五套题
● 摘要
一、单项选择题
1． 站点A 、B 、C 通过CDMA 共享链路, A 、B 、C 的码片序列(chippingsequence)分别是(1, 1, 1, 1) 、(1, -1, 1, -1) 和(1, 1, -1, -1) , 若C 从链路上收到的序列是(2, 0, 2, 0, 0, -2, 0, -2, 0, 2, 0, 2) , 则C 收到A 发送的数据是（ ）
A.000
B.101
C.110
D.111
【答案】B
【解析】用A 的码片与信息做内积运算
2． 对于栈操作数据的原则是（ ）
A. 先进先出
B. 后进先出
C. 后进后出
D. 不分顺序
【答案】B
【解析】先进先出是队列操作数据的原则。先进后出是栈操作数据的原则，栈限定在表尾进行插入和删除。
3． 下列给出的指令系统特点中, 有利于实现指令流水线的是（ ）。
Ⅰ. 指令格式规整且长度一致
Ⅱ. 指令和数据按边界对齐存放
Ⅲ. 只有Load/Store指令才能对操作数进行存储访问
A. 仅Ⅰ、Ⅱ
B. 仅Ⅱ、Ⅲ
C. 仅Ⅰ、Ⅲ
D. Ⅰ、Ⅱ、Ⅲ
【答案】D
【解析】特点Ⅰ和Ⅲ都是RISC 机的特征, 而特点Ⅱ则有利于指令和数据的存放, 所以以上三个特点都有利于实现指令流水线。
4． 某同步总线采用数据线和地址线复用方式。其中地址数据线有8根, 总线时钟频率为66MHZ , 每个时钟同期传送两次数据。(上升沿和下降沿各传送一次数据) 该总线的最大数据传输率是(总线带宽) :（ ）
A.132MB/S
B.264MB/S
C.528MB/S
D.1056MB/S
【答案】C
【解析】总线带宽=总线工作频率X(总线宽度/8), 由于地址线与数据线复用, 所以在两次数据
, 所以选C 传输过程中总线上数据一共传输了8次, 那么总线带宽为
5． 进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下:
则并发执行进程P0和PI 时产生的情况是（ ）.
A. 不能保证进程互斥进入临界区，会出现“饥饿”现象
B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象
C. 能保证进程互斥进入临界区，会出现“饥饿”现象
D. 能保证进程互斥进入临界区，不会出现“饥饿”现象
【答案】D
【解析】这是皮特森算法(Peterson’SAlgorithm)的实现，保证进入临界区的进程合理安全. 该算法为了防止两个进程为进入临界区而无限期等待，设置变量tum ，表示不允许进入临界区的编号，每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区. 保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入. 先到先人，后到等待，从而完成临界区访问的要求.
6． 若对如下无向图进行遍历, 则下列选项中, 不是广度优先遍历序列的是（ ）
A.h , c , a , b , d , e , g , f
B.e , a , f , g , b , h , c , d
C.d , b , c , a , h , e , f , g
D.a , b , c , d , h , e , f , g
【答案】D
【解析】根据广度优先遍历的定义, 可知选项A 、B 、C 都为广度优先遍历, 而选项D 是深度优先遍历而不是广度优先遍历, 故答案为D 。
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． 在OSI 参考模型中, 直接为会话层提供服务的是（ ）
A. 应用层
B. 表示层
C. 传输层
D. 网络层
【答案】C
【解析】OSI 参考模型中, 下层直接为上层提供服务, 而会话层的下层为传输层。
9． 图G 是n 个顶点的无向完全图，则下列说法不正确的是（ ）
A.G 的邻接多重表需要n(n－1) 个边结点和n 个顶点结点
B.G 的连通分量个数最少