2022年重庆大学计算机学院917计算机学科专业基础综合之数据结构

专注考研专业课13年，提供海量考研优质文档！

第 1 页，共 66 页

目录

2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研基础五套测试题（一）

................................................................................................................................................ 2 2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研基础五套测试题（二）

.............................................................................................................................................. 15 2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研基础五套测试题（三）

.............................................................................................................................................. 28 2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研基础五套测试题（四）

.............................................................................................................................................. 42 2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研基础五套测试题（五）

(54)

专注考研专业课13年，提供海量考研优质文档！ 第 2 页，共 66 页 2018年重庆大学计算机学院917计算机学科专业基础综合之数据结构考研基础五套

测试题（一）

说明：根据本校该考试科目历年考研命题规律，结合出题侧重点和难度，精心整理编写。基础检测使用。共五套试题，均含有详细答案解析，也是众多专业课辅导机构参考借鉴资料，考研必备。 ——————————————————————————————————————————

一、单项选择题

1． 下列选项中,能缩短程序执行时间的措施是（ ）。

Ⅰ.提高CPU 时钟频率

Ⅱ.优化数据通路结构

Ⅲ.对程序进行编译优化

A.仅Ⅰ和Ⅱ

b.仅Ⅰ和Ⅲ

c.仅Ⅱ和Ⅲ

d.Ⅰ、Ⅱ和Ⅲ

【答案】D

【解析】一般说来,CPU 时钟频率(主频)越高,CPU 的速度就越快;优化数据通路结构,可以有效提高计算机系统的吞吐量;编译优化可得到更优的指令序列。所以Ⅰ、Ⅱ、Ⅲ都是有效措施。

2． 设无向图的顶点个数为m 则该图最多有（ ）条边。

A.n-1

B.

C.

D.0E.n2

【答案】B

【解析】在数据结构中仅讨论简单图，在计算无向图的最多边时，不考虑顶点与顶点的边。因此边数最多时，构成的是无向完全图。此时的边数为

。

3． 下列选项中,在用户态执行的是（ ）。

A.命令解释程序

B.缺页处理程序

C.进程调度程序

D.时钟中断处理程序

【答案】A

【解析】题目是问用户态执行,可见是有关操作系统基本概念的问题。四个选项中,用户唯一能面对的是命令解释程序,缺页处理程序和时钟中断都属于中断,在核心态执行,而进城调度属于系统调用在核心态执行。只有命令解释程序属于命令接口,可以运行在用户态,接受用户的命令操

专注考研专业课13年，提供海量考研优质文档！ 第 3 页，共 66 页 作控制。

4． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为

字节，页表项大小为

2字节，逻辑地址结构为:

逻辑地址空间大小为

页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是

（ ）.

A.64

B.128

C.256

D.512

【答案】B

【解析】地址空间分为逻辑地址空间和物理地址空间.页的大小为

字节，页表项大小为2B ，采用二级页表，

一页可存放

个页表项，本题中逻辑地址空间大小为字节，

故最少需要个页面来保存页表项，故本题答案为B.

5． 进程P0和P1的共享变量定义及若进程P0和P1访问临界资源的类C 伪代码实现如下:

则并发执行进程P0和PI 时产生的情况是（ ）.

A.不能保证进程互斥进入临界区，会出现“饥饿”现象

B.不能保证进程互斥进入临界区，不会出现“饥饿”现象

C.能保证进程互斥进入临界区，会出现“饥饿”现象

D.能保证进程互斥进入临界区，不会出现“饥饿”现象

【答案】D

【解析】这是皮特森算法(Peterson’SAlgorithm)的实现，保证进入临界区的进程合理安全.该算法为了防止两个进程为进入临界区而无限期等待，设置变量tum ，表示不允许进入临界区的编号，

专注考研专业课13年，提供海量考研优质文档！ 第 4 页，共 66 页 每个进程在先设置自己标志后再设置turn 标志，不允许另一个进程进入，这时，再同时检测另一个进程状态标志和不允许进入标志，这样可以保证当两个进程同时要求进入临界区时只允许一个进程进入临界区.保存的是较晚的一次赋值，则较晚的进程等待，较早的进程进入.先到先人，后到等待，从而完成临界区访问的要求.

6． 串的长度是指（ ）。

A.串中所含不同字母的个数

B.串中所含字符的个数

C.串中所含不同字符的个数

D.串中所含非空格字符的个数

【答案】B

【解析】串中字符的数目n 称为字符的长度，不必考虑其中单个字符是否相等。

7． 假定编译器将赋值语句“x=x+3;”转换为指令”add xaddt ,3”,其中xaddt 是x 对应的存储单元地址,若执行该指令的计算机采用页式虚拟存储管理方式,并配有相应的TLB ,且Cache 使用直写(Write Through)方式,则完成该指令功能需要访问主存的次数至少是（ ）。

A.0

B.1

C.2

D.3

【答案】C

【解析】采用页式虚拟存储管理方式时,若页表全部放在内存中,则存取一个数据最少要访问两次内存:第一次是访问页表,得到所存取的数据或指令的物理地址;第二次根据该地址存取数据或指令。在配有TLB 的页式虚拟管理方式中,如果给出的地址在TLB 中,则直接根据该地址取数据或指令,仅需要一次访问内存。Cache 使用直写方式时,计算完需要将数据写回到内存中,因此完成整个指令功能至少需要访问主存2次。

8． 在系统总线的数据线上,不可能传输的是（ ）。

A.指令

B.操作数

C.握手(应答)信号

D.中断类型号型号

【答案】C

【解析】握手(应答)信号属于通信联络控制信号应该在通信总线上传输,不可能在数据总线上传输。而指令、操作数和中断类型码都可以在数据线上传输。

本文来源：https://www.bwwdw.com/article/qlqq.html