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

一、单项选择题

1． 下列选项中, 属于多级页表优点的是（ ）

A. 加快地址变换速度

B. 减少缺页中断次数

C. 减少页表项所占字节数

D. 减少页表所占的连续内存空间

【答案】D

【解析】多级页表避免了把所有的页表一直保存在内存中

2． 稀疏矩阵一般的压缩存储方法有两种，即（ ）。

A. 二维数组和三维数组

B. 三元组和散列

C. 三元组和十字链表

D. 散列和十字链表

【答案】C

【解析】稀疏矩阵一般的压缩方法为三元组表和十字链表。三元组表就是将非零元素及其对应的行和列构成一个三元组(行标，列标，值) 。十字链表相比三元组表而言，主要是对每个结点增加了两个链域。如果数组经常运算时，会产生大量数据元素的移动，此时，采用链表存储结构更为恰当。

3． 先序序列为a , b , c , d 的不同二叉树的个数是（ ）。

A.13

B.14

C.15

D.16

【答案】B

【解析】二叉树的先序遍历定义为:若二叉树为空, 则空操作; 否则, 访问根节点, 然后先序遍历左子树, 最后先序遍历右子树。本题中, 结点a 为二叉树的根节点, 左右子树的先序遍历可能存在下面四种情况:

①左子树为空, bcd 为右子树; ②b 为左子树, cd 为右子树; ③bc 为左子树, d 为右子树; ④bcd 为左子树, 右子树为空。

然后将左右子树继续分解, 如第①种情况的右子树先序遍历(bcd)可能有:

A. 左子树为空, 右子树为cd ;

b. 左子树为c , 右子树为d ;

c. 左子树为cd , 右子树为空。

按照这种方法继续分解左右子树, 直到不能再分解为止, 可得第①和④种情况各包含5种不同情况, 第②和③种情况各包含2种情况, 因此总共有14种不同的二叉树。

4． 设被排序的结点序列共有N 个结点，在该序列中的结点已十分接近排序的情况下，用直接插入法、归并法和一般的快速排序法对其排序，这些算法的时间复杂性应为（ ）。 A. B. | C. D.

【答案】C

【解析】因为该序列中的结点己经十分接近排序的情况，对于直接插入法，大部分结点只需要直接插入后面即可，因此时间复杂度为O(N)。对于采用归并法，它是一种稳定的排序方法，它的时间复杂度为。对于一般的快速排序法，序列越接近有序，所需要的比较次数越多，此时的时间复杂度为。

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

若record 变量的首地址为0xC008, 则地址中内容及的地址分别为（ ）。 A. B. C. D.

【答案】D 。

32位整数a 需要占4个字节, 16位整数c 需要占2个字节, 而字符数据b 占一个字节。【解析】

a=273, 转换成十六进制是111H , 采用小端方式存放数据, 地址

边界对齐存储,

地址

中存放c 。

6． 由3个“1”和5个“0”组成的8位二进制补码, 能表示的最小整数是（ ）。

A.-126

B.-125

C.-32

D.-3

中的内容为11H 。由于数据按中存放b ,

地址中空闲,

地址中存放a ,

地址

【答案】B

【解析】能表示的最小整数一定是负数, 符号位占用1个“1”; 负数的补码和原码的转化是:原码符号位不变, 数值部分按位取反, 末位加“1”。

因此最小的整数的补码是“10000011”, 原码为“111111101”, 即。

7． 设有两个串S1和S2，求S2在S1中首次出现的位置的运算称作（ ）。

A. 求子串

B. 判断是否相等

C. 模型匹配

D. 连接

【答案】C

【解析】常用的串的基本操作有七种，INDEX(s，t) 是其中的定位函数，这种运算就是所说的模式匹配。

8． 排序算法的稳定性是指（ ）。

A. 经过排序之后，能使值相同的数据保持原顺序中的相对位置不变

B. 经过排序之后，能使值相同的数据保持原顺序中的绝对位置不变

C. 算法的排序性能与被排序元素的数量关系不大

D. 算法的排序性能与被排序元素的数量关系密切

【答案】A

【解析】假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=tj，且ri 在ij 之前，而在排序后的序列中，ri 仍在rj 之前，则称这种排序算法是稳定的；否则称为不稳定的。

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

Ⅰ. 提高CPU 时钟频率

Ⅱ. 优化数据通路结构

Ⅲ. 对程序进行编译优化

A. 仅Ⅰ和Ⅱ

b. 仅Ⅰ和Ⅲ

c. 仅Ⅱ和Ⅲ

d. Ⅰ、Ⅱ和Ⅲ

【答案】D

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