天勤论坛：www.csbiji.com
关于天勤十套模拟卷的一些说明
（1）题源
高分笔记系列书籍之终极十套模拟卷的试题来源:市面上权威模拟卷里的经典题目+根据学长以前考研复习
笔记编写的易错易混题+各大高校考研经典题目
（2）定位
此模拟卷的定位主要是经典的题目+详细的解释+知识点的归类，主要目的是帮助考生在最后的冲刺时刻把握考试
的难点和重点，尽量以真题的形式去出，比如：
【2】假设栈的容量为3，入栈的序列为1，2，3，4，5，则出栈的序列可能为（Ⅰ．5，4，3，2，1Ⅲ．3，2，1，5，4A．Ⅰ、ⅢC．Ⅱ、Ⅲ
Ⅱ．1，5，4，3，2Ⅳ．4，3，2，1，5B．只有ⅢD．只有Ⅳ
）
这种题型是真题比较喜欢考的，所以在这十套模拟卷里面我们编写了大量的这种习题，希望能让考生在考场上有种似曾
相似的感觉，这样才有可能超长发挥。
（3）出题思路
该十套模拟卷的出题思路完全依照某机构权威老师的预测知识点来选题，所以希望考生一定要好好把这十套模拟卷认认真真的研究透彻，也许拿到考研试卷，会给你带来惊喜。
希望大家能把做后的反馈信息及时反馈到论坛！
天道酬勤，厚德载物
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
2011天勤计算机考研模拟试题（八）
单项选择题(1-40小题,每小题2分,共80分,下列每小题给出的四个选项中,只有一项符合一、一、单项选择题(1-40每小题
．)题目要求,把所选项前的字母填在题后的括号内把所选项前的字母填在题后的括号内．【1】在双链表中p所指的结点之前插入一个结点q的操作为（）。
A．p→prior=q;q→next=p;p→prior→next=q;q→prior=p→prior;B．q→prior=p→prior;p→prior→next=q;q→next=p;p→prior=q→next;C．q→next=p;p→next=q;q→prior→next=q;q→next=p;
D．p→prior→next=q;q→next=p;q→prior=p→prior;p→prior=q;
【2】适合用做链栈的链表是（以下链表没有头结点）（Ⅰ.只有表头指针没有表尾指针的循环双链表Ⅱ.只有表尾指针没有表头指针的循环双链表Ⅲ.只有表尾指针没有表头指针的循环单链表Ⅳ.只有表头指针没有表尾指针的循环单链表A．Ⅰ、ⅡB．Ⅱ、ⅢC．Ⅲ、Ⅳ
D．Ⅰ、Ⅱ、Ⅲ
）。
【3】用单链表（含有头结点）表示的队列的队头可能在链表的（Ⅰ.链头Ⅱ.链尾Ⅲ.链中A．只有ⅠC．只有Ⅱ
B．Ⅱ、ⅢD．都有可能
）位置。
【4】在由4棵树组成的森林中，第一、第二、第三和第四棵树中的结点个数分别为30，10，20，5，当把森林转换成二叉树后，对应的二叉树中根节点的左子树中结点个数为（）。A．64B．29C．30D．4
【5】已知结点A左孩子的平衡因子为-1，右孩子的平衡因子为0，在平衡二叉树中插入一个结点后造成了不平衡，假设最低的不平衡结点在A，则应该进行（）型旋转以使其平衡。A．LLB．LRC．RLD．RR
【6】根据使用频率为5个字符设计的哈夫曼编码不可能是（A．000,001,010,011,1C．000,001,01,10,11
B．0000,0001,001,01,1D．00,100,101,110,111
）。
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
【7】已知一棵深度为K的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有结点总数为（A．2k-1-1C．2k-1
）。
B．2k-1+1
D．2k+1
【8】如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。A．完全图B．连通图C．有回路D．一棵树
【9】若一个有向图中的顶点不能排成一个拓扑序列，则断定该有向图（）。A．含有多个出度为0的顶点B．是个强连通图C．含有多个入度为0的顶点D．含有顶点数目大于1的强连通分量【10】关于Hash查找说法不正确的有几个（）。
Ⅰ．采用链地址法解决冲突时，查找任一个元素的时间都是相同的；
Ⅱ．采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的；Ⅲ．用链地址法解决冲突易引起堆积现象；Ⅳ．线性探查法不易产生堆积现象；A．1
B．2
C．3
D．4
【11】一组记录的关键字为｛25，50，15，35，80，85，20，40，36，70｝，其中含有5个长度为2的有序表，用归并排序方法对该序列进行一趟归并后的结果是（A．15，25，35，50，20，40，80，85，36，70B．15，25，35，50，80，20，85，40，70，36C．15，25，50，35，80，85，20，36，40，70D．15，25，35，50，80，20，36，40，70，85【12】原码加减交替除法又称为不恢复余数法，因此（A．不存在恢复余数的操作
B．当某一步运算不够减时，做恢复余数的操作C．仅当最后一步余数为负时，做恢复余数的操作D．当某一步余数为负时，做恢复余数的操作【13】在原码一位乘中，当乘数Yi为1时，（）。A．被乘数连同符号位与原部分积相加后，右移一位B．被乘数绝对值与原部分积相加后，右移一位C．被乘数连同符号位右移一位后，再与原部分积相加D．被乘数绝对值右移一位后，再与原部分积相加
【14】关于虚拟存储器，下列说法正确的是（）。Ⅰ、虚拟存储器利用了局部性原理；
Ⅱ、页式虚拟存储器的页面如果很小，主存中存放的页面数较多，导致缺页频率较低，换页次数减少，最终可以提升操作速度；
）。
）。
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
Ⅲ、页式虚拟存储器的页面如果很大，主存中存放页面数较少，导致页面调度频率较高，换页次数增加，降低操作速度；
Ⅳ、段式虚拟存储器中，段具有逻辑独立性，易于实现程序的编译．管理和保护，也便于多道程序共享；A．Ⅰ、Ⅲ、ⅣC．Ⅰ、Ⅱ、Ⅳ
B．Ⅰ、Ⅱ、ⅢD．Ⅱ、Ⅲ、Ⅳ
【15】下面关于ROM的说法中，正确的有（）。
Ⅰ、ROM所存数据稳定，结构较简单，读出较方便，常用于存储各种固定程序和数据；Ⅱ、PROM只能写录一次；
Ⅲ、EPROM可进行多次读写，但擦除较为麻烦，使用很不方便；
Ⅳ、快闪存储器存储单元结构同EPROM相似，但其集成度高．功耗低．体积小，又能在线快速擦除，因而使用广泛。A．Ⅰ、Ⅱ、Ⅲ、ⅣC．Ⅰ、Ⅱ、Ⅳ
【16】指令（）从主存中读出。A．总是根据程序计数器PC
B．有时根据PC，有时根据转移指令C．根据地址寄存器
D．有时根据PC，有时根据地址寄存器
【17】以下关于指令字长的说法，正确的是（）。
A．一般来说，目前的计算机指令字长、机器字长和存储字长是相等的B．通常一台计算机的指令系统中，指令字长是固定不变的C．控制变长指令的电路要比控制单字长指令的电路简单些
D．通常把常用的一些指令设计成单字长或者短字长格式的指令
【18】关于流水线技术的说法，错误的是（）。
A．超标量技术需要配置多个功能部件和指令译码电路等
B．与超标量技术和超流水线技术相比，超长指令字技术对优化编译器要求更高，而无其他硬件要求
C．流水线按序流动时，在RAW、WAR和WAW中，只可能出现RAW相关
D．超流水线技术相当于将流水线再分段，从而提高每个周期内功能部件的使用次数【19】下列说法错误的是（）。Ⅰ、显示编码可以用较少的二进制信息表示较多的微操作命令信号，例如有两组互斥微命令中，微命令个数分别为8和9，则只分别需要3位和4为即可表示
Ⅱ、微地址形成部件实际上是一个编码器，通常可以采用PROM来实现
Ⅲ、垂直型微指令以较长的微程序结构换取较短的微指令结构，因而执行效率高、灵活性强都高于水平型微指令
Ⅳ、隐式编码中，一个字段的译码输出，需要依靠另外一个字段某一个信号的输出A．Ⅰ、Ⅲ、ⅣB．Ⅱ、Ⅲ、ⅣC．Ⅱ、Ⅳ
D．Ⅰ、Ⅱ、Ⅲ、Ⅳ
B．Ⅱ、Ⅲ、Ⅳ
D．Ⅰ、Ⅱ、Ⅲ
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
【20】某数组多路通道最大数据传输率为1MB/s，它有10个子通道，则每个子通道的最大数据传输率为（）。A．100KB/sB．1MB/s
C．介于A、B之间D．无法判断
【21】下列关于I/O设备的说法中正确的是（）。Ⅰ、键盘、鼠标、显示器、打印机属于人机交互设备
Ⅱ、微型计算机中，VGA代表的显示标准
Ⅲ、打印机从打字原理的角度来区分，可以分为点阵式打印机和活字式打印机Ⅳ、鼠标适合于用中断方式来实现输入操作A．Ⅱ、Ⅲ、ⅣC．Ⅰ、Ⅱ、Ⅲ
B．Ⅰ、Ⅱ、Ⅳ
D．Ⅰ、Ⅱ、Ⅲ、Ⅳ
【22】可能会产生DMA请求的总线部件是（）。Ⅰ、高速外设
Ⅱ、需要与主机批量交换数据的外设Ⅲ、具有DMA接口的设备A．只有ⅠC．Ⅰ、Ⅲ
B．只有ⅢD．Ⅱ、Ⅲ
【23】下列说法正确的有（）。
I．批处理的主要缺点是需要大量内存。
II．当计算机提供了管态（系统态）和目态（用户态）时，输入/输出指令必须在管态下执行。III．操作系统中采用多道程序设计技术最主要原因是为了提高CPU和外部设备的可靠性。IV．操作系统中，通道技术是一种硬件技术。A．I、IIB．I、IIIC．II、IVD．II、III、IV
【24】若每个作业只能建立一个进程，为了照顾短作业用户，应采用_______；为了照顾紧急作业用户，应采用_______；为了实现人机交互，应采用_______；而能使短作业，长作业和交互作业用户都满意，应采用_______。I．FCFS调度算法
II．短作业优先调度算法III．时间片轮转法
IV．多级反馈队列调度算法V．基于优先级的剥夺调度算法A．II、V、I、IVB．I、V、III、IVC．I、II、IV、III
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
D．II、V、III、IV
【25】有一个计数信号量S，（1）假如若干个进程对S进行了28次P操作和18次V操作之后，信号量S的值为0。（2）假如若干个进程对信号量S进行了15次P操作和2次V操作。请问此时有多少个进程等待在信号量S的队列中（A．2B．3C．5D．7【26】有以下的进程需要调度执行：
进程名P1P2P3P4P5
到达时间0.00.41.05.57
运行时间
94142
）
1)如果用非抢占的短进程优先调度算法，请问这5个进程的平均周转时间？2)如果采用抢占的短进程优先调度算法，请问这5个进程的平均周转时间？A．8.62；6.34B．8.62；6.8C．10.62；6.34D．10.62；6.8
【27】有两个并发进程P1，P2，其程序代码如下：
可能打印出z的值有？可能打印出的c值有？（其中x为P1，P2的共享变量）A．z=1，﹣3；c=﹣1，9；B．z=﹣1，3；C．z=﹣1，3，1；D．z=3；
c=1，9；c=9；c=1，9；
）。
【28】下列说法正确的有（
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
I.先进先出（FIFO）页面置换算法会产生Belady现象。
II.最近最少使用（LRU）页面置换算法会产生Belady现象。
III.在进程运行时，如果它的工作集页面都在虚拟存储器内，能够使该进程有效地运行，否则会出现频繁的页面调入/调出现象。
IV.在进程运行时，如果它的工作集页面都在主存储器内，能够使该进程有效地运行，否则会出现频繁的页面调入/调出现象。A．I、IIIB．I、IVC．II、IIID．II、IV
【29】假定有一个请求分页存储管理系统，测得系统各相关设备的利用宰为：CPU利用率为10％，磁盘交换区为99．7％：其他I/O设备为5％。试问：下面（）措施将可能改进CPU的利用率？I．增大内存的容量
II．增大磁盘交换区的容量III．减少多道程序的度数IV．增加多道程序的度数V．使用更快速的磁盘交换区VI．使用更快速的CPUA．I、II、III、IVB．I、IIIC．II、III、VD．II、VI
【30】某系统有4分页框，某个进程页面使用情况如表所示
页号0123
装入时间126230120160
上次引用时间
279260272280
R（读）
0111
M（修改）
0011
请问采用FIFO置换算法将会替换（）页？采用LRU置换算法将会替换（）页？
采用简单CLOCK置换算法将会替换（）页？采用改进型CLOCK置换算法将会替换（）页？A．0B．1C．2D．3
【31】有一磁盘组共有10个盘面，每个盘面上有100个磁道，每个磁道有16个扇区。每个扇区大小为100K。假设分配以扇区为单位。空白文件目录的每个表目占用5个字节，问什么时候空白文件目录大于位示图？
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
A．400B．4000C．40000D．400000
【32】下列说法正确的有（）。
I.如果I/O所花费的时间比CPU'处理时间短的多，则缓冲区最有效。
II.提高单机资源利用率的最关键技术是SPOOLing技术。
III.在采用SPOOLing技术的系统中，用户的打印数据首先被送到内存固定区域。IV.在操作系统中，用户在使用I/O设备时，通常采用物理设备名。A．I、IIIB．II、IIIC．IIID．都错
【33】10Base-T指的是（）。
A．10M波特率，使用数字信号，使用双绞线B．10Mbps，使用数字信号，使用双绞线C．10M波特率，使用模拟信号，使用双绞线D．10Mbps，使用模拟信号，使用双绞线
【34】CSMA协议可以利用多种监听算法来减小发送冲突的概率，下面关于各种监听算法的描述中，错误的是（）。
Ⅰ．非坚持型监听算法有利于减少网络空闲时间；Ⅱ．1-坚持型监听算法有利于减少冲突的概率；Ⅲ．P坚持型监听算法无法减少网络的空闲时间；Ⅳ．1-坚持型监听算法能够及时抢占信道；A．Ⅰ、Ⅱ、ⅢB．Ⅱ、ⅢC．Ⅰ、Ⅱ、Ⅳ
D．Ⅱ、Ⅳ
【35】同一局域网上的两个设备具有相同的静态MAC地址时，其结果是（）。A．首次引导的设备使用该地址，第二个设备不能通信B．最后引导的设备使用该地址，第一个设备不能通信C．这两个设备都能正常通信D．这两个设备都不能通信
【36】设有下面4条路由：172．18．129．0/24、172．18．130．0/24、172．18．132．0/24和172．18．133．0/24，如果进行路由聚合，能覆盖这4条路由的地址是（A．172．18．128．0/21B．172．18．128．0/22C．172．18．130．0/22D．172．18．132．0/23
）。
【37】因特网的RIP协议、OSPF协议、BGP协议分别使用了什么路由选择算法（）。Ⅰ．路径-向量路由选择协议Ⅱ．链路状态协议Ⅲ．距离-向量路由选择协议A．I、Ⅱ、Ⅲ
B．Ⅱ、Ⅲ、I
C．Ⅱ、I、Ⅲ
D．Ⅲ、Ⅱ、I
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
【38】如果IPv4的分组太大，则会在传输中被分片，那么在（）地方将对分片后的数据报重组。
A．中间路由器B．下一跳路由器C．核心路由器
D．目的端主机
【39】TCP的通信双方，有一方发送了带有FIN标志的数据段后表示（）。A．将断开通信双方的TCP连接
B．单方面释放连接，表示本方已经无数据发送，但是可以接受对方的数据C．中止数据发送，双方都不能发送数据D．连接被重新建立【40】（
）可以将其管辖的主机名转换为该主机的IP地址。
B．根域名服务器
D．代理域名服务器
A．本地域名服务器C．授权域名服务器
二、综合应用题(41-47小题,共70分)
【41】（10分）有一种简单的排序算法，叫做计数排序（count
sorting）。这种排序算法对
一个待排序的表(用数组表示)进行排序，并将排序结果存放到另一个新的表中。必须注意的是，表中所有待排序的关键码互不相同，计数排序算法针对表中的每个记录，扫描待排序的表一趟，统计表中有多少个记录的关键码比该记录的关键码小，假设针对某一个记录，统计出的计数值为c，那么，这个记录在新的有序表中的合适的存放位置即为c。
(1)给出适用于计数排序的数据表定义；
(2)使用C或C++或JAVA语言编写实现计数排序的算法；(3)对于有n个记录的表，关键码比较次数是多少？(4)与简单选择排序相比较，这种方法是否更好?为什么?
【42】（13分）设计一个算法，判断给定的二叉树是否是二叉排序树，假设二叉排序树已经存储在二叉链表存储结构中，树结点个数为n，结点值为int型。要求：（1）给出基本设计思想。
（2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。（3）分析算法的时间复杂度和空间复杂度。
【43】（11分）某计算机的主存地址位数为32位，按字节编址。假定数据cache中最多存放128个主存块，采用4路组相联方式，块大小为64Bytes，每块设置了1位有效位“Valid”位。要求：
（1）分别指出主存地址中标记（Tag）、组号（Index）和块内地址（Offset）三部分的位置与位数。
（2）计算该数据Cache的总容量（请给出详细计算过程）。
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
【44】（12分）某机器中，已知配有一个地址空间为(0000—1FFF)16的ROM区域，现在用一个SRAM芯片（8K×4位）形成一个16K×8位的RAM区域，起始地址为（2000）16。假设SRAM芯片有CS和WE控制端，CPU地址总线A15——A0，数据总线为D7——D0，控制信号为R/W（读/写），MREQ（当存储器读或写时，该信号指示地址总线上的地址是有效的）。要求：
（1）满足已知条件的存储器，画出地址译码方案。（2）画出ROM与RAM同CPU连接图。
【45】（8分）在一个分页存储管理系统中，地址空间分页(每页1K)，物理空间分块，设主存总容量是256K，描述主存分配情况的位示图如下图所示(0表示未分配，1表示已分配)，此时作业调度程序选中一个长为5.2K的作业投入内存。问：
（1）为该作业分配内存后(分配内存时，首先分配低地址的内存空间)，请填写该作业的页表内容?
（2）页式存储管理有无零头存在，若有，会存在什么零头?为该作业分配内存后，会产生零头吗?如果产生，大小为多少?
（3）假设一个64M内存容量的计算机，其操作系统采用页式存储管理(页面大小为4K)，内存分配采用位示图方式管理，请问位示图将占用多大的内存?
页号
块号(0开始编址)
【46】（7分）在实现文件系统时，为加快文件目录的检索速度，可利用“文件控制快分解法”。假设目录文件存放在磁盘上，每个盘块512字节。文件控制块占64字节。其中文件名占8个字节。通常将文件控制块分解成两部分，第一部分占10字节（包括文件名和文件内部号），第二部分占56字节（包括文件内部号和文件其他描述信息）。
（1）假设某一目录文件共有254个文件控制块，试分别给出采用分解法前和分解法后，查找该目录文件的某一个文件控制块的平均访问磁盘次数。
（2）一般地，若目录文件分解前占用n个盘块，分解后改用m个盘块存放文件名和文件内部号部分，请给出访问磁盘次数减少的条件。
【47】（9分）考虑如图所示的采用基于距离矢量的路由选择算法的子网。假设路由器C刚启动，并测得到达它的邻接路由器B、D和E的时延分别等于6、3和5。此后，路由器C依次收到下列矢量：来自D的(16,12,6,0,9,10)、来自E的(7,6,3,9,0,4)以及来自B的(5,0,8,12,6,2)。上面的矢量表示的是发送该矢量的结点分别与结点A、B、C、D、E、F的延时。则路由器C在收到3个矢量之后的新路由表是什么？
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
BA
6
5C
3DEF参考答案与解析：
单项选择题答案与解析一、一、单项选择题单项选择题答案与解析
【1】D。本题考查双链表的操作；这种题目其实大部分考生都见过，为什么还要出这么老套的题目？因为不少考生在做这种题目的时候经常会死记硬背，或者经常出现指针断裂找不到结点的情况，所以希望通过此题给大家做一个总结，看完总结，就可以迎刃而解。
技巧：这种题目的目的仅仅是需要把一个结点插进两个结点之间即可，答案肯定不唯一。但是我们应该从一些正确答案中挑选出一个万能的插入公式，只要遇到这种题目，这么插准没错就OK了。看如下例题：
例：假设在双链表中p所指的结点之后插入一个结点s，其操作语句描述为：s->next=p->next;s->prior=p;
p->next=s;
s->next->prior=s;指针变化过程如图1所示。
图1双链表结点插入过程图
说明：不知道大家有没有注意到在插入时，如果按照上面的顺序来插入，可以看成是一个万能的插入方式。不管怎样，先将要插入的结点两边链接好，这样有什么好处？对了，就是可以保证不会发生链断之后找不到结点的情况。所以请考生们一定要记住这种万能插入结点的方式。
知道了这种方式，自然该选择题的分析步骤就很明显了，分以下四部：（1）p结点前驱结点的后继应该指向q，即p→prior→next=q；（2）q的后继结点指向P，即q→next=p；
上面2步的完成就已经算是把结点正确插入了，因为至少接下来的步骤不存在了锻炼，只需画图完成连接即可；
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
（3）q的前驱结点指向p的前驱结点，即q→prior=p→prior;p→prior=q;
（4）p的前驱结点指向q，即p→prior=q;综上分析，D选项正确；
当然，恰好选择题也有这个选项，如果选择题的正确答案不是这种万能插入方式的话，那怎么办?这个就能自己一步步的去画图了，看看中间过程有没有断链就可以。【2】D。本题考查栈的存储结构的选取；
链栈在链表的头部进行操作（插入和删除结点），因此需要很方便的找到链表开始结点的前驱结点才行。而只有表头指针没有表尾指针的循环单链表，不方便查找开始结点的前驱结点（查找时间复杂度为O(n)）而其他三种链表都是可以很方便的找到开始结点的前驱结点。
综上分析，Ⅰ、Ⅱ、Ⅲ都是可以的。【3】B。本题考查链表在队列上的应用；
带有头结点的链表用作队列的存储结构时，链表的头结点不存储信息，链表的开始结点存有队头信息，因此当队列中的元素大于1个的时候队头在链表的链中位置（链中位置是指除去表头结点和表尾结点以外的结点位置），当队列中的元素只有1个的时候，队头结点在链表的表尾位置。
综上分析，Ⅱ、Ⅲ都有可能。
注意一点：带有头结点的链表用作队列的存储结构时，队列的队尾只能在链表的链尾。【4】B。本题考查森林与二叉树的转换；
森林转换成二叉树后根节点的左子树其实就是原来第一棵树除了根节点的所有结点，所以二叉树中根节点的左子树中结点个数为29。【5】B。本题考查树的旋转；
由题意可知，树的结构如下图所示：
由图可知，A的平衡因子为1，插入一个结点造成不平衡，说明这个结点一定是插在结点A的左孩子的右孩子上，如下图所示：
或者
所以需要进行LR旋转。
【6】D。本题考查哈夫曼树的性质；
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
哈夫曼树中只有度为0或2的结点，由选项D可以做出如下二叉树：
由哈夫曼树的性质知道，树中不含单分支结点，因此D项不可能。
【7】C。本题考查平衡二叉树的基本概念；
每个非叶子结点的平衡因子均为0，说明了该平衡二叉树为满二叉树，所以结点总数为2k-1。
【8】B。本题考查图的遍历及连通图的性质；
图的一次深度优先搜索遍历，可以遍历完图中一个连通分量中所有的顶点。如果图是连通的，则图只含有一个连通分量，即图本身，这样一次深度优先搜索遍历即可遍历完图中所有顶点。因此本题选B。无向完全图相当于在连通图上加上了更严格的条件，即任意两个顶间都存在边，对于满足本题的要求不需要完全图，条件达到连通图的强度就足够了。【9】D。本题考查拓扑排序；
有向图中的顶点不能排成一个拓扑序列，则该有向图中一定含有环。顶点数目大于1的强连通图一定含有环，因此本题选D。A,C显然不对。B项，顶点数目为1的图也是强连通图，这是一种特例。
【10】C。本题考查Hash冲突的处理方法；
如果两个元素在同一个链表中，查找时间肯定不相同，故Ⅰ不正确。插入规定在链首的话，插入操作不需要查找插入位置即可直接进行，因此插入任何一个元素的时间均相同，这是相对于链表的尾插法而言的，在尾插法中，需要找到链表的尾部，因此链表的长度决定了插入元素的执行时间，故Ⅱ正确。
所谓堆积问题即在Hash表的建立过程中，某些Hash地址是由冲突处理产生的，而不是直接由Hash函数直接产生的，这就可能造成原本Key1与Key2虽然不是同义词，但是最后却得出了相同的Hash地址。比如在线性探查法处理冲突的过程中，设第一个同义词占用单元d，这之后连续的若干个同义词将占用Hash表的d,d+1,d+2等单元，此时随后任何d+1,d+2等单元上的Hash映射都会由于前面的同义词堆积而产生冲突，尽管随后的这些关键字并没有同义词。故Ⅳ不正确，显然链地址法不会产生堆积现象，因为多个同义词只会占用表中的一个地址，故Ⅲ不正确。
【11】A。本题考查归并排序；
根据归并算法的思想，对5个长度为2的有序表一趟归并后得到两个长度为4的有序表和一个长度为2的有序表，只有A满足。【12】C。本题考查基本的原码加减交替除法；
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
在用原码加减交替法作除法运算时，商的符号位是由除数和被除数的符号位异或来决定的，商的数值是由除数、被除数的绝对值通过加减交替运算求得的。由于除数、被除数取的都是绝对值，那么最终的余数当然应是正数。如果最后一步余数为负，则应将该余数加上除数，将余数恢复为正数，称为恢复余数。
【13】B。本题考查原码一位乘的基本规则；
具体请参看下表：原码、补码乘法与除法的总结运算种类原码乘法补码乘法符号位处理两数符号位异或不单独处理大致规则乘数Yi为1时，被乘数绝对值与原部分积相加后，右移一位；乘数Yi为0时，直接右移一位。1、被乘数x符号任意，乘数y为正：同原码一位乘；2、被乘数x符号任意，乘数y为负：先将[y]补去掉符号位，进行原码一位乘操作，得到的结果进行+[-x]补校正；3、Booth算法：乘数连同符号位一同加入运算，并且增加一位附加位yn+1，其初始值为0。每一次计算时，需要查看yiyi+1：00和11时，部分积右移一位；01时，部分积加[x]补，再右移一位；10时，部分积加[-x]补，再右移一位。（注意：Booth算法在最后一步是不移位的，即如果出现00和11则计算结束；若出现10或01，则部分积加相应值后结束计算）原码除法两数符号位异或1、恢复余数法：首先将被除数绝对值+[-y*]补，若余数为正，上商“1”，左移一位，然后继续进行该操作；若余数为负，上商“0”，恢复余数+[y*]补。如此重复。2、加减交替法：首先将被除数绝对值+[-y*]补，若余数为正，上商“1”，左移一位，+[-y*]补；若余数为负，上商“0”，左移一位，+[y*]补。补码除法不单独处理首先判断[x]和[y]是否同号，若同号，则+[-y]补，若异号，则+[y]补。然后，查看余数[R]补和[y]补是否同号，若同号，则上商“1”，左移一位，然后+[-y]补；若异号，左移一位，然后+[y]补。如此重复。友情提示：此表只是列出大体的运算规则，具体的操作还需要读者进行一些针对的练习，虽然作为大题考到的概率几乎为0，但是也应该从练习中多总结一些规律，以应付选择题。【14】A。本题考查虚拟存储器的基本原理；
页式虚拟存储器中，页面如果很小，虚拟存储器中包贪的页面个数就会过多，使得页表的体积过大，导致页表本身占据的存储空间过大，这将会使得操作速度变慢，故Ⅱ错误。
Ⅰ选项：CPU访问存储器时，无论是存取指令还是存取数据，所访问的存储单元都趋于聚集在一个较小的连续区域中，虚拟存储器正是依据了这一原理来设计的，故Ⅰ正确；
Ⅲ选项：当页面很大时，虚拟存储器中的页面个数会变少，由于主存的容量比虚拟存储器的容量少，主存中的页面个数会更少，每一次页面装入的时间会变长，每当需要装入新的页面时，速度会变慢，故Ⅲ正确；
Ⅳ选项：段式虚拟存储器是按照程序的逻辑性来设计的，具有易于实现程序的编译、管理和保护，也便于多道程序共享的优点，故Ⅳ正确。
综上分析：Ⅰ、Ⅲ、Ⅳ正确。
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
【15】A。本题考查各种ROM基本概念及原理；
Ⅰ：ROM所存数据，一般是装入整机前事先写好的，整机工作过程中只能读出，而不像随机存储器那样能快速地．方便地加以改写。ROM所存数据稳定，断电后所存数据也不会改变；其结构较简单，读出较方便，因而常用于存储各种固定程序和数据，故Ⅰ正确；
Ⅱ：PROM之内部有行列式的镕丝，视需要利用电流将其烧断，写入所需的资料，但仅能写录一次。PROM在出厂时，存储的内容全为1，用户可以根据需要将其中的某些单元写入数据0(部分的PROM在出厂时数据全为0，则用户可以将其中的部分单元写入1)，以实现对其“编程”的目的，故Ⅱ正确；
Ⅲ：EPROM需用紫外光长时间照射才能擦除，使用很不方便。20世纪80年代制出的EEPROM，克服了EPROM的不足，但集成度不高，价格较贵，故Ⅲ正确；
Ⅳ：快闪存储器是在EEPROM之后开发出的存储设备，存储单元结构同EPROM相似，但其集成度高．功耗低．体积小，又能在线快速擦除，因而使用广泛，故Ⅳ正确；
综上分析：Ⅰ、Ⅱ、Ⅲ、Ⅳ全对。
【16】A。本题考查CPU取指的基本原理；
指令总是根据程序计数器PC从主存中读出（一定记住）。可能考生会想到无条件转移指令情况，认为不一定总是根据PC读出。实际上，正确的执行顺序是这样的，当前指令正在执行时，其实PC已经是下一条指令的地址了，如果遇到了无条件转移指令，只需要简单的把跳转的地址覆盖PC的内容就可以了，最终的结果还是指令需要根据程序计数器PC从主存读出。
【17】D。本题考查指令字长的基本理论；
A，早期的计算机，三个字长是相等的，现在的计算机已经不是这样；
B，一台机器的指令系统可以采用位数不同的的指令，如单字长指令、多字长指令；
C，显然，控制这类指令的电路必然是复杂的；
D，将常用的指令设计成较简单的格式，有利于提高整个CPU的效率。综上分析，D正确。
【18】B。本题考查流水线的基本概念；
A，要实现超标量技术，要求处理机中配置多个功能部件和指令译码电路，以及多个寄存器端口和总线，以便能实现同时执行多个操作；
B，超长指令字技术对cache的容量要求更大，因为需要执行的指令长度也许会很长；C，流水线按序流动，肯定不会出现先读后写和写后写相关（根据定义可以知道）。只有可能会出现没有等到上一条指令写入，当前指令去读寄存器的错误（此时可以采用旁路相关来解决）。
提醒：直接按照中文翻译的比如“读后写”容易理解为“先读后写”，事实上根据英文的意思，应该是“先写后读”，容易绕晕，注意理顺思路，要反着读；
D，超流水线技术是通过细化流水，提高主频，使得机器在一个周期内完成一个甚至多个操作，其实质是用时间换取空间。这一点我们可以用日常事例来说明，比如有5个人接力传送木头（对应一个5级的流水线），超流水是说细化该流水过程，即由10个人接力（此时为10级流水），显然完成全部任务的速度会快，也就是常说的“人多力量大”。【19】A。本题考查微指令编码的基本原理；
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
Ⅰ：微命令个数为8时，需要4位方可，假设只用三位，那么则会造成每个编码都会输出一个微命令，事实上，微命令的编码需要预留一个字段表示不输出，故Ⅰ错误；
Ⅱ：微地址形成部件是一个编码器，通常可以采用PROM来实现，这点不做重点，了解即可，故Ⅱ正确；
Ⅲ：垂直型微指令以较长的微程序结构换取较短的微指令结构，它在并行操作能力、效率和灵活性方面是低于水平型微指令的，故Ⅲ错误；
Ⅳ：这种说法不准确，应该是某一个字段的译码输出，还需要由另外一个字段的某些微命令来解释输出，这也就是说，不是依靠与另一个字段的某一个信号，而是依靠于其产生的某个译码输出，故Ⅳ错误。
综上分析：Ⅰ、Ⅲ、Ⅳ错误。【20】B。本题考查数组多路通道的基本概念；
数组多路通道以数据块为传输单位，一段时间内只能为一个子通道服务，子通道接受服务时的数据传输率即为通道的最大数据传输率。【21】B。本题考查各种I/O设备的基本理论；
Ⅰ：键盘、鼠标、显示器、打印机等都是属于机器与人交互的媒介（键盘鼠标是人操作来控制计算机，显示器和打印机都是计算机给人传递信息），故Ⅰ正确；
Ⅱ：VGA是一个用于显示的视频传输标准，故Ⅱ正确；Ⅲ：打印机从打字原理的角度来区分，可分为击打式和非击打式，按照能否打出汉字来分，可分为点阵式打印机和活字式打印机，故Ⅲ错误；
Ⅳ：键盘、鼠标等输入设备，一般都采用I/O方式来实现输入，原因在于CPU需要及时响应这些操作，并且在不及时响应时，容易造成输入的丢失，故Ⅳ正确。
综上分析：Ⅰ、Ⅱ、Ⅳ正确。
【22】B。本题考查DMA的基本概念；
只有具有DMA接口的外设才能产生DMA请求，即使当前设备是高速设备或者是需要与主机批量交换数据，如果没有DMA接口的话，也是不能产生DMA请求的。【23】C。本题综合考查一些基本概念的内容。
I错误：批处理的主要缺点是缺少交互性。
II正确：输入/输出指令需要中断操作，中断必须在管态（系统态）下执行。III错误：多道性是为了提高系统利用率而提出的设计思想。
IV正确：I/O通道实际上是一种特殊的处理机。它具有执行I/O指令的能力，并通过执行通道（I/O）程序来控制I/O操作。
综上分析：II、IV正确。
【24】D。本题考查处理机调度算法。
第一空：为了照顾短作业，赋予短作业高的优先级，所以采用短作业优先调度算法。第二空：为了照顾紧急作业，必须采用可剥夺的调度算法，且同时需要赋予紧急作业高的优先级，所以采用基于优先级的剥夺调度算法。
第三空：为了实现人机交互，即需要较短的响应时间。时间片轮转法，是保证响应时间最短的处理机调度算法。
第四空：为了使各种作业都满意，只有采用多级反馈队列调度算法，这样才能相对平衡
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
得满足不同种作业的需要。
【25】B。本题考查信号量的内容。
由（1）对S进行了28次P操作和18次V操作，即S－28+18=0，得S=10；
（2）对信号量S进行了15次P操作和2次V操作，即S－15+2=10－15+2=－3，S信号量的负值的绝对值，表示等待队列中进程数。所以有3个进程等待在信号量S的队列中。【26】D。本题考查短进程优先调度算法。非抢占式：进程名P1P2P3P4P5
到达时间0.00.41.05.57
运行时间
94142
开始时间0.012.09.016.010.0
结束时间9.016.010.020.012.0
周转时间
915.6914.55
平均周转时间为（9+15.6+9+14.5+5）/5=10.62。2)抢占式：进程名P1P2P3P4P5
到达时间0.00.41.05.57
运行时间
94142
开始时间0.00.41.05.57.0
结束时间20.05.42.011.59.0
周转时间205162
平均周转时间为（20+5+1+6+2）/5=6.8。
【27】B。本题考查对共享变量的非互斥访问所导致程序结果不唯一的问题；
本题关键是输出语句A2，B2中读取的x的值不同，由于A1，B1执行的先后问题，使得在执行A2，B2前，x的可能取值有两个就是1，-3；这样输出z的值可能是1+2=3或者是（-3）+2=-1；输出c的值可能是1*1=1或者是（-3）*（-3）=9；【28】B。本题考查虚拟存储的内容；
I正确，举个例子：使用先进先出(FIFO)页面置换算法，页面引用串为1、2、3、4、1、2、5、1、2、3、4、5时，当分配3帧时产生9次缺页中断，分配4帧时产生10次缺页中断。
II错误。最近最少使用（LRU）页面置换算法没有这样的问题。
III错误，IV正确：若页面在内存中，不会产生缺页中断，也即不会出现页面的调入/调出。而不是虚拟存储器（包括作为虚拟内存那部分硬盘）。
综上分析：I、IV正确。
【29】B。本题考查分页存储管理的内容；
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
I正确：增大内存的容量。增大内存可使每个程序得到更多的页面，能减少缺页率，因而减少换入换出过程，可提高CPU的利用率。
II错误：增大磁盘交换区的容量。因为系统实际已处于频繁的换入换出过程中，不是因为磁盘交换区容量不够，因此增大磁盘交换区的容量无用。
III正确：减少多道程序的度数。可以提高CPU的利用率，因为从给定的条件中磁盘交换区的利用率为99．7％，说明系统现在已经处于频繁的换入换出过程中，可减少主存中的程序。
IV错误：增加多道程序的度数。系统处于频繁的换入换出过程中，再增加主存中的用户进程数，只能导致系统的换入换出更频繁，使性能更差。
V错误：使用更快速的磁盘交换区。因为系统现在处于频繁的换入换出过程中，即使采用更快的磁盘交换区，其换入换出频率也不会改变，因此没用。
VI错误：使用更快速的CPU。系统处于频繁的换入换出过程中，CPU处于空闲状态，利用率不高，提高CPU的速度无济于事。
综上分析：I、III可以改进CPU的利用率。【30】C；B；A；A。本题考查页面置换算法的内容。
FIFO置换算法选择最先进入内存的页面进行替换。由表中装入时间可知，第2页最先进入内存，故FIFO置换算法选择第2页替换。
LRU置换算法选择最近最长时间未使用的页面进行替换。由表中上次引用时间可知，第1页是最长时间未使用的页面，故LRU置换算法将选择第1页替换。
简单CLOCK置换算法从上一次位置开始扫描，选择第一个访问位为0的页面进行替换。由表中R（读）标志位可知，依次扫描1、2、3、0，页面0未被访问，扫描结束，故简单CLOCK置换算法将选择第0页替换。
改进型CLOCK置换算法从上一次位置开始扫描，首先寻找未被访问的修改的页面。由表中R（读）标志位和M（修改）标志位可知，只有页面0满足R=0和M=0，故改进型CLOCK置换算法将选择第0页置换。【31】A。本题考查位示图的内容。
由题设知，磁盘组扇区总数为16*100*10=16000，因此使用位示图描述扇区状态需要的位数为16000/8=2000B。已知空白文件目录的每个表项占5个字节，而位示图需占2000字节，即2000字节可存放的表项数为2000/5=400。故当空白区数目大于400时，空白文件目录大于位示图。
【32】D。本题考查I/O部分内容。
I错误：缓冲区主要解决输入输出速度比CPU处理的速度慢而造成的数据积压的矛盾，所以，如果I/O花费的时间比CPU处理时间短的多，则缓冲区就没有必要设置。
II错误：在单级系统中，最关键的资源就是处理机资源，最大化的提高处理机利用率，就是最大化的提高系统效率。多道程序设计技术是提高处理机利用率的最关键技术。
III错误：打印数据先存入输出井，在送入打印机，输出井位于磁盘而不是内存。IV错误：采用的是逻辑设备名，不是物理设备名。
综上分析：全部错误。
【33】B。本题考查了一些术语的概念；
10表示每秒传输10M比特数据，因此是10Mbps。Base表示采用基带型号传输（基带
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
传输使用数字信号），T表示使用了双绞线（Twisted-pair）。【34】A。本题考查CSMA协议的各种监听；
按总线争用协议来分类，CSMA有三种类型：
1）非坚持CSMA。一个站点在发送数据帧之前，先要对媒体进行检测。如果没有其它站点在发送数据，则该站点开始发送数据。如果媒体被占用，则该站点不会持续监听媒体，而等待一个随机的延迟时间之后再监听。采用随机的监听延迟时间可以减少冲突的可能性，但其缺点也是很明显的：即使有多个站点有数据要发送，因为此时所有站点可能都在等待各自的随机延迟时间，而媒体仍然可能处于空闲状态，这样就使得媒体的利用率较为低下，故Ⅰ错误。
2）1-坚持CSMA。当一个站点要发送数据帧时，它就监听媒体，判断当前时刻是否有其他站点正在传输数据。如果媒体忙的话，该站点等待直至媒体空闲。一旦该站点检测到媒体空闲，它就立即发送数据帧，故Ⅳ正确。如果产生冲突，则等待一个随机时间再监听。之所以叫“1-坚持”，是因为当一个站点发现媒体空闲的时候，它传输数据帧的概率是1。1-坚持CSMA的优点是：只要媒体空闲，站点就立即发送；它的缺点在于：假如有两个或两个以上的站点有数据要发送，冲突就不可避免，故Ⅱ错误。
3）P-坚持CSMA。P-坚持CSMA是非坚持CSMA和1-坚持CSMA的折中。P-坚持CSMA应用于划分时槽的媒体，其工作过程如下：当一个站点要发送数据帧的时候，它先检测媒体。若媒体空闲，则该站点按照概率P的可能性发送数据，而有1-P的概率会把要发送数据帧的任务延迟到下一个时槽。按照这样的规则，若下一个时槽也是空闲的，则站点同样按照概率P的可能性发送数据，所以说如果处理得当P坚持型监听算法还是可以减少网络的空闲时间的，故Ⅲ错误。
综上分析，Ⅰ、Ⅱ、Ⅲ错误。【35】D。本题考查局域网的通信；
在使用静态地址的系统上，如果有重复的硬件地址，那么着两个设备都不能通信。在局域网上，每个设备必须有一个唯一的硬件地址，故选【D】。【36】A。本题继续考查路由的聚合；
前两个字节和最后一个字节不做比较了，只比较第三个字节即可，129→10000001130→10000010132→10000100133→10000101
显然，这四个数字只有前五位是完全相同的，因此汇聚后的网络的第三个字节应该是10000000→128。汇聚后的网络的掩码中1的数量应该有8+8+5=21，因此答案是172．18．128．0/21。
【37】D。本题考查对三种常见路由选择算法的理解；
RIP即路由信息协议，OSPF即开放最短路径优先协议，BGP即边界网关协议。RIP和OSPF协议属于内部网关协议，主要处理自治系统内部的路由选择问题，BGP属于外部网关协议，主要处理自治系统之间的路由选择问题。
RIP：是一种分布式的基于距离-向量的路由选择协议。RIP协议的距离也称为“跳数”，跳数越少，距离越短。RIP协议优先选择距离短的路径。
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
OSPF：最主要的特征是使用分布式的链路状态协议。在OSPF中，路由器间彼此交换的信息是与本路由器相邻的所有路由器的链路状态，最终各自建立一个链路数据库，这个链路数据库实际上就是全网拓扑结构图。每个路由器使用链路状态数。据库中的数据来构造自己的路由表。
BGP：只是力求寻找一条能够到达目的网络且比较好的路由，而并非要寻找一条最佳路由，所以它采用的是路径-向量路由选择协议。在BGP协议中，每个自治系统选出一个BGP发言人，这些发言人通过相互交换自己的路径向量（即网络可达性的信息）后，就可找出到达各自治系统的比较好的路由。补充知识点：RIP、OSPF、BGP总结
主要特点网关协议路由表内容最优通路依据算法传送方式
RIP内部
目的网络，下一站，距离
跳数距离-向量协议运输层UDP简单、效率低、跳数
其他
为16不可达、好消息传的快，坏消息传的慢
OSPF内部
目的网络，下一站，距离
费用链路状态协议IP数据报效率高、路由器频繁交换信息，难维持一致性；规模大、统一度量为可达性
BGP外部
目的网络，完整路径
多种有关策略路径-向量协议建立TCP连接
【38】D。本题考查IP数据报的分片与重组；
数据报被分片后，每个分片都将独立地传输到目的地，期间有可能会经过不同的路径，而最后在目的端主机分组被重组。
【39】B。本题考查TCP首部各个标志位的意义，谢希仁第五版课本194页；
FIN位用来释放一个连接，它表示本方已经没有数据要传输了。然而，在关闭一个连接之后，对方还可以继续发送数据，所以还有可能接收到数据的。
【40】C。本题考查各种域名服务器的概念，参考补充知识点；
每一个主机都必须在授权域名服务器处注册登记，授权域名服务器一定能够将其管辖的主机名转换为该主机的IP地址。补充知识点：
域名服务器：因特网的域名系统DNS被设计成一个联机分布式的数据库系统，并采用客户/服务器模型。名字到域名的解析是由若干个域名服务器来完成的，域名服务器程序在专设的结点上运行，运行该程序的机器称为域名服务器。
一个服务器所负责管辖的（或有权限的）范围叫做区(zone)。各单位根据具体情况来划分自己管辖范围的区。但在一个区中的所有节点必须是能够连通的。每一个区设置相应的权限域名服务器，用来保存该区中的所有主机的域名到IP地址的映射。DNS服务器的管辖范围不是以“域”为单位，而是以“区”为单位，区一定小于等于域(课本228页图6-2)。因特网上的域名服务器系统是按照域名的层次来安排的，因此，每个域名服务器都只对域名体系中的一部分进行管辖。因此，共有以下四种不同类型的域名服务器：
（1）根域名服务器（最高层次的域名服务器）：根域名服务器是最重要的域名服务器。
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
所有的根域名服务器都知道所有的顶级域名服务器的域名和IP地址。不管是哪一个本地域名服务器，若要对因特网上任何一个域名进行解析，只要自己无法解析，就首先求助于根域名服务器。其他关于根域名服务器的详细细节请参考课本229页。
（2）顶级域名服务器：这些域名服务器负责管理在该顶级域名服务器注册的所有二级域名。当收到DNS查询请求时，就给出相应的回答（可能是最后的结果，也可能是下一步应当找的域名服务器的IP地址）。
（3）权限域名服务器：这就是前面已经讲过的负责一个区的域名服务器。当一个权限域名服务器还不能给出最后的查询回答时，就会告诉发出查询请求的DNS客户，下一步应当找哪一个权限域名服务器。
（4）本地域名服务器：本地域名服务器对域名系统非常重要。当一个主机发出DNS查询请求时，这个查询请求报文就发送给本地域名服务器。每一个因特网服务提供者ISP，或一个大学，甚至一个大学里的系，都可以拥有一个本地域名服务器，这种域名服务器有时也称为默认域名服务器。
其他补充：DNS域名服务器都把数据复制到几个域名服务器来保存，其中的一个是主域名服务器，其他的是辅助域名服务器。当主域名服务器出故障时，辅助域名服务器可以保证DNS的查询工作不会中断。主域名服务器定期把数据复制到辅助域名服务器中，而更改数据只能在主域名服务器中进行。这样就保证了数据的一致性。二、综合应用题答案与解析【41】本题考查计数排序的概念；解析：
（1）数据表中除了要设置一个变量来存储数据本身的信息外，还需要有一个数据域来表示每一个记录的关键字。因此数据表的结构如下：
（2）从题目给出的对计数排序算法的思想描述，我们可以大致得出需要两层循环，最外层的循环是对这n个记录进行处理，里层的循环式对每一个记录与其他记录的关键字进行比较，从而统计出计数值，即该记录在新表中应该存放的位置。
（3）从上面的程序中可以看出，程序有两层循环，对于有n个记录的表，关键码比较n2
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
次。
（4）结论：简单选择排序算法比本算法好。
简单选择排序比较次数是n(n-1)/2,，且简单选择排序仅用一个交换记录的空间；而计数排序的比较次数是n2，且需要另外开辟一个数组空间。
总结：（1）因题目要求“针对表中的每个记录，扫描待排序的表一趟”，所以比较次数是n2次。若限制“对任意两个记录之间应该只进行一次比较”，则可把以上算法中的比较语句改为：
（2）如果关键字有重复的话，那么对于关键字相同不同的表项会出现一样的统计值，这样在存储表项到新表中时就发生了冲突，简单的一种处理办法是，碰到冲突时，就将待存入的表项存放到紧邻的下一表项中，若仍然冲突则继续后移，直到找到一个没有冲突的位置来存放表项。
【42】本题考查二叉排序树算法的应用；解析：
（1）基本设计思想：
对二叉排序树来说，其中序遍历序列为递增有序序列。因此，对给定的二叉排序树进行中序遍历，如果能保证前一个值不比后一个值大，则说明该二叉树是一棵二叉排序树。（2）算法描述：
intpredt=INF;//假设INF为已定义的常量，它小于树中的任何值，predt始终
//记录着当所访问结点的前驱的值。
intjudBST(BTNode*bt){
intb1,b2;
if(bt==NULL)//空树是二叉排序树。
return1;else{
b1=judBST(bt->lchild);//递归的判断左子树是否是二叉排序树。if(b1==0||predt>bt->data)//左子树不是二叉排序树或者predt大
return0;//于当前根结点值则该树不是二叉排序树。
predt=bt->data;//将要访问右子树根的时候，predt记录下当前根结点的值。b2=judBST(bt->rchild);//递归的判断右子树是否为二叉排序树。returnb2;}
}
（3）时间复杂度与空间复杂度分析：
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
①时间复杂度分析：本题基本操作实质上对排序树的中序遍历序列中的元素的检查，即用当前元素与其前驱的比较。元素的个数为n因此时间复杂度为O(n)。
②空间复杂度分析：本题是个递归的过程，用到了系统栈，栈的最大深度决定了空间复杂度。对于一棵二叉树进行递归遍历，所需栈的最大深度即为二叉树的深度，对于结点树为n的二叉树，其深度为log2n级因此空间复杂度为O(log2n)。【43】本题考查主存地址的格式和Cache容量的计算；
解析：
（1）分析：根据组相联的定义，主存按Cache容量分区，每个区分为若干组，每组包含若干块。Cache也进行同样的分组和分块。主存中一个组内的块数与Cache中一个组内的块数相等。组间采用直接映射方式，组内采用全相连映射方式（主存中任何一个块均可以映像装入到Cache中对应组的任何一个块的位置上）。
·因为块的大小为64Bytes，内存是以字节编址的，所以需要6bit就可以表示出一个块的块内偏移。
·因为组间是直接映射，所以组的个数就应该为cache中的块数/每组中块的个数=32组，5bit即可表示所有组号。
·因为主存为32位，因此tag的位数应该为32-6-5=21位。综上分析，得出主存地址的格式为：
21位5位6位
TAG
组号
块内地址
（2）根据cache可知，需要1bit作为valid位，需要21bit对应相映射主存单元，64*8bit位
块的大小，所以Cache的总容量为(1+21+64*8)*128/8=8544B。【44】本题考查存储器与CPU的连接；解析：
存储器地址空间分布如图一所示，分三组，每组8K×8位。由此可得存储器方案要点如下：
（1）组内地址：A12——A0（A0为低位）；（2）组号译码使用2：4译码器；
（3）RAM1，RAM2各用两片SRAM芯片位进行并联连接，其中一片组成高4位，另一片组成低4位。
（4）用MREQ作为2：4译码器使能控制端，该信号低电平（有效）时，译码器工作。（5）CPU的R/W信号与SRAM的WE端连接，当R/W=1时存储器执行读操作，当R/W=0时，存储器执行写操作，如图二所示：
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
图一
CPU
图二
注意：考试一般不会直接要求考生从零开始画出图二，可能会给考生一定的基础框架，需要考生在框架的基础上再去连线，这个是很有可能会考查的，一定要重视！【45】本题考查位示图的相关内容；解析：
（1）位示图是利用二进制的一位来表示磁盘中一个盘块的使用情况，其值为“0”时，表示对应盘块空闲，为“1”时，表示已分配，地址空间分页，每页为1K，则对应盘块大小也为1K，主存总容量为256K，则可分成256个盘块．长5.2K的作业需要占用6页空间，假设页号与物理块号都是从0开始，则根据位示图，可得到页表内容。页表内容如下：
页号
012345
块号212728293435
（2）页式存储管理中有零头的存在，会存在内零头，为该作业分配内存后，会产生零头，因为此作业大小为5.2K，占6页，前5页满，最后一页只占了0.2K的空间，则零头大小为1K-0.2K=0.8K。
（3）64M内存，一页大小为4K，则共可分成64K∗1K/4K=l6K个物理盘块，在位示图中每一个盘块占1位，则共占16Kb空间，因为lB=8b，所以此位示图共占2KB空间的内存。【46】本题考查文件系统的目录检索；解析：
此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。
天勤论坛：www.csbiji.com
分析：“文件控制块分解法”能加快目录检索速度的原理是：目录是存在磁盘上的，所以检索目录的时候需要访问磁盘，速度很慢；而文件控制块分解法将文件控制块的一部分分解出去，存放在另一个数据结构中，而在目录中仅留下文件的基本信息和指向该数据结构的指针，这样一来就有效地缩减了目录的体积，减少了目录在磁盘中的块数，于是检索目录时读取磁盘的次数也减少，于是就加快了检索目录的次数。
【注】因为原本整个文件控制块都是在目录中的，而文件控制块分解法将文件控制块的部分内容放在了目录外，所以检索完目录后别忘了还需要读取一个磁盘找齐所有的文件控制块的内容。
（1）分解法前，目录的磁盘块数为64×254/512=31.75，即32块。所找的目录项在第1,2,3，…，32块的所需的磁盘访问次数分别为1,2,3，…，32次。所以查找该目录文件的某一个文件控制块的平均访问磁盘次数=（1+2+3+…+32）/32=16.5次。分解法后，目录的磁盘块数为10×254/512=4.96块，即5块。所找的目录项在第1、2、3、4、5块的所需的磁盘访问次数分别为2、3、4、5、6次（为何要多一次磁盘访问请看【注】）。所以查找该目录文件的某一个文件控制块的平均访问磁盘次数=（2+3+4+5+6）/5=4次。（2）分解法前平均访问磁盘次数：
（1+2+3+…+n）/n=n×（n+1）/2/n=(n+1)/2次
分解法后平均访问磁盘次数：
（2+3+4+…+（m+1））/m=m×（m+3）/2/m=(m+3)/2次。
为了使访问磁盘次数减少，显然需要：
（m+3）/2<（n+1）/2，即m 已知路由器C测得到自己的另连接路由器B、D和E的时延分别等于6、3和5.在收到、来自D的矢量(16,12,6,0,9,10)后，路由器C的路由表如图(一)所示。 路由器C的路由表(一) 站点ABC 下一跳DB— 度量196— 站点DEF 下一跳DED 度量3513 在收到来自E的矢量(7,6,3,9,0,4)后，路由器C的路由表如下图(二) 路由器C的路由表(二) 站点ABC 下一跳EB— 度量126— 站点DEF 下一跳DEE 度量359 在收到来自B的矢量(5,0,8,12,6,2)后，路由器C的路由表如图(三)所示。 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com 路由器C的路由表(三) 站点ABC 下一跳BB— 度量116— 站点DEF 下一跳DEB 度量358 总结：由于求的是最短路径，所以从表（一）到表（三），路由器C到其他站点的路径一定是越来越少。 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com 最后补充几道大题 【1】设向量A[0..n-1]中存有n个互不相同的整数，每个元素的值均在0到n-1之间。试写一算法将向量A排序，结果输出到另一个向量B[0..n-1]中。（1）给出算法的基本设计思想。 （2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（3）分析本题的时间复杂度与空间复杂度。 【2】请利用两个栈S1和S2来模拟一个队列，假设栈中元素为int型，栈中元素最多为MAX。已知栈的三个运算定义如下： PUSH(ST,x)：元素x入ST栈； POP(ST,&x)：ST栈顶元素出栈，赋给变量x； Sempty(ST)：判ST栈是否为空。 如何利用栈的运算来实现该队列的三个运算：enqueue:元素入队列；dequeue:元素出队列；queue_empty：判断队列是否为空，空返回1不，空返回0。要求： （1）给出基本设计思想。 （2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。 【3】已知一个带表头结点的自组织单链表的结点类型LinkNode定义为： structLinkNode{intdata;intfreq;structLinkNode*link;}; 其中data为结点值域，freq为该结点元素的访问计数，初始为0；link为指向链表中该结点后继结点的指针域，设该链表所有结点按照freq值从大到小链接。试编写一个查找函数Search，从链表首元结点开始查找结点data值与给定值相等的结点。如果找到，则将该结点的freq值加1，然后把它前移到与结点freq值相等的结点的后面，使得所有结点仍然都保持按照freq值从大到小链接。 （1）试写出算法的设计思路。 （2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。【4】设A、B是两个长度为n的整型数据的有序顺序表，如果把这2n个整数全部排序，位于第n个位置的整数称为中位数。试编写一个时间复杂度为O(log2n)的算法，求A和B的中位数。 （1）给出基本设计思想。 （2）根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。【5】硬磁盘共有4个记录面，存储区域内半径为10厘米，外半径为15.5厘米，道密度为60道/cm，外层位密度为600bit/cm，转速为6000r/min。问：（1）硬磁盘的磁道总数是多少？ （2）硬磁盘的容量是多少？磁盘的非格式化容量和格式化容量是一个什么概念，二者之间有个什么关系？ （3）将长度超过一个磁道容量的文件记录在同一个柱面上是否合理？ 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com （4）采用定长数据块记录格式，直接寻址的最小单位是什么？寻址命令中磁盘地址如何表示？ （5）假定每个扇区的容量512B，每个磁道有12个扇区，寻道的平均等待时间为10.5ms，试计算读出磁盘一个扇区中数据的平均时间。 【6】设CPU中各部件及其相互连接关系如下图所示。图中W是写控制标志，R是读控制标志，R1和R2是暂存器。 （1）假设要求在取指周期由ALU完成（PC）+1→PC的操作（即ALU可以对它的一个源操作数完成加1的运算）。要求以最少的节拍写出取指周期全部微操作命令及节拍安排。 （2）写出指令ADD#α（#为立即寻址特征，隐含的操作数在ACC中）在执行阶段所需的微操作命令及节拍安排。 __________ 【7】设CPU共有16根地址线，8根数据线，并用MREQ作访存控制信号（低电平有效），用WR作读写控制信号（高电平为读，低电平为写）。现有下列芯片及各种门电路（门电路自定），如图所示。画出CPU与存储器的连接图，要求： （1）存储芯片地址空间分配为：最大4K地址空间为系统程序区，相邻的4K地址空间为系统程序工作区，最小16K地址空间为用户程序区。（2）指出选用的存储芯片类型及数量。（3）详细画出片选逻辑。 _____ 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com （1）主存地址空间分配如下： 6000H～67FFH为系统程序区；6800H～6BFFH为用户程序区；（2）合理选用上述存储芯片，说明各选几片？（3）详细画出存储芯片的片选逻辑图。 补充题答案 【1】本题考查简单算法的应用； 解析： （1）算法设计思想： A[]数组地址范围为0~n-1，数值范围也是0~n-1，且数值各不相同，由此可知，对每个元素来说，元素值本身即指出了这个元素在数组中的位置。因此只需根据元素值将其存入数组B[]中合适的位置。（2）算法描述： voidSort(intA[],intB[],intn) { inti; for(i=0;i<=n-1;i++) B[A[i]]=A[i];//A[]数组中每个元素的值即为本元素在数组B[]中的地址。 } （3）时间复杂度分与空间复杂度析： ①本题为单层循环，B[A[i]]=A[i];为基本操作，执行次数为n，因此算法时间复杂度为O(n)。 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com ②本题用到一个与原序列长度相同的辅助数组，因此空间复杂度为O(n)。 【2】本题考查队列的的模拟算法； 解析： （1）基本思想 栈的特点是后进先出，队列的特点是先进先出。所以，用两个栈s1和s2模拟一个队列时，s1作输入栈，逐个元素压栈，以此模拟队列元素的入队。当需要出队时，将栈s1退栈并逐个压入栈s2中，s1中最先入栈的元素，在s2中处于栈顶。s2退栈，相当于队列的出队，实现了先进先出。只有栈s2为空且s1也为空，才算是队列空。 （2）算法描述 ①intenqueue(SqStack&s1,SqStack&s2,intx) /*s1是容量为MAX的栈。本算法将x入栈，若入栈成功返回1，否则返回0。*/{ inty; if(s1.top==MAX-1){ if(!Sempty(s2)) return0; elseif(Sempty(s2)){ //栈s1满，则看st2是否为空。 //s1满s2非空，这时s1不能再入栈，返回0。//若s2为空，先将s1退栈，元素压栈到s2。 while(!Sempty(s1)){ POP(s1,y); PUSH(s2,y);} PUSH(s1,x);//x入栈，实现了元素的入队，返回1。return1; }}else{ PUSH(s1,x);//st1没有满，则x直接入栈，返回1。return1;}} ②intdequeue(SqStack&s2,SqStack&s1,int&x) /*s2栈顶元素退栈，实现出队操作，x接受出队元素。成功返回1，否则返回0。*/{ inty; if(!Sempty(s2))//栈s2不空，则直接出队，返回1。{ POP(s2,x);return1。 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com }else//处理s2空栈。{ if(Sempty(s1)) return0;//若输入栈也为空，则判定队空，返回0。else//先将栈s1倒入s2中，再作出队操作。{ while(!Sempty(s1)){ POP(s1,y);PUSH(s2,y);} POP(s2,x);//s2退栈，实现队列出队return1;//返回1。}}} ③intqueue_empty(SqStacks2,SqStacks2)/*本算法判用栈s1和s2模拟的队列是否为空。*/{ if(Sempty(s1)&&Sempty(s2))elsereturn0;} return1;//队列空。 //队列不空。 【3】本题考查链表的基本算法； 解析： （1）算法的设计思路 设置3个指针p、pre和q，从链表的首元结点开始，用p作为检测指针顺序检测，比较给定值value与p->data，指针pre是亦步亦趋跟在*p后面的前驱指针，为从链中摘下*p而用。另外用指针q用于记忆freq下降的结点，为插入结点*p而用。若设链表有n个结点，查找成功时指针*p停留在第i（1≤i≤n）个结点，则算法的平均查找长度为n(n-1)/2。删除和插入结点*p时仅修改指针。f 查找12f 381q381q441p12144175023pree75012p023pre0∧0∧pre后摘下p,插入q后面（2）算法描述. boolselfOrganizationList(LinkNode*f,intvalue,LinkNode*&p); LinkNode*pre,*q;p=q=f->link;pre=f; while(p!=NULL&&p->data!=value){ 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com if(pre!=f&&pre->freq>p->freq)q=pre;pre=p; p=p->link; } if(p==NULL) returnfalse;p->freq++; pre->link=p->link; p->link=q->link;q->link=p;returntrue;}; 【4】本题考查折半查找算法的应用； 解析：去年出题方式是让考生分析自己所设计算法的时间复杂度，当然很有可能反着考，即让考生设置一个复杂度已给出的算法，希望考生引起重视；（1）算法设计思路 设A、B是长度为k的有序表，比较它们各自的中位数A[k/2]和B[k/2]： (1)如果A[k/2]==B[k/2]，则A[k/2]同时大于A[0]～A[k/2-1]和B[0]～B[k/2-1]， A[k/2]即为第k大的整型数； (2)如果A[k/2]>B[k/2]，则A[k/2]～A[k]都大于B[0]～B[k/2-1]，且B[k/2]～B[k] 都大于B[0]～B[k/2-1]，第k大的整数不可能在B[0]～B[k/2-1]，舍弃B[0]～B[k/2-1]。类似地，第k大的整数也不可能在A[k/2+1]～A[k]中，舍弃之，这样得到两个新的序列A[0]～A[k/2]和B[k/2]～B[k]，再对它们递归处理。(3)如果A[k/2] （2）算法的描述 intmedian(intA[],intB[],intleftA,intrightA,intleftB,intrightB){ if(leftA if(A[midA]==B[midB])returnA[midA];if(A[midA]>B[midB]) madian(A,B,leftA,midA,midB,rightB); else median(A,B,midA,rightA,leftB,midB); } if(A[leftA]>B[leftB]) returnA[leftA]; else returnB[leftB]; } 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com 因为每次比较都能把参加比较的元素减少一半，所以递归深度为log2n，即比较次数达到log2n，算法的时间复杂度为O(log2n)。 【5】本题考查磁盘的基本概念； 解析： （1）有效存储区域=15.5–10=5.5（cm），道密度=60道/cm，因此每个面60×5.5=330道，即有330个柱面，磁道总数＝4×330＝1320个磁道。（2）外层磁道的长度为2πR=2×3.14×15.5=97.34（cm） 每道信息量=600位/cm×97.34cm=58404位=7300B磁盘总容量=7300B×1320=9636000B（非格式化容量） 磁盘在使用之前要对其执行格式化操作，要首先完成划分磁道和扇区，设置文件目录区等。非格式化容量是指一个盘片上可以记录的二进制位的总数量，而格式化容量通常是指用户可用空间的二进制位的总数量，前者比后者要大，因为系统要管理磁盘会占用一定的存储空间，还要使用一个磁道用于同步，扇区之间还有间隔和一些为保存检错纠错信息的空间，磁盘上往往还会留有一些备份磁道。在谈到磁盘容量时,通常指的是格式化之后用户可用的磁盘容量。 （3）如果长度超过一个磁道容量的文件，将它记录在同一个柱面上比较合理，因为不需要重新寻找磁道，这样数据读/写速度快。 （4）采用定长数据块格式，直接寻址的最小单位是一个扇区，每个扇区记录固定字节数目的信息，在定长记录的数据块中，活动头磁盘组的编址方式可用如下格式： 15141376430 硬盘号 柱面号 磁头号 扇区号 此地址格式表示最多可以接4台硬盘，每台最多有8个记录面，每面最多可有128个磁 道，每道最多可有16个扇区。 （5）读一个扇区中数据所用的时间： 找磁道的时间+找扇区的时间+磁头扫过一个扇区的时间 找磁道时间是指磁头从当前所处磁道运动到目标磁道的时间，一般选用磁头在磁盘径向方向上移动1/2个半径长度所用时间为平均值来估算，题中给的是10.5ms。 找扇区的时间是指磁头从当前所处扇区运动到目标扇区的时间，一般选用磁盘旋转半周的所用时间作为平均值来估算，题中给出磁盘转速为每分钟6000转，则每秒为100转，即转磁盘转一周用时为10ms，转半周的时间是5ms。 题中给出每个磁道有12个扇区，磁头扫过一个扇区用时为10/12=8.33ms，计算结果应该为10.5+5+0.83=16.33(ms)。 为了减少寻找磁道和等待扇区所占时间的比例，磁盘通常应该以多个扇区为单位进行读写，一旦开始具体的读写操作，就对多个连续的扇区进行顺序读写，读些的数据首先保存到系统设置的一个缓存区中，CPU通常要经过操作系统实现与这个缓冲区交换数据，而不是直接与磁盘设备本身交换数据。 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com 【6】本题考查微命令和节拍的设置；解析： 【7】本题考查CPU与存储器的连接；解析： （2）根据主存地址空间分配，最大4K地址空间为系统程序区，选用2片2K×8位ROM芯片；相邻的4K地址空间为系统程序工作区，选用2片4K×4位RAM芯片。最小16K地址空间为用户程序区，选用2片8K×8位RAM芯片。（3）存储芯片的片选逻辑图如下图所示： 此模拟试卷为天勤论坛所著，任何商业机构不得用来进行任何利益交易。 天勤论坛：www.csbiji.com 提醒：这八套试卷组成的大题没有涉及浮点数的加减，但是这个是重点，希望考生能够把课本上的步骤牢牢记住，最后，天勤论坛管理团队祝每一位考生都能圆梦！ 因篇幅问题不能全部显示，请点此查看更多更全内容