2009-2010计算机考研真题及答案（含选择题解析）WORD高清晰版(4)

直接插入排序基本思想:

将一个记录插入到已排序的有序表中，使插入后的表仍然有序。

折半插入排序基本思想：

将一个记录插入到已排序的有序表中，使插入后的表仍然有序，但插入时利用折半搜索法寻找元素的插入位置。

归并排序基本思想：

又一类不同的排序方法，将两个或两个以上的有序表合并成一个新的有序表。

快速排序基本思想：

取R[1..n]中任一记录作为“枢轴”，一趟排序之后枢轴的值均小于“枢轴”左边的值，枢轴右边的值均大于“枢轴”的值。

堆排序基本思想：

1.如何将一个无序序列调整为堆？

2.如何在互换堆顶之后重新调整为堆（关键）？ 希尔排序 (Shell Sort) 基本思想：

1.n大，划分成若干子序列，分别直接插入排序。 2.待整个记录“基本有序”时，对整体直接重排。

11.冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是指令周期的不同阶段。

12.十进制转换：

十进制转任意进制的通用方法是：除x取余倒排法（x代表进制数）。 如：将十进制数76转换成任意进制

11

1.转成二进制 76 / 2 ... 0 = 38 / 2 ... 0 = 19 / 2 ... 1 = 9 / 2 ... 1 = 4 / 2 ... 0 = 2 / 2 ... 0 = 1 / 2 ... 1

76(10) = 1001100(2)

2.转成八进制 76 / 8 ... 4 = 9 / 8 ... 1 = 1 / 8 ... 1 76(10) = 114(8)

3.转成十六进制 76 / 16 ... 12 = 4 / 16 ... 4 76(10)=4C(16) B ：二进制数。 Q ：八进制数。 D ：十进制数。 H ：十六进制数。

负数用十六进制和八进制怎么表示？

使用补码（二进制），而且还要指定字长

比如说一个二字节整型的 -2 就应该是： 11111111 11111110 再转化其它进制

12

十六进制：FFFE 八进制：177776

13.浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）。若有两个数X=2^7*29/32，Y=2^5*5/8,则用浮点加法计算X+Y的最终结果是发生溢出

浮点数表示：小数点的位置可以在一定范围内浮动。

E为阶，包括阶符和阶码（整数），阶码为数决定了浮点数的表示范围。 M为位数，包括数符和尾数，表示数的精度和正负。 对阶原则：小阶对大阶。

双符号位判溢：加，减后。两个符号位出现“01”，表示已经溢出，即结果大于+1.

14.存储器的分类：

1.按存储介子分:(1)半导体存储器;(2)磁表面存储器;(3)光介子存储器。

2.按存取方式分类:(1)随机存取存储器 RAM；(2)顺序存储器 SAM；(3)直接存取存储器 DAM。 3.按计算机功能分类: (1)主存储器（主存）

用于存放计算机运行期间的大量程序和数据的存储器，CPU能直接访问。由MOS存储器构成。

(2)高速缓冲存储器（Cache）

Cache是介于CPU和主存之间高速小容量存储器，用于存放最活跃的程序块和数据。由静态MOS存储器构成。

特点：速度快，但容量小，位价格较高。

主存和Cache一起构成计算机的内存储器（内存），是CPU能直接访问的存储器。

13

(3)辅助存储器（外存储器）

存放当前暂不参与运行的程序和数据，需要时再与主存成批交换信息的存储器。

特点是容量大，可存放大量的程序和数据，但速度慢。

(4)控制存储器（CM）

在微程序控制的计算机中，用于存放执行指令的微程序的存储器。

CM一般由ROM构成，属于控制器的一部分。 4.其它分类： a.按读写功能分类：

(1)只读存储器(ROM):工作时只能读出不能写入的存储器。 (2)读写存储器(RAM):既能读出又能写入的存储器。 b.按信息的可保存性分类

(1)永久性存储器：指断电后仍能保存信息的存储器，如磁表面存储器。 (2)非永久性存储器:指断电后信息即消失的存储器，如半导体读写存储器。

某计算机的Cache共有16块，采用2路组相连映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到Cache组号是(4)

15.主存容量是根据地址线的位数来确定的,在16位PC机中地址总线的宽度是20位,则主存大小为:2^20 byte=1MB,现在的PC机一般都是32位地址总线的,最大直接寻址空间为:2^32,即主存最大容量为4GB 某计算机主存容量为64KB，其中ROM区为4KB，其余为RAM区，按字节编址。现要用2K*8位的ROM芯片和4K*4位的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和RAM芯片数分别是2 30 …… 此处隐藏：232字，全部文档内容请下载后查看。喜欢就下载吧 ……