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

2017年中北大学计算机与控制工程学院821数据结构与算法考研强化模拟题

  摘要

一、选择题

1. 某计算机系统中有8台打印机,由K 个进程竞争使用,每个进程最多需要3台打印机。该系统可能会发生死锁的K 最小值是( )。

A.2 B.3 C.4 D.5

【答案】C

【解析】死锁的抽屉原理一般描述是:将5个苹果放进4个抽屉,那么,必然有1个抽屉中至少有2个苹果。计算机系统的资源分配充分体现了这一原理。考察进程运行的特点,只要有一个进程能够运行,则运行结束后必然会归还资源,其余的进程也就会得到满足从而可以执行(这里考虑的资源主要是可重用的资源,不可重用的资源会消失,就不可用上述方法分析)。所以最少需要4个进程竞争使用,每个进程占用2台打印机,此时会产生死锁。

2. 循环队列存储在数组中,则入队时的操作为( )。

A.

B.

C.

D. 【答案】D

3. 设被排序的结点序列共有N 个结点,在该序列中的结点已十分接近排序的情况下,用直接插入法、归并法和一般的快速排序法对其排序,这些算法的时间复杂性应为( )。

【答案】C

【解析】因为该序列中的结点已经十分接近排序的情况,对于直接插入法,大部分结点只需要直接插入后面即可,因此时间复杂度为的时间复杂度为

对于采用归并法,它是一种稳定的排序方法,它

对于一般的快速排序法,序列越接近有序,所需要的比较次数越多,

此时的时间复杂度为

4. 某计算机存储器按字节编址,采用小端方式存放数据。假定编译器规定int 和short 型长度分别为32位和16位,并且数据按边界对齐存储。某C 语言程序段如下:

若record

变量的首地址为A.

B.

C.

D. 【答案】D 。

则地址

中内容及record.c 的地址分别为( )。

【解析】32位整数a 需要占4个字节,16位整数c 需要占2个字节,而字符数据b 占一个字节。a=273, 转换成十六进制是111H , 采用小端方式存放数据,地址0xC008中的内容为11H 。由于数据按边界对齐存储,地址

地址

中存放c 。

中,且队列非空时front 和rear 分别指向队头元素和

5. 已知循环队列存储在一维数组rear 的值分别是( )。

A.0, 0 B.0, n-1 C.n-1, 0 D.n-1, n-1

【答案】B

【解析】题目要求队列非空时front 和rear 分别指向队头元素和队尾元素,若初始时队列为空,且要求第1 个进入队列的元素存储在A[0]处,则此时front 和rear 的值都为0。由于进队操作要执行(rear+1) % n,则初始 时front 的值为0、rear 的值为n-1。

6. 从堆中删除一个元素的时间复杂度为( )。

【答案】B

【解析】堆中删除一个元素,需要重新调整堆,其时间复杂度为

7. 已知串其Next 数组值为( )。

A.0123 B.1123 C.1231 D.1211 【答案】A

【解析】KMP 算法的next 数组建立的原则

中存放a , 地址

中存放b , 地址

中空闲,

队尾元素。若初始时队列为空,且要求第1个进入队列的元素存储在A[0]处,则初始时front 和

8. 对任意一棵树,设它有n 个结点,这n 个结点的度数之和为( )。

A.n

B.

C.

D. 【答案】C

【解析】每个结点(除根节点外)都是一个分支,即所有结点的度数之和等于分支个数等于总的结点数减一,即n-1。

9. 计算机开后,操作系统最终被加载到( )

A.BIOS B.ROM C.EPROM D.RAM 【答案】D

【解析】系统开机后, 操作系统的程序会被自动加载到内存中的系统区,这段区城是RAM ,故答案选D 。

10.在下列表述中,正确的是( )

A. 含有一个或多个空格字符的串称为空格串 B.

个顶点的网,求出权最小的

条边便可构成其最小生成树

C. 选择排序算法是不稳定的

D. 平衡二叉树的左右子树的结点数之差的绝对值不超过1 【答案】C

【解析】平衡二叉树的左右子树的深度之差的绝对值不超过1。求最小生成树时,每次挑最小权值边,是要求该边的两点都在不同的连通分量上的。

11.某机器有一个标志寄存器,其中有进位/借位标志CF 、零标志ZF 、符号标志SF 和溢出标志OF ,条件转移指令bgt (无符号整数比较大于时转移)的转移条件是( )。

A.CF+OF=0 B.SF+ZF=0 C.CF+ZF=0 D.CF+SF=0 【答案】C

【解析】判断无符号整数A>B成立,满足的条件是结果不等于0, 即零标志ZF=0, 且不发生进位,即进位/借位标志CF=0。所以正确选项为C 。其余选项中用到了符号标志SF 和溢出标志OF , 显然可以排除掉。

12.希尔排序的组内排序采用的是( )。

A. 直接插入排序 B. 折半插入排序