[考研类试卷]计算机专业（基础综合）模拟试卷65及答案与解析.doc

《[考研类试卷]计算机专业（基础综合）模拟试卷65及答案与解析.doc》由会员分享，可在线阅读，更多相关《[考研类试卷]计算机专业（基础综合）模拟试卷65及答案与解析.doc（42页珍藏版）》请在麦多课文档分享上搜索。

1、计算机专业（基础综合）模拟试卷 65 及答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 在 n 个结点的线性表的数组表示中，以下算法的时间复杂度是 O(1)的操作是( )。访问第 i 个结点(1in)和求第 i 个结点的直接前驱 (2in)在最后一个结点后插入一个新的结点删除第一个结点在第 i 个结点后插入一个结点(1in)（A）仅（B）仅 、（C）仅 、（D）仅、2 中缀表达式 a*(b+c)-d 的后缀表达式是 ( )。（A）abcd*+-（B） abc+*d（C） abc*+d-（D）-+*abcd3 设

2、线性表有 n 个元素，以下操作中，( )在顺序表上实现比链表上实现效率更高。（A）输出第 i(1in)个元素值（B）交换第 1 个元素与第 2 个元素的值（C）顺序输出这 n 个元素的值（D）输出与给定值 x 相等的元素在线性表中的序号4 设 k 是中序线索二叉树中一个有左子女的结点，且 k 不是根结点，则 k 在中序序列下的直接前驱结点是( )。（A）k 的左线索(指示中序前驱)所指示的结点（B）从 k 父结点的左子女开始沿右子女链走到底的结点（C）从 k 的左子女开始沿右子女链走到底的结点（D）从 k 的左子女开始沿左子女链走到底的结点5 假定一组元素序列为38，42，55，15，23，4

3、4，34，74，45，26 ，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为 2 的结点个数为( )。（A）1（B） 3（C） 4（D）56 某二叉树的先序序列和后序序列正好相反，则该二叉树可能是( )。空或只有一个结点 任意一个结点无右孩子 任意一个结点无左孩子（A）只可能为（B）只可能为（C）只可能为（D）、都有可能7 对图 41 进行拓扑排序，可以得到不同的拓扑序列的个数是( )。（A）4（B） 3（C） 2（D）18 如果从无向图的任意一个顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是( ) 。（A）完全图（B）连通图（C）有回路（D）一棵树9 以下有

4、关 m 阶 B-树的说法中正确的有( )。每个结点至少有两棵非空子树树中每个结点至多有 m-1 个关键字所有叶子在同一层上 当插入一个数据项引起 B 一树结点分裂后，树长高一层（A）仅、（B）仅 、（C）仅 、IV（D）仅、10 在下列排序方法中，平均时间复杂度为 O(nlogn)的排序算法是( )。快速排序 冒泡排序 希尔排序 选择排序（A）仅、（B）仅 、（C）仅 、（D）仅、11 某个文件经内部排序得到 80 个初始归并段。如果操作系统要求一个程序同时可用的输入输出文件的总数不超过 15 个，则按多路归并至少需要( )趟可以完成排序。（A）2（B） 3（C） 4（D）512 考虑以下 C

5、 语言代码： short si=-8196； unsigned short usi=si ； 执行上述程序段后，usi 的值为( )。（A）8196（B） 34572（C） 57339（D）5734013 32 位字长的浮点数，其中阶码 8 位(含 1 位阶符)，尾数 24 位(含 1 位数符)，机器数采用补码表示，且尾数为规格化形式，则对应的最小正数为( )。（A）2 127(1-2-23)（B） 2-129（C） 2-1282-23（D）2 -1272-2314 硬盘平均寻道时间为 12ms，传输速率为 10MBs ，磁盘控制器延时为 2ms，则一个转速为 7200rmin 的硬盘写 1K

6、B 数据的时间为 ( )。（A）1311 ms（B） 1413ms（C） 1515ms（D）1827ms15 下面关于各种存储器的说法中，正确的有( )。静态 RAM 不是易失性存储器，而动态 RAM 是易失性存储器PROM 只能写录一次EPROM 是可改写的，并且也是随机存储器的一种EEPROM 存储器是可写存储器（A）仅、（B）仅 、（C）仅 、（D）仅、16 一个 Cache-主存系统，采用 50MHz 的时钟，存储器以每一个时钟周期传输一个字的速率，连续传输 8 个字，以支持块长为 8 个字的 Cache，每个字 4B。假设读操作所花的时间是：1 个周期接受地址，3 个周期延迟，8 个

