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

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

2、bcd3 设线性表有 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，1

3、5，23，44，34，74，45，26 ，按次序插入每个元素生成一棵平衡二叉树，那么最后得到的平衡二叉树中度为 2 的结点个数为( )。（A）1（B） 3（C） 4（D）56 由 23、12、45、36 构成的二叉排序树有( )个，其中 AVL 树有( )个。（A）13；4（B） 13；5（C） 14；5（D）14；47 对图 41 进行拓扑排序，可以得到不同的拓扑序列的个数是( )。（A）4（B） 3（C） 2（D）18 无向图 G 有 16 条边，有 3 个度为 4 的顶点，4 个度为 3 的顶点，其余顶点的度均小于 3，则 G 至少有( )个顶点。（A）10（B） 11（C） 12（D）

4、139 以下有关 m 阶 B树的说法中正确的有( )。每个结点至少有两棵非空子树树中每个结点至多有 m1 个关键字所有叶子在同一层上当插入一个数据项引起 B树结点分裂后，树长高一层（A）仅、（B）仅 、（C）仅 、（D）仅、10 对以下关键字序列用快速排序进行排序，速度最慢的是( )。（A）19 ，23 ，3，15，7，21，28（B） 23，21，28，15，19，3，7（C） 19，7，15，28，23，21，3（D）3 ，7， 15，19，21，23，2811 某个文件经内部排序得到 80 个初始归并段。如果操作系统要求一个程序同时可用的输入/输出文件的总数不超过 15 个，则按多路归并

5、至少需要 ( )趟可以完成排序。（A）2（B） 3（C） 4（D）512 考虑以下 C 语言代码：vc short si=8196；unsingned short usi=si；执行上述程序段后，usi 的值为( )。（A）8196（B） 34572（C） 57339（D）5734013 设浮点数的阶码用移码表示，尾数用补码表示，阶码的底数为 2，阶码用 3 位表示（包含一位符号位），尾数用 5 位表示（包含 1 位符号位），则它能表示的最小负数为( )。（A）8（B） 75（C） 128（D）25614 硬盘平均寻道时间为 12ms，传输速率为 10MB/s，磁盘控制器延时为 2ms，则一个

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

