2011年全国硕士研究生入学考试计算机统考试题
一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。请在答题卡上将所选项的字母涂黑。1.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是
x = 2;
while ( x
27.某时刻进程的资源使用情况如下表所示。
进程
已分配资源
尚需资源
可用资源
R1
R2
R3
R1
R2
R3
R1
R2
R3
P1
2
0
0
0
0
1
0
2
1
P2
1
2
0
1
3
2
P3
0
1
1
1
3
1
P4
0
0
1
2
0
0
此时的安全序列是
A.P1, P2, P3, P4 B.P1, P3, P2, P4
C.P1, P4, P3, P2 D.不存在
28.在缺页处理过程中，操作系统执行的操作可能是
I.修改页表 II.磁盘I/O III.分配页框
A.仅I、II B.仅II C.仅III D.I、II和III
29.当系统发生抖动(thrashing)时，可以采取的有效措施是
I. 撤销部分进程
II. 增加磁盘交换区的容量
III.提高用户进程的优先级
A.仅I B.仅II C.仅III D.仅I、II
30.在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是
A.编辑 B.编译 C.链接 D.装载
31.某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析。假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100 μs，将缓冲区的数据传送到用户区的时间是50 μs，CPU对一块数据进行分析的时间为50 μs。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是
A.1500 μs、1000 μs B.1550 μs、1100 μs
C.1550 μs、1550 μs D.2000 μs、2000 μs
32.有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。
两个操作完成后，x的值
A.可能为-1或3 B.只能为1
C.可能为0、1或2 D.可能为-1、0、1或2
33.TCP/IP参考模型的网络层提供的是
A.无连接不可靠的数据报服务 B.无连接可靠的数据报服务
C.有连接不可靠的虚电路服务 D.有连接可靠的虚电路服务
34.若某通信链路的数据传输速率为2400 bps，采用4相位调制，则该链路的波特率是
A.600波特 B.1200波特 C.4800波特 D.9600波特
35.数据链路层采用选择重传协议(SR)传输数据，发送方已发送了0 ~ 3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是
A.1 B.2 C.3 D.4
36.下列选项中，对正确接收到的数据帧进行确认的MAC协议是
A.CSMA B.CDMA C.CSMA/CD D.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.0 B.1 C.2 D.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.300 B.500 C.1200 D.1400
二、综合应用题：41～47小题，共70分。请将答案写在答题纸指定位置上。
41.(8分)已知有6个顶点(顶点编号为0 ~ 5)的有向带权图G，其邻接矩阵A为上三角矩阵，按行为主序(行优先)保存在如下的一维数组中。
要求：
(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程序段：
unsigned int x = 134;
unsigned int y = 246;
int m = x;
int n = y;
unsigned int z1 = x–y;
unsigned int z2 = x+y;
int k1 = m–n;
int k2 = 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分)某计算机存储器按字节编址，虚拟(逻辑)地址空间大小为16 MB，主存(物理)地址空间大小为1 MB，页面大小为4 KB;Cache采用直接映射方式，共8行;主存与Cache之间交换的块大小为32 B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44-a图、题44-b图所示，图中页框号及标记字段的内容为十六进制形式。
请回答下列问题。
(1)虚拟地址共有几位，哪几位表示虚页号?物理地址共有几位，哪几位表示页框号(物理页号)?
(2)使用物理地址访问Cache时，物理地址应划分成哪几个字段?要求说明每个字段的位数及在物理地址中的位置。
(3)虚拟地址001C60H所在的页面是否在主存中?若在主存中，则该虚拟地址对应的物理地址是什么?访问该地址时是否Cache命中?要求说明理由。
(4)假定为该机配置一个4路组相联的TLB，该TLB共可存放8个页表项，若其当前内容(十六进制)如题44-c图所示，则此时虚拟地址024BACH所在的页面是否在主存中?要求说明理由。
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-b图 以太网数据帧(前80字节)
页:
[1]