7、传输周期传输 8 个字；写操作所花的时间是：1 个周期接受地址，2 个周期延迟，8 个周期传输 8 个字，3 个周期恢复和写入纠错码，当系统以 35为读操作、65为写操作的访问情况工作，则存储器最大带宽为( )。（A）1332MBs（B） 1144MBs（C） 126MBs（D）1203MBs17 在二地址指令中，操作数的物理位置可安排在( )。两个主存单元 两个寄存器 一个主存单元和一个寄存器 栈顶和次栈顶（A）仅、（B）仅 、（C）仅 、（D）仅、18 某计算机采用微程序控制，微指令字中操作控制字段共 12 位，下列说法正确的是( )。若采用直接控制，则此时一条微指令最多可同时启动 1 2

8、 个微操作若采用字段直接编码控制，并要求一条微指令需同时启动 3 个微操作，则微指令字中的操作控制字段应分 6 段 若采用字段直接编码控制，并要求一条微指令需同时启动 3 个微操作，每个字段的微命令数相同，这样的微指令格式最多可包含 45 个微操作命令（A）仅、（B）仅 、（C）仅 、（D）、和19 一条双字长直接寻址的子程序调用 CALL 指令，其第一个字为操作码和寻址特征，第二个字为地址码 5000H。假设 PC(程序计数器)当前值为 1000H，SP 的内容为 0100H，栈顶内容为 1234H，存储器按字编址，而且进栈操作是先(SP)-1SP，后存入数据。则 CALL 指令执行后，SP

9、 及栈项的内容分别为 ( )。（A）OOFFH，1000H（B） 0101H，1000H（C） OOFEH，1002H（D）OOFFH，1002H20 指令流水线将一条指令的执行过程分为 4 步，其中第 1、2 和 4 步的执行时间为t，如图 4-2 所示。若该流水线顺序执行 50 条指令共用了 203t(无需考虑相关问题)，则该流水线的第 3 步的执行时间是( )。（A）3t（B） 4t（C） 5t（D）6t21 某总线共有 88 根信号线，其中数据总线为 32bit，地址总线为 20bit，控制总线为 36 根，总线的工作频率为 66MHz，则总线宽度为( )，传输速率为( )。（A）32

10、bit 264MB s（B） 20bit 264MBs（C） 32bit 254MBs（D）20bit 264MB s22 设置中断排队判优逻辑的目的是( )。（A）产生中断源编码（B）使同时提出的请求中的优先级别最高者得到及时响应（C）使 CPU 能方便地转入中断服务子程序（D）提高中断响应速度23 实时系统中，通常采用( )算法进行进程调度。（A）先来先服务（B）时间片轮换（C）抢占式的优先数高者优先（D）响应比高者优先24 考虑下面的基于动态改变优先级的可抢占式优先权调度算法。大的优先权数代表高优先级。当一个进程在等待 CPU 时(在就绪队列中，但未执行)，优先权以 速率改变；当它运行时

11、，优先权以 速率改变。所有的进程在进入就绪队列被给定优先权数为 0。参数 和 可以设定给许多不同的调度算法。下列( )设定可以实现进程 FIFO(First In First Out)。（A）0（B） 0（C） 0（D）025 假设系统有 5 个进程，A、B、C 三类资源。某时刻进程和资源状态如表 4-1 所示。下面叙述正确的是( )。（A）系统不安全（B）该时刻，系统安全，安全序列为（C）该时刻，系统安全，安全序列为（D）该时刻，系统安全，安全序列为26 某系统拥有一个 CPU。IO1 和 IO2 为两个不同步的输入输出装置，它们能够同时工作。当使用 CPU 之后控制转向 IO1、： IO2

12、 时，或者使用。IO1、 IO2 之后控制转向 CPU 时，由控制程序执行中断处理，但这段处理时间可以忽略不计。有 A、B 两个进程同时被创建，进程 B 的调度优先权比进程 A 高，但是当进程 A 正在占用 CPU 时，即使进程 B 需要占用 CPU，也不能打断进程 A的执行。若在同一体系中分别单独执行，则需要占用 CPU、IO1 、IO2 的时间如下表所示。进程 A： 进程 B：经过计算可知：( )先结束。（A）进程 A（B）进程 B（C）进程 A 和进程 B 同时结束（D）不一定27 考虑在一个虚拟页式存储管理的系统中，在地址变换过程中，进程状态可能发生的变化有( ) 。 进程被撤销 进程