7、：1 个周期接受地址，3 个周期延迟，8 个传输周期传输8 个字；写操作所花的时间是：1 个周期接受地址，2 个周期延迟，8 个周期传输 8个字，3 个周期恢复和写入纠错码，则当系统以 35为读操作，65为写操作的访问情况工作，则存储器最大带宽为( )。（A）1332MB/s（B） 1144MB/s（C） 126MB/s（D）1203MB/s17 以下是一段指令序列：1 addi R1，20 (R1)202 1w R2， R0 ，12 (R2)M(12+(R0)3 add R3，R1，R2 (R3)(R1)+(R2)以上指令序列中，假定采用“取指、译码/取数、执行、访存、写回”这种五段流水线方

8、式，那么在采用“ 转发 ”技术时，需要在第 3 条指令之前至少加入 ( )条空操作(nop)指令，才能使这段程序不发生数据冒险。（A）0（B） 1（C） 2（D）318 某计算机采用微程序控制，微指令字中操作控制字段共 12 位，下列说法正确的是( )。若采用直接控制，则此时一条微指令最多可同时启动 11 个微操作若采用字段直接编码控制，并要求一条微指令需同时启动 3 个微操作，则微指令字中的操作控制字段应分 6 段若采用字段直接编码控制，并要求一条微指令需同时启动 3 个微操作，每个字段的微命令数相同，这样的微指令格式最多可包含 45 个微操作命令（A）仅、（B）仅 、（C）仅 、（D）、和

9、19 一条双字长直接寻址的子程序调用 CALL 指令，其第一个字为操作码和寻址特征，第二个字为地址码 5000H。假设 PC（程序计数器）当前值为 1000H，SP 的内容为 0100H，栈顶内容为 1234H，存储器按字编址，而且进栈操作是先(SP)1SP，后存入数据。则 CALL 指令执行后，SP 及栈顶的内容分别为( )。（A）00FFH，1000H（B） 0101H，1000H（C） 00FEH，1002H（D）00FFH，1002H20 指令流水线将一条指令的执行过程分为 4 步，其中第 1、2 和 4 步的执行时间为t，如图 42 所示。若该流水线顺序执行 50 条指令共用了 20

10、3At（无需考虑相关问题），则该流水线的第 3 步的执行时间是( )。（A）3t（B） 4t（C） 5t（D）6t21 某总线总共有 88 根信号线，其中数据总线为 32bit，地址总线为 20bit，控制总线为 36 根，总线的工作频率为 66MHz，则总线宽度为( )，传输速率为( )。（A）32bit 264MB/s（B） 20bit 264MB/s（C） 32bit 254MB/s（D）20bit 264MB/s22 指令( ) 从主存中读出。（A）总是根据程序计数器(PC)（B）有时根据 PC，有时根据转移指令（C）根据地址寄存器（D）有时根据 PC，有时根据地址寄存器23 在操作系

11、统中，用户在使用 I/O 设备时，通常采用( )。（A）物理设备名（B）逻辑设备名（C）虚拟设备名（D）设备序号24 考虑下面的基于动态改变优先级的可抢占式优先权调度算法。大的优先权数代表高优先级。当一个进程在等待 CPU 时（在就绪队列中，但未执行），优先权以 速率改变；当它运行时，优先权以 p 速率改变。所有的进程在进入就绪队列被给定优先权数为 O。参数 a 和 p 可以设定给许多不同的调度算法。下列( )设定可以实现进程 FIFO (First In First Out)。（A）0（B） 0（C） 0（D）025 假设系统有 5 个进程，A、B、C 三类资源。某时刻进程和资源状态如表 4

12、1所示。下面叙述正确的是( )。（A）系统不安全（B）该时刻，系统安全，安全序列为P1，P2 ，P3，P4，P5 （C）该时刻，系统安全，安全序列为P2，P3 ，P4，P5，P1 （D）该时刻，系统安全，安全序列为P4，P5 ，P1 ，P2，P326 设有一个发送者进程和接收者进程，其流程图如图 43 所示。S 是用于实现进程同步的信号量，mutex 是用于实现进程互斥的信号量。试问流程图中的A、B、C 、D4 个框中应填写什么？假定缓冲区有无限多个且初始为空，S 和mutex 的初值应该是什么？( )（A）P(mutex) 、V(mutex)、P(S)、P(mutex) S= 缓冲区的个数

13、mutex=1（B） P(S)、V (mutex)、P(S)、P(mutex) S=0 mutex=1（C） P(mutex)、V(mutex) 、P(S) 、P(mutex) S=0 mutex=1（D）P(S)、V(mutex)、P(S)、P(mutcx) S=缓冲区的个数 mutex=027 考虑在一个虚拟页式存储管理的系统中，在地址变换过程中，进程状态可能发生的变化有( ) 。进程被撤销进程变为阻塞（A）（B） （C） 和（D）都不可能28 在虚拟分页存储管理系统中，若进程访问的页面不在主存，且主存中没有可用的空闲帧时，系统正确的处理顺序为( )。（A）决定淘汰页页面调出缺页中断页面调

14、入（B）决定淘汰页页面调入缺页中断页面调出（C）缺页中断决定淘汰页页面调出页面调入（D）缺页中断决定淘汰页页面调入页面调出29 下列关于 Belady 现象和工作集的说法正确的是( )。先进先出(FIFO)页面置换算法会产生 Belady 现象最近最少使用(LRU) 页面置换算法会产生 Belady 现象为了保证进程高效的运行，它的工作集页面需要都在虚拟存储器内，否则会出现频繁的页面调入/调出现象为了保证进程高效的运行，它的工作集页面需要都在主存储器内，否则会出现频繁的页面调入/调出现象（A）、（B） 、（C） 、（D）、30 某文件系统物理结构采用三级索引分配方法，如果每个磁盘块的大小为10

15、24B，每个盘块索引号占用 4B，请问在该文件系统中，最大的文件大小最接近的是( )。（A）8GB（B） 16GB（C） 32GB（D）2TB31 信息在外存空间的排列也会影响存取等待时间。考虑几个逻辑记录A、B、C 、 、J，它们被存放于磁盘上，每个磁道存放 10 个记录，安排如表 42 所示。假定要经常顺序处理这些记录，磁盘旋转速度为 20ms/r，处理程序读出每个记录后花 4ms 进行处理。考虑对信息的分布进行优化，如表 43 所示，相比之前的信息分布，优化后的时间缩短了( )。（A）60ms（B） 104ms（C） 144ms（D）204ms32 考虑单用户计算机上的下列 I/O 操作

16、，需要使用缓冲技术的是( )。图形用户界面下使用鼠标在多任务操作系统下的磁带驱动器（假设没有设备预分配）包含用户文件的磁盘驱动器使用存储器映射 I/O，直接和总线相连的图形卡（A）、（B） 、（C） 、（D）全选33 假定运行发送窗口大小为 5 和接收窗口大小为 3 的滑动窗口算法，并且在传输过程中不会发生分组失序的问题，帧序号的编码至少有( )位。（A）2（B） 3（C） 4（D）534 以下几种 CSMA 协议中，什么协议在监听到介质是空闲时一定发送( )。1持续 CSMA.p 一持续 CSMA.非持续的 CSMA（A）只有（B） 、（C） 、（D）只有35 10 个站点连接到一个 10M

17、bit/s 的以太网交换机上，下面说法正确的是 ( )。（A）每个站点共享 10Mbit/s（B）每个站点都独享 1Mbit/s（C）每个站点共享 1Mbit/s（D）每个站点都独享 10Mbit/s36 个 IPv6 包中“通信量类”字段的值为 0，表明 ( )。（A）该包优先级最低，拥塞时可以被丢弃（B）该包优先级最高，拥塞时不能被丢弃（C）该包中没有用户数据，只有首部（D）该包不可进行路由器转发37 以太网组播 IP 地址 224215，145230 应该映射到组播 MAC 地址( )。（A）01005E5791E6（B） 01005ED791E6（C） 01005E5B91E6（D）0

18、1005E5591E638 在 IP 首部的字段中，与分片和重组无关的字段是 ( )。总长度标识标志域片偏移（A）仅（B）仅 、（C）仅 、（D）仅、39 以下字段中，TCP 首部和 UDP 首部都有的字段为( )。目标端口号帧序号源端口号校验号（A）仅、（B）仅 、（C）仅 、（D）仅、40 路由汇聚是把小的子网汇聚成大的网络，下面 4 个子网：172161930/24、172161940/24、172161960/24、172161980/24，进行路由汇聚后的网络地址是( )。（A）172161920/21（B） 172161920/22（C） 172162000/22（D）172162

19、240/20二、综合应用题41-47 小题，共 70 分。40 表 51 给出了某工程各工序之间的优先关系和各工序所需的时间（其中“ ” 表示无先驱工序），请完成以下各题：41 画出相应的 AOE 网。42 列出各事件的最早发生时间和最迟发生时间。43 求出关键路径并指明完成该工程所需的最短时间。43 输入一个按升序排序过的整数数组1、2、4、7、11、15 以及一个整数数字15，我们可以从该数组中找到两个数字，即 4 和 11，使得 4+11=15。请实现一个时间上尽可能高效率的算法，当输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们的和正好是输入的那个整数数字

20、。如果有多对数字的和等于输入的整数数字，输出任意一对即可。要求：44 给出算法的基本设计思想。45 根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。46 说明你所设计算法的时间复杂度。46 某高级语言程序中的一个 while 语句为“while(savei=k) i+=1 ；”，若对其编译时，编译器将 i 和 k 分别分配在寄存器 s3 和 s5 中，数组 save 的基址存放在 s6 中，则生成的 MIPS 汇编代码如下：loop: sll t1，s3， 2 #R tlR s3 2，即 R t1=i*4add t1， t1， s6 #R t1R t1+R s6

21、，即 R t1 =Address of save it0， 0 (t1) #R t0M R t1 +0， gp Rt0 =save ibne . t0，s5f exit #if Rt0Rs5 then goto exitaddi s3， s3，1 #R s3R s3+1，即 i=i+lj loop #goto loopexit；假设从 loop 处开始的指令序列存放在内存 80000 处，则上述循环对应的 MIPS 机器码如图 51所示。根据上述叙述，回答下列问题，要求说明理由或给出计算过程。47 MIPS 的编址单位是多少？数组 save 每个元素占几个字节？48 为什么指令“sll t1，

22、s3，2”能实现 4*i 的功能？49 t0 和 s6 的编号各为多少？50 指令“jloop”的操作码是什么？（用二进制表示）51 标号 exit 的值是多少？如何根据指令计算得到？52 标号 loop 的值是多少？如何根据指令计算得到？52 假设某计算机的主存地址空间大小为 64KB，采用字节编址方式。其 Cache 数据区容量为 4KB，采用 4 路组相联映射方式、LRU 替换和回写(write back)策略，块大小为 64B，并且每块设置了 1 位有效位。请问：53 主存地址字段如何划分？要求说明每个字段的含义、位数和在主存地址中的位置。54 该 Cache 的总容量有多少位？55

23、若 Cache 初始为空，CPU 依次从 0 号地址单元顺序访问到 4344 号单元，重复按此序列共访问 16 次。若 Cache 命中时间为 20ns，主存存取时间为 200ns，试估计 CPU 访存的平均时间。55 在下列代码中，有 3 个进程 Pl、P2 和 P3，它们使用了字符输出函数 putc 来进行输出（每次输出一个字符），并使用了两个信号量 L 和 R 来进行进程间的同步。请问：56 这组进程在运行时，最后打印出来了多少个“D”字符？57 当这组进程在运行的时候，在何种情形下，打印出来的字符“A“的个数是最少的，最少的个数是多少？58 当这组进程在运行的时候，“CABABDDCA

24、BCABD”是不是一种可能的输出序列，为什么？59 当这组进程在运行的时候，“CABACDBCABDD”是不是一种可能的输出序列，为什么？semaphore L=3，R=0 ； /*初始化*/*进程 P1*/ /+进程 P2*/ /*进程 P3*/while(1) while (1) while (1) P(L)； P(R)； P(R)；putc(C)； putc(A)； putc(D)；V (R)； putc(B)； V(R)；59 某操作系统支持页式虚拟存储管理，其中央处理器的周期是 1s。当不是处于同一页面时，访问另一个页面耗时 1s。一个页面含 1K 字。使用磁盘作为外存，其转速为 3

25、 000r/min，传输率 1M 字/s。还测得下列数据：磁盘平均寻道时间为19ms， 1的指令要访问不处于同一页面的其他页面内容，这当中，80的被访问页已经在内存中。需要新页面时，50的被换出页面已经修改过了。60 如果磁盘设备要连续传输 10K 字的数据，请计算出平均情况下总的访问时间。61 请计算该系统的有效指令时间，假设系统只有一个 CPU，而且它在磁盘传输数据时是空闲的。（假设逻辑相邻的页面在磁盘上都不相邻。）61 某单位有 1 个总部和 6 个分部，各个部门都有自己的局域网。该单位申请了 6个 C 类 IP 地址 202115 100/24202115150/24 ，其中总部与分部

26、 4 共用一个 C 类地址。网络采用 R1R7 共 7 台路由器，采用动态路由协议 OSPF，并划分了 3 个 OSPF 区域。网络拓扑图如图 52 所示，路由器的 lP 地址分配见表52。62 请指出本网中哪个区域为主干区域，以及指出主干区域中的区域边界路由器及区域内路由器。63 R3 路由器各端口 IP 地址如何设置？64 如部门 4 共有 110 台计算机，通过交换机连接路由器 R5 接入网络。其中一台计算机 IP 地址为 202115135，试给出其子网掩码和网关地址。计算机专业（基础综合）模拟试卷 100 答案与解析一、单项选择题1-40 小题，每小题 2 分，共 80 分。下列每题

27、给出的四个选项中，只有一个选项是最符合题目要求的。1 【正确答案】 C【试题解析】 ：由于线性表是用数组表示，即顺序存储，可以直接通过结点编号访问，所以的时间复杂度一定是 O(1)。：由于是在最后一个结点处插入一个结点，所以不需要移动元素，故时间复杂度为 O(1)。：删除第一个结点之后，需要将后续所有结点往前移动，所以时间复杂度为O(n)。：由于 i 是不固定的，所以后续结点 i+1，1+2，n1，都需要向后移动，所以时间复杂度为 O(n)。2 【正确答案】 B【试题解析】 本题转化过程如图 45 所示。 由图 45 可以写出以下转化过程：第一步：b+cbc+（假设 x=“bc+”）第二步：a

28、 *xax *（假设 y=“ax*”）第三步：ydyd将 xy 还原后得到：abc+ *d。补充知识点(1):中缀表达式转换成后缀表达式的另一种方式。解析：可以通过手工加上、除掉括号来将中缀表达式转换成后缀表达式，其过程如下：先根据中缀表达式的求值次序加上括号，将右括号用相应的运算符替换，再除掉所有的左括号。例如，中缀表达式“5+2*(1+6) 8/2”转换成后缀表达式的过程如下：手工判断该表达式的计算过程。首先肯定是先计算 2*(1+6)，加上括号变为“5+(2 *(1+6)8/2”，再计算除法 8/2，加上括号变为“5+（2 *（1+6） (8/2)”，接着进行加法运算，加上括号变为“(5

29、+(2*(1+6)一(8/2)”，最后再进行减法运算，加上括号变为“(5+(2 *(1+6)一(8/2)”。运算符和右括号的对应关系如图 4.6 所示，将右括号用对应的运算符替换，变为“（5（2（16+ *+（8 2/一 ”，最后除掉所有左括号得到的后缀表达式为“5216+*+82/一 ”。 注：本方法需要人工判断表达式的执行顺序（即加括号），所以无法用程序实现。一此方法引自李春葆老师的书籍按照以上方式可以很轻松地解题，不妨试着将中缀表达式 a*(b+c)d 转换成后缀表达式。第一步：进行乘法运算，加括号变为：(a *(b+c)一 d。第二步：进行减法运算，加括号变为：(a *(b+c)一 d

30、）。第三步：找出运算符和右括号的对应关系，将右括号用对应的运算符替换，变为（a（bc+ *d 一。第四步：最后除掉所有左括号得到的后缀表达式为：abc+ *d。补充知识点(2):怎么将后缀表达式转换成中缀表达式？解析：当遇到数值的时候入栈，当遇到运算符的时候，连续两次出栈，将两个出栈元素结合运算符进行运算，将结果当成新遇到的数值入栈。如此往复，直到扫描到终止符“0”，此时栈底元素值即为表达式的值。例：将后缀表达式xy+z+转换为中缀表达式。先将 x、y 入栈，遇到了+，然后弹出栈顶的 2 个元素，即 x、y，然后对 x、y 做加法，现在将(x+y)的值入栈，然后 Z 入栈，遇到了操作符+，所以

31、最后的中缀表达式为：(x+y)+z。注意：中缀表达式转化成后缀或者是前缀，结果并不一定唯一。比如 ab+c d*+e/同样是(a+b+c *d)/e 的后缀式。后缀式和前缀式都只有唯一的一种运算次序，而中缀式却不一定，后缀式和前缀式是由中缀式按某一种运算次序而生成的，因此对于一个中缀式可能有多种后缀式或者前缀式。比如 a+b+c 可以先算 a+b 也可以先算 b+c，这样就有两种后缀式与其对应，分别是 ab+c+和 abc+。例：下列关于后缀表达式的比较中，结果为“假”的是( )。. xy+z+=xyz+ . xy+z=xyz-+xyz+=xyz+xyz =xyz-AB、C、D、C。本题考查后

32、缀表达式。：xy+z+=xyz+转换成中缀表达式为(x+y)+z=x+(y+z)，比较结果为“真”。：xy+z=xyz+转换成中缀表达式为(x+y)一 z=x+(yz)，比较结果为“真”。：xyz+=xyz+转换成中缀表达式为(xy)+z=x 一(y+z)，比较结果为“假。：xyz =xyz-转换成中缀表达式为(Xy)一 z=x 一(yz)，比较结果为“假”。综上所述，、为假。3 【正确答案】 A【试题解析】 顺序表支持随机存储，链表不支持，因此顺序表输出第 i 个元素的值的时间复杂度为 O(1)，链表则为 O(n)，因此 A 正确。交换第 1 个与第 2 个元素的值，对于顺序表和链表，时间复

33、杂度均为 O(1)，因此B 不对。输出 n 个元素的值，两者时间复杂度均为 O(n)，因此 C 不对输出与给定值 x 相等的元素在线性表中的序号，对于顺序表和链表，count 需要搜索整个表，因此时间复杂度为 O(n)，因此 D 不对。【注】 有的同学认为 B 也是正确的，其实严格来说 B 确实是对的，因为线性表交换要执行 3 次操作：temp=a 1 ；a 2=temD；而链表要执行 5 次：p=headnext ；q=headnextnext；temp=pdata；pdata=qdata ；qdata=temp；但本题是单选题的时候，考生需要选择更准确的一项，显然与 B 项相比，A 项更准

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

35、序列找出题目要求中结点的前驱和后继，然后连接线索。图 47 中二叉树的中序遍历序列为D，B，E ，A，C。结点 E 的前驱为 B，后继为 A，因此其右线索应该指向 A，结果如图 48 所示。总结：(1)引入二叉线索树的目的：加快查找结点的前驱或后继的速度。(2)二叉树在线索化后，仍不能解决的问题：后序线索二叉树中求后序后继。(3)n 个结点的线索二叉树上含有的线索树为： n+1。5 【正确答案】 C【试题解析】 根据题目所给的元素序列，可以得到以下的平衡二叉树，如图 49所示。 可以看出度为 2 的结点有 4 个。6 【正确答案】 C【试题解析】 该题的结点不多，可以采用枚举法。但枚举法比较容

36、易造成遗漏，所以在枚举时要按照一定的规律，而且在枚举完之后看是否有重合的树并将其去掉，为避免重复可以采用根结点来枚举，枚举得二叉排序树共有 14 个，其中 5 个为AVL 树。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【试题解析】 度的定义

37、指的是进入一个顶点的边数和从该顶点出去的边数之和。我们可以根据这个关系来求解此题。由于题目已经告诉度为 4 的顶点有 3 个，度为3 的顶点有 4 个，其余的顶点的度均小于 3，而已知有 16 条边，则总的度数应为162=32。所以要求最小的顶点个数，我们应当尽量增加每个顶点的度数，这里将剩下的结点的度数全部看成 2，设结点数为 x，则 34+43+(x34)232，解得x 至少为 11。补充：解这题的过程中，我们是从假设剩下的结点的度数为 2 来考虑的，这样才能最大程度地减小结点的个数。这其实用到了一种称为贪心的思想，这是一种很重要的思想，每次决策的时候都是按照最有利的情况去考虑。这种思想在

38、其他几门课程当中也会有体现，读者应自己去发现和总结。9 【正确答案】 B【试题解析】 中：m 阶 B树根结点至少有两棵子树，并且这两颗子树可以是空树，其余结点至少有m/2个分支，即m/2 个子树，所以 错误。补充：B树中每个结点至多有 m 棵子树，m1 个关键字值。中：每个结点中关键字的个数比分支数少 1，m 阶 B树的一个结点中至多有 m 个分支，因此至多有 ml 个关键字，所以正确。中：B树是平衡的多路查找树，叶子结点均在同一层上，所以正确。中：发生结点分裂的时候不一定会使树长高。比如向图 410 中的B树插入一个关键字 10 变成图 411 中的 B树，使得第二层右端的一个结点分裂成两个

39、，但是树并没有长高，所以错误。综上所述，、正确。10 【正确答案】 D【试题解析】 这种题目其实就是考查考生的记忆能力，因为在考研紧张的氛围下，很少有考生在做这种选择题的时候能够分析其算法来选择答案。这里就是变相地考查快速排序算法的最坏情况。快速排序法的最坏情况为待排序列是有序或接近有序的时候，由于 D 中元素已经有序，所以选择 D。评注：本题是指定了使用某种排序方法，当题目中没有指定具体的排序方法的时候，我们一定不要急于挨个用每个算法去试，而应该从所给的待排序列出发，观察序列元素的信息，找出某种特殊的性质。11 【正确答案】 A【试题解析】 不妨设采用 m 路归并，则至少需要 m 个输入缓冲

40、区和 1 个输出缓冲区。因为一个缓冲区对应一个文件，所以 m+1=15，解得 m=14，所以可做 14 路归并。假设需要 s 趟可以完成排序，则 s=log1480=2。12 【正确答案】 D【试题解析】 首先，求得8196 的补码表示为 1 101 1 1 1 1 1 1 1 1 1 100，赋值给usi 后，由于 usi 为无符号数，所以将二进制 1101 1111 1111 1100 转换为十进制为57340。技巧：FFFFH 的二进制应该记住，为 65535。然后减去 3 个 0 对应的权值，分别为 8192、2、1，即最后的结果为 65535819221=57340。13 【正确答案

41、】 A【试题解析】 要求最小负数，按照浮点数的格式来看，我们要尽量使尾数最小，达到补码所能表示的最小的负数，另外还要使阶码最大，达到移码所能表示的最大整数，而由补码的性质可知，无论对于尾数多少位来说，尾数的最小值永远是一1，阶码最大为 3。故最小的负数为8。14 【正确答案】 D【试题解析】 首先，需要判断 1KB 数据是否需要存储到多个磁道上。7200r/min=120r/s；因为传输速率为 10MB/s，故每转容量为： ，所以 1KB 的数据只要在一个磁道上就能存储下了，无须换道。其次，写数据时间=磁盘启动时间+ 磁盘寻道时间+ 旋转等待时间+数据传输时间。旋转等待时间为：旋转半圈的时间，

42、及( 60/7200)1/2=4.17ms；数据传输时间等于lKB/10MB/s=0.1ms，所以写 1KB 数据的时间为：2ms+12ms+4.17ms+0.1ms=18.27ms。可能疑问点：计算机网络高分笔记不是说在通信领域 K 取 1000，在计算机领域 K 取 1024 吗？此道题目中 1KB 应该是属于计算机领域，为什么取值 1000?解析：计算机网络高分笔记给出的是最一般的理解的方式，不是绝对的。至于 K 到底取多少，至今没有统一标准。笔者根据经验总结出两点：(1)如果在考试中遇到，K 取多少，就看约分，考研的答案一定是最简化的，肯定可以约分，哪个好约分取哪个。如果分子和分母都有

43、 K 那就最好了。(2)如果实在不放心，可以参考教育部针对真题的解释，看看他们取值多少，照着取即可。15 【正确答案】 B【试题解析】 ：静态 RAM 和动态 RAM 都是易失性存储器，断电后信息都会遗失，所以错误。: PROM 的内部有行列式的熔丝，视需要利用电流将其烧断，写入所需的资料，但仅能写录一次。PROM 在出厂时，存储的内容全为 1，用户可以根据需要将其中的某些单元写入数据 0（部分的 PROM 在出厂时数据全为 0，则用户可以将其中的部分单元写入 1），以实现对其“编程”的目的，所以正确。：EPROM 是可改写的，但它不属于随机存储器，所以错误。：EEPROM（Electrica

44、lly Erasable Programmable ReadOnly Memory），电可擦可编程只读存储器，属于一种掉电后数据不丢失的存储芯片。EEPROM 可以在计算机上或专用设备上擦除已有信息，重新编程，所以正确。16 【正确答案】 D【试题解析】 题目很长，首先需要弄清题目的意思。题目告诉了时钟周期、速率以及读和写操作各自花的时钟周期数，所要求的是存储器的最大带宽，也就是单位时间内传输的有效信息量。计算过程如下： 读操作的时间为 TF (1+3+8)20ns=240ns 写操作的时间为 Tw=(1+2+8+3)20ns=280ns 则综合加权的时间为 240ns0.35+280ns0.

45、65=266ns 带宽为（也就是 266ns 可以传输 8 个字，或者说传输 32B） Bn=32B/ (26610 9S)120.3MB/s17 【正确答案】 B【试题解析】 通过观察这三条指令发现，第一、二条指令与第三条指令存在写后读的数据冒险，也就是说有可能在第一、二条指令执行结束后还没来得及将最终的结果存入寄存器 R1 和 R2 中，第三条指令就开始直接读取寄存器 R1 和 R2 中的内容。于是为了防止出现数据冒险，在执行第三条指令之前至少应加入一条空操作来保证取 R1 和 R2 中内容的滞后性。18 【正确答案】 B【试题解析】 对于选项：如果 12 个微操作都是相容的话，可以最多同

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

47、2H 进栈，此时 SP=OOFFH(因为进栈操作需要将 SP 的值减 1，即 0100H0001H=00FFH)，栈顶内容为 1002H。20 【正确答案】 B【试题解析】 根据题意可以看到，在此流水线中顺序执行 50 条指令用了 203t(正常情况下如果第 3 步的执行时间为t ，则执行 50 条指令只需要 4+ (501)t=53t)，所以流水线的瓶颈必定是第 3 步。 补充：对于包含瓶颈段的指令流水线，不妨设流水线共有 k 段，且需要执行 n 条指令，则总的执行时间为 i=1kt1+(n1)max t1，t 2，t k 根据上述公式，假定流水线中第 3 步的执行时间为 S，该指令流水线顺序执行 50 条指令所用的时间为：t+t+S+t+ （501）max t，t， S，t=203 t，解得 S=4t，即第 3 步的执行时间为 4t。21 【正确答案】 A【试题解析】 需要清楚的是，总线的宽度不是地址总线的位数，也不是控制总线的位数，而是数据总线的位数，所以此题总线的宽度应该是 32bit。而总线的传输速率为总线的工作频率乘以总线宽度，即 66MHz32bit=66MHz4B=264MB/s.22 【正确答案】 A【试题解析】 指令总是根据程序