当前位置:问答库>考研试题

2017年哈尔滨师范大学计算机科学与信息工程学院922程序设计与数据结构[专业硕士]考研冲刺密押题

  摘要

一、选择题

1. 对有2个顶点e 条边且使用邻接表存储的有向图进行广度优先遍历,其算法时间复杂度是( )。 A. B. C. D.

【答案】C 。

【解析】遍历图的过程实质上是对每个顶点查找其邻接点的过程。其耗费的时间则取决于所采用的存储结构。当用二维数组表示邻接矩阵图的存储结构时,查找每个顶点的邻接点所需时间

为其中n 为图中顶点数。而当以邻接表作图的存储结构时,找邻接点所需时间为其中e 为无向图中边的数或有向图中弧的数。由此,当以邻接表作存储结构时,深度优先搜索遍历图的时间复杂度为即可得出正确答案。

2. 下列选项中,不属于网络体系结构中所描述的内容是( )。

A. 网络的层次

B. 每一层使用的协议

C. 协议的内部实现细节

D. 每一层必须完成的功能

【答案】C

【解析】体系结构仅规定协议的功能和消息格式,但对具体的实现细节由具体设备厂商来确定,对于网络的层次,以及每一个层次的协议及其功能都是网络体系结构所要描述的内容,因此答案为选项C 。

3. 设栈S 和队列Q 的初始状态为空,元素

后即进队列Q ,若6个元素出队的序列是

A.6

B.4

C.3

D.2

第 2 页,共 51 页 依次通过栈S ,一个元素出栈 则栈S 的容量至少应该是( )。

【答案】C

4. 元素a , b , c , d , e 依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素d 开头的序列个数是( )。

A.3

B.4

C.5

D.6

【答案】B

【解析】d 首先出栈后的状态如下图所示。

此时可有以下4种操作:

(1)e 进找后出栈,出梭序列为decba 。

(2)c 出找,e 进找后出栈,出找序列为dceba 。

(3)cb 出找,e 进找后出栈,出找序列为dcbea 。

(4)cba 出找,e 进找后出找,出找序列为dcbae 。

5. 假设某系统总线在一个总线周期中并行传输4字节信息,一个总线周期占用2个时钟周期,总线时钟频率为10MHz , 则总线带宽是( )。

A.lOMB/s

B.20MB/S

C.40MB/S

D.80MB/S

【答案】B

【解析】因为一个总线周期占用2个时钟周期,完成一个32位数据的传送。总线时钟频率为10MHz , 时钟周期为0.1押,总线周期占用2个时钟周期,为0.2两。一个总线周期中并行传输4

=20MB/s。 字节信息, 则总线带宽是4B ÷

6. 假定有k 个关键字互为同义词,若用线性探测法把这k 个关键字存入哈希表中,至少要进行多少次探测?( )

【答案】D

【解析】至少探测次数

7. 栈和队的共同点是( )。

A. 都是先进后出

第 3 页,共 51 页

B. 都是后进先出

C. 只允许在端点处插入和删除元素

D. 没有共同点

【答案】C

【解析】栈和队列的区别是栈是先进后出的数据结构,队列是先进先出的数据结构,栈和队列的共同点是都只能在端点处插入和删除元素。

8.

协议对

A.011111000011111010

B.011111000111110101111110

C.01111100011111010

D.011111000111111001111101

【答案】A 组帧后对应的比特串为( )

HDLC 协议对比特串进行组帧时,HDLC 数据帧以位模式0111 1110标识每一个帧的【解析】

开始和结束,因此在帧数据中凡是出现了 5个连续的位“1”的时候,就会在输出的位流中填充一个“0”。所以答案为A 。

9. 下列关于进程和线程的叙述中,正确的是( )。

A. 不管系统是否支持线程,进程都是资源分配的基本单位

B. 线程是资源分配的基本单位,进程是调度的基本单位

C. 系统级线程和用户级线程的切换都需要内核的支持

D. 同一进程中的各个线程拥有各自不同的地址空间

【答案】A 。

“线程是资源分配的基本单位,【解析】利用排除法来确定正确答案:进程是调度的基本单位”

这句话说反了,明显错误。“系统级线程和用户级线程的切换都需要内核的支持”也不正确,因为用户级线程的切换由用户编写的RuntimeSystem 执行的,内核并不感知。“同一进程中的各个线程拥有各自不同的地址空间”明显错误,引入线程的目的就是为了同一进程的所有线程能共享进程的地址空间,故“不管系统是否支持线程,进程都是资源分配的基本单位”是正确的。

10.串的长度是指( )。

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

B. 串中所含字符的个数

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

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

【答案】B

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

第 4 页,共 51 页