13、变为阻塞（A）（B） （C） 和（D）都不可能28 在虚拟分页存储管理系统中，若进程访问的页面不在主存，且主存中没有可用的空闲帧时，系统正确的处理顺序为( )。（A）决定淘汰页页面调出缺页中断页面调入（B）决定淘汰页页面调入缺页中断页面调出（C）缺页中断决定淘汰页页面调出页面调入（D）缺页中断决定淘汰页页面调入页面调出29 下列关于 Belady 现象和工作集的说法正确的是( )。先进先出(FIFO)页面置换算法会产生 Belady 现象最近最少使用(LRU)页面置换算法会产生 Belady 现象为了保证进程高效地运行，它的工作集页面需要都在虚拟存储器内，否则会出现频繁的页面调入调出现象为了保

14、证进程高效地运行，它的工作集页面需要都在主存储器内，否则会出现频繁的页面调入调出现象（A）、（B） 、（C） 、（D）、30 某操作系统的文件管理采用直接索引和多级索引混合方式，文件索引表共有 10项，其中前 8 项是直接索引项，第 9 项是一次间接索引项，第 10 页是二次间接索引项，假定物理块的大小是 2KB，每个索引项占用 4B，假定一个文件的实际大小是 128MB，该文件实际占用磁盘空间为( )(包括索引表所占空间)。（A）128MB（B） 128MB+2KB（C） 128MB+256KB（D）128MB+258KB31 信息在外存空间的排列也会影响存取等待时间。考虑几个逻辑记录A、B

15、、C 、 、J，它们被存放于磁盘上，每个磁道存放 10 个记录，安排如表 42 所示。 假定要经常顺序处理这些记录，磁盘旋转速度为 20msr，处理程序读出每个记录后花 4ms 进行处理。考虑对信息的分布进行优化，如表 43 所示，相比之前的信息分布，优化后的时间缩短了( )。（A）60ms（B） 104ms（C） 144ms（D）204ms32 考虑单用户计算机上的下列 IO 操作，需要使用缓冲技术的是( )。图形用户界面下使用鼠标在多任务操作系统下的磁带驱动器(假设没有设备预分配)包含用户文件的磁盘驱动器使用存储器映射 IO，直接和总线相连的图形卡（A）、（B） 、（C） 、IV（D）全选

16、33 电路交换的优点有( )。传输时延小 分组按序到达无需建立连接 线路利用率高（A）、 （B） 、（C） 、（D）、34 以下几种 CSMA 协议中，( )协议在监听到介质是空闲时一定发送。1- 持续 CSMA p-持续 CSMA 非持续的 CSMA（A）只有（B） 、（C） 、（D）只有35 以下滑动窗口协议收到的分组一定是按序接收的( )。停止一等待协议 后退 N 帧协议 选择重传协议（A）、（B） 、 （C） 、（D）都有可能36 一个 IPv6 包中“通信量类”字段的值为 0，表明 ( )。（A）该包优先级最低，拥塞时可以被丢弃（B）该包优先级最高，拥塞时不能被丢弃（C）该包中没有用

17、户数据，只有首部（D）该包不可进行路由器转发37 以太网组播 IP 地址 224215145230 应该映射到组播 MAC 地址( )。（A）01005E 一 5791 一 E6（B） 0100 一 5ED791 一 E6（C） 01 一 005E 一 5B91E6（D）01 一 005E 一 5591E638 在 IP 首部的字段中，与分片和重组无关的字段是 ( )。总长度 标识 标志域 片偏移（A）仅（B）仅 、（C）仅 、（D）仅、39 以下字段中，TCP 首部和 UDP 首部都有的字段为( )。目标端口号 帧序号 源端口号 校验号（A）仅、（B）仅 、（C）仅 、（D）仅、40 ( )

18、可以将其管辖的主机名转换为该主机的 IP 地址。（A）本地域名服务器（B）根域名服务器（C）授权域名服务器（D）代理域名服务器二、综合应用题41-47 小题，共 70 分。40 设有 3 阶 B 一树，如图 1-4 所示。41 在该 B 一树上依次插入关键字 33 和 97。试画出两次插入后的 B-树。42 从(1)得到的 B-树上删除 66。试画出删除后的 B-树。42 设一个一维整数数组中有 n(n1)个元素，设计一个在时间和空间两方面尽可能高效的算法，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。要求：43 给出算法的基本设计思想。44 根据设计思想，采用 C、C+或 Ja

