x=2*x;
A.O（log2n）B.O（n）C.O（nlog2n）D.O（n2）
2.元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是
A.3B.4C.5D.6
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
4.若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是
A.257B.258C.384D.385
5.若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是
A.1,2,3,4B.2,3,4,1C.3,2,4,1D.4,3,2,1
6.已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是
A.115B.116C.1895D.1896
7.对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是
A.95,22,91,24,94,71B.92,20,91,34,88,35
C.21,89,77,29,36,38D.12,25,71,68,33,34
8.下列关于图的叙述中，正确的是
I.回路是简单路径
II.存储稀疏图，用邻接矩阵比邻接表更省空间
III.若有向图中存在拓扑序列，则该图不存在回路
A.仅IIB.仅I、IIC.仅IIID.仅I、III
9.为提高散列（Hash）表的查找效率，可以采取的正确措施是
I.增大装填（载）因子
II.设计冲突（碰撞）少的散列函数
III.处理冲突（碰撞）时避免产生聚集（堆积）现象
A.仅IB.仅IIC.仅I、IID.仅II、III
10.为实现快速排序算法，待排序序列宜采用的存储方式是
A.顺序存储B.散列存储C.链式存储D.索引存储
11.已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是
A.1B.2C.4D.5
12.下列选项中，描述浮点数操作速度指标的是
A.MIPSB.CPIC.IPCD.MFLOPS
13.float型数据通常用IEEE754单精度浮点数格式表示。
若编译器将float型变量x分配在一个32位浮点寄存器FR1中，且x=-8.25，则FR1的内容是
A.C1040000HB.C2420000HC.C1840000HD.C1C20000H
14.下列各类存储器中，不采用随机存取方式的是
A.EPROMB.CDROMC.DRAMD.SRAM
15.某计算机存储器按字节编址，主存地址空间大小为64MB，现用4M×8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是
A.22位B.23位C.25位D.26位
16.偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。
下列寻址方式中，不属于偏移寻址方式的是
A.间接寻址B.基址寻址C.相对寻址D.变址寻址
17.某机器有一个标志寄存器，其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt（无符号整数比较大于时转移）的转移条件是
A.CF+OF=1B.=1C.=1D.=1
18.下列给出的指令系统特点中，有利于实现指令流水线的是
I.指令格式规整且长度一致II.指令和数据按边界对齐存放
III.只有Load/Store指令才能对操作数进行存储访问
A.仅I、IIB.仅II、IIIC.仅I、IIID.I、II、III
19.假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是
A.每个指令周期中CPU都至少访问内存一次
B.每个指令周期一定大于或等于一个CPU时钟周期
C.空操作指令的指令周期中任何寄存器的内容都不会被改变
D.当前程序在每条指令执行结束时都可能被外部中断打断
20.在系统总线的数据线上，不可能传输的是
A.指令B.操作数
C.握手（应答）信号D.中断类型号
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
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%
23.下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是
A.先来先服务B.高响应比优先
C.时间片轮转D.非抢占式短任务优先
24.下列选项中，在用户态执行的是
A.命令解释程序B.缺页处理程序
C.进程调度程序D.时钟中断处理程序
25.在支持多线程的系统中，进程P创建的若干个线程不能共享的是
A.进程P的代码段B.进程P中打开的文件
C.进程P的全局变量D.进程P中某线程的栈指针
26.用户程序发出磁盘I/O请求后，系统的正确处理流程是
A.用户程序→系统调用处理程序→中断处理程序→设备驱动程序
B.用户程序→系统调用处理程序→设备驱动程序→中断处理程序
C.用户程序→设备驱动程序→系统调用处理程序→中断处理程序
D.用户程序→设备驱动程序→中断处理程序→系统调用处理程序
27.某时刻进程的资源使用情况如下表所示。
进程已分配资源尚需资源可用资源
R1R2R3R1R2R3R1R2R3
P1*******21
P2120132
P3011131
P4001200
此时的安全序列是
A.P1,P2,P3,P4B.P1,P3,P2,P4
C.P1,P4,P3,P2D.不存在
28.在缺页处理过程中，操作系统执行的操作可能是
I.修改页表II.磁盘I/OIII.分配页框
A.仅I、IIB.仅IIC.仅IIID.I、II和III
29.当系统发生抖动（thrashing）时，可以采取的有效措施是
I.撤销部分进程
II.增加磁盘交换区的容量
III.提高用户进程的优先级
A.仅IB.仅IIC.仅IIID.仅I、II
30.在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是
A.编辑B.编译C.链接D.装载
31.某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。
假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。
在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是
A.1500μs、1000μsB.1550μs、1100μs
C.1550μs、1550μsD.2000μs、2000μs
32.有两个并发执行的进程P1和P2，共享初值为1的变量x。
P1对x加1，P2对x减1。
加1和减1操作的指令序列分别如下所示。
//加1操作
loadR1,x//取x到寄存器R1中
incR1
storex,R1//将R1的内容存入x//减1操作
loadR2,x
decR2
storex,R2
两个操作完成后，x的值
A.可能为-1或3B.只能为1
C.可能为0、1或2D.可能为-1、0、1或2
33.TCP/IP参考模型的网络层提供的是
A.无连接不可靠的数据报服务B.无连接可靠的数据报服务
C.有连接不可靠的虚电路服务D.有连接可靠的虚电路服务
34.若某通信链路的数据传输速率为2400bps，采用4相位调制，则该链路的波特率是
A.600波特B.1200波特C.4800波特D.9600波特
35.数据链路层采用选择重传协议（SR）传输数据，发送方已发送了0~3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是
A.1B.2C.3D.4
36.下列选项中，对正确接收到的数据帧进行确认的MAC协议是
A.CSMAB.CDMAC.CSMA/CDD.CSMA/CA
37.某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。
为使R1可以将IP分组正确地路由到图中所有子网，则在R1中需要增加的一条路由（目的网络，子网掩码，下一跳）是
A.192.168.2.0，255.255.255.128，192.168.1.1
B.192.168.2.0，255.255.255.0，192.168.1.1
C.192.168.2.0，255.255.255.128，192.168.1.2
D.192.168.2.0，255.255.255.0，192.168.1.2
38.在子网192.168.4.0/30中，能接收目的地址为192.168.4.3的IP分组的最大主机数是
A.0B.1C.2D.4
39.主机甲向主机乙发送一个（SYN=1,seq=11220）的TCP段，期望与主机乙建立TCP连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP段可能是
A.（SYN=0,ACK=0,seq=11221,ack=11221）
B.（SYN=1,ACK=1,seq=11220,ack=11220）
C.（SYN=1,ACK=1,seq=11221,ack=11221）
D.（SYN=0,ACK=0,seq=11220,ack=11220）
40.主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3个连续的TCP段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。
若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是
A.300B.500C.1200D.1400
二、综合应用题：
41～47小题，共70分。
请将答案写在答题纸指定位置上。
41.（8分）已知有6个顶点（顶点编号为0~5）的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。
46∞∞∞5∞∞∞43∞∞33
要求：
（1）写出图G的邻接矩阵A。
（2）画出有向带权图G。
（3）求图G的关键路径，并计算该关键路径的长度。
42.（15分）一个长度为L（L≥1）的升序序列S，处在第éL/2ù个位置的数称为S的中位数。
例如，若序列S1=（11,13,15,17,19），则S1的中位数是15。
两个序列的中位数是含它们所有元素的升序序列的中位数。
例如，若S2=（2,4,6,8,20），则S1和S2的中位数是11。
现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
43.（11分）假定在一个8位字长的计算机中运行如下类C程序段：
unsignedintx=134;
unsignedinty=246;
intm=x;
intn=y;
unsignedintz1=x–y;
unsignedintz2=x+y;
intk1=m–n;
intk2=m+n;
若编译器编译时将8个8位寄存器R1~R8分别分配给变量x、y、m、n、z1、z2、k1和k2。
请回答下列问题。
（提示：
带符号整数用补码表示）
（1）执行上述程序段后，寄存器R1、R5和R6的内容分别是什么?
（用十六进制表示）
（2）执行上述程序段后，变量m和k1的值分别是多少?
（用十进制表示）
（3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器及辅助电路实现?
简述理由。
（4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出?
上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出?
44.（12分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB，主存（物理）地址空间大小为1MB，页面大小为4KB;Cache采用直接映射方式，共8行;主存与Cache之间交换的块大小为32B。
系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44-a图、题44-b图所示，图中页框号及标记字段的内容为十六进制形式。
虚页号有效位页框号…行号有效位标记…
0106…01020…
1104…10-…
2115…2101D…
3102…31105…
40-…41064…
512B…5114D…
60–…60-…
7132…7127A…
题44-a图页表的部分内容题44-b图Cache的部分内容
请回答下列问题。
（1）虚拟地址共有几位，哪几位表示虚页号?
物理地址共有几位，哪几位表示页框号（物理页号）?
（2）使用物理地址访问Cache时，物理地址应划分成哪几个字段?
要求说明每个字段的位数及在物理地址中的位置。
（3）虚拟地址001C60H所在的页面是否在主存中?
若在主存中，则该虚拟地址对应的物理地址是什么?
访问该地址时是否Cache命中?
要求说明理由。
（4）假定为该机配置一个4路组相联的TLB，该TLB共可存放8个页表项，若其当前内容（十六进制）如题44-c图所示，则此时虚拟地址024BACH所在的页面是否在主存中?
要求说明理由。
组号有效位标记页框号有效位标记页框号有效位标记页框号有效位标记页框号
00-–1001150-–10121F
110132D0-–10087E0-–
题44-c图TLB的部分内容
45.（8分）某银行提供1个服务窗口和10个供顾客等待的座位。
顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。
取号机每次仅允许一位顾客使用。
当营业员空闲时，通过叫号选取一位顾客，并为其服务。
顾客和营业员的活动过程描述如下：
cobegin
{
process顾客i
{
从取号机获得一个号码;
等待叫号;
获得服务;
}
process营业员
{
while（TRUE）
{
叫号;
为顾客服务;
}
}
}coend
请添加必要的信号量和P、V（或wait（）、signal（））操作，实现上述过程中的互斥与同步。
要求写出完整的过程，说明信号量的含义并赋初值。
46.（7分）某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。
请回答如下问题。
（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适?
要求说明理由。
为定位文件数据块，需在FCB中设计哪些相关描述字段?
（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好?
要求说明理由。
47.（9分）某主机的MAC地址为00-15-C5-C1-5E-28，IP地址为10.2.128.100（私有地址）。
题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80个字节的十六进制及ASCII码内容。
题47-a图网络拓扑
题47-b图以太网数据帧（前80字节）
请参考图中的数据回答以下问题。
（1）Web服务器的IP地址是什么?
该主机的默认网关的MAC地址是什么?
（2）该主机在构造题47-b图的数据帧时，使用什么协议确定目的MAC地址?
封装该协议请求报文的以太网帧的目的MAC地址是什么?
（3）假设HTTP/1.1协议以持续的非流水线方式工作，一次请求-响应时间为RTT，rfc.html页面引用了5个JPEG小图像，则从发出题47-b图中的Web请求开始到浏览器收到全部内容为止，需要多少个RTT?
（4）该帧所封装的IP分组经过路由器R转发时，需修改IP分组头中的哪些字段?
注：
以太网数据帧结构和IP分组头结构分别如题47-c图、题47-d图所示。
题47-c图以太网帧结构
题47-d图IP分组头结构
2011年全国硕士研究生入学考试计算机科学与技术入学考试答案及详解
一、单项选择题：
1～40小题，每小题2分，共80分。
下列每题给出的四个选项中，只有一个选项是最符合题目要求的。
请在答题卡上将所选项的字母涂黑。
1.
【答案】A
2.
【答案】B
3.
【答案】B
4.
【答案】C
5.
【答案】C
6.
【答案】D
7.
【答案】A
8.
【答案】C
9.
【答案】B
10.
【答案】A
11.
【答案】B
12.
【答案】D
13.
【答案】A
14.
【答案】B
15.
【答案】D
16.
【答案】A
17.
【答案】C
18.
【答案】D
19.
【答案】C
20.
【答案】C
21.
【答案】D
22.
【答案】C
23.
【答案】B
24.
【答案】A
25.
【答案】D
26.
【答案】B
27.
【答案】D
28.
【答案】D
29.
【答案】A
30.
【答案】B
31.
【答案】B
32.
【答案】C
33.
【答案】A
34.
【答案】B
35.
【答案】B
36.
【答案】D
37.
【答案】D
38.
【答案】C
39.
【答案】C
40.
【答案】B
二、综合应用题：
41～47小题，共70分。
请将答案写在答题纸指定位置上。
41.
【答案解析】此题考察的知识点是图的存储以及关键路径求解的综合知识。
（1）由题可以画出待定上三角矩阵的结构图如下（图中“?
”待定元素）
可以看出，第一行至第五行主对角线上方的元素分别5、4、3、2、1个，由此可以画出
压缩存储数组中的元素所属行的情况，如下图所示：
46∞∞∞5∞∞∞43∞∞33
第五行
第一行
第二行
第三行
第四行
将个元素填入各行即得邻接矩阵：
（2分）
A=
（2）根据第一步所得矩阵A容易做出有向带权图G，如下：
（2分）
0
1
2
3
4
5
4
6
5
4
3
3
3
（3）下图中粗线箭头所标识的4个活动组成G的关键路径（3分）
0
1
2
3
4
5
4
6
5
4
3
3
3
由上图容易求得图的关键路径长度为：
4+5+4+3=16。
42.
【答案解析】此题考察的知识点是基本算法的灵活运用。
（1）算法的基本设计思想：
（5分）
1）比较笨的方法：
将两升序序列归并排序，然后求其中位数，时间复杂度是O（n），空间复杂度O（n）。
2）高效的方法：
分别求两个升序序列A和B的中位数，设为a和b。
如果a=b，则a或者b即为所求的中位数。
原因：
如果将两序列归并排序，则最终序列中，排在子序列ab前边的元素为先前两序列中排在a和b前边的元素;排在子序列ab后边的元素为先前两序列a和b后边的元素。
所以子序列ab一定位于最终序列的中间，有因为a=b，显然a就是中位数。
如果a≠b（假设a
原因：
同样可以用归并排序后的序列来验证，归并后排序后必然有形如…a…b…的序列出现，中位数必然出现在（a，b）范围内。
因此可以做如下处理：
舍弃a所在序列A之中比较小的一半，同时舍弃b所在序列B之中比较大的一半。
在保留的两个升序序列中求出新的中位数a和b，重复上述过程，直到两个序列只含一个元素为止，则较小者即为所求中位数。
（2）算法实现（高效方法）：
（8分）
intSearch（intA[],intB[],intn）
{
ints1,e1,mid1,s2,e2,mid2;
s1=0;
e1=n-1;
s2=1;
e2=n-1;
while（s1!
=e1||s2!
=e2）
{
mid1=（s1+e1）/2;
mid2=（s2+e2）/2;
if（A[mid1]==B[mid2]）
returnA[mid1];
if（A[mid1]
{
//分别考虑奇数和偶数，保持两个子数组元素个数相等
if（（s1+e1）%2==0）//若元素个数为奇数
{
s1=mid1;//舍弃A中间点以前部分且保留中间点
e2=mid2;//舍弃B中间点以
升级会员 