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

一、单项选择题

1． 设有向图G=(V, E) , 顶点集

边集,

,

若从顶点V0开始对图进行深度优先遍历, 则可能得到的不同遍历序列个数是（ ）。

A.2

B.3

C.4

D.5

【答案】D

【解析】根据题意知有向图的结构如图所示。深度优先遍历的特点是尽可能先对纵深方向进行搜索, 所以可能得到的不同遍历序列分别是: ①

④

' ; ②; ⑤; ③。

2． 冯•诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依据是（ ）.

A. 指令操作码的译码结果

B. 指令和数据的寻址方式

C. 指令周期的不同阶段

D. 指令和数据所在的存储单元

【答案】C

【解析】在冯•诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU 可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段(分析取数阶段、执行阶段) 取出的是数据. 所以，CPU 区分指令和数据的依据是指令周期的不同阶段.

3． 设n 是描述问题规模的非负整数, 下面程序片段的时间复杂度是（ ）。

第 2 页，共 61 页 ;

A. B. C. D.

【答案】A

【解析】其中, 以基本的原操作重复执行的次数作为算法的时间度量。题目中的基本运算是语

句, 设其执行时间为, 则有即。

4． 以下说法错误的是（ ）。

(1)算法原地工作的含义是指不需要任何额外的辅助空间

(2)在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2n ) 的算法

(3)所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

(4)同一个算法，实现语言的级别越高，执行效率就越低

A.(1)

B.(1), (2)

C.(1), (4)

D.(3)

【答案】A

【解析】算法原地工作的含义不是指不需要任何额外的辅助，而是算法所需要的辅助空间不随着问题的规模而变化，是一个确定的值。

5． 图中有关路径的定义正确的是（ ）。

A. 由顶点和相邻顶点构成的边所形成的序列

B. 由不同顶点所形成的序列

C. 由不同边所形成的序列

D. 上述定义都不是

【答案】A

【解析】顶点到顶点之间的一条路径是指顶点序列。路径上边的数目称为路径的长度。

6． 在文件的索引节点中存放直接索引指针10个, 一级二级索引指针各1个, 磁盘块大小为1KB 。每个索引指针占4个字节。若某个文件的索引节点已在内存中, 到把该文件的偏移量(按字节编址) 为1234和307400处所在的磁盘块读入内存。需访问的磁盘块个数分别是（ ）。

A.1, 2

B.1, 3

C.2, 3

D.2, 4

【答案】B

【解析】文件的索引结点的直接索引指针有10个, 因此直接索引的偏移量范围是0〜2559, 一

第 3 页，共 61 页

级索引的偏移量范围是2560〜65791, 二级索引访问的偏移量范围是65792〜45183907。偏移量1234可以通过直接索引得到在磁盘块的地址, 因此需要一次访问, 307400需要通过二级索引查找其在磁盘的位置, 需要分别访问存放二级索引的两个索引块以及对应的数据块。

7． 对一组数据(2, 12, 16, 88, 5, 10) 进行排序, 若前三趟排序结果如下:

第一趟:2, 12, 16, 5, 10, 88

第二趟:2, 12, 5, 10, 16, 88

第三趟:2, 5, 10, 12, 16, 88

则采用的排序方法可能是（ ）。

A. 起泡排序

B. 希尔排序

C. 归并排序

D. 基数排序

【答案】A

【解析】题目中所给的三趟排序过程, 显然是使用起泡排序方法, 每趟排序时从前往后依次比较, 使大值“沉底”。希尔排序的基本思想是:先对序列进行“宏观调整”, 待序列中的记录“基本有序”时再进行直接插入排序。宏观调整的方法是:通过某种规则将大的待排序序列分割为若干小的待排序序列, 再依次对这些小的序列直接插入排序。宏观调整可以多次, 每次分割的序列数逐渐增多, 而每个序列中所包含的元素数逐渐减少。归并排序的基本操作是将多个小的有序序列合并为一个大的有序序列, 然后“逐趙归并”, 直至整个序列为有序为止。基数排序是分配排序的一种, 这类排序不是通过关键字比较, 而是通过“分配”和“收集”过程来实现排序的。本题中, 很容易看出大值逐渐“沉底”, 显然使用的是起泡排序法。

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

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

【答案】D 。

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

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

第 4 页，共 61 页 中的内容为11H 。由于数据按