19、va 语言描述算法，关键之处给出注释。45 说明你所设计算法的时间复杂度和空间复杂度。45 通过对方格中每个点设置相应的 CMYK 值就可以将方格涂上相应的颜色。 以下 3 个程序段都可实现对一个 88 的方格涂上黄色的功能。假设Cache 的数据区大小为 512B，采用直接映射，块大小为 32B，存储器按字节编址，sizeof(int)=4。编译时变量 i 和 j 分配在寄存器中，数组 square 按行优先方式存放在000008COH 开始的连续区域中，主存地址为 32 位。要求：46 对 3 个程序段 A、B、C 中数组访问的时间局部性和空间局部性进行分析比较。47 画出主存中的数组元素

20、和 Cache 中行的对应关系图。48 计算 3 个程序段 A、B、C 中的写 Cache 操作次数、写 Cache 不命中次数和写Cache 缺失率。48 某微型计算机的寻址范围为 64KB，CPU 外接 8 片 8KB 的 RAM 芯片(片号从O 开始)，存储芯片的片选信号为 CS(低电平有效)。试回答以下问题：49 画出片选电路的逻辑图(允许使用译码器)。50 写出每片 RAM 的地址范围。51 如果运行时发现不论往哪片 RAM 芯片上写入 8KB 数据，以 6000H 为起始地址的 RAM 芯片上都会写入相同的数据，试分析故障的原因。52 如果运行时发现以 0000H 为起始地址的一片

21、存储芯片不能读写，试分析故障原因。53 若发现第 1、3、5、7 片 RAM 始终不被选中，试分析故障原因。54 下图中有 3 个进程 P0、P1 、P2 和 3 个缓冲区 B0、B1、B2。进程间借助于相邻缓冲区传递消息，即 Pi 每次从 Bi 取一条消息，经加工送入 B(i+1)mod3 中，B0、B1、B2 分别可存放 3、2、2 个消息，初始时，仅 B0 有一条消息，利用信号量机制解决 P0、P1 、P2 之间的同步及互斥关系。54 有如下的文件目录结构。55 可否进行下列操作，为什么?a)在目录 D 中建立一个文件，取名为 A；b)将目录 C 改名为 A。56 若 E 和 G 是两个

22、用户各自的目录，问：a)使用目录 E 的用户要共享文件 M，如何实现?b)在一段时间内，使用目录 G 的用户主要使用文件 S 和 T，应如何处置? 其目的是什么?57 使用目录 E 的用户与对文件 I 加以保护，不许别人使用，如何实现?57 一个公司有两个部门，研发部和市场部，研发部有 29 台计算机，市场部有 11台计算机。现在，公司申请了一个 C 类地址 212112320，规划的网络拓扑如图 1 一 5 所示。试问：58 请给出合理的子网规划，并说明理由，然后将规划填入表 1-3。59 根据第一题的规划，请为两个部门各分配一个子网网络地址，并为两个路由器的接口和各台计算机分配 IP 地址

23、。60 如果路由器 R1 和 R2 都采用了路由信息协议(Routing Information Protocol，RIP)作为路由选择协议，当稳定运行之后，R1 的路由表应该是怎样的?请填写表 1 一4。61 当路由器 R1 的接口 E0 断掉了，经过一次信息交互之后， R1 的路由表发生了怎样的变化?请填写表 1-5。计算机专业（基础综合）模拟试卷 65 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 ：由于线性表是用数组表示的(即顺序存储)，可以直接通过结点编号访问，所以 I

24、 的时间复杂度一定是 O(1)。：由于是在最后一个结点处插入一个结点，所以不需要移动元素，故时间复杂度为 O(1)。：删除第一个结点之后，需要将后续所有结点往前移动，所以时间复杂度为O(n)。：由于 i 是不固定的，后续结点 i+1，i+2， ，n 一 1 都需要向后移动，所以时间复杂度为 O(n)。2 【正确答案】 B【试题解析】 本题转化过程如图 4-4 所示。 由图 4-4 可以写出以下转化过程。 第一步：b+cbc+(假设 x=“bc+”) 第二步：a*xax*(假设 v=“ax*”) 第三步：ydvd- 将 xy 还原后得到：abc+*d 一。 补充知识点(1)：中缀表达式转换成后缀

