2009年统考计算机考研真题.doc

2009 年统考计算机考研真题年统考计算机考研真题一一 单项选择题，每小题单项选择题，每小题 2 分，共分，共 80 分。分。 1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将 要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻 辑结构应该是辑结构应该是 A.栈栈 B.队列队列 C.树树 D.图图 2.设栈设栈 S 和队列和队列 Q 的初始状态均为空，元素的初始状态均为空，元素 abcdefg 依次进入栈依次进入栈 S。若每个元素出栈后立。若每个元素出栈后立 即进入队列即进入队列 Q，且，且 7 个元素出队的顺序是个元素出队的顺序是 bdcfeag，则栈，则栈 S 的容量至少是的容量至少是A1 B.2 C.3 D.4 3.给定二叉树图所示。设给定二叉树图所示。设 N 代表二叉树的根，代表二叉树的根，L 代表根结点的左子树，代表根结点的左子树，R 代代 表根结点的右子树。若遍历后的结点序列为表根结点的右子树。若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍，则其遍 历方式是历方式是 ALRN B.NRL C.RLN D.RNL 4.下列二叉排序树中，满足平衡二叉树定义的是下列二叉排序树中，满足平衡二叉树定义的是 5.已知一棵完全二叉树的第已知一棵完全二叉树的第 6 层（设根为第层（设根为第 1 层）有层）有 8 个叶结点，则完全二叉树的结点个个叶结点，则完全二叉树的结点个 数最多是数最多是 A39 B.52 C.111 D.119 6.将森林转换为对应的二叉树，若在二叉树中，结点将森林转换为对应的二叉树，若在二叉树中，结点 u 是结点是结点 v 的父结点的父结点，则在的父结点的父结点，则在 原来的森林中，原来的森林中，u 和和 v 可能具有的关系是可能具有的关系是 I父子关系父子关系 II.兄弟关系兄弟关系 III. u 的父结点与的父结点与 v 的父结点是兄弟关系的父结点是兄弟关系 A.只有只有 II B.I 和和 II C.I 和和 III D.I、II 和和 III 7.下列关于无向连通图特性的叙述中，正确的是下列关于无向连通图特性的叙述中，正确的是 I所有顶点的度之和为偶数所有顶点的度之和为偶数 II.边数大于顶点个数减边数大于顶点个数减 1 III.至少有一个顶点的度为至少有一个顶点的度为 1 A.只有只有 I B. 只有只有 II C.I 和和 II D.I 和和 III 8.下列叙述中，不符合下列叙述中，不符合 m 阶阶 B 树定义要求的是树定义要求的是A根节点最多有根节点最多有 m 棵子树棵子树 B.所有叶结点都在同一层上所有叶结点都在同一层上 C各结点内关键字均升序或降序排列各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接叶结点之间通过指针链接 9.已知关键序列已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆）是小根堆（最小堆） ，插入关键字，插入关键字 3，调，调 整后得到的小根堆是整后得到的小根堆是 A3，5，12，8，28，20，15，22，19 B. 3，5，12，19，20，15，22，8，28 C3，8，12，5，20，15，22，28，19 D. 3，12，5，8，28，20，15，22，19 10.若数据元素序列若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二是采用下列排序方法之一得到的第二 趟排序后的结果，则该排序算法只能是趟排序后的结果，则该排序算法只能是 A起泡排序起泡排序 B.插入排序插入排序 C.选择排序选择排序 D.二路归并排序二路归并排序 11.冯冯··诺依曼计算机中指令和数据均以二进制形式存放在存储器中，诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU 区分它们的依区分它们的依 据是据是 A指令操作码的译码结果指令操作码的译码结果 B.指令和数据的寻址方式指令和数据的寻址方式 C.指令周期的不同阶段指令周期的不同阶段 D.指令和数据所在的存储单元指令和数据所在的存储单元 12.一个一个 C 语言程序在一台语言程序在一台 32 位机器上运行。程序中定义了三个变量位机器上运行。程序中定义了三个变量 xyz，其中，其中 x 和和 z 是是 int 型，型，y 为为 short 型。当型。当 x=127，y=-9 时，执行赋值语句时，执行赋值语句 z=x+y 后，后，xyz 的值分别是的值分别是 AX=0000007FH，y=FFF9H，z=00000076H AX=0000007FH，y=FFF9H，z=FFFF0076H AX=0000007FH，y=FFF7H，z=FFFF0076H AX=0000007FH，y=FFF7H，z=00000076H 13.浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点 数的阶码和尾数均采用补码表示，且位数分别为数的阶码和尾数均采用补码表示，且位数分别为 5 位和位和 7 位（均含位（均含 2 位符号位）位符号位） 。若有两个。若有两个 数数 X=27××29/32，Y=25××5/8，则用浮点加法计算，则用浮点加法计算 X+Y 的最终结果是的最终结果是 A00111 1100010 B.00111 0100010 C01000 0010001 D.发生溢出发生溢出 14.某计算机的某计算机的 Cache 共有共有 16 块，采用块，采用 2 路组相联映射方式（即每组路组相联映射方式（即每组 2 块）块） 。每个主存块。每个主存块 大小为大小为 32 字节，按字节编址。主存字节，按字节编址。主存 129 号单元所在主存块应装入到的号单元所在主存块应装入到的 Cache 组号是组号是 A0 B.2 C.4 D.6 15.某计算机主存容量为某计算机主存容量为 64KB，其中，其中 ROM 区为区为 4KB，其余为，其余为 RAM 区，按字节编址。现区，按字节编址。现 要用要用 2K××8 位的位的 ROM 芯片和芯片和 4K××4 位的位的 RAM 芯片来设计该存储器，则需要上述规格的芯片来设计该存储器，则需要上述规格的 ROM 芯片数和芯片数和 RAM 芯片数分别是芯片数分别是 A1、15 B2、15 C1、30 D2、30 16.某机器字长某机器字长 16 位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一 字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节 PC 自动自动 加加 1。若某转移指令所在主存地址为。若某转移指令所在主存地址为 2000H，相对位移量字段的内容为，相对位移量字段的内容为 06H，则该转移指，则该转移指 令成功转以后的目标地址是令成功转以后的目标地址是 A.2006H B.2007H C.2008H D.2009H 17.下列关于下列关于 RISC 的叙述中，错误的是的叙述中，错误的是 ARISC 普遍采用微程序控制器普遍采用微程序控制器 BRISC 大多数指令在一个时钟周期内完成大多数指令在一个时钟周期内完成 CRISC 的内部通用寄存器数量相对的内部通用寄存器数量相对 CISC 多多 DRISC 的指令数、寻址方式和指令格式种类相对的指令数、寻址方式和指令格式种类相对 CISC 少少 18.某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之 间的间的 缓存时间）分别是缓存时间）分别是 90ns、80ns、70ns 和和 60ns，则该计算机的，则该计算机的 CPU 时钟周期至少是时钟周期至少是 A90ns B.80ns C.70ns D.60ns 19.相对于微程序控制器，硬布线控制器的特点是相对于微程序控制器，硬布线控制器的特点是 A指令执行速度慢，指令功能的修改和扩展容易指令执行速度慢，指令功能的修改和扩展容易 B指令执行速度慢，指令功能的修改和扩展难指令执行速度慢，指令功能的修改和扩展难 C指令执行速度快，指令功能的修改和扩展容易指令执行速度快，指令功能的修改和扩展容易 D指令执行速度快，指令功能的修改和扩展难指令执行速度快，指令功能的修改和扩展难 20.假设某系统总线在一个总线周期中并行传输假设某系统总线在一个总线周期中并行传输 4 字节信息，一个总线周期占用字节信息，一个总线周期占用 2 个时钟周个时钟周 期，总线时钟频率为期，总线时钟频率为 10MHz，则总线带宽是，则总线带宽是 A10MB/s B.20MB/S C.40MB/S D.80MB/S 21.假设某计算机的存储系统由假设某计算机的存储系统由 Cache 和主存组成，某程序执行过程中访存和主存组成，某程序执行过程中访存 1000 次，其中次，其中 访问访问 Cache 缺失（未命中）缺失（未命中）50 次，则次，则 Cache 的命中率是的命中率是 A5% B.9.5% C.50% D.95% 22.下列选项中，能引起外部中断的事件是下列选项中，能引起外部中断的事件是 A键盘输入键盘输入 B.除数为除数为 0 C.浮点运算下溢浮点运算下溢 D.访存缺页访存缺页 23.单处理机系统中，可并行的是单处理机系统中，可并行的是 I 进程与进程进程与进程 II 处理机与设备处理机与设备 III 处理机与通道处理机与通道 IV 设备与设设备与设 备备 AI、II 和和 III B. I、II 和和 IV C. I、III 和和 IV D. II、III 和和 IV 24.下列进程调度算法中，综合考虑进程等待时间和执行时间的是下列进程调度算法中，综合考虑进程等待时间和执行时间的是 A时间片轮转调度算法时间片轮转调度算法 B.短进程优先调度算法短进程优先调度算法 C.先来先服务调度算法先来先服务调度算法 D.高响应比优先调度算法高响应比优先调度算法 25.某计算机系统中有某计算机系统中有 8 台打印机，有台打印机，有 K 个进程竞争使用，每个进程个进程竞争使用，每个进程 最多需要最多需要 3 台打印机。该系统可能台打印机。该系统可能会发生死锁的会发生死锁的 K 的最小值的最小值是是（）（） 不死锁需要不死锁需要 2K+10）个单元的缓冲）个单元的缓冲 区。区。P1 每次用每次用 produce（）生成一个正整数并用（）生成一个正整数并用 put（）送入缓冲区某一空单（）送入缓冲区某一空单 元中；元中；P2 每次用每次用 getodd（）从该缓冲区中取出一个奇数并用（）从该缓冲区中取出一个奇数并用 countodd（）统（）统 计奇数个数；计奇数个数；P3 每次用每次用 geteven（）从该缓冲区中取出一个偶数并用（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活 动，并说明所定义的信号量的含义。要求用伪代码描述。动，并说明所定义的信号量的含义。要求用伪代码描述。 46.（8 分）请求分页管理系统中，假设某进程的页表内容如下表所示。分）请求分页管理系统中，假设某进程的页表内容如下表所示。 页面大小为页面大小为 4KB，一次内存的访问时间，一次内存的访问时间 是是 100ns，一次快表（，一次快表（TLB）的访问时间是）的访问时间是 10ns，处理一次缺页的平均时间为，处理一次缺页的平均时间为 108ns（已含更新（已含更新 TLB 和页表的时间）和页表的时间） ，进，进 程的驻留集大小固定为程的驻留集大小固定为 2，采用最近最少使，采用最近最少使 用置换算法（用置换算法（LRU）和局部淘汰策略。假设）和局部淘汰策略。假设TLB 初始为空；初始为空；地址转换时先访问地址转换时先访问 TLB，若，若 TLB 未命中，再访问页表未命中，再访问页表 （忽略访问页表之后的（忽略访问页表之后的 TLB 更新时间）更新时间） ； 有效位为有效位为 0 表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产 生缺页中断的指令处重新执行。设有虚地址访问序列生缺页中断的指令处重新执行。设有虚地址访问序列 2362H、1565H、25A5H，请问：，请问： （1） 依次访问上述三个虚地址，各需多少时间？给出计算过程。依次访问上述三个虚地址，各需多少时间？给出计算过程。 （2） 基于上述访问序列，虚地址基于上述访问序列，虚地址 1565H 的的 物理地址是多少？请说明理由。物理地址是多少？请说明理由。 47 （9 分）某公司网络拓扑图如下图所示，路由器分）某公司网络拓扑图如下图所示，路由器 R1 通过接口通过接口 E1、E2 分别连接局域网分别连接局域网 1、局域网、局域网 2， 通过接口通过接口 L0 连接路由器连接路由器 R2，并通过路由器，并通过路由器 R2 连接域名服务器与互联网。连接域名服务器与互联网。R1 的的 L0 接口接口 的的 IP 地址是地址是 202.118.2.1；R2 的的 L0 接口的接口的 IP 地址是地址是 202.118.2.2，L1 接口的接口的 IP 地址是地址是 130.11.120.1，E0 接口的接口的 IP 地址是地址是 202.118.3.1；域名服务器的；域名服务器的 IP 地址是地址是 202.118.3.2。 将将 IP 地址空间地址空间 202.118.1.0/24 划分为两个子网，分配给局域网划分为两个子网，分配给局域网 1、局域网、局域网 2，每个局域网分，每个局域网分页号页号页框号页框号有效位有效位 （存在位）（存在位） 0101H1 1-0 2254H1配的地配的地 址数不少于址数不少于 120 个，请给出子网划分结果。说明理由或给出必要的计算过程。个，请给出子网划分结果。说明理由或给出必要的计算过程。 请给出请给出 R1 的路由表，使其明确包括到局域网的路由表，使其明确包括到局域网 1 的路由、局域网的路由、局域网 2 的路由、域名服务器的的路由、域名服务器的 主机路由和主机路由和 互联网的路由。互联网的路由。 请采用路由聚合技术，给出请采用路由聚合技术，给出 R2 到局域网到局域网 1 和局域网和局域网 2 的路由。的路由。 2009 年计算机统考真题参考答案年计算机统考真题参考答案一一 选择题选择题 1 2 3 4 5 6 7 8 9 10 B C D B C B A D A B 11 12 13 14 15 16 17 18 19 20 C D D C D C A A D B 21 22 23 24 25 26 27 28 29 30 D A D D C A C B A A 31 32 33 34 35 36 37 38 39 40 B A B B C A D D C A 1.1.为解决计算机与打印机之间速度不匹配的问题为解决计算机与打印机之间速度不匹配的问题, ,通常设置一个打印数据缓冲区，该缓冲区通常设置一个打印数据缓冲区，该缓冲区的的逻辑结构逻辑结构应该是（队列）应该是（队列）栈栈的定义的定义: :栈是只准在表尾进行插入和删除的线性表，称为栈是只准在表尾进行插入和删除的线性表，称为 LIOFOLIOFO（即后进先出表）。允许（即后进先出表）。允许插入和删除的一端叫栈顶，另一端叫栈底。插入和删除的一端叫栈顶，另一端叫栈底。队列队列的定义：队列是允许在一端进行插入而在另一端进行删除的线性表。允许插入的一端的定义：队列是允许在一端进行插入而在另一端进行删除的线性表。允许插入的一端称为队尾，允许删除的一端称为队头。队列也称为先进先出表（称为队尾，允许删除的一端称为队头。队列也称为先进先出表（FIFOFIFO）树树的定义：树是包含的定义：树是包含 n n 个结点的有限集合（个结点的有限集合（n>0n>0）图图的定义：图（的定义：图（GraphGraph）是由非空的顶点集合和一个描述顶点之间关系）是由非空的顶点集合和一个描述顶点之间关系边（或者弧）的边（或者弧）的集合组成。其形式化定义为：集合组成。其形式化定义为：G=(VG=(V ,E,E）其中其中 G G 表一个图，表一个图，V V 是图是图 G G 中顶点的集合，中顶点的集合，E E 是图是图 G G 中边的集合。中边的集合。2.2.设栈设栈 S S 和队列和队列 Q Q 的初始状态均为空的初始状态均为空, ,元素元素 abcdefgabcdefg 依次进入栈依次进入栈 S S。若每个元素出栈后立即。若每个元素出栈后立即进入队列进入队列 Q Q，且，且 7 7 个元素出队的顺序是个元素出队的顺序是 bdcfeag,bdcfeag,则则栈栈 S S 的容量的容量？（？（3 3）3.3.给定二叉树图，若遍历后的结点序列为给定二叉树图，若遍历后的结点序列为 XXXXXX，则其，则其遍历方式遍历方式是？是？设设 N N 代表二叉树的根，代表二叉树的根，L L 代表根结点的左子树，代表根结点的左子树，R R 代表根结点的右子树。代表根结点的右子树。4.4.平衡二叉树定义平衡二叉树定义: :若一棵二叉树中每个结点的左、右子树的高度至多相差若一棵二叉树中每个结点的左、右子树的高度至多相差 1 1，则称此树为，则称此树为平衡二叉树。我们把二叉树中每个结点的左子树高度减去右子树高度定义为该结点的平衡平衡二叉树。我们把二叉树中每个结点的左子树高度减去右子树高度定义为该结点的平衡因子因子(balance(balance factor)factor)。因此，平衡树中每个结点的平衡因子只能是。因此，平衡树中每个结点的平衡因子只能是 1 1、0 0 或或-1-1。5.5.已知一棵完全二叉树的第已知一棵完全二叉树的第 6 6 层（层（设根为第设根为第 1 1 层层）有）有 8 8 个叶结点，则个叶结点，则完全二叉树的结点个完全二叉树的结点个数数最多是？（最多是？（111111）二叉树二叉树：二叉树是一种重要的树形结构，它是：二叉树是一种重要的树形结构，它是 n n（n>=0n>=0）个结点的有限集，其子树分为互）个结点的有限集，其子树分为互不相交的两个集合，分别称为左子树和右子树，左子树和右子树也是如上定义的二叉树。不相交的两个集合，分别称为左子树和右子树，左子树和右子树也是如上定义的二叉树。左子树和右子树的顺序不能互换。左子树和右子树的顺序不能互换。满二叉树满二叉树：深度为：深度为 k k 结点数为结点数为 2k-12k-1 的二叉树。的二叉树。完全二叉树完全二叉树：若对满二叉树的结点从上到下从左到右进行编号，则深度为：若对满二叉树的结点从上到下从左到右进行编号，则深度为 k k 且有且有 n n 个结点个结点的二叉树，当且仅当其每一个结点都与深度为的二叉树，当且仅当其每一个结点都与深度为 k k 的满二叉树的编号从的满二叉树的编号从 1 1 到到 n n 一一对应时，一一对应时，称为完全二叉树。称为完全二叉树。6.6.将将森林转换为对应的二叉树森林转换为对应的二叉树，若在，若在二叉树二叉树中，结点中，结点 u u 是结点是结点 v v 的父结点的父结点，则在的父结点的父结点，则在原来的森林中原来的森林中，u u 和和 v v 可能具有的关系是可能具有的关系是: :父子关系或兄弟关系。父子关系或兄弟关系。森林转换为对应的二叉树森林转换为对应的二叉树: :兄弟之间连线，父只与长子连线。（左孩子右兄弟）兄弟之间连线，父只与长子连线。（左孩子右兄弟）7.7.无向连通图特性无向连通图特性的叙述的叙述: :所有所有顶点的度顶点的度之和为之和为偶数偶数。顶点的度顶点的度定义：与定点定义：与定点 v v 相关联的边数相关联的边数( (每个环计算两次每个环计算两次) )。 度为零的顶点称为孤立顶点，度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。度为零的顶点称为孤立顶点，度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。8.8.一棵一棵 m m 阶阶 B B 树树（19701970 年，年，R.BayerR.Bayer 和和 E.mccreightE.mccreight 提出了一种适用于提出了一种适用于外查找外查找的树，它是的树，它是一种一种平衡多叉树平衡多叉树）定义：定义： 树中每个结点至多有树中每个结点至多有 m m 个孩子；个孩子； 除根结点和叶子结点外，其它每个结点至少有除根结点和叶子结点外，其它每个结点至少有 m/2m/2 个孩子；个孩子； 若根结点不是叶子结点，则至少有若根结点不是叶子结点，则至少有 2 2 个孩子个孩子( (除非除非 B B 树只有一个结点树只有一个结点) )； 所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息；所有叶子结点都出现在同一层，叶子结点不包含任何关键字信息； 有有 k k 个孩子的非终端结点恰好包含有个孩子的非终端结点恰好包含有 k-1k-1 个关键字个关键字( (各节点内关键字均升序或降序排列各节点内关键字均升序或降序排列).).9.9.堆堆(Heap)(Heap)分为小根堆和大根堆两种，对于一个小根堆，它是具有如下特性的一棵完全二分为小根堆和大根堆两种，对于一个小根堆，它是具有如下特性的一棵完全二叉树：叉树：(1)(1)若树根结点存在左孩子，则根结点的值若树根结点存在左孩子，则根结点的值( (或某个域的值或某个域的值) )小于等于左孩子结点的值小于等于左孩子结点的值( (或某或某个域的值个域的值) )；(2)(2)若树根结点存在右孩子，则根结点的值若树根结点存在右孩子，则根结点的值( (或某个域的值或某个域的值) )小于等于右孩子结点的值小于等于右孩子结点的值( (或某或某个域的值个域的值) )；(3)(3)以左、右孩子为根的子树又各是一个堆。以左、右孩子为根的子树又各是一个堆。大根堆的定义与上述类似，只要把小于等于改为大于等于就得到了。大根堆的定义与上述类似，只要把小于等于改为大于等于就得到了。由堆的定义可知，若一棵完全二叉树是堆，则该树中以每个结点为根的子树也都是一个堆。由堆的定义可知，若一棵完全二叉树是堆，则该树中以每个结点为根的子树也都是一个堆。分别为一个小根堆和一个大根堆。根据堆的定义可知，堆顶结点，即整个完全二叉树的根分别为一个小根堆和一个大根堆。根据堆的定义可知，堆顶结点，即整个完全二叉树的根结点，对于小根堆来说具有最小值，对于大根堆来说具有最大值。结点，对于小根堆来说具有最小值，对于大根堆来说具有最大值。堆排序堆排序利用了大根堆利用了大根堆( (或小根堆或小根堆) )堆顶记录的关键字最大堆顶记录的关键字最大( (或最小或最小) )这一特征，使得在当前无这一特征，使得在当前无序区中选取最大序区中选取最大( (或最小或最小) )关键字的记录变得简单。关键字的记录变得简单。当向一个小根堆插入一个具有最小值的元素时当向一个小根堆插入一个具有最小值的元素时, ,该元素需要逐层该元素需要逐层向上向上调整调整, ,直到被调整到直到被调整到堆堆顶顶位置为止。位置为止。10.10.数据元素序列数据元素序列 1111，1212，1313，7 7，8 8，9 9，2323，4 4，5 5 是第二趟排序后的结果，则该排序算法是第二趟排序后的结果，则该排序算法只能是只能是插入排序。插入排序。气泡排序基本思想气泡排序基本思想：设待排序对象序列中的对象个数为设待排序对象序列中的对象个数为 n n。一般地，第。一般地，第 i i 趟起泡排序从趟起泡排序从 1 1 到到 n-i+1n-i+1 依次比较相依次比较相邻两个记录地关键字，如果发生逆序，则交换之，其结果是这邻两个记录地关键字，如果发生逆序，则交换之，其结果是这 n-i+1n-i+1 个记录中，关键字最个记录中，关键字最大的记录被交换到第大的记录被交换到第 n-i+1n-i+1 的位置上，最多作的位置上，最多作 n-1n-1 趟。趟。简单选择排序基本思想简单选择排序基本思想：第一趟在第一趟在 R1.nR1.n中选最小的，与中选最小的，与 R1R1交换交换第二趟在第二趟在 R2.nR2.n中选最小的，与中选最小的，与 R2R2交换，依次类推，进行交换，依次类推，进行 n-1n-1 次选择后，整个文件有次选择后，整个文件有序。序。直接插入排序基本思想直接插入排序基本思想: :将一个记录插入到已排序的有序表中，使插入后将一个记录插入到已排序的有序表中，使插入后的表仍然有序。的表仍然有序。折半插入排序基本思想折半插入排序基本思想：将一个记录插入到已排序的有序表中，使插入后的表仍然有序，但插入时利用折半搜索法将一个记录插入到已排序的有序表中，使插入后的表仍然有序，但插入时利用折半搜索法寻找元素的插入位置。寻找元素的插入位置。归并排序基本思想归并排序基本思想：又一类不同的排序方法，将两个或两个以上的有序表合并成一个新的有序表。又一类不同的排序方法，将两个或两个以上的有序表合并成一个新的有序表。快速排序基本思想快速排序基本思想：取取 R1.nR1.n中任一记录作为中任一记录作为“枢轴枢轴”，一趟排序之后枢轴的值均小于，一趟排序之后枢轴的值均小于“枢轴枢轴”左边的值，左边的值，枢轴右边的值均大于枢轴右边的值均大于“枢轴枢轴”的值。的值。堆排序基本思想：堆排序基本思想：1.1.如何将一个无序序列调整为堆？如何将一个无序序列调整为堆？2. .如何在互换堆顶之后重新如何在互换堆顶之后重新调整为堆（关键）调整为堆（关键）？希尔排序希尔排序 (Shell Sort) 基本思想基本思想：1.n 大，划分成若干子序列，分别直接插入排序。大，划分成若干子序列，分别直接插入排序。2.待整个记录待整个记录“基本有序基本有序”时，对整体直接重排。时，对整体直接重排。11. .冯冯··诺依曼计算机中诺依曼计算机中指令和数据指令和数据均以二进制形式存放在存储器中，均以二进制形式存放在存储器中，CPUCPU 区分它们的依据区分它们的依据是是指令周期的不同阶段指令周期的不同阶段。12.12.十进制转换十进制转换：十进制转任意进制的通用方法是：除十进制转任意进制的通用方法是：除 x x 取余倒排法（取余倒排法（x x 代表进制数）。代表进制数）。如：将十进制数如：将十进制数 7676 转换成任意进制转换成任意进制1.1.转成二进制转成二进制7676 / / 2 2 . 0 0= = 3838 / / 2 2 . 0 0= = 1919 / / 2 2 . 1 1= = 9 9 / / 2 2 . 1 1= = 4 4 / / 2 2 . 0 0= = 2 2 / / 2 2 . 0 0= = 1 1 / / 2 2 . 1 176(10)76(10) = = 1001100(2)1001100(2)2.2.转成八进制转成八进制7676 / / 8 8 . 4 4= = 9 9 / / 8 8 . 1 1= = 1 1 / / 8 8 . 1 176(10)76(10) = = 114(8)114(8)3.3.转成十六进制转成十六进制7676 / / 1616 . 1212= = 4 4 / / 1616 . 4 476(10)=4C(16)76(10)=4C(16)B B ：二进制数。：二进制数。Q Q ：八进制数。：八进制数。D D ：十进制数。：十进制数。H H ：十六进制数。：十六进制数。负数用十六进制和八进制怎么表示负数用十六进制和八进制怎么表示？使用使用补码（二进制）补码（二进制），而且还要指定字长，而且还要指定字长比如说一个二字节整型的比如说一个二字节整型的 -2-2 就应该是：就应该是：1111111111111111 1111111011111110再转化其它进制再转化其它进制十六进制：十六进制：FFFEFFFE八进制：八进制：17777617777613.13.浮点数浮点数加减运算过程一般包括加减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点等步骤。设浮点数的数的阶码和尾数阶码和尾数均采用均采用补码补码表示，且位数分别为表示，且位数分别为 5 5 位和位和 7 7 位（均含位（均含 2 2 位符号位）。若有两位符号位）。若有两个数个数 X=27*29/32X=27*29/32，Y=25*5/8,Y=25*5/8,则用浮点加法计算则用浮点加法计算 X+YX+Y 的最终结果是发生溢出的最终结果是发生溢出浮点数浮点数表示：小数点的位置可以在一定范围内浮动。表示：小数点的位置可以在一定范围内浮动。E E 为阶，包括阶符和阶码（整数），阶码为数决定了浮点数的表示范围。为阶，包括阶符和阶码（整数），阶码为数决定了浮点数的表示范围。M M 为位数，包括数符和尾数，表示数的精度和正负。为位数，包括数符和尾数，表示数的精度和正负。对阶原则：小阶对大阶。对阶原则：小阶对大阶。双符号位判溢双符号位判溢：加，减后。两个符号位出现：加，减后。两个符号位出现“0101”，表示已经，表示已经溢出溢出，即结果大于，即结果大于+1.+1.14.14.存储器的分类存储器的分类：1.1.按存储介子分按存储介子分:(1):(1)半导体存储器半导体存储器;(2);(2)磁表面存储器磁表面存储器;(3);(3)光介子存储器。光介子存储器。2.2.按存取方式分类按存取方式分类:(1):(1)随机存取存储器随机存取存储器 RAMRAM；(2)(2)顺序存储器顺序存储器 SAMSAM；(3)(3)直接存取存储器直接存取存储器 DAMDAM。3.3.按计算机功能分类按计算机功能分类: :(1)(1)主存储器（主存）主存储器（主存）用于存放计算机运行期间的大量程序和数据的存储器，用于存放计算机运行期间的大量程序和数据的存储器，CPUCPU 能直接访问。由能直接访问。由 MOSMOS 存储器构存储器构成。成。(2)(2)高速缓冲存储器（高速缓冲存储器（CacheCache）CacheCache 是介于是介于 CPUCPU 和主存之间高速小容量存储器，用于存放最活跃的程序块和数据。由静和主存之间高速小容量存储器，用于存放最活跃的程序块和数据。由静态态 MOSMOS 存储器构成。存储器构成。特点：速度快，但容量小，位价格较高。特点：速度快，但容量小，位价格较高。主存和主存和 CacheCache 一起构成计算机的一起构成计算机的内存储器内存储器（内存），是（内存），是 CPUCPU 能直接访问的存储器能直接访问的存储器。(3)(3)辅助存储器（外存储器）辅助存储器（外存储器）存放当前暂不参与运行的程序和数据，需要时再与主存成批交换信息的存储器。存放当前暂不参与运行的程序和数据，需要时再与主存成批交换信息的存储器。特点是容量大，可存放大量的程序和数据，但速度慢。特点是容量大，可存放大量的程序和数据，但速度慢。(4)(4)控制存储器（控制存储器（CMCM）在微程序控制的计算机中，用于存放执行指令的微程序的存储器。在微程序控制的计算机中，用于存放执行指令的微程序的存储器。CMCM 一般由一般由 ROMROM 构成，属于控制器的一部分。构成，属于控制器的一部分。4.4.其它分类：其它分类：a.a.按读写功能分类：按读写功能分类：(1)(1)只读存储器只读存储器(ROM):(ROM):工作时只能读出不能写入的存储器。工作时只能读出不能写入的存储器。(2)(2)读写存储器读写存储器(RAM):(RAM):既能读出又能写入的存储器。既能读出又能写入的存储器。b.b.按信息的可保存性分类按信息的可保存性分类(1)(1)永久性存储器：指断电后仍能保存信息的存储器，如磁表面存储器。永久性存储器：指断电后仍能保存信息的存储器，如磁表面存储器。(2)(2)非永久性存储器非永久性存储器: :指断电后信息即消失的存储器，如半导体读写存储器。指断电后信息即消失的存储器，如半导体读写存储器。某计算机的某计算机的 CacheCache 共有共有 1616 块，采用块，采用 2 2 路组相连映射方式（即每组路组相连映射方式（即每组 2 2 块）。每个主存块大小块）。每个主存块大小为为 3232 字节，按字节编址。主存字节，按字节编址。主存 129129 号单元所在主存块应装入到号单元所在主存块应装入到 CacheCache 组号是组号是(4)(4)15.15.主存容量主存容量是根据是根据地址线的位数地址线的位数来确定的来确定的, ,在在 1616 位位 PCPC 机中地址总线的宽度是机中地址总线的宽度是 2020 位位, ,则主则主存大小为存大小为:220:220 byte=1MB,byte=1MB,现在的现在的 PCPC 机一般都是机一般都是 3232 位地址总线的位地址总线的, ,最大直接寻址空间为最大直接寻址空间为: :232,232,即主存最大容量为即主存最大容量为 4GB4GB某计算机主存容量为某计算机主存容量为 6464KBKB，其中，其中 ROMROM 区为区为 4KB4KB，其余为，其余为 RAMRAM 区，按字节编址。现要用区，按字节编址。现要用 2K*82K*8位的位的 ROMROM 芯片和芯片和 4K*44K*4 位的位的 RAMRAM 芯片来设计该存储器，则需要上述规格的芯片来设计该存储器，则需要上述规格的 ROMROM 芯片数和芯片数和 RAMRAM芯片数分别是芯片数分别是 2 2 303016.16.某计算机字长某计算机字长 1616 位，主存按字节编址，转换指令采用相对寻址，由两个字节组成，第位，主存按字节编址，转换指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一字节一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一字节 PCPC 自动加自动加1 1。若某转移指令所在主存地址为。若某转移指令所在主存地址为 2000H2000H，相对位移量字段的内容为，相对位移量