当前位置：问答库＞考研试题

一、单项选择题

1． 对同一待排序列分别进行折半插入排序和直接插入排序, 两者之间可能的不同之处是 （ ）。

A. 排序的总趟数

B. 元素的移动次数

C. 使用辅助空间的数量

D. 元素之间的比较次数

【答案】D 。

【解析】折半插入排序所需附加存储空间和直接插入排序相同, 从时间上比较, 折半插入排序仅减少了关键字间的比较次数, 而记录的移动次数不变。折半插入排序的时间复杂度仍为, 所以两者之间的不同只可能是元素之间的比较次数。

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

A.2

B.3

C.4

D.5

【答案】C

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

3． 希尔排序的组内排序采用的是（ ）。

A. 直接插入排序

B. 折半插入排序

C. 快速排序

D. 归并排序

【答案】A

【解析】希尔排序基本思想是:先将整个待排元素序列按某个增量分割成若干个子序列, 在子

序列内进行直接插入排序, 然后依次缩减增量再进行排序, 待整个序列中的元素基本有序(增量足够小) 时, 再对全体元素进行一次直接插入排序。

4． 对任意一棵树，设它有n 个结点，这n 个结点的度数之和为（ ）。

A.n

B.n ﹣2

C.n ﹣1

D.n ＋1

【答案】c

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

5． 已知串其Next 数组值为（ ）。

A.0123

B.1123

C.1231

D.1211

【答案】A

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

接口) 之间互连的接口标准是（ ） 6． 下列选项中, 用于设备和控制器(

A.PCI

B.USB

C.AGP D.

【答案】B

【解析】设备和设备控制器之间的接口是USB 接口, 其余选项不符合, 故答案为B 。

7． —个进程的读磁区操作完成后, 操作系统针对该进程必做的是（ ）

A. 修改进程状态为就绪态

B. 降低进程优先级

C. 进程分配用户内存空间

D. 增加进程的时间片大小

【答案】A

【解析】进程等待的

操作完成便会从等待状态转移到就绪状态。

8． 对矩阵压缩存储是为了（ ）。

A. 方便运算

B. 方便存储

C. 提高运算速度

D. 减少存储空间

【答案】D

【解析】压缩存储也就是对那些没用的元素不进行存储或者对那些具有一定规律的相同元素放在一个存储空间，目的就是为了节省空间。

9． 当字符序列 作为图输入时，输出长度为3的且可用作C 语言标识符的序列的有（ ）。

A.4个

B.5个

C.3个

D.6个

图

【答案】C

【解析】首先需要明白C 语言标识符的命名规则。数字不能作为标识符的开头，因此第一个字符只能为t 或者下划线。若首字符为t ，有两种结果

和，若首字符为，

则只有一种结果

因此总共有3种结果。

10．若下图为10BaseT 网卡接收到的信号波形, 则该比特串是（ ）

A.00110110

B.10101101

C.01010010

D.11000101

【答案】A

【解析】以太网采用曼彻斯特编码, 其将一个码元分成两个相等的间隔, 前一个间隔为高电平而后一个间隔为低电平表示1, 反之则表示0。故根据波形图, 可得答案为A 。

11．对n 个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确的是（ ）。

A. 每次分区后，先处理较短的部分