即k=log2n+C（为方便说明，其中C为起修正作用的常数）。
综上得：
时间复杂度为O（log2n）。
【2】元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是（）。
A.3B.4C.5D.6
【解析】B。
若要保证出栈序列以d开头，则前三个元素必连续进栈，中间不能出现出栈的情况，然后d出栈，此时栈内元素由底到顶为，a,b,c，栈外元素为e，出栈序列中元素为d。
因为a,b,c三个元素在栈内的顺序已定，由栈的先进后出原则，其在出栈序列中的相对位置必为…c…b…a…；加上d的位置已定，所以出栈待定序列必为d…c…b…a…。
显然在栈外的e可以在任何时候出栈入栈，即可以出现在以上待定序列中任何一个省略号的位置，即出栈序列可为：
1:
d,e,c,b,a；2:
d,c,e,b,a；3:
d,c,b,e,a；4:
d,c,b,a,e。
【3】已知循环队列存储在一维数组A[0…n-1]中，且队列非空时front和rear分别指向队头和队尾元素。
若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是（）。
A.0,0B.0,n-1C.n-1,0D,n-1,n-1
【解析】B。
插入元素时，front不变，rear+1.而插入第一个元素后，队尾要指向尾元素，显然，rear初始应该为n-1，front为0。
【4】若一棵完全二叉树有768个结点，则该二叉树中叶子结点的个数是（）。
A.257B.258C.384D.385
【解析】C。
由完全二叉树的高度和结点个数的关系可得本完全二叉树的高度为10。
第10层上的结点个数为768-（29-1）=257（这些全为叶子结点）；第9层上的非叶结点为（257-1）/2+1=129；则第9层上的叶子结点个数为：
29-1-129=127；则叶子结点总数为257+127=384。
【5】若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是（）。
A.1,2,3,4
树排除选项：
B.2,3,4,1C.3,2,4,1D.4,3,2,1【解析】C。
满足题干的二叉树必须满足树中不存在双分支结点。
则可以画出以下二叉
可以看出A,B,D三项都是可以的。
【6】已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点的个数是（）。
A.115B.116C.1895D.1896
【解析】D
。
可以采用特殊情况法去解。
可举以下特例：
如上图，则对应的二叉树中仅有前115个结点有右孩子。
【7】对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）。
A.95,22,91,24,94,71
C.21,89,77,29,36,38
【解析】A
。
B.92,20,91,34,88,35D.12,25,71,68,33,34
由选项A做出查找路径的一部分，发现在91的左子树中出现了大于91的94，因此A
选项不可能。
【8】下列关于图的叙述中，正确的是（）。
①回路是简单路径
②存储稀疏图，用邻接矩阵比邻接表更省空间
③若有向图中存在拓扑序列，则该图不存在回路
A.仅①
【解析】C。
（1）若路径中除了开始点和结束点可以相同以外，其余顶点均不相同，则称这条路径为简单路径。
（2）若一条路径中第一个顶点和最后一个顶点相同，则这条路径是一条回路（回路中可能存在既不是起点也不是终点的相同点）。
（3）邻接矩阵不图稀疏还是稠密，都取的是最大的存储空间，因此不如邻接表更适合存储稀疏矩阵。
（4）用拓扑排序的方法可以判断图中是否存在回路，如果对一个图可以完成拓扑排序，则此图不存在回路。
【9】为提高散列（Hash）表的查找效率，可采取的正确措施是（）。
①增大装填因子
②设计冲突少的散列函数
③处理冲突时避免产证聚集现象
A.仅①
【解析】B。
要提高查找效率，就要减少Hash表的冲突，因此②是正确的措施。
对于①装填因子增大，则相应的表中空闲位置就少，更容易发生冲突，因此①不对。
聚集现象是不可避免的，因此③不对。
【10】为实现快速排序算法，待排序序列宜采用的存储方式是（）。
A.顺序存储B.散列存储C链式存储D索引存储
【解析】A。
内部排序均采用顺序结构存储。
【11】已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（）。
A.1
【解析】B。
在序列尾部插入18
后当前堆如下：
B.2C.4D.5B.仅②C.仅①②D.仅②③B仅①、②C仅③D仅①、③
可见10<18（第一次比较），需要调整，因此交换10和10
得如下堆：
可见18<25（第二次比较）不需要再次调整，因此只需要调整2次。
【12】下列选项中，描述浮点数操作速度指标的是（）。
A.MIPSB.CPIC.IPCD.MFLOPS
【解析】D。
这个不需要解释了，MFLOPS表示每秒百万次浮点运算。
【13】float型数据通常用IEEE754单精度浮点数格式表示。
如编译器将float型变量x分配在一个32位浮点寄存器FR1中，且x=-8.25，则FR1的内容是（）。
A.C1040000HB.C2420000HC.C1840000HD.C1C20000H
11【解析】A。
此题着重考查了IEEE754单精度浮点数格式。
只要知道格式，基本上就是硬套公式了。
首先，将x表示成二进制，即-1000.01=-1.00001×2。
其次应该计算阶码（不
妨设为E），根据IEEE754单精度浮点数格式有E-127=3，故E=130，换成二进制为10000010。
最后，要记住最高位“1”是被隐藏的。
所以，根据IEEE754格式：
符号（1位）+偏移的阶码（8位）+尾数（23位），即：
1+10000010+0000100000000000000
转换成十六进制：
11000001000001000000000000000000，即C1040000H。
【14】下列各类存储器中，不采用随机存取方式的是（）。
A.EPROMB.CDROMC.DRAMD.SRAM
【解析】B。
首先，ROM和RAM都是随机存储的。
而EPROM属于ROM；SRAM和DRAM属于RAM，故都是采用随机存取方式。
而CDROM属于光盘，为非随机存储。
【15】某计算机存储器按字节编址，主存地址空间大小为64MB，现用4Mx8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是（）。
A.22位B.23位C.25位D.26位
【解析】D。
本题有个陷阱，相信不少考生会以32MB的实际主存来计算，从而得到答案25位，这种解法是错误的。
尽管多余的32MB没有使用，但是你也得防备以后要用。
不能只看眼前呀！
知道以64MB来计算就很好做了。
由于采用字节寻址，所以寻址范围是64M，而226=64M。
故存储器地址寄存器MAR的位数至少是26位。
【16】偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。
下列寻址方式中，不属于偏移寻址方式的是（）。
A.间接寻址
考寻址方式总结。
各种寻址方式的有效地址和用途总结：
寻址方式
立即寻址
直接寻址
隐含寻址
一次间接寻址有效地址计算方式——用途及特点通常用于给寄存器赋初值——缩短指令字长。
扩大寻址范围，易于完成子程
序返回。
B.基址寻址C.相对寻址D.变址寻址【解析】A。
B、C、D都是某个寄存器内容与一个形式地址相加而生成有效地址，请参EA=A——EA=（A）
寄存器寻址
寄存器间接寻址
基址寻址EA=RiEA=（Ri）EA=A+（BR）指令字较短；指令执行速度较快。
扩大寻址范围。
扩大操作数寻址范围；适用于多道程序设计，常用于为程序
或数据分配存储空间。
变址寻址
相对寻址
先间接再变址EA=A+（IX）EA=A+（PC）EA=（A）+（IX）主要用于处理数组问题。
用于转移指令和程序浮动——
【17】某机器有一个标志寄存器，其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt（无符号整数比较大于时转移）的转移条件是（）。
A.CF+OF=1B.SF+ZF=1C.CF+ZF=1D.CF+SF=1
【解析】C。
假设有两个无符号整数x、y，bgt为无符号整数比较大于时转移，不妨设x>y，那么x−y就肯定大于0且不会溢出，故符号标志SF和溢出标志OF用不上。
根据排除法答案自然选C。
因为x−y>0，所以肯定不会借位和进位，且x−y≠0。
故CF和ZF标志均为0。
【18】下列给出的指令系统特点中，有利于实现指令流水线的是（）。
I.指令格式规整且长度一致
II.指令和数据按边界对齐存放
III.只有Load/Store指令才能对操作数进行存储访问
A.仅I、IIB.仅II、IIIC.仅I、IIID.I、II、III
【解析】D。
I、II、III均为RISC的特性，所以都可以简化流水线的复杂度。
�选取使用频度较高的一些简单指令以及一些很有用但又不复杂的指令，让复杂指令指令长度固定，指令格式总类少，寻址方式种类少。
只有取数/存数指令访问存储器，其余指令的操作都在寄存器内完成。
CPU中有多个通用寄存器（比CISC的多）。
采用流水线技术（注意：
RISC一定是采用流水线），大部分指令在一个时钟周期的功能由频度高的简单指令的组合来实现。
内完成。
采用超标量和超流水线技术（这两个技术在第五章会详细讲解，这里知道就好），可使每条指令的平均执行时间小于一个时钟周期。
�控制器采用组合逻辑控制，不用微程序控制（什么是组合逻辑第二章讲过，说白了采用优化的编译程序。
就是N多的逻辑电路；微程序控制将会在第五章讲解）。
【19】假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是（）。
A.每个指令周期中CPU都至少访问内存一次
B.每个指令周期一定大于或等于一个CPU时钟周期
C.空操作指令的指令周期中任何寄存器的内容都不会被改变
D.当前程序在每条指令执行结束时都可能被外部中断打断
【解析】C。
由于不采用Cache和指令预取技术，所以不可能从Cache以及在前一个指令执行的时候取指令，所以每个指令周期中CPU必须访问一次主存取指令，故A正确。
B是显然正确。
至少PC寄存器的内容会自加1，故C错误。
由于机器处于“开中断”状态，所以当前程序在每条指令执行结束时都可能被外部中断打断。
【20】在系统总线的数据线上，不可能传输的是（）。
A.指令
C.握手（应答）信号
号必须在通信总线中传输。
总结：
总线被分为片内总线、系统总线（包括数据总线、控制总线、地址总线）、通信总线。
【21】某计算机有五级中断L4~L0，中断屏蔽字为M4M3M2M1M0,Mi=1（0≤i≤4）表示对Li级中断进行屏蔽。
若中断响应优先级从高到低的顺序是L0→L1→L2→L3→L4，且要求中断处理优先级从高到低的顺序是L4→L0→L2→L1→L3，则L1的中断处理程序中设置的中断屏蔽字是（）。
A.11110B.01101C.00011D.01010
【解析】D。
只要知道做题方法，5秒钟搞定。
首先看L1所在的位置。
后面只有L3比自己低，所以把自己和L3位置的屏蔽触发器的内容置为1，其余为0，即01010。
【22】某计算机处理器主频为50MHz，采用定时查询方式控制设备A的I/O，查询程序运行一次所用的时钟周期至少为500。
在设备A工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是（）。
A.0.02%B.0.05%C.0.20%D.0.50%
【解析】C。
由于CPU每秒需对其查询至少200次，每次500个时钟周期。
所以CPU用于设备A的I/O时间每秒最少500×200=100000个时钟周期。
故CPU用于设备A的I/O的时间占整个CPU时间的百分比至少为：
B.操作数D.中断类信号【解析】C。
指令、操作数、中断类信号都是可以在数据线上传输，而握手（应答）信
100000100000×100%=×100%=0.2%50M50000000
【23】下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（
A．先来先服务
B．高响应比优先
C．时间片轮转
D．非抢占式短任务优先）。
【解答】B。
这里考察的是多种作业调度算法的特点。
响应比=作业响应时间/作业执行时间=（作业执行时间+作业等待时间）/作业执行时间。
高响应比算法，在等待时间相同情况下，作业执行的时间越短，响应比越高，满足段任务优先。
同时响应比会随着等待时间增加而变大，优先级会提高，能够避免饥饿现象。
【24】下列选项中，在用户态执行的是（）。
A．命令解释程序B．缺页处理程序C．进程调度程序
D．时钟中断处理程序
【解析】A。
CPU状态分为管态和目态，管态又称特权状态、系统态或核心态。
通常，操作系统在管态下运行，CPU在管态下可以执行指令系统的全集。
目态又称常态或用户态，机器处于目态时，程序只能执行非特权指令，用户程序只能在目态下运行。
CPU将指令分为特权指令和非特权指令，对于那些危险的指令，只允许操作系统及其相关模块使用，普通的应用程序不能使用。
缺页处理与时钟中断都属于中断，会对系统造成影响，因此只能在核心态执行。
进程调度属于系统的一部分，也只能在核心态执行。
命令解释程序属于命令接口，是操作系统提供给用户所使用的接口，因此可以用在用户态执行。
补充：
常见的特权指令有以下几种
（1）有关对I/O设备使用的指令。
如启动I/O设备指令、测试I/O设备工作状态和控制I/O设备动作的指令等。
（2）有关访问程序状态的指令。
如对程序状态字（PSW）的指令等。
（3）存取特殊寄存器指令。
如存取中断寄存器、时钟寄存器等指令。
（4）其他指令
本题中B、D都是要修改中断寄存器，C要修改程序状态字（PSW）。
【25】在支持多线程的系统中，进程P创建的若干个线程不能共享的是（A．进程P的代码段B．进程P中打开的文件C．进程P的全局变量）。
D．进程P中某线程的栈指针
【解析】D。
进程是资源分配的基本单元，进程下的各线程可以并行执行，它们共享进程的虚地址空间，但各个进程有自己的栈，各自的栈指针对其他线程是透明的，因此进程P中某线程的栈指针是不能共享的。
【26】用户程序发出磁盘I/O请求后，系统的正确处理流程是（）。
A．用户程序→系统调用处理程序→中断处理程序→设备驱动程序B．用户程序→系统调用处理程序→设备驱动程序→中断处理程序C．用户程序→设备驱动程序→系统调用处理程序→中断处理程序D．用户程序→设备驱动程序→中断处理程序→系统调用处理程序
【解析】B。
首先用户程序（目态）是不能直接调用设备驱动程序的，有关对I/O设备使用的指令是特权指令，通过系统调用，把进程的状态从用户态变为核心态，故C、D错误。
I/O软件一般从上到下分为四个层次：
用户层、与设备无关软件层、设备驱动程序及中断处理程序。
与设备无关软件也就是系统调用的处理程序。
因此正确处理流程为B。
【27】某时刻进程的资源使用情况如下表所示：
进程
R1
P1P2P3P4
2100
已分配资源
R20210
R30011
R10112
仍需分配
R20330
R31210
R10
可用资源
R22
R31
此时的安全序列是（）。
A.P1,P2，P3,P4B.P1，P3，P2，P4C.P1，P4，P3，P2D.不存在
【解析】D。
使用银行家算法可知，不存在安全序列。
由于初始R1资源没有剩余，只能分配资源给P1执行，P1完成之后释放资源，这时由于R2只有2个剩余，因此只能分配对应资源给P4执行，P4完成之后释放资源，但此时R2仍然只有2个剩余，无法满足P2、P3的要求，无法分配。
因此产生死锁状态。
【28】在缺页处理过程中，操作系统执行的操作可能是（）。
I修改页表II磁盘I/OIII分配页框
A.仅I,IIB.仅IIC.仅IIID.I,II和III
【解析】D。
这些情况都可能发生，当产生缺页中断时，肯定会修改页表项并分配页框（分配页框出现在有空余页面的情况下），并且会从外存将所缺页调入，产生磁盘I/O。
【29】当系统发生抖动（trashing）时，可以采取的有效措施是（）。
I.撤销部分进程
II.增加磁盘交换区的容量III.提高用户进程的优先级
A.仅IB.仅IIC.仅IIID.仅I,II
【解析】A。
在具有对换功能的操作系统中，通常把外存分为文件区和对换区。
前者用于存放文件，后者用于存放从内存中换出的进程。
抖动现象是指刚刚被换出的内容又要被访问，因此马上又要换入这种系统频繁置换页面的现象。
发生抖动时系统会将大部分时间用于处理页面置换上，降低系统效率。
撤销部分进程可以减少系统页面数，可以有效防止系统抖动。
改变优先级与增大交换区容量对减少抖动没有帮助。
【30】在虚拟内存管理中，地址变换机构将逻辑地址变为物理地址，形成该逻辑地址的阶段是（）。
A.编辑B.编译C.链接D.装载
【解析】B。
编译过程指编译程序将用户源代码编译成目标模块，在编译源代码的过程中，编译程序会将程序所使用的变量地址信息转化为逻辑地址。
编辑过程是指编辑源代码的过程，此时还没有地址的概念。
而链接和装载都是对编译好的程序进行处理，包括将逻辑地址转化为物理地址。
【31】某文件占10个磁盘块，现要把文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。
在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是（）。
A.1500μs，1000μsB.1550μs，1100μs
C.1550μs，1550μtsD.2000μs，2000μs
【解析】B。
单缓冲区当上一个磁盘块从缓冲区读入用户区完成时下一磁盘块才能开始读入，也就是当最后一块磁盘块读入用户区完毕时所用时间为150×10=1500，加上处理最后一个磁盘块的时间50，得1550。
双缓冲区情况下，不存在等待磁盘块从缓冲区读入用户区的问题，因此传输数据全部传输到缓冲区的时间为100×10=1000，再加上将双缓冲区的数据传输到用户区并处理完的时间2×50=100，得1100。
【32】有两个并发执行的进程P1和P2，共享初值为1的变量x。
P1对x加1，P2对x减1。
加1和减1操作的指令序列分别如下所示。
//加1操作//减1操作
loadR1，x①//取x到寄存器R1中loadR2，x④
incR1②decR2⑤
storex,R1③//将R1的内容存入xstorex，R2⑥
两个操作完成后，x的值（）。
A.可能为-1或3B.只能为1
C.可能为0、1或2D.可能为-1、0、1或2
【解答】C。
执行①②③④⑤⑥结果为1，执行①②④⑤⑥③结果为2，执行④⑤①②③⑥结果为0，结果-1无法得到。
【33】TCP/IP参考模型的网络层提供的是（）。
A.无连接不可靠的数据报服务
C.有链接不可靠的虚电路服务B.无连接可靠的数据报服务D.有链接可靠的虚电路服务
【解析】A。
首先，网络层的传输采用的是IP分组，IP分组中头部含有源IP地址和目的IP地址，并不是一个虚电路号，所以网络层采用的是数据报服务；其次，IP分组的头部也没有对分组进行编号和提供校验字段，所以网络层提供的是不可靠服务；最后，IP分组首部也没有相关的建立连接的字段，所以网络层属于无连接。
【34】若某通信链路的数据传输速率为2400bps，采用4相位调制，则该链路的波特率是（）。
A.600波特B.1200波特C.4800波特D.9600波特
【解析】B。
题目中说采用4个相位，换句话说就是可以表示4种状态，故一个码元可以携带2bit（2=4）的信息。
根据比特率（或者称为数据传输率）和波特率的关系。
假设每个码元可以携带n位信息，则比特率=n×码元率，由题意可知，比特率为2400bps，且n=2，故码元率为1200bps。
【35】数据链路层采用选择重传协议（SR）传输数据，发送方已发送了0~3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是（）。
A.1B.2C.3D.4
【解析】B。
此题需要考生很清楚的了解选择重传的工作原理。
选择重传协议是不支持累积确认的。
何为累积确认？
即如果发送方连续发送0、1、2、3、4号帧。
前面0、1、2、3号帧的确认都丢失，但是在发送方重发之前却收到了ACK5，表明前面的0、1、2、3、4都已经收到，接收方期待5号帧的接收。
后退N帧协议是支持累积确认的。
回到题目，由于只收到1号帧的确认，0、2号帧超时，且由于不支持累积确认，所以需要重传0、2号帧。
如果此题数据链路层采用后退N帧协议（GBN）传输数据，由于它具有累积确认的作用，答案就应该选择A了。
可能疑问点：
如果不按序的接收，交给主机的话岂不是全部乱套了？
解析：
如果没有按序，正确的接收帧先存入接收方的缓冲区中，同时要求发送方重传出错帧，一旦收到重传帧后，就和原先存在缓冲区的其余帧一起按正确的顺序送主机。
所以说选择重传协议避免了重复传输那些本来已经正确到达接收方的数据帧，进一步提高了信道利用率。
但是代价是增加了缓冲空间。
【36】下列选项中，对正确接收到的数据帧进行确认的MAC协议是（）。
A.CSMAB.CDMAC.CSMA/CDD.CSMA/CA
【解析】D。
此题相信大部分考生的情况是对于A和C比较熟悉，B和D完全不知所云。
因为在复习的过程中可能不会太在意。
CSMA/CD协议相信考生再熟悉不过，整个过程也能够倒背如流，并没有看到任何需要进行确认的影子，立马可以被排除。
其次，CSMA/CD协议是对CSMA协议的改进，既然CSMA/CD都没有，那CSMA协议就必然没有。
CSMA/CA主要用在无线局域网中，由IEEE802.11标准定义，它在CSMA的基础上增加了冲突避免的功能。
冲突避免要求每个结点在发送数据之前监听信道。
如果信道空闲，则发送数据。
发送结点在发送完一个帧后，必须等待一段称为帧间间隔的时间，检查接收方是否发回帧的确认。
如果收到确认，则表明无冲突发生；如果在规定时间内没有收到确认，表明出现冲突，重发该帧。
CDMA被称为码分多路复用，工作在物理层，不存在对数据帧进行确认。
【37】某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。
为使R1可以将IP分组正确地路由到图中所有子网，则在R1中需要增加的一条路由（目地网络，子网掩码，下一跳）是（）。
【解析】D。
很明显本题考察了路由聚合的相关知识点。
首先将网络192.168.2.0/25和网络192.168.2.128/25进行聚合。
方法如下：
192.168.
升级会员 