25、表达式的另一种方式。 提示：可以通过手工加除括号来将中缀表达式转换成后缀表达式，其过程如下：先根据中缀表达式的求值次序加上括号，将右括号用相应的运算符替换，再除掉所有的左括号。 例如，中缀表达式“5+2*(1+6)-82”转换成后缀表达式的过程如下：手工判断该表达式的计算过程。首先肯定是先计算2*(1+6)，加上括号变为“5+(2*(1+6)-82”，再计算除法 82，加上括号变为“5+(2*(1+6)一(8 2)”，接着进行加法运算，加上括号变为“(5+(2*(1+6) 一(82)”，最后再进行减法运算，加上括号变为“(5+(2*(1+6)一(82)” 。运算符和右括号的对应关系如图 4-5

26、 所示，将右括号用对应的运算符替换，变为“(5(2(16+*+(8 2一”，最后除掉所有左括号得到的后缀表达式为“5 2 1 6+*+8 2-”。 注：本方法需要人工判断表达式的执行顺序(即加括号)，所以无法用程序实现。 按照以上方式可以很轻松地解题，不妨试着将中缀表达式a*(b+c)一 d 转换成后缀表达式。 第一步：进行乘法运算，加括号变为(a*(b+c)一d。 第二步：进行减法运算，加括号变为(a*(b+c)一 d)。 第三步：找出运算符和右括号的对应关系，将右括号用对应的运算符替换，变为(a(bc+*d-。 第四步：最后除掉所有左括号得到的后缀表达式为 abc+*d-。 补充知识点(2

27、)：怎么将后缀表达式转换成中缀表达式? 提示：当遇到数值的时候入栈，当遇到运算符的时候，连续两次出栈，将两个出栈元素结合运算符进行运算，将结果当成新遇到的数值入栈。如此往复，直到扫描到终止符“0”，此时栈底元素值即为表达式的值。 例：将后缀表达式 xy+z+转换为中缀表达式。 先将 x、y 入栈，遇到了“+” ，然后弹出栈顶的两个元素，即 x、y，然后对 x、y 做加法，现在将(x+y)的值入栈，然后 z 入栈，遇到了操作符+，所以最后的中缀表达式为：(x+y)+Z。 注意：中缀表达式转化成后缀或者是前缀，结果并不一定唯一。比如 ab+cd*+e同样是(a+b+c*d)e 的后缀式。后缀式和前

28、缀式都只有唯一的一种运算次序，而中缀式却不一定，后缀式和前缀式是由中缀式按某一种运算次序而生成的，因此对于一个中缀式可能有多种后缀式或者前缀式。例如，a+b+c 可以先算 a+b，也可以先算 b+c，这样就有两种后缀式与其对应，分别是 ab+c+和 abc+。3 【正确答案】 A【试题解析】 顺序表支持随机存储，链表不支持，因此顺序表输出第 i 个元素的值的时间复杂度为 O(1)，链表则为 O(n)，因此 A 正确。 交换第 1 个与第 2 个元素的值，对于顺序表和链表，时间复杂度均为 O(1)，因此B 不对。输出 n 个元素的值，两者时间复杂度均为 O(n)，因此 C 不对。输出与给定值 x

29、 相等的元素在线性表中的序号，对于顺序表和链表，count 需要搜索整个表，因此时问复杂度为 O(n)，因此 D 不对。【注】有的同学认为 B 也是正确的，其实严格来说 B 确实是对的，因为线性表交换要执行 3 次操作：temp=a1；a1=a2；a2=temp；而链表要执行 5 次：p=head-next；q=head-next-next；temp=p-data；p-data=q-data；q-data=temp，但本题是单选题的时候，考生需要选择更准确的一项，显然与 B 项相比，A 项更准确。4 【正确答案】 C【试题解析】 如果 k 没有左子女，则 k 的左指针即为指向 k 的中序前驱的

30、线索；当 k 有左子女时， k 的中序直接前驱结点是 k 的左子树中中序的最后一个结点，即从 k 的左子女开始沿右链走到右指针不再是右子女的结点为止，该结点即为 k 的中序前驱结点。 说明：上述二叉树的线索化算法其实考试中涉及的不多，本节在考试中涉及最多的是，在选择题中给你一棵二叉树，让你指出其中一个结点的线索按照某种线索化方法所应该指向的结点。 例如：请画出图 46 中按照中序线索化方法线索化后 E 结点的右线索的接连情况。 解决这类题的方法为，先写出题目所要求的遍历方式下的结点访问序列，根据此序列找出题目要求中结点的前驱和后继，然后连接线索。图 46 中二叉树的中序遍历序列为 D，B ，E

31、，A ，C 。结点 E 的前驱为 B，后继为 A，因此其右线索应该指向 A，结果如图 47 所示。总结：(1)引入二叉线索树的目的：加快查找结点的前驱或后继的速度。(2)二叉树在线索化后，仍不能解决的问题：后序线索二叉树中求后序后继。(3)n 个结点的线索二叉树上含有的线索树为 n+1。5 【正确答案】 C【试题解析】 根据题目所给的元素序列，可以得到以下的平衡二叉树，如图 4-8所示。 可以看出度为 2 的结点有 4 个。6 【正确答案】 D【试题解析】 考生一定需要知道做这种题目的正确思路，而不是在草稿纸上随意画一棵二叉树去套答案，因为有些题目是不可能通过举反例来验证的。解题思路：首先前序

32、序列和后序序列的遍历顺序分别为 TLR(根左右) 和 LRT(左右根)，然后分以下几种情况：(1)假设该二叉树只有一个根结点，此时前序序列和后序序列也算是相反，所以满足题意。但是空树比较特殊，不存在遍历的概念，无法给出解释，记住就行，所以 I 错误。(2)假设任意一个结点无左孩子，则前序的遍历变成 TR，后序的遍历变成 RT，恰好相反，所以该假设的二叉树成立。(3)假设任意一个结点无右孩子，则前序的遍历变成 TL，后序的遍历变成 LT，恰好相反，所以该假设的二叉树成立。综上所述，和都有可能。 提醒：如果此题为单项选择题，假设出现选项二叉树的高度等于结点的个数也是正确答案，因为这个答案把和的情况

33、都包括了。7 【正确答案】 B【试题解析】 寻找拓扑排序的步骤：(1)在有向图中选一个没有前驱的顶点并且输出。(2)从图中删除该顶点和所有以它为尾的弧。重复上述两步，直至全部顶点均已输出。由于没有前驱的顶点可能不唯一，所以拓扑排序的结果也不唯一。 题中所给图有 3 个不同的拓扑排序序列，分别为：1)a， b， c， e ， d。2)a， b， e， c ， d。3)a， e， b， c ， d。8 【正确答案】 B【试题解析】 图的一次深度优先搜索遍历，可以遍历完图中一个连通分量中所有的顶点。如果图是连通的，则图只含有一个连通分量，即图本身，这样一次深度优先搜索遍历即可遍历完图中所有顶点。因此

34、本题选 B。完全图相当于在连通图上加上了更严格的条件，即任意两个顶点间都存在边，对于满足本题的要求不需要完全图，条件达到连通图的强度就足够了。可能疑问点：有些考生可能认为 D 也正确，树难道不是连通图吗 ? 提示：树的类型有很多，相信选 D 的同学必定是思维定式，总是想着普通的无向树，这些树当然是连通图。但是，是否想过有向树?想必提到这个概念误选 D 的考生就会恍然大悟了，不再多做解释。补充：用深度优先算法遍历一个无环有向图，并在深度优先退栈返回时打印相应的顶点，则输出的顶点序列是逆拓扑有序。9 【正确答案】 B【试题解析】 中：m 阶 B 一树根结点至少有两棵子树，并且这两颗子树可以是空树，

35、其余结点至少有m2个分支，即m 2个子树，所以错误。 补充：B一树中每个结点至多有 m 棵子树，m 一 1 个关键字值。 中：每个结点中关键字的个数比分支数少 1，m 阶 B 一树的一个结点中至多有 m 个分支，因此至多有m1 个关键字，所以正确。 中：B 一树是平衡的多路查找树，叶子结点均在同一层上，所以正确。 中：发生结点分裂的时候不一定会使树长高。比如向图 4-9 中的 B 一树插入一个关键字 10 变成图 4 一 10 中的 B 一树，使得第二层右端的一个结点分裂成两个，但是树并没有长高，所以错误。 综上所述，、正确。10 【正确答案】 B【试题解析】 这种题目其实就是考查考生的记忆能

36、力，因为在考研紧张的氛围下，很少有考生在做这种选择题的时候能够分析其算法来选择答案。下面与大家分享一个记忆总结，该总结可以将内部排序所有的记忆性题目轻轻松松地拿下。由以下总结可以很轻松地得到答案 B。 稳定性、时间复杂度、空间复杂度总结： (1)稳定性总结：一句话解决：本人考研无聊中，那么就快(快速排序)些(些和希尔谐音，希尔排序)选 (选择排序 )堆(堆排序 )来聊!这里面都是不稳定的，其他的就自然都是稳定的了。 (2)时间复杂度总结： 1)在军训的时候，教官说了一句话：快(快速排序)些(希尔排序)以 nlogn 的速度归 (归并排序)队(堆排序)!在这句话里面包含的排序，时间复杂度都是 O

37、(nlogn)1 2)冒泡冒得好就是 O(n)，冒泡冒得不好就是 O(n2)。 3)直接插插得好就是 O(n)，插得不好就是 O(n2)，其中插得好、冒得好分别对应最好的时间复杂度，插得不好、冒得不好分别对应最坏时间复杂度，而平均时间复杂度对应最坏的时间复杂度。 (3)辅助空间总结：只需记住几个特殊的就好，归并 O(n)、快速O(log2n)、基数排序 O(r+d)，其他的就自然全部是 O(1)了。11 【正确答案】 A【试题解析】 不妨设采用 m 路归并，则至少需要 m 个输入缓冲区和 1 个输出缓冲区。因为一个缓冲区对应一个文件，所以 m+1=15，解得 m=14，所以可做 14 路归并。

38、假设需要 s 趟可以完成排序，则 s=log 1480=2。12 【正确答案】 D【试题解析】 此种题型已经在 2012 年真题中考查过。 首先，求得-8196 的补码表示为 1101 1111 1111 1100，赋值给 usi 后，由于 usi 为无符号数，所以将二进制1101 1111 1111 1100 转换为十进制为 57 340。 技巧：FFFFH 的二进制为 65 535，应该记住。然后减去 3 个 0 对应的权值，分别为 8192、2、1，即最后的结果为 65 53581922 一 1=57 340。13 【正确答案】 B【试题解析】 最大数、最小数及规格化浮点数的二进制表示如

39、表 45 所示。分析： (1)最大数的二进制表示：首先要使得数最大，很明显前面 2 的次方必须是最大的，自然就想到 01111111，后面的尾数也尽量离 1 最近，自然想到011111111111111111111111。 (2)最小数的二进制表示：首先要使得数最小，很明显前面 2 的次方必须是最大的，自然就想到 01111111，后面的尾数也尽量离-1最近，因为越近和前面的指数乘起来就会越远离 0。而补码又恰好可以取到-1，那就肯定是选择-1 了，自然就想到 1 00000000000000000000000。 (3)规格化形式范围其实和(1)(2)的情况类似，这里只讲一个比较难理解的，即规

40、格化最大负数。首先不考虑规格化的事情，要使得一个数是最大的负数，也就是离 0 越近越好，所以自然想到 2 的指数越小越好，既然是补码，自然就想到最小的数-128，所以阶码应该是 10000000，尾数也应该离 1 最近，现在的离 1 最近就不能随便选了，因为是要选择满足规格化的前提下离 1 最近的数字。而规格化要求 12s1，所以 s应当取得-1 2 才是最理想的，但是-12 不是规格化数，所以退一步，加一个最小的数，也就是 2-23，得到所要的结论。 考生看完此总结以后，应当能马上写出任何位数以补码形式表示的规格化浮点数的范围，不是补码也没有关系，只要知道此X 码能够表示数的范围就好了，思路

41、都是一致的。14 【正确答案】 D【试题解析】 首先，需要判断 1KB 数据是否需要存储到多个磁道上。7200r/min=120r/s；因为传输速率为 10MBs，故每转容量为： ，所以1KB 的数据只要在一个磁道上就能存储下了，无须换道。其次，写数据时间= 磁盘启动时间+磁盘寻道时间+旋转等待时间+ 数据传输时间。旋转等待时间为旋转半圈的时间，即(607200)12=417ms；数据传输时间等于1KB 10MBs=0 1ms ，所以写 1KB 数据的时间为：2ms+12ms+417ms+0 1ms=18 27ms。 可能疑问点：计算机网络高分笔记不是说在通信领域 K 取 1000，在计算机领

42、域 K 取 1024 吗?此道题目中 1KB 应该是属于计算机领域，为什么取值 1000? 提示：计算机网络高分笔记给出的是最一般的理解的方式，不是绝对的。至于 K 到底取多少，至今没有统一标准。笔者根据经验总结出两点： (1)如果在考试中遇到，K 取多少，就看约分，考研的答案一定是最简化的，肯定可以约分，哪个好约分取哪个。如果分子和分母都有 K 那就最好了。 (2)如果实在不放心，可以参考教育部针对真题的解释，看看他们取值多少，照着取即可。15 【正确答案】 B【试题解析】 ：静态 RAM 和动态 RAM 都是易失性存储器，断电后信息都会遗失，所以错误。：PROM 的内部有行列式的熔丝，视需

43、要利用电流将其烧断，写入所需的资料，但仅能写录一次。PROM 在出厂时，存储的内容全为 1，用户可以根据需要将其中的某些单元写入数据 0(部分的 PROM 在出厂时数据全为 0，则用户可以将其中的部分单元写入 1)，以实现对其“编程”的目的，所以正确。：EPROM 是可改写的，但它不属于随机存储器，所以错误。：(电可擦可编程只读存储器，Electrically Erasable Programmable Read-Only。Memory，EEPROM)属于一种掉电后数据不丢失的存储芯片。EEPROM可以在计算机上或专用设备上擦除已有信息，重新编程，所以正确。16 【正确答案】 D【试题解析】

44、题目很长，首先需要弄清题目的意思。题目告诉了时钟周期、速率以及读和写操作各自花的时钟周期数，所要求的是存储器的最大带宽，也就是单位时间内传输的有效信息量。计算过程如下 ： 读操作的时间为 Tr=(1+3+8)20ns=240ns 写操作的时间为 Tw=(1+2+8+3)20ns=280ns 则综合加权的时间为 240ns035+280ns0 65=266ns 带宽为(也就是 266ns 可以传输 8 个字，或者说传输 32B) Bn=32B(26610 -9)1203MB s17 【正确答案】 B【试题解析】 这里、应该没有什么疑问，在一般指令中都可以见到(对应 RR、RS、SS 指令)，主要

45、解释一下 。首先，采用栈项和次栈顶的物理位置在执行上是可行的，但是这样的指令容易受到不确定性的影响。举例来说明：一个这样的指令在执行完毕之后，得到的结果必然还是要存入到栈顶(二地址指令存数地址也由其中一个地址指定)，在这个结果被使用之前，如果有其他的指令又进行了栈操作(仍比如存数吧) ，这样就导致栈顶操作数变化，于是就造成了后续指令执行的错误。这种情况当然可以避免，但是会对编制程序造成很大的限制，因此在实际中不予采用。但是，一般来说零地址指令的操作数是来自堆栈和次堆栈，记住就好。18 【正确答案】 B【试题解析】 对于选项：如果 12 个微操作都相容的话，最多可以同时启动 12个微操作，故正确

46、。对于选项：首先，如果要同时启动 3 个微操作，那么这 3个微操作必须是相容的，所以要将控制字段分为 3 段，也就是每段占 4 位，故错误。对于选项：由的分析可知，由于每段占 4 位，每个字段可表示 15 种状态(保留一个状态表示不发微命令)，那么一共就可以表示 45 个状态，故正确。19 【正确答案】 D【试题解析】 当子程序调用 CALL 指令时，首先需要将程序断点(PC 的值)保存在堆栈中，然后将 CALL 指令的地址码送入 PC。因为指令为双字长，所以取出CALL 指令后，PC 的值需要加 2，即 1002H。当 CALL 指令执行后，程序断点1002H 进栈，此时 SP=00FFH(

47、因为进栈操作需要将 SP 的值减 1，即 0100H-0001H=00FFH)，栈项内容为 1002H。20 【正确答案】 B【试题解析】 根据题意可以看到，在此流水线中顺序执行 50 条指令用了 203t(正常情况下如果第 3 步的执行时间为t ，则执行 50 条指令只需要 4+(501)At=53At)，所以流水线的瓶颈必定是第 3 步。 补充：对于包含瓶颈段的指令流水线，不妨设流水线共有 k 段，且需要执行 n 条指令，则总的执行时间为 i=1ktt+(n1)maxt1，t 2，t k 根据上述公式，假定流水线中第 3 步的执行时间为 S，该指令流水线顺序执行 50 条指令所用的时间为t

48、+ t+S+t+(501)maxt,t,S,t=203t，解得 S=4t，即第 3 步的执行时间为 4t。21 【正确答案】 A【试题解析】 需要清楚的是，总线的宽度不是地址总线的位数，也不是控制总线的位数，而是数据总线的位数，所以此题总线的宽度应该是 32bit。而总线的传输速率为总线的工作频率乘以总线宽度，即 66MHz32bit=66MHz4B=264MBs。22 【正确答案】 B【试题解析】 当有多个中断请求同时出现时，中断服务系统必须能从中选出当前最需要给予响应的最重要的中断请求，这就需要预先对所有的中断进行优先级排队，这个工作可由中断优先级判断逻辑来完成，排队的规则可由软件通过对中断屏蔽寄存器进行设置来确定。2