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

一、填空题

1． 假定查找有序表

【答案】

表

平均查找次数为。

2． 分别采用堆排序，快速排序，起泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是_____算法。

【答案】起泡；快速

【解析】当初态为有序表时，冒泡排序只需要进行一趟比较即可，此时时间复杂度为O(n)，

2

而快速排序算 法需要比较的次数达到最大，时间复杂度为O (n) 。

3． 设数组数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开

中每个元素的概率相等，则进行折半查找时的平均查找长度为_____。

【解析】折半查找时每个的次数如表所示:

始连续存放在主内存里，主内存字长为16位，那么

(1)存放该数组至少需要的单元数是_____；

(2)存放数组的第8列的所有元素至少需要的单元数_____； (3)数组按列存储时，元素A[5，8]的起始地址是_____。 【答案】270；27；2204

【解析】数组的元素个数为9*10＝90，因为每个元素占内存48个二进制位，即6个字节。故总需要90*6＝540个字节，因为主内存字长为16位，即2个字节，所以至少需要540/2＝270个单元数。第8列有9个元素，共占9*6＝54个字节，因此至少需要54/2＝27个单元数。由题知，每个元素占3个单元。按列存储时，A[5，8]的起始地址为2000＋[(8﹣1)*9＋(5﹣0)]*3＝2204。

4． 对于双向链表，在两个结点之间插入一个新结点需修改的指针共_____个，单链表为_____个。

【答案】4；2

5． 对n 个记录的表

【答案】n (n－1) /2

第 2 页，共 49 页

进行简单选择排序，所需进行的关键字间的比较次数为_____。

【解析】第一次需要n －1次比较，第i 此需要n －i 此比较，所以共需要

。

二、单项选择题

6． 采用开址定址法解决冲突的哈希查找中，发生集聚的原因主要是（ ）。

A. 数据元素过多 B. 负载因子过大 C. 哈希函数选择不当 D. 解决冲突的算法选择不好 【答案】D

【解析】开放定址法就是从发生冲突的那个单元开始，按照一定的次序，从散列表中查找出一个空闲的存储单元，把发生冲突的待插入元素存入到该单元中的一类处理冲突的方法。

7． 某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为字节，页表项大小为2字节，逻辑地址结构为:

逻辑地址空间大小为（ ）.

A.64 B.128 C.256 D.512

【答案】B

【解析】地址空间分为逻辑地址空间和物理地址空间. 页的大小为采用二级页表，

一页可存放

个页面来保存页表项，故本题答案为B.

8． 对序列{15，9，7，8，20，-1，4，}用希尔排序方法排序，经一趟后序列变为{15，-1，4，8，20，9，7}则该次釆用的增量是（ ）。

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

【答案】B

【解析】由所给的序列知，本序列要进行递增排序，经过一趟后15的位置没有变化，而给的序列中只有20比15大，20的位置和15的位置相差4。所以该次采用的增量是4。

9． 若x=103, y=-25测下列表达式采用8位定点补码运算实现时, 会发生溢出的是（ ）

A.x+y B.-x+y

第 3 页，共 49 页

页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少是

字节，页表项大小为2B ，

字节，

故最少需要

个页表项，本题中逻辑地址空间大小为

C.x-y D.-x-y

【答案】C

答:8位定点补码能表示的数的范围为:-128~127

A 结果为78, B 结果为-128, D结果为-78都在此范围内, 只有C 结果128超过了8位定点补码能表示的数的范围, 会发生溢出

10．下列寄存器中, 汇编语言程序员可见的是（ ）。

A. 存储器地址寄存器(MAR) B. 程序计数器(PC)

C. 存储器数据寄存器(MDR) D. 指令寄存器(IR) 【答案】B

【解析】CPU 有5个专用寄存器, 它们是程序计数器(PC)、指令寄存器(IR)、存储器地址寄存器(MAR)、存储器数据寄存器(MBR)和状态标志寄存器(PSWR), 这些寄存器中有些是CPU 的内部工作寄存器, 对汇编语言程序员来说是透明的, 在汇编语言程序设计中不会出现。但汇编语言程序员可以通过制定待执行指令的地址来设置PC 的值, 所以程序计数器(PC)对于汇编语言程序员可见的。

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

A. B. C. D. 【答案】A

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

句

, 设其执行时间为

, 则有

即

,

G 的拓扑序列是（ ）。 A. B. C. D.

【答案】A

能被称为。

12．已知有向图G=(V，E) , 其中

【解析】设G=(V，E) 是一个具有n 个顶点的有向图，V 中顶点序列

第 4 页，共 49 页