1、全国硕士研究生入学统一考试计算机学科专业基础综合真题 2012 年及答案解析(总分：149.98，做题时间：180 分钟)一、单项选择题(总题数：40，分数：80.00)1.求整数 n(n0)阶乘的算法如下，其时间复杂度是 int fact(int n) if(n=1)return 1； return n*fact(n-1)； （分数：2.00）A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)2.已知操作符包括“+”、“-”、“*”、“/”、“(”和“)”。将中缀表达式 a+b-a*(c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+时，用栈来存
2、放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是 （分数：2.00）A.5B.7C.8D.113.若一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c，d，e，a，则根结点的孩子结点 （分数：2.00）A.只有 eB.有 e、bC.有 e、cD.无法确定4.若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为 （分数：2.00）A.12B.20C.32D.335.对有 n 个顶点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是 （分数：2.00）A.O(n)B.O(e)
3、C.O(n+e)D.O(ne)6.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是 （分数：2.00）A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一D.无法确定是否存在7.对如下有向带权图，若采用迪杰斯特拉(Dijkstra)算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是 （分数：2.00）A.defB.e，d，fC.f，d，eD.f，e，d8.下列关于最小生成树的叙述中，正确的是 最小生成树的代价唯一 权值最小的边一定会出现在所有的最小生成树中
4、 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同 （分数：2.00）A.仅B.仅C.仅、D.仅、9.设有一棵 3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是 （分数：2.00）A.60B.60，62C.62，65D.6510.排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是 简单选择排序 希尔排序 快速排序 堆排序 二路归并排序 （分数：2.00）A.仅、B.仅、C.仅、
5、D.仅、11.对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是 （分数：2.00）A.排序的总趟数B.元素的移动次数C.使用辅助空间的数量D.元素之间的比较次数12.假定基准程序 A 在某计算机上的运行时间为 100 秒，其中 90 秒为 CPU 时间，其余为 I/O 时间。若 CPU速度提高 50%，I/O 速度不变，则运行基准程序 A 所耗费的时间是 （分数：2.00）A.55 秒B.60 秒C.65 秒D.70 秒13.假定编译器规定 int 和 short 类型长度分别为 32 位和 16 位，执行下列 C 语言语句： unsigned short x=655
6、30； unsigned int y=x； 得到 y 的机器数为 （分数：2.00）A.0000 7FFAHB.0000 FFFAHC.FFFF 7FFAHD.FFFF FFFAH14.float 类型(即 IEEE 754 单精度浮点数格式)能表示的最大正整数是（分数：2.00）A.2126-2103B.2127-2104C.2127-2103D.2128-210415.某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定 int 和 short 型长度分别为 32位和 16 位，并且数据按边界对齐存储。某 C 语言程序段如下： struct int a； char b； shor
7、t c； record； record.a=273； 若 record 变量的首地址为 0xC008，则地址 0xC008 中内容及 record.c 的地址分别为 （分数：2.00）A.0x00、0xC00DB.0x00、0xC00EC.0x11、0xC00DD.0x11、0xC00E16.下列关于闪存(Flash Memory)的叙述中，错误的是 （分数：2.00）A.信息可读可写，并且读、写速度一样快B.存储元由 MOS 管组成，是一种半导体存储器C.掉电后信息不丢失，是一种非易失性存储器D.采用随机访问方式，可替代计算机外部存储器17.假设某计算机按字编址，Cache 有 4 个行，C
8、ache 和主存之间交换的块大小为 1 个字。若 Cache 的内容初始为空，采用 2 路组相联映射方式和 LRU 替换算法，当访问的主存地址依次为0，4，8，2，0，6，8，6，4，8 时，命中 Cache 的次数是 （分数：2.00）A.1B.2C.3D.418.某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33 个微命令，构成 5 个互斥类，分别包含 7、3、12、5 和 6 个微命令，则操作控制字段至少有 （分数：2.00）A.5 位B.6 位C.15 位D.33 位19.某同步总线的时钟频率为 100MHz，宽度为 32 位，地址/数据线复用，每
9、传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发)传输方式，则一次“主存写”总线事务传输 128 位数据所需要的时间至少是 （分数：2.00）A.20nsB.40nsC.50nsD.80ns20.下列关于 USB 总线特性的描述中，错误的是 （分数：2.00）A.可实现外设的即插即用和热插拔B.可通过级联方式连接多台外设C.是一种通信总线，可连接不同外设D.同时可传输 2 位数据，数据传输率高21.下列选项中，在 I/O 总线的数据线上传输的信息包括 I/O 接口中的命令字 I/O 接口中的状态字 中断类型号 （分数：2.00）A.仅、B.仅、C.仅、D.、22.响应外部中断的过程中
10、，中断隐指令完成的操作，除保护断点外，还包括 关中断 保存通用寄存器的内容 形成中断服务程序入口地址并送 PC （分数：2.00）A.仅、B.仅、C.仅、D.、23.下列选项中，不可能在用户态发生的事件是 （分数：2.00）A.系统调用B.外部中断C.进程切换D.缺页24.中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是 （分数：2.00）A.程序计数器B.程序状态字寄存器C.通用数据寄存器D.通用地址寄存器25.下列关于虚拟存储的叙述中，正确的是 （分数：2.00）A.虚拟存储只能基于连续分配技术B.虚拟存储只能基于非连续分配技术C.虚拟存储容量只
11、受外存容量的限制D.虚拟存储容量只受内存容量的限制26.操作系统的 I/O 子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是 （分数：2.00）A.用户级 I/O 软件、设备无关软件、设备驱动程序、中断处理程序B.用户级 I/O 软件、设备无关软件、中断处理程序、设备驱动程序C.用户级 I/O 软件、设备驱动程序、设备无关软件、中断处理程序D.用户级 I/O 软件、中断处理程序、设备无关软件、设备驱动程序27.假设 5 个进程 P0、P1、P2、P3、P4 共享三类资源 R1、R2、R3，这些资源总数分别为 18、6、22。T0时刻的资源分配情况如下表所示
12、，此时存在的一个安全序列是 进程 已分配资源 资源最大需求 R1 R2 R3 R1 R2 R3 P0 3 2 3 5 5 10 P1 4 0 3 5 3 6 P2 4 0 5 4 0 11 P3 2 0 4 4 2 5 P4 3 1 4 4 2 4 （分数：2.00）A.P0，P2，P4，P1，P3B.P1，P0，P3，P4，P2C.P2，P1，P0，P3，P4D.P3，P4，P2，P1，P028.若一个用户进程通过 read 系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是 若该文件的数据不在内存，则该进程进入睡眠等待状态 请求 read 系统调用会导致 CPU 从用户态
13、切换到核心态 read 系统调用的参数应包含文件的名称 （分数：2.00）A.仅、B.仅、C.仅、D.、和29.一个多道批处理系统中仅有 P1 和 P2 两个作业，P2 比 P1 晚 5ms 到达。它们的计算和 I/O 操作顺序如下： P1：计算 60ms，I/O 80ms，计算 20ms P2：计算 120ms，I/O 40ms，计算 40ms 若不考虑调度和切换时间，则完成两个作业需要的时间最少是 （分数：2.00）A.240msB.260msC.340msD.360ms30.若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是 （分数：2.00）A.在进程结束
14、时能进行处理机调度B.创建新进程后能进行处理机调度C.在进程处于临界区时不能进行处理机调度D.在系统调用完成并返回用户态时能进行处理机调度31.下列关于进程和线程的叙述中，正确的是 （分数：2.00）A.不管系统是否支持线程，进程都是资源分配的基本单位B.线程是资源分配的基本单位，进程是调度的基本单位C.系统级线程和用户级线程的切换都需要内核的支持D.同一进程中的各个线程拥有各自不同的地址空间32.下列选项中，不能改善磁盘设备 I/O 性能的是 （分数：2.00）A.重排 I/O 请求次序B.在一个磁盘上设置多个分区C.预读和滞后写D.优化文件物理块的分布33.在 TCP/IP 体系结构中，直
15、接为 ICMP 提供服务的协议是 （分数：2.00）A.PPPB.IPC.UDPD.TCP34.在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是 （分数：2.00）A.机械特性B.功能特性C.过程特性D.电气特性35.以太网的 MAC 协议提供的是 （分数：2.00）A.无连接不可靠服务B.无连接可靠服务C.有连接不可靠服务D.有连接可靠服务36.两台主机之间的数据链路层采用后退 N 帧协议(GBN)传输数据，数据传输速率为 16kbps，单向传播时延为 270ms，数据帧长度范围是 128512 字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少
16、为 （分数：2.00）A.5B.4C.3D.237.下列关于 IP 路由器功能的描述中，正确的是 运行路由协议，设置路由表 监测到拥塞时，合理丢弃 IP 分组 对收到的 IP 分组头进行差错校验，确保传输的 IP 分组不丢失 根据收到的 IP 分组的目的 IP 地址，将其转发到合适的输出线路上 （分数：2.00）A.仅、B.仅、C.仅、D.、38.ARP 协议的功能是 （分数：2.00）A.根据 IP 地址查询 MAC 地址B.根据 MAC 地址查询 IP 地址C.根据域名查询 IP 地址D.根据 IP 地址查询域名39.某主机的 IP 地址为 180.80.77.55，子网掩码为 255.2
17、55.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是 （分数：2.00）A.180.80.76.0B.180.80.76.255C.180.80.77.255D.180.80.79.25540.若用户 1 与用户 2 之间发送和接收电子邮件的过程如下图所示，则图中、阶段分别使用的应用层协议可以是 （分数：2.00）A.SMTP、SMTP、SMTPB.POP3、SMTP、POP3C.POP3、SMTP、SMTPD.SMTP、SMTP、POP3二、综合应用题(总题数：7，分数：70.00)设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200
18、 个数据元素，各表中元素按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达到最小。请回答下列问题。（分数：10.00）(1).给出完整的合并过程，并求出最坏情况下比较的总次数。（分数：5.00）_(2).根据你的合并过程，描述 n(n2)个不等长升序表的合并策略，并说明理由。（分数：5.00）_假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储空间。例如，“loading”和“being”的存储映像如下图所示。 设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 （分数：9.99）
19、(1).给出算法的基本设计思想。（分数：3.33）_(2).根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（分数：3.33）_(3).说明你所设计算法的时间复杂度。（分数：3.33）_假定某计算机的 CPU 主频为 80MHz，CPI 为 4，并且平均每条指令访存 1.5 次，主存与 Cache 之间交换的块大小为 16B，Cache 的命中率为 99%，存储器总线宽度为 32 位。请回答下列问题。（分数：10.00）(1).该计算机的 MIPS 数是多少?平均每秒 Cache 缺失的次数是多少?在不考虑 DMA 传送的情况下，主存带宽至少达到多少才能满足 CP
20、U 的访存要求?（分数：2.50）_(2).假定在 Cache 缺失的情况下访问主存时，存在 0.0005%的缺页率，则 CPU 平均每秒产生多少次缺页异常?若页面大小为 4KB，每次缺页都需要访问磁盘，访问磁盘时 DMA 传送采用周期挪用公式，磁盘 I/O 接口的数据缓冲寄存器为 32 位，则磁盘 I/O 接口平均每秒发出的 DMA 请求次数至少是多少?（分数：2.50）_(3).CPU 和 DMA 控制器同时要求使用存储器总线时，哪个优先级更高?为什么?（分数：2.50）_(4).为了提高性能，主存采用 4 体交叉存储模式，工作时每 1/4 个存储周期启动一个体。若每个体的存储周期为 50
21、ns，则该主存能提供的最大带宽是多少?（分数：2.50）_某 16 位计算机中，带符号整数用补码表示，数据 Cache 和指令 Cache 分离。下表给出了指令系统中部分指令格式，其中 Rs 和 Rd 表示寄存器，mem 表示存储单元地址，(x)表示寄存器 x 或存储单元 x 的内容。 指令系统中部分指令格式 指令系统中部分指令格式 名称 指令的汇编格式 指令功能 加法指令 ADD Rs,Rd (Rs)+(Rd)Rd 算术/逻辑左移 SHL Rd 2*(Rd)Rd 算术右移 SHR Rd (Rd)/2Rd 取数指令 LOAD Rd,mem (mem)Rd 存数指令 STORE Rs,mem (
22、Rs)mem 该计算机采用 5 段流水方式执行指令，各流水段分别是取指(IF)、译码/读寄存器(ID)、执行/计算有效地址(EX)、访问存储器(M)和结果写回寄存器(WB)，流水线采用“按序发射，按序完成”方式，没有采用转发技术处理数据相关，并且同一个寄存器的读和写操作不能在同一个时钟周期内进行。请回答下列问题。 （分数：10.00）(1).若 int 型变量 x 的值为-513，存放在寄存器 R1 中，则执行指令“SHR R1”后，R1 的内容是多少?(用十六进制表示)（分数：2.50）_(2).若某个时间段中，有连续的 4 条指令进入流水线，在其执行过程中没有发生任何阻塞，则执行这 4 条
23、指令所需的时钟周期数为多少?（分数：2.50）_(3).若高级语言程序中某赋值语句为 x=a+b，x、a 和 b 均为 int 型变量，它们的存储单元地址分别表示为x、a和b。该语句对应的指令序列及其在指令流水线中的执行过程如图所示。 （分数：2.50）_(4).若高级语言程序中某赋值语句为 x=2*x+a，x 和 a 均为 unsigned int 类型变量，它们的存储单元地址分别表示为x、a，则执行这条语句至少需要多少个时钟周期?要求模仿上图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。（分数：2.50）_某请求分页系统的局部页面置换策略如下： 系统从 0 时刻开始扫描，每隔
24、5 个时间单位扫描一轮驻留集(扫描时间忽略不计)，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次被分配之前不被清空。当发生缺页时，如果该页曾被使用过且还在空闲页框链表中，则重新放回进程的驻留集中；否则，从空闲页框链表头部取出一个页框。假设不考虑其他进程的影响和系统开销，初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为 32、15、21、41。进程 P 依次访问的虚拟页号，访问时刻是：1，1、3，2、0，4、0，6、1，11、0，13、2，14。请回答下列问题。 （分数：10.00）(1).访问0，4时，对应的页框号是什么?（分数：2.50）_(2).访问1，
25、11时，对应的页框号是什么?说明理由。 （分数：2.50）_(3).访问2，14时，对应的页框号是什么?说明理由。 （分数：2.50）_(4).该策略是否适合于时间局部性好的程序?说明理由。（分数：2.50）_某文件系统空间的最大容量为 4TB(1 T=240)，以磁盘块为基本分配单位，磁盘块大小为 1KB。文件控制块(FCB)包含一个 512B 的索引表区。请回答下列问题。（分数：10.00）(1).假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号。索引表项中块号最少占多少字节?可支持的单个文件最大长度是多少字节?（分数：5.00）_(2).假设索引表区采用如下结构：第 07
26、字节采用起始块号，块数格式表示文件创建时预分配的连续存储空间，其中起始块号占 6B，块数占 2B；剩余 504 字节采用直接索引结构，一个索引项占 6B，则可支持的单个文件最大长度是多少字节?为了使单个文件的长度达到最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。（分数：5.00）_主机 H 通过快速以太网连接 Internet，IP 地址为 192.168.0.8，服务器 S 的 IP 地址为 211.68.71.80。H与 S 使用 TCP 通信时，在 H 上捕获的其中 5 个 IP 分组如题 a 表所示。 请回答下列问题。 （分数：9.99）(1).a 表中的 IP 分组中，
27、哪几个是由 H 发送的?哪几个完成了 TCP 连接建立过程?哪几个在通过快速以太网传输时进行了填充? （分数：3.33）_(2).根据 a 表中的 IP 分组，分析 S 已经收到的应用层数据字节数是多少?（分数：3.33）_(3).若 a 表中的某个 IP 分组在 S 发出时的前 40 字节如 b 表所示，则该 IP 分组到达 H 时经过了多少个路由器? （分数：3.33）_全国硕士研究生入学统一考试计算机学科专业基础综合真题 2012 年答案解析(总分：149.98，做题时间：180 分钟)一、单项选择题(总题数：40，分数：80.00)1.求整数 n(n0)阶乘的算法如下，其时间复杂度是
28、int fact(int n) if(n=1)return 1； return n*fact(n-1)； （分数：2.00）A.O(log2n)B.O(n) C.O(nlog2n)D.O(n2)解析：2.已知操作符包括“+”、“-”、“*”、“/”、“(”和“)”。将中缀表达式 a+b-a*(c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是 （分数：2.00）A.5 B.7C.8D.11解析：根据题目要求，栈中只存储操作符“+”，“-”，“*”，“/”，“(
29、”和“)”，并不存储字母，这一点一定要看清楚。根据中缀表达式 a+b-a*(e+d)/e-f)+g，可以利用栈将其转换为后缀表达式ab+acd+e/f-*-g+，在转换过程中，栈中的操作符最多有 5 个。这种情况出现在第二个“+”号入栈后，栈中的操作符分别为：“-”，“*”，“(”，“(”，“+”。3.若一棵二叉树的前序遍历序列为 a，e，b，d，c，后序遍历序列为 b，c，d，e，a，则根结点的孩子结点 （分数：2.00）A.只有 e B.有 e、bC.有 e、cD.无法确定解析：根据题中给出的二叉树的前序遍历 a、e、b、d、c 和后序遍历 b、c、d、e、a 可以确定的是 a 为二叉树的
30、根结点。那么根据前序遍历的访问次序为根结点、左子树、右子树，可以确定 e 为左子树或右子树的根结点，即根结点的孩子结点。假设 e 为左孩子结点，那么根据后序遍历的结果可知，b、c、d 一定在左子树上，不可能为 a 的孩子结点。若 e 为右子树的根结点，根据前序遍历结果可知，此二又树没有左子树。4.若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为 （分数：2.00）A.12B.20 C.32D.33解析：5.对有 n 个顶点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法的时间复杂度是 （分数：2.00）A.O(n)B.O(e)C.O(n+e) D
31、.O(ne)解析：邻接表存储的有向图进行广度优先遍历的时间复杂度与图中的顶点个数以及边数都相关，因此答案选 C。6.若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是 （分数：2.00）A.存在，且唯一B.存在，且不唯一C.存在，可能不唯一 D.无法确定是否存在解析：邻接矩阵存储有向图且主对角线以下的元素均为零，说明在此有向图中，1 为起点，n 为终点。任何一个顶点都不能到达比其号码小的顶点。在这种有向图中拓扑序列是存在的，但是可能唯一，也可能不唯一。例如，只有两个顶点的有向图，其拓扑序列就唯一。但是，三个顶点的有向图中拓扑序列就可能不唯一了。7.对如下有向带权
32、图，若采用迪杰斯特拉(Dijkstra)算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是 （分数：2.00）A.defB.e，d，fC.f，d，e D.f，e，d解析：根据迪杰斯特拉(Dijkstra)算法，可以得到以下过程： 从 a 出发，与其直接相邻的是 b(2)、c(5)，因此可以得到第一条最短路径的目标顶点是 b。 从a，b出发，与其相邻的是 c(3)、d(5)、e(6)，因此可以得到第二条最短路径的目标顶点是 c。 从a，b，c出发，与其相邻的是 d(5)、e(6)、f(4)，因
33、此可以得到第三条最短路径的目标顶点是 f。 从a，b，c，f出发，与其相邻的是 d(5)、e(6)，因此可以得到第四、五条最短路径的目标顶点是 d、e。因此结点的顺序为 f、d、e，即 C 选项。 8.下列关于最小生成树的叙述中，正确的是 最小生成树的代价唯一 权值最小的边一定会出现在所有的最小生成树中 使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同 （分数：2.00）A.仅 B.仅C.仅、D.仅、解析：最小生成树的代价唯一这种叙述是正确的。如果利用 kruskal 算法，那么权值最小的边一定会出现在所
34、有的最小生成树中，但是利用 prim 算法权值最小的边不一定会在最小生成树中。用prim 算法从不同的顶点开始得到的最小生成树也不一定相同。最后，用 prim 算法和 kruskal 算法得到的最小生成树也有可能相同。9.设有一棵 3 阶 B 树，如下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是 （分数：2.00）A.60B.60，62C.62，65D.65 解析：删除关键字 78，则需要对非叶子结点55，65进行分裂。将 65 与叶子结点60，62合并成一个叶子结点60，62，65，在 3 阶 B 树中，叶子结点中元素的个数不能多于 3 个，因此，叶子结点60，6
35、2，65需要进行分裂。将 62 转到非叶子结点中，与 55 合并，即55，62；而 60 与 65 分别构成新的叶子结点。最右边的叶子结点的关键字为 65。10.排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是 简单选择排序 希尔排序 快速排序 堆排序 二路归并排序 （分数：2.00）A.仅、 B.仅、C.仅、D.仅、解析：每一趟排序结束都至少能够确定一个元素最终位置的方法有：简单选择排序、快速排序、堆排序。11.对同一待排序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是 （分数：2.00）
36、A.排序的总趟数B.元素的移动次数C.使用辅助空间的数量D.元素之间的比较次数 解析：折半插入排序和直接插入排序二者之间的不同之处在于，查找插入位置时，折半插入排序进行元素的比较次数比较少。12.假定基准程序 A 在某计算机上的运行时间为 100 秒，其中 90 秒为 CPU 时间，其余为 I/O 时间。若 CPU速度提高 50%，I/O 速度不变，则运行基准程序 A 所耗费的时间是 （分数：2.00）A.55 秒B.60 秒C.65 秒D.70 秒 解析：基准程序 A 的运行时间为 100 秒，90 秒为 CPU 时间，10 秒为 I/O 时间。由于 CPU 速度提高 50%，则原来要执行
37、90 秒的任务，现在缩短为 90/(1+50%)=60 秒。由于 I/0 速度不变，则运行基准程序 A 所耗费的时间为 10 秒+60 秒=70 秒。13.假定编译器规定 int 和 short 类型长度分别为 32 位和 16 位，执行下列 C 语言语句： unsigned short x=65530； unsigned int y=x； 得到 y 的机器数为 （分数：2.00）A.0000 7FFAHB.0000 FFFAH C.FFFF 7FFAHD.FFFF FFFAH解析：对于 unsigned short x=65530；可先将其化成二进制：1111 1111 1111 1010，
38、对应的十六进制数为 FFFA，将其转换成 32 位 unsigned int 类型为 0000 FFFAH。即 y 的机器数为：0000 FFFAH。14.float 类型(即 IEEE 754 单精度浮点数格式)能表示的最大正整数是（分数：2.00）A.2126-2103B.2127-2104C.2127-2103D.2128-2104 解析：本题考查的是 IEEE754 单精度浮点数格式的表示范围，答案为 D。15.某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定 int 和 short 型长度分别为 32位和 16 位，并且数据按边界对齐存储。某 C 语言程序段如下： st
39、ruct int a； char b； short c； record； record.a=273； 若 record 变量的首地址为 0xC008，则地址 0xC008 中内容及 record.c 的地址分别为 （分数：2.00）A.0x00、0xC00DB.0x00、0xC00EC.0x11、0xC00DD.0x11、0xC00E 解析：小端方式存放数据是指将最后一个字节存放在首地址处。显然，0xC008 存放的是 a 变量的最后一个字节，而 273 用十六进制表示为 0000 0111H。即将 a 分成 4 个字节存放，分别为：0x 00，0x 00，0x 01，0x 11。而 0xC0
40、08 存放的是 a 变量的最后一个字节，即 0x 11。在程序执行过程中，先给 record.a分配内存，然后给 record.b 分配内存，而 record.a 占 4 个字节，record.b 占 1 个字节，那么存放record.c 的地址要偏移 5 个字节，但是在小端存放数据的方式中，则需要偏移 6 个字节，即0xC008+0x0006=0xC00E。16.下列关于闪存(Flash Memory)的叙述中，错误的是 （分数：2.00）A.信息可读可写，并且读、写速度一样快 B.存储元由 MOS 管组成，是一种半导体存储器C.掉电后信息不丢失，是一种非易失性存储器D.采用随机访问方式，可
41、替代计算机外部存储器解析：闪存是电子可擦除只读存储器(EEPROM)的变种，闪存掉电后信息不丢失，是一种非易失性存储器。采用随机访问方式，可替代计算机外部存储器。闪存是一种半导体存储器，不能实现信息可读可写。删除或重写闪存中的内容是有条件的，而且有次数的限制。闪存与 EEPROM 不同的是，它能在字节水平上进行删除和重写而不是整个芯片擦写，这样闪存就比 EEPROM 的更新速度快。17.假设某计算机按字编址，Cache 有 4 个行，Cache 和主存之间交换的块大小为 1 个字。若 Cache 的内容初始为空，采用 2 路组相联映射方式和 LRU 替换算法，当访问的主存地址依次为0，4，8，
42、2，0，6，8，6，4，8 时，命中 Cache 的次数是 （分数：2.00）A.1B.2C.3 D.4解析：根据 2 路组相连的映射方式和 LRU 替换策略可以得到，命中 cache 的次数是 3 次。18.某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33 个微命令，构成 5 个互斥类，分别包含 7、3、12、5 和 6 个微命令，则操作控制字段至少有 （分数：2.00）A.5 位B.6 位C.15 位 D.33 位解析：操作控制字段采用字段直接编码法，要表示 33 个微命令，构成 5 个互斥类，那么控制字段至少要15 位。19.某同步总线的时钟频率为 100MHz，宽度为 32 位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发(猝发)传输方式，则一次“主存写”总线事务传输 128 位数据所需要的时间至少是 （分数：2.00）A.20nsB.40nsC.50ns D.80ns解析：根据题中条件可知：总线频率为 100MHz，可以求得一个时钟周期的时间为 1/100MHz
