2009至2019年计算机考研408历年真题及解析

2024年1月22日发(作者：嘉年华手表是什么档次)

2009年全国硕士研究生入学统一考试

计算机科学与技术学科联考

计算机学科专业基础综合试题

一、单项选择题：第1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。

1.为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是。A．栈 B．队列 C．树

2. D．图设栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则栈S的容量至少是。A．1 B．2 C．3 D．43.给定二叉树如右图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列是3，1，7，5，6，2，4，则其遍历方式是A．LRNB．NRL C．RLN D．RNL

。

4.下列二叉排序树中，满足平衡二叉树定义的是______。

5.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是______。

A． 39 B．52 C．111 D．1196.将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是______。Ⅰ．父子关系 Ⅱ．兄弟关系Ⅲ．u的父结点与v的父结点是兄弟关系A．只有Ⅱ B．Ⅰ和Ⅱ C．Ⅰ和Ⅲ D．Ⅰ、Ⅱ和Ⅲ7.下列关于无向连通图特性的叙述中，正确的是______。

.所有顶点的度之和为偶数

边数大于顶点个数减1至少有一个顶点的度为18.A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ

下列叙述中，不．符合m阶B树定义要求的是______。A．根节点最多有m棵子树C．各结点内关键字均升序或降序排列B．所有叶结点都在同一层上

D．叶结点之间通过指针链接

9.已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后得到的小根堆是______。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，19

10.若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是______。

A．起泡排序 B．插入排序 C．选择排序 D．二路归并排序11.冯?诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是A．指令操作码的译码结果 B．指令和数据的寻址方式C．指令周期的不同阶段 D．指令和数据所在的存储单元12.一个C语言程序在一台32位机器上运行。程序中定义了三个变量x、y和z，其中x和z为int型，y为short型。当x=127，y=-9时，执行赋值语句z=x+y后，x、y和z的值分别是。A． x=0000007FH，y=FFF9H，z=00000076HB． x=0000007FH，y=FFF9H，z=FFFF0076HC． x=0000007FH，y=FFF7H，z=FFFF0076HD． x=0000007FH，y=FFF7H，z=00000076H13.浮点数加、减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均含2位符号位）。若有两个数X=27×29/32，Y=25×5/8，则用浮点加法计算X+Y的最终结果是A．00111 1100010C．01000 0010001。

。

B．00111 0100010

D．发生溢出

14.某计算机的Cache共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是。A．0 B．1 C．4 D．615.某计算机主存容量为64KB，其中ROM区为4KB，其余为RAM区，按字节编址。现要用2K×8位的ROM芯片和4K×4位的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和RAM芯片数分别是。A．1、15 B．2、15 C．1、30 D．2、3016.某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节PC自动加1。若某转移指令所在主存地址为2000H，相对位移量字段的内容为06H，则该转移指令成功转移后的目标地址是_____。A．2006H B．2007H C．2008H D．2009H17.下列关于RISC的叙述中，错误的是。．．A．RISC普遍采用微程序控制器B．RISC大多数指令在一个时钟周期内完成C．RISC的内部通用寄存器数量相对CISC多D．RISC的指令数、寻址方式和指令格式种类相对CISC少18.某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90 ns、80 ns、70 ns、和60 ns，则该计算机的CPU时钟周期至少是。A．90 ns B．80 ns C．70 ns D．60 ns19.相对于微程序控制器，硬布线控制器的特点是A．指令执行速度慢，指令功能的修改和扩展容易B．指令执行速度慢，指令功能的修改和扩展难C．指令执行速度快，指令功能的修改和扩展容易D．指令执行速度快，指令功能的修改和扩展难。

20.假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是______。

A．10MB/S B．20MB/S C．40MB/S D．80MB/S21.假设某计算机的存储系统由Cache和主存组成，某程序执行过程中访存1 000次，其中访问Cache缺失（未命中）50次，则Cache的命中率是A．5%

A．键盘输入C．浮点运算下溢Ⅰ 进程与进程A．Ⅰ、Ⅱ和ⅢC．Ⅰ、Ⅲ和ⅣA．时间片轮转调度算法

C．先来先服务调度算法

B．9.5%

22.下列选项中，能引起外部中断的事件是B．除数为0

D．访存缺页

。

Ⅳ 设备与设备

B．Ⅰ、Ⅱ和Ⅳ

D．Ⅱ、Ⅲ和Ⅳ

B．短进程优先调度算法D．高响应比优先调度算法Ⅱ 处理机与设备 Ⅲ 处理机与通道

。

D．95% C．50%

23.单处理机系统中，可并行的是24.下列进程调度算法中，综合考虑进程等待时间和执行时间的是______。25.某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是______。

A．2 B．3 C．4 D．526.分区分配内存管理方式的主要保护措施是______。

A．界地址保护 B．程序代码保护C．数据保护 D．栈保护

27.一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是______。A．28字节 B．216字节 C．224字节 D．232字节28.下列文件物理结构中，适合随机访问且易于文件扩展的是______。A．连续结构

B．索引结构D．链式结构且磁盘块变长C．链式结构且磁盘块定长

29.假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35，45，12，68，110，180，170，195，采用SCAN调度(电梯调度)算法得到的磁道访问序列是 ______。A．110,170,180,195,68,45,35,12

C．110,170,180,195,12,35,45,68

B．110,68,45,35,12,170,180,195D．12,35,45,68,110,170,180,19530.文件系统中，文件访问控制信息存储的合理位置是______。A．文件控制块 B．文件分配表 C．用户口令表 D．系统注册表

31.设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是______。

A． 0、1

A．逻辑设备名

C．主设备号

B．1、1 C．1、2 D．2、1

B．物理设备名D．从设备号32.程序员利用系统调用打开I/O设备时，通常使用的设备标识是 ______。

33.在OSI参考模型中，自下而上第一个提供端到端服务的层次是______。

A．数据链路层 B．传输层 C．会话层D．应用层

34.在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，

则该通信链路的最大数据传输速率是______。

A．12kbps B．24 kbps C．48 kbps D．96 kbps

35.数据链路层采用后退N帧（GBN）协议，发送方已经发送了编号为0~7的帧。当计时器超时时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是______。A．2 B．3

C．4

D．536.以太网交换机进行转发决策时使用的PDU地址是______。

A．目的物理地址

C．源物理地址

B．目的IP地址D．源IP地址37.在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps，电缆中的信号传播速度是200 000km/s 。若最小数据帧长度减少800比特，则最远的两个站点之间的距离至少需要______。

A．增加160m

C．减少 160m

B．增加 80mD．减少 80m38.主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是______。A．500 B．700 C．800 D．100039.一个TCP连接总是以1KB的最大段长发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT（往返时间）时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是______。A．7 KB B．8 KB C．9 KB D．16 客户和服务器间传递FTP命令时，使用的连接是______。A．建立在TCP之上的控制连接C．建立在UDP之上的控制连接二、综合应用题：第41~47题，共70分。

41.（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：①设最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点；②选择离u最近且尚未在最短路径中的一个顶点v，加入到最短路径中，修改当前顶点u=v；③重复步骤②，直到u是目标顶点时为止。B．建立在TCP之上的数据连接

D．建立在UDP之上的数据连接

请问上述方法能否求得最短路径？若该方法可行，请证明之；否则，请举例说明。

42.（15分）已知一个带有表头结点的单链表，结点结构为：data link

假设该链表只给出了头指针list。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点(k为正整数)。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：

⑴描述算法的基本设计思想；⑵描述算法的详细实现步骤；⑶根据设计思想和实现步骤，采用程序设计语言描述算法（使用C、C++或Java语言实现），关键之处请给出简要注释。

43.（8分）某计算机的CPU主频为500MHz，CPI为5（即执行每条指令平均需5个时钟周期）。假定某外设

的数据传输率为0.5MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。

1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？

2）当该外设的数据传输率达到5MB/s时，改用DMA方式传送数据。假定每次DMA传送块大小为5000B，且DMA预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？（假设DMA与CPU之间没有访存冲突）

44.（13分）某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效、为0时表示无效。例如控制信号MDRinE为1表示允许数据从DB打入MDR，MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状态。加法指令“ADD (R1)，R0”的功能为(R0)+((R1))?(R1)，即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。下表给出了上述指令取指和译码阶段每个节拍(时钟周期)的功能和有效控制信号，请按表中描述方式用表格．．列出指令执行阶段每个节拍的功能和有效控制信号。．．．．．．时钟

功能

MAR?(PC)MDR?M(MDR)

PC?(PC)+1

IR?(MDR)

指令译码

MDRout, IRin

无

有效控制信号

PCout, MARin

MemR, MDRinE, PC+1

45.（7分）三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。P1每次用produce()生成一个正整数并用put()送入缓冲区某一空单元中；P2每次用getodd()从该缓冲区中取出一个奇数并用countodd()统计奇数个数；P3每次用geteven()从该缓冲区中取出一个偶数并用counteven()统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。46.（8分）请求分页管理系统中，假设某进程的页表内容如下表所示：页号页框(Page Frame)号有效位(存在位)

101H

——

254H

页面大小为4KB，一次内存的访问时间是100ns，一次快表(TLB)的访问时间是10ns，处理一次缺页的平均时间108ns(已含更新TLB和页表的时间)，进程的驻留集大小固定为2，采用最近最少使用置换算法(LRU)和局部淘汰策略。假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表(忽略访问页表之后的TLB更新时间)；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：

(1) 依次访问上述三个虚地址，各需多少时间？给出计算过程。

(2) 基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。

47.（9分）某网络拓扑如下图所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口L0连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的L0接口的IP地址是202.118.2.1；R2的L0接口的IP地址是202.118.2.2，L1接口的IP地址是130.11.120.1，E0接口的IP地址是202.118.3.1；域名服务器的IP地址是202.118.3.2。R1和R2的路由表结构为：

目的网络IP地址子网掩码下一跳IP地址接口

⑴将IP地址空间202.118.1.0/24划分为2个子网，分别分配给局域网1、局域网2，每个局域网需分配的IP地址数不少于120个。请给出子网划分结果，说明理由或给出必要的计算过程。

⑵请给出R1的路由表，使其明确包括到局域网1的路由、局域网2的路由、域名服务器的主机路由和互联网的路由。

⑶请采用路由聚合技术，给出R2到局域网1和局域网2的路由。

参考答案

一、单项选择题（后附有解析）

1.B9.A17.A25.C33.B41．解答：

该方法不一定能（或不能）求得最短路径。

例如，对于下图所示的带权图，如果按照题中的原则，从A到C的最短路径是A->B->C，事实上其最短路径是A->D->C。

2.C10.B18.A26.A34.B3.D11.C19.D27.C35.C4.B12.D20.B28.B36.A5.C13.D21.D29.A37.D6.B14.C22.A30.A38.D7.A15.D23.D31.B39.C8.D16.C24.D32.A40.A二、综合应用题

42．解答：

（1）算法的基本设计思想（5分）：

问题的关键是设计一个尽可能高效的算法，通过链表的一趟遍历，找到倒数第k个结点的位置。算法的基本设计思想是：定义两个指针变量p和q，初始时均指向头结点的下一个结点（链表的第一个结点）。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到最后一个结点时，q指针所指示结点为倒数第k个结点。以上过程对链表仅进行一遍扫描。

（2）算法的详细实现步骤（5分）：

①count=0，p和q指向链表表头结点的下一个结点；②若p为空，转⑤；③若count等于k，则q指向下一个结点；否则，count=count+1；④p指向下一个结点，转②；⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，说明k值超过了线性表的长度，查找失败，返回0；

⑥算法结束。（3）算法实现（5分）：

typedef int ElemType;

typedef struct LNode{

ElemType data;

∥链表数据的类型定义

∥链表结点的结构定义

∥结点数据

∥结点链接指针

struct Lnode *link;} *LinkList;

int Search_k(LinkList list, int k){

∥查找链表list倒数第k个结点，并输出该结点data域的值LinkList p = list->link, q = list->link; ∥指针p、q指示第一个结点

int count = 0;

while(p != NULL){ ∥遍历链表直到最后一个结点

∥计数，若count < k只移动p∥之后让p、q同步移动if(count < k) count++;

else q = q->link; p = p->link;

} ∥whileif(count < k)

return 0; ∥查找失败返回0else { ∥否则打印并返回1printf(“%d”,q->data);

return 1;

}

} ∥Search_k

提示：算法程序题，如果能够写出数据结构类型定义、正确的算法思想都会至少给一半以上分数，如果能用伪代码写出自然更好，比较复杂的地方可以直接用文字表达。

若所给出的算法采用一遍扫描方式就能得到正确结果，可给满分15分；若采用两遍或多遍扫描才能得到正确结果的，最高分10分。若采用递归算法得到正确结果的，最高给10分；若实现算法的空间复杂度过高（使用了大小与k有关的辅助数组），但结果正确，最高给10分。

43．解答：

(1) 按题意，外设每秒传送0.5MB，中断时每次传送4B。中断方式下，CPU每次用于数据传送的时钟周期为：5?18+5?2=100.为达到外设0.5MB/s的数据传输率，外设每秒申请的中断次数为：0.5MB/4B=125 000。

1秒钟内用于中断的开销：100?125 000=12 500 000=12.5M个时钟周期。CPU用于外设I/O的时间占整个CPU时间的百分比：12.5M/500M=2.5%。

(2) 当外设数据传输率提高到5MB/s时改用DMA方式传送，每次DMA传送5 000B，1秒钟内需产生的DMA次数：5 MB/5 000 B=1 000.

CPU 用于DMA处理的总开销：1 000?500=500 000=0.5M个时钟周期。CPU 用于外设I/O的时间占整个CPU时间的百分比：0.5M/500M=0.1%。

44．解答：

一条指令的执行过程通常由取指、译码和执行3个步骤完成，本题中取指用3个节拍、译码用1个节拍，执行加法运算并把结果写入主存如何完成呢？包括划分执行步骤、确定完成的功能、要提供的控制信号，这是本题要测试的内容。为回答这个问题，首先要看清图中给出的部件组成情况和信息传送的路径。

要完成的功能时（R0）+（（R1））?（R1），从图中看到：(1) R0、R1都有送自己内容到内总线的路径，控制信号分别是R0out和R1out；

(2) ALU加运算，2个数据由工作寄存器A和内总线提供，控制信号是Add；A只接收内总线的内容，控制信号是Ain；结果需存AC，控制信号是ACin；AC的内容可送内总线，控制信号是ACout;

(3) PC可接收内总线的内容，还可增1，控制信号是PCin和PC+1，PC的内容可送内总线，控制信号是PCout；

(4) 指令寄存器IR可接收内总线的内容，控制信号是IRin；

(5) 读写存储器时，地址由MAR经AB提供，MAR只接收总线上的信息，控制信号是MARin;

(6) 读存储器，提供读命令MemR，并通过DB送入MDR，控制信号是MDRinE;MDR的内容可送入总线，控制信号是MDRout;

(7) 写存储器，提供写命令MemW,数据由MDR通过DB送到存储器的数据引脚，控制信号是MDRoutE;

然后是划分执行步骤、确定每一步完成的功能、需要提供的控制信号。这是由指令应完成的功能和计算机硬件的实际组成情况和信息传送的可用路径共同决定的，基本原则是步骤越少越好。硬件电路要能支持，可以有多种方案，解题时应参照以给出的答题格式，即取指和译码阶段的那张表的内容，但不必把表已有的内容再抄一遍。

划分指令执行步骤，确定每一步完成的功能、给出需要提供的控制信号：

请注意，（R0）+（（R1））表示：R0寄存器的内容与R1作地址从主存中读出来的数据完成加法运算；而?（R1）表示把R1的内容作为主存储器的地址完成写主存操作。为防止出现误解，题中还特地对此作了文字说明。这条指令的功能是先到主存储器取一个数，之后运算，再将结果写回主存储器。

(1) 执行相加运算，需把存储器中的数据读出，为此首先送地址，将R1的内容送MAR，控制信号是R1out、MARin。

(2) 启动读主存操作，读出的内容送入MDR，控制信号是MemR、MDRinE。还可同时把R0的内容经内总线送入A，用到的控制信号是R0out、Ain。

(3) 执行加法运算，即A的内容与MDR的内容相加，结果保存到AC，控制信号是MDRout、Add、Acin。

(4) 要把AC的内容写入主存，由于R1的内容已经在MAR中，地址已经有了，但需要把写入的数据（已经在AC中）经内总线送入MDR，控制信号是ACout、MDRin。

(5) 给出写主存的命令，把MDR的内容经DB送存储器的数据线引脚，执行写操作，控制信号是MDRoutE、MemW。

这几个步骤是有先后次序的，前面的完成了，下一步才可以执行，也保证了不会产生硬件线路的冲突。请注意，使用最为频繁的是内总线，它在任何时刻只能接收一个输入数据，并且向内总线发送信息的电路只能以三态门器件连接到内总线，5个向内总裁发送信息的控制信号（ACout，PCout，R0out，R1out，MDRout）最多只能有一个为1，其他4个必须全为0，或者5个全为0.

仔细看一下，发现可以把第2个步骤的操作划分到两个步骤中完成，一个步骤中安排MDR接收从存储器中读出的内容，到另外一个步骤实现R0的内容送入A，这多用了一个操作步骤，指令的执行速度会变慢。有些解题者在写存储器之前，还会再执行一次把R1的内容送MAR，尽管无此必要，但不属于原理上的错误。

当然还可以有其他的设计结果。

解题时这些叙述内容不必写出来（这里写出这些内容是希望帮助大家领会本题要测试的知识点和指令的执行过程），直接按照已经给出的表格的形式、按照提供的填写办法把设计的表格及其内容填好就可以了。

请注意，题目表格内容（告诉你答题的格式和答题内容的表达方式）与你答题的表格内容合在一起才是这条指令的完整的执行过程，千万不要产生任何错觉。

参考答案一：

时钟

功能

MAR?（R1）MDR?M(MAR)A?(R0)C7

参考答案二：

时钟

功能

MAR?（R1）有效控制信号

R1out,MARin

AC?(MDR)+(A)MDR?(AC)M(MAR)?(MDR)有效控制信号

R1out,MARin

MemR,MDRinE,

R0out,Ain

MDRout,Add,ACin

ACout,MDRin

MDRoutE,MemW

“A?(R0)”也可在C7：“AC?（MDR）+（A）”之前单列的一个时钟周期内执行。

C10

45．解答：

MDR?M(MAR)A?(MDR)AC?(A)+(R0)MDR?(AC)M(MAR)?(MDR)MemR,MDRinE

MDRout,Ain

R0out,Add,ACin

ACout,MDRin

MDRoutE,MemW

定义信号量odd控制P1与P2之间的同步；even控制P1与P3之间的同步；empty控制生产者与消费者之间的同步；mutex控制进程间互斥使用缓冲区。程序如下：

semaphore odd = 0, even = 0, empty = N, mutex = 1;

P1( )

{

x = produce();

P(empty);

P(mutex);

Put();

V(mutex);

if(x%2 == 0)

V(even);

else

V(odd);

}

P2( )

{

P(odd);

P(mutex);

getodd();

V(mutex);

V(empty);

countodd();

}

P3( )

{

P(even);

P(mutext);

geteven();

V(mutex);

V(empty);

counteven();

}

46．解答：

(1) 根据页式管理的工作原理，应先考虑页面大小，以便将页号和页内位移分解出来。页面大小为4KB，∥释放缓冲区

∥向P1发信号，多出一个空单元∥收到P1发来的信号，已产生一个偶数∥缓冲区是否被占用

∥释放缓冲区

∥向P1发信号，多出一个空单元∥收到P1发来的信号，已产生一个奇数∥缓冲区是否被占用

∥如果是奇数，向P2发出信号∥如果是偶数，向P3发出信号∥释放缓冲区

∥生成一个数

∥判断缓冲区是否有空单元

∥缓冲区是否被占用

即212，则得到页内位移占虚地址的低12位，页号占剩余高位。可得三个虚地址的页号P如下（十六进制的一位数字转换成4位二进制，因此，十六进制的低三位正好为页内位移，最高位为页号）：

2362H：P=2，访问快表10ns，因初始为空，访问页表100ns得到页框号，合成物理地址后访问主存100ns，共计10ns+100ns+100ns=210ns。

1565H：P=1，访问快表10ns，落空，访问页表100ns落空，进行缺页中断处理108ns，访问快表10ns，合成物理地址后访问主存100ns，共计10ns+100ns+108ns+10ns+100ns=100 000 220ns。25A5H：P=2，访问快表，因第一次访问已将该页号放入快表，因此花费10ns便可合成物理地址，访问主存100ns，共计10ns+100ns=110ns。

(2) 当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应页框号为101H。由此可得1565H的物理地址为101565H。

47．解答：

⑴CIDR中的子网号可以全0或全1，但主机号不能全0或全1。因此若将IP地址空间202.118.1.0/24划分为2个子网，且每个局域网需分配的IP地址个数不少于120个，子网号至少要占用一位。

由 2-2<120<2-2可知，主机号至少要占用7位。由于源IP地址空间的网络前缀为24位，因此主机号位数+子网号位数=8 。

综上可得主机号位数为7，子网号位数为1。

因此子网的划分结果为：子网1：202.118.1.0/25，子网2：202.118.1.128/25。

地址分配方案：子网1分配给局域网1，子网2分配给局域网2，或子网1分配给局域网2，子网2分配给局域网1。

⑵由于局域网1和局域网2分别与路由器R1的E1、E2接口直接相连，因此在R1的路由表中，目的网络为局域网1的转发路径是直接通过接口E1转发，目的网络为局域网2的转发路径是直接通过接口E1转发。由于局域网1、2的网络前缀均为25位，因此它们的子网掩码均为255.255.255.128。

根据题意，R1专门为域名服务器设定了一个特定的路由表项，因此该路由表项中的子网掩码应为255.255.255.255。对应的下一跳转发地址是202.118.2.2，转发接口是L0。

根据题意，到互联网的路由实质上相当于一个默认路由，默认路由一般写作0/0，即目的地址为0.0.0.0，子网掩码为0.0.0.0。对应的下一跳转发地址是202.118.2.2，转发接口是L0。

综上可得到路由器R1的路由表为：

（若子网1分配给局域网1，子网2分配给局域网2）

目的网络IP地址

202.118.1.0

202.118.1.128

202.118.3.2

0.0.0.0

子网掩码

255.255.255.128

255.255.255.255

0.0.0.0

下一跳IP地址

—

202.118.2.2

接口

（若子网1分配给局域网2，子网2分配给局域网1）

目的网络IP地址

202.118.1.128

202.118.1.0

202.118.3.2

0.0.0.0

子网掩码

255.255.255.128

255.255.255.255

0.0.0.0

下一跳IP地址

—

202.118.2.2

接口

⑶局域网1和局域网2的地址可以聚合为202.118.1.0/24，而对于路由器R2来说，通往局域网1和2的

转发路径都是从L0接口转发，因此采用路由聚合技术后，路由器R2到局域网1和局域网2的路由为：

目的网络IP地址

202.118.1.0

子网掩码

255.255.255.0

下一跳IP地址

202.118.2.1

接口

2009年全国硕士研究生入学统一考试

计算机学科专业基础综合试题——选择题部分解析

一、单项选择题

1．考查栈和队列的特点及应用。

C和D直接排除，缓冲区的特点需要先进先出，若用栈，则先进入缓冲区的数据则要排队到最后才能打印，不符题意，所以只有队列符合题意。

2．考查栈的最大递归深度。

时刻注意栈的特点是先进后出。下面是出入栈的详细过程：

序号

说明

a入栈

b入栈

b出栈

c入栈

d入栈

d出栈

c出栈

acd

bdc

栈内栈外序号

说明

e入栈

f入栈

f出栈

e出栈

a出栈

g入栈

g出栈

栈内

aef

栈外

bdc

bdcf

bdcfe

bdcfea

bdcfeag

栈内的最大深度为3，故栈S的容量至少是3。

3．考查二叉树的特殊遍历。

分析遍历后的结点序列，可以看出根结点是在中间被访问的，而且右子树结点在左子树之前，则遍历的方法是RNL。本题考查的遍历方法并不是二叉树遍历的三种基本遍历方法，对于考生而言，重要的是要掌握遍历的思想。

4．考查平衡二叉树的定义。

根据平衡二叉树的定义有，任意结点的左右子树高度差的绝对值不超过1。而其余三个答案均可以找到不符合的结点。

5．考查完全二叉树的特点。

完全二叉树比起满二叉树只是在最下面一层的右边缺少了部分叶结点，而最后一层之上是个满二叉树，并且只有最后两层上有叶结点。第6层有叶结点则完全二叉树的高度可能为6或7，显然树高为7时结点更多。若第6层上有8个叶结点，则前六层为满二叉树，而第7层缺失了8×2＝16个叶结点，故完全二叉树的结点个数最多为27-1-16=111个结点。6．考查森林和二叉树的转换。

森林与二叉树的转换规则为“左孩子右兄弟”。在最后生成的二叉树中，父子关系在对应森林关系中可能是兄弟关系或原本就是父子关系。

情形Ⅰ：若结点v是结点u的第二个孩子结点，在转换时，结点v就变成结点u第一个孩子的右孩子，符合要求。

情形Ⅱ：结点u和v是兄弟结点的关系，但二者之中还有一个兄弟结点k，则转换后，结点v就变为结点k的右孩子，而结点k则是结点u的右孩子，符合要求。

情形Ⅲ：结点v的父结点要么是原先的父结点或兄弟结点。若结点u的父结点与v的父结点是兄弟关系，则转换之后，不可能出现结点u是结点v的父结点的父结点。

7．考查无向连通图的特性。

每条边都连接了两个结点，则在计算顶点的度之时，这条边都被计算了两次，故所有顶点的度之和

为边数的两倍，显然必为偶数。而ii和iii则不一定正确，如：对顶点数N≥1无向完全图不存在一个顶点的度为1，并且边数与顶点数的差要大于1。

8．考查m阶B-树的定义。

A、B和C都是B-树的特点，而选项D则是B+树的特点。注意区别B-树和B+树各自的特点。

9．考查小根堆的调整操作。

小顶堆在逻辑上可以用完全二叉树来表示，根据关键序列得到的小顶堆的二叉树形式为下图左图：

插入关键字3时，先将其放在小顶堆的末端，再将该关键字向上进行调整，得到的结果上图右边所示。所以，调整后的小顶堆序列为：3，5，12，8，28，20，15，22，19。

10．考查各排序算法的特点。

解答本题之前要对不同排序算法的特点极为清楚。对于起泡排序和选择排序而言，每一趟过后都能确定一个元素的最终位置，而由题目中所说，前两个元素和后两个元素均不是最小或最大的两个元素并按序排列。答案D中的二路归并排序，第一趟排序结束都可以得到若干个有序子序列，而此时的序列中并没有两两元素有序排列。插入排序在每趟排序结束后能保证前面的若干元素是有序的，而此时第二趟排序后，序列的前三个元素是有序的，符合其特点。

11．考查指令执行过程。

通常完成一条指令可分为取指阶段和执行阶段。在取指阶段通过访问存储器可将指令取出；在执行阶段通过访问存储器可以将操作数取出。这样，虽然指令和数据都是以二进制代码形式存放在存储器中，但CPU可以判断在取指阶段访问存储器取出的二进制代码是指令；在执行阶段访存取出的二进制代码是数据。

12．考查符号位的扩展。

结合题干及选项可知，int为32位，short为16位；又C语言的数据在内存中为补码形式，故x、y的机器数写为0000007FH、FFF7H;

执行z=x+y时，由于x是int型，y为short型，故需将y的类型强制转换为int，在机器中通过符号位扩展实现，由于y的符号位为1，故在y的前面添加16个1，即可将y强制转换为int型，其十六进制形式为FFFFFFF7H;

然后执行加法，即0000007FH+FFFFFFF7H=00000076H，其中最高位的进位1自然丢弃。故选D。

13．考查浮点加法运算。

根据题意，X可记为00, 111; 00, 11101（分号前为阶码，分号后为尾数），Y可记为00, 101; 00, 10100。

首先对阶，X、Y阶码相减，即00, 111-00, 101=00, 111+11, 0111=00, 010，可知X的阶码比Y的价码大2，根据小阶向大阶看齐的原则，将Y的阶码加2，尾数右移2位，可得Y为00, 111; 00, 00101。

尾数相加，即00, 11101+00, 00101=01, 00010，尾数相加结果符号位为01，故需进行右规。

规格化，将尾数右移1位，阶码加1，得X+Y为01, 000; 00, 1000，阶码符号位为01，说明发生溢出。

14．考查Cache与主存之间的映射方式。

由于Cache共有16块，采用2路组相联，因此共有8组，0，1，2，...，7。并且主存的某一字块按模8映像到Cache某组的任一字块中，即主存的第0，8，16...字块可以映像到Cache第0组2个字块的任一字块中，而129号单元是位于第4块主存块中，因此将映射到Cache第4组2个字块的任一字块中。

注意：由于在计算机系统结构中和计算机组成原理的某些教材中介绍的组相联跟此处的组相联并不相同，导致部分考生理解错题目。考生应以真题为准，以后再出现类似题目，应以此种解答为标准。

15．考查存储器的扩展。

首先确定ROM的个数，ROM区为4KB，选用2K×8的ROM芯片，需要方式；60KB的RAM区，选用4K×4的RAM芯片，需要16．考查相对寻址。

相对寻址EA=(PC)+A，首先要求的是取指令后PC的值。转移指令由两个字节组成，每取一个字节PC自动加1，因此取指令后PC值为2002H，故EA=(PC)+A=2002H+06H=2008H。

17．考查RISC的特性。

相对于CISC计算机，RISC计算机的特点指令条数少；指令长度固定，指令格式和寻址种类少；只有取数/存数指令访问存储器，其余指令的操作均在寄存器之间进行；CPU中通用寄存器多；大部分指令在一个或者小于一个机器周期内完成；以硬布线逻辑为主，不用或者少用微程序控制。

18．考查流水线中时钟周期的特性。

时钟周期应以最长的执行时间为准，否则用时长的流水段的功能将不能正确完成。

19．考查硬布线控制器的特点。

硬布线控制器的速度取决于电路延迟，所以速度快；微程序控制器采用了存储程序原理，每条指令都要访控存，所以速度慢。硬布线控制器采用专门的逻辑电路实现，修改和扩展困难。

20．考查总线的基本概念。

总线带宽是指单位时间内总线上可传输数据的位数，通常用每秒钟传送信息的字节数来衡量，单位可用字节/秒（Bps）表示。根据题意可知，在2*1/10MHz秒内传输了4B，所以4B*10MHz/2=20MB/S。

21．考查Cache的命中率。

命中率=Cache命中的次数/所有访问次数，有了这个公式这道题就很容易看出，要注意的一点是看清题，题中说明的是缺失50次，而不是命中50次，仔细审题是做对题的第一步。

22．考查中断的分类。

选项中能引起外部中断的只能是输入设备键盘。

23．考查并行性的限定。

单处理机系统中只有一条指令流水线，一个多功能的操作部件，每个时钟周期只能完成一条指令，故进程与进程显然不可以并行。

24．考查几种基本的调度算法概念。

高响应比优先调度算法，同时考虑每个进程的等待时间和需要的执行时间，从中选出响应比最高的进程投入执行。响应比R定义如下：

响应比R = (等待时间+执行时间) / 执行时间

4K?8?2片，采用字扩展2K?860K?8?30片，采用字和位同时扩展方式。

4K?425．考查死锁的条件。

这种题用到组合数学中鸽巢原理的思想，考虑最极端情况，因为每个进程最多需要3台打印机，如果每个进程已经占有了两个打印机，那么只要还有多的打印机，那么总能满足达到3台的条件，所以，将8台打印机分给K个进程，每个进程有2台打印机，这个情况就是极端情况，K为4。

26．考查分区分配存储管理方式的保护措施。

分区分配存储管理方式的保护措施是设置界地址寄存器。每个进程都有自己独立的进程空间，如果一个进程在运行时所产生的地址在其地址空间之外，则发生地址越界，即当程序要访问某个内存单元时，由硬件检查是否允许，如果允许则执行，否则产生地址越界中断,由操作系统进行相应处理。

27．考查分段存储管理系统。

段地址为32位二进制数，其中8位表示段号，则段内位移占用32-8=24位二进制数，故最大段长为224字节。28．考查文件物理结构的特性。

随机访问是索引结构的特性。

29．考查磁盘的调度算法。

类似于电梯调度的思想。首先，磁头选择与当前磁头所在磁道距离最近的请求作为首次服务的对象（110），当磁头沿途相应访问请求序列直到达到一端末（110,170,180,195），再反向移动响应另一端的访问请求（68,45,35,12）。

30．考查文件控制块的内容。

在文件控制块中，通常含有以下3类信息，即基本信息、存取控制信息及使用信息。

31．考查软/硬链接建立的属性。

建立符号链接（软链接）时，引用计数值直接复制；建立硬链接时，引用计数值加1。删除文件时，删除操作对于符号链接是不可见的，这并不影响文件系统，当以后再通过符号链接访问时，发现文件不存在，直接删除符号链接；但是对于硬链接则不可以直接删除，引用计数值减1，若值不为0，则不能删除此文件，因为还有其它硬链接指向此文件。

32．考查系统调用的设备标识。

用户程序对I/O设备的请求采用逻辑设备名，而在程序实际执行时使用物理设备名。

33．考查OSI模型中传输层的功能。

传输层提供应用进程间的逻辑通信，即端到端的通信。而网络层提供点到点的逻辑通信。因此选B。

34．考查奈氏准则和香农定理。

采用4个相位，每个相位有4种幅度的QAM调制方法，每个信号可以有16种变化，传输4bit的数据。根据奈奎斯特定理，信息的最大传输速率为2×3K×4=24Kbps。

35．考查后退N帧协议的工作原理。

在后退N帧协议中，发送方可以连续发送若干个数据帧，如果收到接收方的确认帧则可以继续发送。若某个帧出错，接收方只是简单的丢弃该帧及其后所有的后续帧，发送方超时后需重传该数据帧及其后续的所有数据帧。这里要注意，连续ARQ协议中，接收方一般采用累积确认的方式，即接收方对按序到达的最后一个分组发送确认，因此题目中收到3的确认帧就代表编号为0、1、2、3的帧已接收，而此时发送方未收到1号帧的确认只能代表确认帧在返回的过程中丢失了，而不代表1号帧未到达接收方。因此需要重传的帧为编号是4、5、6、7的帧。

36．考查交换机的工作原理。

交换机实质上是一个多端口网桥，工作在数据链路层，数据链路层使用物理地址进行转发，而转发通常都是根据目的地址来决定出端口。

37．考查CSMA/CD协议的工作原理。

首先由例8可知，若最短帧长减少，而数据传输速率不变，则需要使冲突域的最大距离变短来实现争用期的减少。争用期是指网络中收发结点间的往返时延，因此假设需要减少的最小距离为s，单位是m，则可以得到下式（注意单位的转换）：2×[s/(2×108)]=800/(1×109)，因此可得s=80，即最远的两个站点

之间的距离最少需要减少80m。

38．考查TCP的数据编号与确认。

TCP是面向字节流的，其选择确认（Selective ACK）机制是接收端对字节序号进行确认，其返回的序号是接收端下一次期望接收的序号，因此主机乙接收两个段后返回给主机甲的确认序列号是1000。

39．考查TCP的拥塞控制方法。

本题计算原理如图4所示。无论在慢开始阶段还是在拥塞避免阶段，只要发送方判断网络出现拥塞（其根据就是没有按时收到确认），就要把慢开始门限ssthresh设置为出现拥塞时的发送方窗口值的一半（但不能小于2）。然后把拥塞窗口cwnd重新设置为1，执行慢开始算法。这样做的目的就是要迅速减少主机发送到网络中的分组数，使得发生拥塞的路由器有足够时间把队列中积压的分组处理完毕。

因此，在发送拥塞后，慢开始门限ssthresh变为16/2 = 8 KB，发送窗口变为1 KB。在接下来的3个RTT内，拥塞窗口执行慢开始算法，呈指数形式增加到8 KB，此时由于慢开始门限ssthresh为8 KB，因此转而执行拥塞避免算法，即拥塞窗口开始“加法增大”。因此第4个RTT结束后，拥塞窗口的大小为9 KB。

40．考查FTP协议的特点。

FTP协议是基于传输层TCP协议的。FTP的控制连接使用端口21，用来传输控制信息（如连接请求，传送请求等），数据连接使用端口20，用来传输数据。

2010年全国硕士研究生入学统一考试

计算机科学与技术学科联考

计算机学科专业基础综合试题

一、单项选择题：第1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。

1.若元素a、b、c、d、e、f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是______。

．A．d c e b f a B．c b d a e f C．b c a e f d D．a f e d c b2.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a、b、c、d、e依次入此队列后再进行出队操作，则不可能得到的出队序列是______。

．A．b a c d e B．d b a c e C．d b c a e D．e c b a d3.下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是______。a

Null

b c b c b c b c

Null

A．

B．

C．

Null

D．

4.在右图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是______。

A．13，48C．24，53B．24，48

D、24，90

5.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是______。A．41 B．82 C．113 D．1226.对n（n≥2）个权值均不相同的字符构造成哈夫曼树。下列关于该哈夫曼树的叙述中，错误．．的是______。

A．该树一定是一棵完全二叉树。B．树中一定没有度为1的结点。C．树中两个权值最小的结点一定是兄弟结点。D．树中任一非叶结点的权值一定不小于下一层任一结点的权值。7.8.9.若无向图G=（V, E）中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是_____。

A．6 B．15 C．16 D．21对右图进行拓扑排序，可以得到不同的拓扑序列的个数是_____。A．4 B． 3 C．2 D．1已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找法查找一个L中不存在的元素，则关键字的比较次数最多的是_____。A．4 B．5 C．6 D．7e

b c

10.采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是______。

A．递归次数与初始数据的排列次序无关。

B．每次划分后，先处理较长的分区可以减少递归次数。

C．每次划分后，先处理较短的分区可以减少递归次数。

D．递归次数与每次划分后得到的分区的处理顺序无关。

11.对一组数据(2，12，16，88，5，10)进行排序，若前三趟排序结果如下：第一趟排序结果：2，12，16，5，10，88第二趟排序结果：2，12，5，10，16，88第三趟排序结果：2，5，10，12，16，88则采用的排序方法可能是______。

A．起泡排序 B．希尔排序Ⅰ. 提高CPU时钟频率Ⅲ. 对程序进行编译优化A．仅Ⅰ和Ⅱ B．仅Ⅰ和ⅢC．仅Ⅱ和Ⅲ D．Ⅰ、Ⅱ和Ⅲ

。

C．归并排序

。

Ⅱ. 优化数据通路结构

D．基数排序

12.下列选项中，能缩短程序执行时间的措施是13.假定有4个整数用8位补码分别表示r1=FEH，r2=F2H，r3=90H，r4=F8H，若将运算结果存放在一个8位寄存器中，则下列运算中会发生溢出的是A．r1 x r2C．r1 x r4B．r2 x r3

D．r2 x r4

14.假定变量i、f和d的数据类型分别为int,float和double（int用补码表示，float和double分别用IEEE754单精度和双精度浮点数格式表示），已知i=785,f=1.5678e3,d=1.5e100。若在32位机器中执行下列关系表达式，则结果为“真”的是。

（I）i == (int)(float)i(II)f == (float)(int)f

(III)f == (float)(double)f(IV)(d+f)-d == f

A．仅I和IIB．仅I和III C．仅II和III D．仅III和IV

15.15．假定用若干个2kx4位的芯片组成一个8kx8位的存储器，则地址0B1FH所在芯片的最小地址是A．0000H B．0600H C．0700H D．0800H。

16.下列有关RAM和ROM的叙述中，正确的是I RAM是易失性存储器，ROM是非易失性存储器

II RAM和ROM都采用随机存取方式进行信息访问

III RAM和ROM都可用作Cache

IV RAM和ROM都需要进行刷新

A．仅I和II B．仅II和III C．仅I,II和IV

。

D．仅II，III和IV

。

17.下列命中组合情况中，一次访存过程中不可能发生的是．A．TLB未命中，Cache未命中，Page未命中B．TLB未命中，Cache命中，Page命中C．TLB命中，Cache未命中，Page命中D．TLB命中，Cache命中，Page未命中18.下列寄存器中，汇编语言程序员可见的是A．存储器地址寄存器(MAR)C．存储器数据寄存器(MDR) 。

B．程序计数器(PC)

D．指令寄存器(IR)

。

19.下列选项中，不．会引起指令流水线阻塞的是A．数据旁路（转发）C．条件转移B．数据相关

D．资源冲突

20.下列选项中的英文缩写均为总线标准的是______。

A．PCI、CRT、USB、EISAB．ISA、CPI、VESA、EISAC．ISA、SCSI、RAM、MIPSD．ISA、EISA、PCI、PCI-Express21.单级中断系统中，中断服务程序内的执行顺序是______。

I保护现场V中断事件处理II开中断

VI恢复现场

III关中断

VII中断返回

B．III->I->V->VII

D．IV->I->V->VI->VII

IV保存断点

A．I->V->VI->II->VIIC．III->IV->V->VI->VII22.假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600*1200，颜色深度为24位，帧频为85HZ，显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为______。A．245Mbps B．979MbpsC．1 958Mbps D．7 834Mbps23.下列选项中，操作系统提供给应用程序的接口是_____。A．系统调用C．库函数Ⅰ用户登录成功 Ⅱ设备分配B．中断

D．原语

Ⅲ启动程序执行

C．仅Ⅰ和Ⅲ D．Ⅰ、Ⅱ和Ⅲ

24.下列选项中，导致创建新进程的操作是______。A．仅Ⅰ和Ⅱ B．仅Ⅱ和Ⅲ数，则M、N分别是______。

A．0、1 B．1、0 C．1、2 D．2、025.设与某资源关联的信号量初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源的进程26.下列选项中，降低进程优先级的合理时机是_____。A. 进程的时间片用完B. 进程刚完成I/O，进入就绪列队C. 进程长期处于就绪列队中D. 进程从就绪态转为运行态27.进程P0和P1的共享变量定义及其初值为boolean flag[2];int turn = 0;flag[0] = FALSE; flag[1] = FALSE;若进程P0和P1访问临界资源的类C伪代码实现如下：void P0() // 进程P0{while(TRUE)

{

flag[0]=TRUE; turn=1;

while(flag[1]&&(turn==1))

;

临界区;flag[0]=FALSE;

}

} }

void P1() // 进程P1{

while(TRUE)

{

flag[1]=TRUE; turn=0;

while(flag[0]&&(turn==0))

;

临界区;flag[1]=FALSE;

}

则并发执行进程P0和P1时产生的情形是______。

A. 不能保证进程互斥进入临界区，会出现“饥饿”现象

B. 不能保证进程互斥进入临界区，不会出现“饥饿”现象

C. 能保证进程互斥进入临界区，会出现“饥饿”现象

D. 能保证进程互斥进入临界区，不会出现“饥饿”现象

28.某基于动态分区存储管理的计算机，其主存容量为55MB(初始为空闲)，采用最佳适配(Best Fit)算法，分配和释放的顺序为：分配15MB，分配30MB，释放15MB，分配8MB，分配6MB，此时主存中最大空闲分区的大小是______。

A．7MB

地址结构为：页目录号页号页内偏移量

逻辑地址空间大小为216页，则表示整个逻辑地址空间的页目录表中包含表项的个数至少．．是______。

A． 64 B． 128 C． 256 D． 512

B．9MB C．10MB D．15MB29.某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为210字节，页表项大小为2字节，逻辑30.设文件索引节点中有7个地址项，其中4个地址项是直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4字节。若磁盘索引块和磁盘数据块大小均为256字节，则可表示的单个文件最大长度是______。

A．33 KB B．519 KB C．1 057 KB D．16 513 KB31.设置当前工作目录的主要目的是_______。A．节省外存空间C．加快文件的检索速度B．节省内存空间

D．加快文件的读/写速度

32.本地用户通过键盘登陆系统时，首先获得键盘输入信息的程序是______。

A．命令解释程序

B．中断处理程序D．用户登录程序C．系统调用服务程序

33.下列选项中，不．属于网络体系结构所描述的内容是______。A．网络的层次C．协议的内部实现细节B．每一层使用的协议

D．每一层必须完成的功能

34.在下图所示的采用“存储-转发”方式的分组交换网络中，所有链路的数据传输速率为100Mbps，分组大小为1000B，其中分组头大小为20B。若主机H1向主机H2发送一个大小为980 000B的文件，则在不考虑分组拆装时间和传播延迟的情况下，从H1发送开始到H2接收完为止，需要的时间至少．．是______。

A．80 ms

C．80.16 ms

B．80.08 ms

D．80.24 ms

35.某自治系统内采用RIP协议，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息，则能得出的结论是______。A．R2可以经过R1到达net1，跳数为17B．R2可以到达net1，跳数为16C．R1可以经过R2到达net1，跳数为17D．R1不能经过R2到达net1

36.若路由器R因为拥塞丢弃IP分组，则此时R可向发出该IP分组的源主机发送的ICMP报文类型是______。

A．路由重定向

C．源点抑制

B．目的不可达D．超时37.某网络的IP地址空间为192.168.5.0/24，采用定长子网划分，子网掩码为255.255.255.248，则该网络中的最大子网个数、每个子网内的最大可分配地址个数分别是______。A．32，8

C．8，32

B．32，6D．8，3038.下列网络设备中，能够抑制广播风暴的是______。

Ⅰ中继器

A．仅Ⅰ和ⅡC．仅Ⅲ和Ⅳ Ⅱ集线器 Ⅲ网桥

B．仅Ⅲ

D．仅Ⅳ

Ⅳ路由器

39.主机甲和主机乙之间已建立了一个TCP连接，TCP最大段长度为1 000字节。若主机甲的当前拥塞窗口为4 000字节，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的第一个段的确认段，确认段中通告的接收窗口大小为2 000字节，则此时主机甲还可以向主机乙发送的最大字节数是______。

A．1 000C．3 000送的域名请求消息数分别为______。

A．一条、一条

C．多条、一条

B．一条、多条D．多条、多条B．2 000

D．4 000

40.如果本地域名服务器无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发二、综合应用题：第41~47题，共70分。

41.（10分）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从0开始的一维数组，散列函数为：H(key) = (keyx3) MOD 7，处理冲突采用线性探测再散列法，要求装填（载）因子为0.7。(1) 请画出所构造的散列表。(2) 分别计算等概率情况下查找成功和查找不成功的平均查找长度。42.（13分）设将n（n>1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法。将R中保存的序列循环左移p（0

12 11

Ms Rs

6 5

源操作数目的操作数

转移指令采用相对寻址方式，相对偏移量用补码表示，寻址方式定义如下：

Ms/Md

000B

寻址方式

寄存器直接

助记符

含义

操作数=（Rn）

王道论坛

予人玫瑰手留余香

001B

010B

011B

寄存器间接

寄存器间接、自增

相对

（Rn）

（Rn）+

D（Rn）

操作数=（(Rn)）

操作数=（(Rn)），（Rn）+1→Rn

转移目标地址=（PC）+（Rn）

注：（X）表示存储器地址X或寄存器X的内容。

请回答下列问题：

⑴该指令系统最多可有多少条指令？该计算机最多有多少个通用寄存器？存储器地址寄存器（MAR）和存储器数据寄存器（MDR）至少各需要多少位？

⑵转移指令的目标地址范围是多少？⑶若操作码0010B表示加法操作（助记符为add），寄存器R4和R5的编号分别为100B和101B，R4的内容为1234H，R5的内容为5678H，地址1234H中的内容为5678H，地址5678H中的内容为1234H，则汇编语言为“add（R4），（R5）+”（逗号前为源操作数，逗号后为目的操作数）对应的机器码是什么（用十六进制表示）？该指令执行后，哪些寄存器和存储单元中的内容会改变？改变后的内容是什么？

44.（12分）某计算机的主存地址空间大小为256MB，按字节编址。指令Cache和数据Cache分离，均有8个Cache行，每个Cache行大小为64B，数据Cache采用直接映射方式。现有两个功能相同的程序A和B，其伪代码如下所示：程序A：int a[256][256]

int sum_array1()

{

int i, j, sum=0;

for(i=0; i<256; i++)

for(j=0; j<256; j++)

sum += a[i][j];

return sum;

}

程序B：int a[256][256]

int sum_array2()

{

int i, j, sum=0;

for(j=0; j<256; j++)

for(i=0; i<256; i++)

sum += a[i][j];

return sum;

}

假定int 类型数据用32位补码表示，程序编译时i，j，sum均分配在寄存器中，数组a按行优先方式存放，其首地址为320（十进制数）。请回答下列问题，要求说明理由或给出计算过程。

(1) 若不考虑用于cache一致性维护和替换算法的控制位，则数据Cache的总容量为多少？

(2) 数组元素a[0][31]和a[1][1]各自所在的主存块对应的Cache行号分别是多少（Cache行号从0开始）？

(3) 程序A和B的数据访问命中率各是多少？哪个程序的执行时间更短？

45.（7分）假设计算机系统采用CSCAN（循环扫描）磁盘调度策略，使用2KB的内存空间记录16 384个磁盘块的空闲状态。(1) 请说明在上述条件下如何进行磁盘块空闲状态的管理。(2) 设某单面磁盘旋转速度为每分钟6000转，每个磁道有100个扇区，相邻磁道间的平均移动时间为1ms。若在某时刻，磁头位于100号磁道处，并沿着磁道号增大的方向移动（如下图所示），磁道号请求队列为50，90，30，120，对请求队列中的每个磁道需读取1个随机分布的扇区，则读完这4个扇区点共需要多少时间？要求给出计算过程。

(3) 如果将磁盘替换为随机访问的Flash半导体存储器（如U盘、SSD等），是否有比CSCAN更高效的磁盘调度策略？若有，给出磁盘调度策略的名称并说明理由；若无，说明理由。

0号磁道随机分布的某扇区磁头移动方向100号磁道46.（8分）设某计算机的逻辑地址空间和物理地址空间均为64KB，按字节编址。若某进程最多需要6页(Page)数据存储空间，页的大小为1KB，操作系统采用固定分配局部置换策略为此进程分配4个页框(Page Frame)。在时刻260前的该进程访问情况如下表所示（访问位即使用位）。页号

页框号

装入时刻

130

230

200

160

访问位

当该进程执行到时刻260时，要访问逻辑地址为17CAH的数据。请回答下列问题：

(1) 该逻辑地址对应的页号是多少？

(2) 若采用先进先出（FIFO）置换算法，该逻辑地址对应的物理地址是多少?要求给出计算过程。

(3) 若采用时钟（CLOCK）置换算法，该逻辑地址对应的物理地址是多少？要求给出计算过程（设搜索下一页的指针沿顺时针方向移动，且当前指向2号页框，示意图如下）。

9号页框

3号页2号页2号页框

7号页框

0号页1号页

4号页框图3.15 页框示意图

47.（9分）某局域网采用CSMA/CD 协议实现介质访问控制，数据传输速率为10Mbps，主机甲和主机乙之间的距离为2 km，信号传播速度是200 000 km/s。请回答下列问题，要求说明理由或写出计算过程。⑴若主机甲和主机乙发送数据时发生冲突，则从开始发送数据时刻起，到两台主机均检测到冲突时刻止，最短需经过多长时间？最长需经过多长时间（假设主机甲和主机乙发送数据过程中，其他主机不发送数据）？

⑵若网络不存在任何冲突与差错，主机甲总是以标准的最长以太网数据帧（1 518字节）向主机乙发送数据，主机乙每成功收到一个数据帧后立即向主机甲发送一个64字节的确认帧，主机甲收到确认帧后方可发送下一个数据帧。此时主机甲的有效数据传输速率是多少（不考虑以太网的前导码）？

参考答案

一、单项选择题（后附有解析）1.D9.B17.D25.B33.C41．解答：

(1) 由装载因子0.7，数据总数为7，得一维数组大小为7/0.7=10，数组下标为0~9。所构造的散列函数值如下所示：

key

H(key)

2.C10.D18.B26.A34.C3.D11.A19.A27.D35.D4.C12.D20.D28.B36.C5.B13.B21.A29.B37.B6.A14.B22.D30.C38.D7.C15.D23.A31.C39.A8.B16.A24.C32.B40.A二、综合应用题

采用线性探测再散列法处理冲突，所构造的散列表为：

地址

关键字

2 3

4 5

(2) 查找成功时，是根据每个元素查找次数来计算平均长度，在等概率的情况下，各关键字的查找次数为：

key

次数

故，ASL成功 = 查找次数 / 元素个数 = (1+2+1+1+1+3+3) / 7 = 12/7

这里要特别防止惯性思维。查找失败时，是根据查找失败位置计算平均次数，根据散列函数MOD 7，初始只可能在0~6的位置。等概率情况下，查找0~6位置查找失败的查找次数为：

H(key)

次数

故，ASL不成功

= 查找次数 / 散列后的地址个数 = (3+2+1+2+1+5+4) / 7 = 18 / 7

42．解答：

（1）算法的基本设计思想：

可以将这个问题看做是把数组ab转换成数组ba（a代表数组的前p个元素，b代表数组中余下的n-p个元素），先将a逆置得到a-1b，再将b逆置得到a-1b-1，最后将整个a-1b-1逆置得到（a-1b-1）-1=ba。设Reverse函数执行将数组元素逆置的操作，对abcdefgh向左循环移动3（p=3）个位置的过程如下：

Reverse(0,p-1)得到cbadefgh；

Reverse(p,n-1)得到cbahgfed；

Reverse(0,n-1)得到defghabc；

注：Reverse中，两个参数分别表示数组中待转换元素的始末位置。

（2）使用c语言描述算法如下：

void Reverse(int R[],int from,int to) {

int i,temp;

for(i = 0; i < (to-from+1)/2; i++)

{ temp = R[from+i]; R[from+i] = R[to-i]; R[to-i] = temp; }

}∥Reverse

void Converse(int R[],int n,int p){

Reverse(R,0,p-1);

Reverse(R,p,n-1);

Reverse(R,0,n-1);

}

（3）上述算法中三个Reverse函数的时间复杂度分别为?(p/2)、?((n?p)/2)和

的算法的时间复杂度为?(n),空间复杂度为?(1)。另解，借助辅助数组来实现：

算法思想：创建大小为p的辅助数组S，将R中前p个整数依次暂存在S中，同时将R中后n-p个整数左移，然后将S中暂存的p个数依次放回到R中的后续单元。

时间复杂度为?(n)，空间复杂度为?(p)。43．解答：

(1) 操作码占4位，则该指令系统最多可有24=16条指令；操作数占6位，寻址方式占3位，于是寄存器编号占3位，则该机最多有23=8个通用寄存器；主存容量128KB，按字编址，计算机字长为16位，划分为128KB/2B=216个存储单元，故MDR和MAR至少各需16位。(2) PC和Rn可表示的地址范围均为0～216-1，而主存地址空间为216，故转移指令的目标地址范围是0000H～FFFFH（0～216-1）。(3) 汇编语句“add (R4), (R5) +”，对应的机器码为0010 0011 0001 0101B=2315H。

该指令执行后，寄存器R5和存储单元5678H的内容会改变。执行后，R5的内容从5678H变成5679H。存储单元5678H中的内容变成该加法指令计算的结果5678H＋1234H=68ACH。

44．解答：

(1) 数据Cache有8个Cache行，每个Cache行大小为64B，Cache中每个字块的Tag字段的位数是28－9＝19位，此外还需使用一个有效位，合计20位。因此，数据Cache的总容量应为：8×(64＋20／8)B＝532B。

(2) 数组a在主存的存放位置及其与Cache之间的映射关系如下图所示：

数组按行优先方式存放，首地址为320，数组元素占四个字节。a[0][31]所在的主存块对应的Cache行号为：

(320＋31×4) DIV 64 = 6 ；

a[1][1]所在的主存块对应的Cache行号为：

(320＋256×4＋1×4) DIV 64 MOD 8 = 5 。

(3) 编译时i、j、sum均分配在寄存器中，故数据访问命中率仅考虑数组a的情况。

①该程序的特点是数组中的每一个元素仅被使用一次。数组a按行优先存放，数据Cache正好放下数组半行中的全部元素，即元素的存储顺序与使用次序高度的吻合，每个字块的16个int型元素中，除访问的第一个不会命中，接下来的15个都会命中。访问全部字块都符合这一规律，故命中率为15／16，即程序A的数据访问命中率是93.75%。

②程序B按照数组的列执行外层循环，在执行内层循环的过程中，将连续访问不同行的同一列的数据，不同行的同一列数组使用的是同一个Cache单元，每次都不会命中，故命中率是0

由于从Cache读数据比从主存读数据快很多，所以程序A的执行比程序B快得多。

注意：本题考查Cache容量计算，直接映射方式的地址计算，以及命中率计算（注意：行优先遍历与列优先遍历命中率差别很大）。

?(n/2)，故所设计

45．解答：

(1) 用位图表示磁盘的空闲状态。每一位表示一个磁盘块的空闲状态，共需要16 384／32=512个字=512×4个字节=2KB，正好可放在系统提供的内存中。

(2) 采用CSCAN调度算法，访问磁道的顺序和移动的磁道数如下表所示：

被访问的下一个磁道号

120

移动距离（磁道数）

移动的磁道数为20+90+20+40=170，故总的移动磁道时间为170ms。

由于转速为6000r/m，则平均旋转延迟为5ms，总的旋转延迟时间=20ms。

由于转速为6000r/m，则读取一个磁道上一个扇区的平均读取时间为0.1ms，总的读取扇区的时间平均读取时间为0.1ms，总的读取扇区的时间为0.4ms。

综上，读取上述磁道上所有扇区所花的总时间为190.4ms。

(3) 采用FCFS（先来先服务）调度策略更高效。因为Flash半导体存储器的物理结构不需要考虑寻道时间和旋转延迟，可直接按I/O请求的先后顺序服务。

46．解答：

(1) 由于该计算机的逻辑地址空间和物理地址空间均为64KB = 216 B，按字节编址，且页的大小为1K = 210，故逻辑地址和物理地址的地址格式均为：

页号/页框号（6位）页内偏移量（10位）

17CAH = 0001 0111 1100 1010B，可知该逻辑地址的页号为000101B = 5

(2) 根据FIFO 算法，需要替换装入时间最早的页，故需要置换装入时间最早的0 号页，即将5号页装入7号页框中，所以物理地址为0001 1111 1100 1010B = 1FCAH。

(3) 根据CLOCK算法，如果当前指针所指页框的使用位为0，则替换该页；否则将使用位清零，并将指针指向下一个页框，继续查找。根据题设和示意图，将从2号页框开始，前4次查找页框号的顺序为

2→4→7→9，并将对应页框的使用位清零。在第5次查找中，指针指向2号页框，因2号页框的使用位为0，故淘汰2号页框对应的2号页，把5号页装入2号页框中，并将对应使用位设置为1，所以对应的物理地址为0000 1011 1100 1010B = 0BCAH。

47．解答：

⑴当主机甲和主机乙同时向对方发送数据时，信号在信道中发生冲突后，冲突信号继续向两个方向传播。这种情况下两台主机均检测到冲突需要经过的时间最短，等于单程的传播时延 t0= 2km/200 000km/s =

0.01ms 。

主机甲（或主机乙）先发送一个数据帧，当该数据帧即将到达主机乙（或主机乙）时，主机乙（或主机甲）也开始发送一个数据帧，这时，主机乙（或主机甲）将立刻检测到冲突，而主机甲（或主机乙）要检测到冲突，冲突信号还需要从主机乙（或主机甲）传播到主机甲（或主机乙），因此甲乙两台主机均检测到冲突所需的最长时间等于双程的传播时延 2*t0 = 0.02ms 。

⑵主机甲发送一个数据帧的时间，即发送时延 t1 = 1518×8b/10Mbps = 1.2144 ms ；主机乙每成功收到一个数据帧后，向主机甲发送确认帧，确认帧的发送时延 t2 = 64×8b/10Mbps = 0.0512ms ；主机甲收到确认帧后，即发送下一数据帧，故主机甲的发送周期T = 数据帧发送时延 t1 + 确认帧发送时延 t2 + 双程传播时延

= t1 + t2 + 2*t0 = 1.2856 ms ；于是主机甲的有效数据传输率为

1500×8/T = 12000b/1.2856 ms ≈ 9.33 Mbps。（以太网有效数据1500字节，即以太网帧的数据部分）

2010年全国硕士研究生入学统一考试

计算机学科专业基础综合试题——选择题部分解析

一、单项选择题

1．考查限定条件的出栈序列。

A可由in,in,in,in,out,out,in,out,out,in,out,out得到；

B可由in,in,in,out,out,in,out,out,in,out,in,out得到；

C可由in,in,out,in,out,out,in,in,out,in,out,out得到；

D可由in,out,in,in,in,in,in,out,out,out,out,out得到，但题意要求不允许连续三次退栈操作，故D错。

2．考查受限的双端队列的出队序列。

A可由左入，左入，右入，右入，右入得到 B可由左入，左入，右入，左入，右入得到。

D可由左入，左入，左入，右入，左入得到所以不可能得到C。

3．考查线索二叉树的基本概念和构造。

题中所给二叉树的后序序列为dbca 。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b；结点b无左子树，左链域指向其前驱结点d；结点c无左子树，左链域指向其前驱结点b，无右子树，右链域指向其后继结点a。

4．考查平衡二叉树的插入算法。

插入48以后，该二叉树根结点的平衡因子由-1变为-2，失去平衡，需进行两次旋转（先右旋后左旋）操作。

5．考查树结点数的特性。

设树中度为i（i=0，1，2，3，4）的结点数分别为Ni，树中结点总数为N，则树中各结点的度之和等于N-1，即N = 1+N1+2N2+3N3+4N4 = N0+ N1+N2+N3+N4，根据题设中的数据，即可得到N0 = 82，即树T的叶结点的个数是82。

6．考查哈弗曼树的特性。

哈夫曼树为带权路径长度最小的二叉树，不一定是完全二叉树。哈夫曼树中没有度为１的结点，B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C正确；哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q的兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树，综上可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。

7．考查图的连通性。

要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通，首先需要G的任意六个结点构成完全连通子图G1，需15条边，然后再添一条边将第7个结点与G1连接起来，共需16条边。

8．考查拓扑排序序列。

题中图有三个不同的拓扑排序序列，分别为 abced，abecd，aebcd。

9．考查折半查找的过程。

具有n个结点的判定树的高度为??log2n???1，长度为16，高度为5，所以最多比较5次。10．考查快速排序。

递归次数与各元素的初始排列有关。如果每一次划分后分区比较平衡，则递归次数少，如果划分后分区不平衡，则递归次数多。递归次数与处理顺序无关。

11．考查各种排序算法的过程。

看第一趟可知仅有88被移到最后.

如果是希尔排序，则12，88，10应变为10，12，88。因此排除希尔排序。

如果是归并排序，则应长度为2的子序列是有序的，由此可排除归并。

如果是基数排序，则16，5，10应变为10，5，16，由此排除基数。

可以看到，每一趟都有一个元素移到其最终位置，符合冒泡排序特点。

12．考查计算机的性能指标。

Ⅰ.CPU的时钟频率，也就是CPU主频率，一般说来，一个时钟周期内完成的指令数是固定的，所以主频越高，CPU的速度也就快，程序的执行时间就越短。

Ⅱ.数据在功能部件之间传送的路径称为数据通路，数据通路的功能是实现CPU内部的运算器和寄存器以及寄存器之间的数据交换。优化数据通路结构，可以有效提高计算机系统的吞吐量，从而加快程序的执行。

Ⅲ.计算机程序需要先转化成机器指令序列才能最终得到执行，通过对程序进行编译优化可以得到更优的指令序列，从而使得程序的执行时间也越短。

13．考查定点数的运算。

用补码表示时8位寄存器所能表示的整数范围为-128~+127。由于r1 = -2，r2 = -14，r3 = -112， r4 = -8，则r2×r3 = 1568，结果溢出。

14．考查不同精度的数在计算机中的表示方法及其相互装换。

由于（int）f=1，小数点后面4位丢失，故II错。IV的计算过程是先将f转化为双精度浮点数据格式，然后进行加法运算，故（d+f）-d得到的结果为双精度浮点数据格式，而f为单精度浮点数据格式，故IV错。

15．考查存储器的组成和设计。

用2K×4位的芯片组成一个8K×8位存储器，每行中所需芯片数为2，每列中所需芯片数为4，各行芯片的地址分配为：

第一行（2个芯片并联） 0000H~07FFH

第二行（2个芯片并联） 0800H~0FFFH

第三行（2个芯片并联） 1000H~17FFH

第四行（2个芯片并联） 1800H~1FFFH

于是地址0B1FH所在芯片的最小地址即为0800H。

16．考查半导体随机存取存储器。

一般Cache采用高速的SRAM制作，比ROM速度快很多，因此III是错误的，排除法即可选A。RAM需要刷新，而ROM不需要刷新。

17．考查TLB、Cache及Page之间的关系。

TLB即为快表，快表只是慢表（Page）的小小副本，因此TLB命中，必然Page也命中，而当Page命中，TLB则未必命中，故D不可能发生；而Cache的命中与否与TLB、Page的命中与否并无必然联系。

18．考查CPU内部寄存器的特性。

汇编程序员可以通过指定待执行指令的地址来设置PC的值，而IR，MAR，MDR是CPU的内部工作寄存器，对程序员不可见。

19．考查指令流水线的基本概念。

有三种相关可能引起指令流水线阻塞：1. 结构相关，又称资源相关；2. 数据相关；3. 控制相关，主要由转移指令引起。

数据旁路技术，其主要思想是不必待某条指令的执行结果送回到寄存器，再从寄存器中取出该结果，作为下一条指令的源操作数，而是直接将执行结果送到其他指令所需要的地方，这样可以使流水线不发生停顿。

20．考查典型的总线标准，

目前典型的总线标准有：ISA、EISA、VESA、 PCI 、PCI-Express、AGP、USB、RS-232C等。

21．考查中断处理过程。

单级中断系统中，不允许中断嵌套。中断的处理过程为：1. 关中断；2. 保存断点；3. 识别中断源；4.保存现场；5. 中断事件处理；（开中断、执行中断服务程序、关中断）6. 恢复现场；7. 开中断；8. 中断返回。其中，1~3步由硬件完成，4~8由中断服务程序完成。

22．考查显示器相关概念。

刷新所需带宽 = 分辨率×色深×帧频 = 1600×1200×24b×85HZ = 3916.8Mbps，显存总带宽的50%用来刷屏，于是需要的显存总带宽为3916.8/0.5 = 7833.6Mbps ≈ 7834Mbps。

23．考查操作系统的接口。

系统调用是能完成特定功能的子程序，当应用程序要求操作系统提供某种服务时，便调用具有相应功能的系统调用。库函数则是高级语言中提供的与系统调用对应的函数（也有些库函数与系统调用无关），目的是隐藏访管指令的细节，使系统调用更为方便抽象。但要注意，库函数属于用户程序而非系统调用，是系统调用的上层。

24．考查引起创建进程的事件。

引起进程创建的事件有：用户登录、作业调度、提供服务、应用请求等，本题的选项分别对应：Ⅰ用户登录成功在分时系统中，用户登录成功，系统将为终端建立一个进程。Ⅱ设备分配设备分配是通过在系统中设置相应的数据结构实现的，不需要创建进程。Ⅲ启动程序执行典型的引起创建进程的事件。

25．考查信号量的原理。

信号量表示当前的可用相关资源数。当信号量K>0时，表示还有K个相关资源可用；而当信号量K<0时，表示有|K|个进程在等待该资源。所以该资源可用数是1，等待该资源的进程数是0。

26．考查进程调度。

进程时间片用完，从执行态进入就绪态应降低优先级以让别的进程被调度进入执行状态。B中进程刚完成I/O，进入就绪队列后应该等待被处理机调度，故应提高优先权；C中有类似的情况；D中不应该在此时降低，应该在时间片用完后降低。

27．考查进程间通信与Peterson算法。

此算法实现互斥的主要思想在于设置了一个turn变量，用于进程间的互相“谦让”。

一般情况下，如果进程p0试图访问临界资源，设置flag[0]=true，表示希望访问。此时如果进程p1还未试图访问临界资源，则flag[1]在进程上一次访问完临界资源退出临界区后已设置为false。所以进程p0在执行循环判断条件时，第一个条件不满足，进程p0可以正常进入临界区，且满足互斥条件。

我们需要考虑的是两个进程同时试图访问临界资源的情况。注意turn变量的含义：进程在试图访问时，首先设置自己的flag变量为true，表示希望访问；但又设置turn变量为对方的进程编号，表示“谦让”，因为在循环判断条件中turn变量不是自己编号时就循环等待。这时两个进程就会互相“谦让”一番，但是这不会造成饥饿的局面，因为turn变量会有一个最终值，所以必定有进程可以结束循环进入临界区。实际的情况是，先作出“谦让”的进程先进入临界区，后作出“谦让”的进程则需要循环等待。

其实这里可以想象为两个人进门，每个人进门前都会和对方客套一句“你走先”。如果进门时没别人，就当和空气说句废话，然后大步登门入室；如果两人同时进门，就互相请先，但各自只客套一次，所以先客套的人请完对方，就等着对方请自己，然后光明正大进门。

28．考查动态分区分配。

考生需对动态分区分配的四种算法加以理解。最佳适配算法是指：每次为作业分配内存空间时，总是找到能满足空间大小需要的最小的空闲分区给作业。可以产生最小的内存空闲分区。下图显示了这个过程的主存空间的变化：

6M15M15M15M15M9M55M40M30M30M30M30M10M10M8M2M8M2M分配6Mb初始分配15Mb分配30Mb释放15Mb分配8Mb图2010-28 最佳适配算法分配示意图

图中，灰色部分为分配出去的空间，白色部分为空闲区。这样，容易发现,此时主存中最大空闲分区的大小为9Mb。

29．考查非连续分配的分页存储管理方式。

页大小为210字节，页表项大小为2字节，采用二级页表，一页可存放29个页表项，逻辑地址空间大小为216页，要使表示整个逻辑地址空间的页目录表中包含的的个数最少，则需要216/29= 27 = 128个页面保存页表项，即页目录表中包含的个数最少为128。

30．考查磁盘文件的大小性质。

因每个磁盘索引块和磁盘数据块大小均为256字节。所以4个直接地址索引指向的数据块大小为4×256字节。2个一级间接索引共包括2×(256÷4)个直接地址索引，既其指向的数据块大小为2×(256÷4)

×256字节。1个二级间接地址索引所包含的直接地址索引数为(256÷4) ×(256÷4)，即其所指向的数据块大小为(256÷4) ×(256÷4) ×256字节。即7个地址项所指向的数据块总大小为4×256+2×(256÷4)

×256+(256÷4) ×(256÷4) ×256=1082368字节=1057KB。

31．考查当前目录的作用。

一个文件系统含有许多级时，每访问一个文件，都要使用从树根开始直到树叶为止，包括各中间节点名的全路径名。当前目录又称工作目录，进程对各个文件的访问都相对于当前目录进行，所以检索速度要快于检索全路径名。

32．考查中断处理。

键盘是典型的通过中断I/O方式工作的外设，当用户输入信息时，计算机响应中断并通过中断处理程序获得输入信息。

33．考查计算机网络体系结构的基本概念。

我们把计算机网络的各层及其协议的集合称为体系结构。因此A、B、D正确，而体系结构是抽象的，它不包括各层协议及功能的具体实现细节。

34．考查存储转发机制。

由题设可知，分组携带的数据长度为980B，文件长度为980000B，需拆分为1000个分组，加上头王道论坛 — 予人玫瑰手留余香

- 9 -

部后，每个分组大小为1000B，总共需要传送的数据量大小为1MB。由于所有链路的数据传输速度相同，因此文件传输经过最短路径时所需时间最少，最短路径经过2个分组交换机。

当t = 1M×8/100Mbps = 80ms时，H1发送完最后一个bit；

由于传输延时，当H1发完所有数据后，还有两个分组未到达目的地，其中最后一个分组，需经过2个分组交换机的转发，在两次转发完成后，所有分组均到达目的主机。每次转发的时间为 t0 =

1K×8/100Mbps = 0.08ms。

所以，在不考虑分组拆装时间和等待延时的情况下，当t = 80ms + 2t0 = 80.16ms时，H2接收完文件，即所需的时间至少为80.16ms。

35．考查RIP路由协议。

RIP使用距离向量算法的工作过程参见内容精讲部分。

R1在收到信息并更新路由表后，若需要经过R2到达net1，则其跳数为17，由于距离为16表示不可达，因此R1不能经过R2到达net1，R2也不可能到达net1。B、C错误，D正确。而题目中并未给出R1向R2发送的信息，因此A也不正确。

36．考查ICMP协议。

ICMP差错报告报文有5种，终点不可达、源点抑制、时间超过、参数问题、改变路由（重定向），其中源点抑制是当路由器或主机由于拥塞而丢弃数据报时，就向源点发送源点抑制报文，使源点知道应当把数据报的发送速率放慢。

37．考查子网划分与子网掩码、CIDR。

由于该网络的IP地址为192.168.5.0/24，因此其网络号为前24位。第25-32位为子网位+主机位。而子网掩码为255.255.255.248，其第25-32位的248用二进制表示为11111000，因此后8位中，前5位用于子网号，后3位用于主机号。

RFC 950文档规定，对分类的IPv4地址进行子网划分时，子网号不能为全1或全0。但随着无分类域间路由选择CIDR的广泛使用，现在全1和全0的子网号也可以使用了，但一定要谨慎使用，要弄清你的路由器所有的路由选择软件是否支持全0或全1的子网号这种用法。但不论是分类的IPv4地址还是无分类域间路由选择CIDR，其子网中的主机号均不能为全1或全0。因此该网络空间的最大子网个数为25 = 32个，每个子网内的最大可分配地址个数为23 -2 = 6 个。38．考查网络设备与网络风暴。

物理层设备中继器和集线器既不隔离冲突域也不隔离广播域；网桥可隔离冲突域，但不隔离广播域；网络层的路由器既隔离冲突域，也隔离广播域；VLAN即虚拟局域网也可隔离广播域。对于不隔离广播域的设备，他们互连的不同网络都属于同一个广播域，因此扩大了广播域的范围，更容易产生网络风暴。

39．考查TCP流量控制与拥塞控制。

发送方的发送窗口的上限值应该取接收方窗口和拥塞窗口这两个值中较小的一个，于是此时发送方的发送窗口为MIN{4000，2000}=2000字节，由于发送方还没有收到第二个最大段的确认，所以此时主机甲还可以向主机乙发送的最大字节数为2000-1000=1000字节。

40．考查DNS系统域名解析过程。

当采用递归查询的方法解析域名时，如果主机所询问的本地域名服务器不知道被查询域名的 IP 地址，那么本地域名服务器就以 DNS 客户的身份，向其他根域名服务器继续发出查询请求报文，这种方法用户主机和本地域名服务器发送的域名请求条数均为1条。

2011年全国硕士研究生入学统一考试

计算机科学与技术学科联考

计算机学科专业基础综合

（科目代码：408）

一、单项选择题：1-40小题，每小题2分，共80分，下列每小题给出的四个选项中，只有一项符合题目要求的。请在答题卡上将所选项的字母涂黑。)

1．设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是

x=2；while（x

2A．O(log2n) B．O(n) C．O(nlog2n) D．O(n)

解答：A。程序中，执行频率最高的语句为“x=2*x”。设该语句执行了t次，则2t+1=n/2，故t=log2(n/2)-1=log2n-2= O(log2n)。2．元素a，b，c，d，e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是

A．3 B．4 C．5 D．6

解答：B。出栈顺序必为d_c_b_a_，e的顺序不定，在任意一个“_”上都有可能。

3．已知循环队列存储在一维数组-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是

A．0,0 B．0，n-1 C．n-1,0 D．n-1，n-1

解答：B。插入元素时，front不变，rear+1.而插入第一个元素之后，队尾要指向尾元素，显然，rear初始应该为n-1,front为0。

4．若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是

A．257 B．258 C．384 D．385

解答：C。叶结点数为n，则度为2的结点数为n-1,度为1的结点数为0或1，本题中为1（总结点数为偶数），故而即2n=768。

5．若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树的中序遍历序列不会是

A．1,2,3,4 B．2,3,4,1 C．3,2,4,1 D．4,3,2,1

解答：C。由前序和后序遍历序列可知3为根结点，故（1,2）为左子树，（4）为右子树，C不可能。或画图即可得出结果。

6．已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是

A．115 B．116 C．1895 D．1896

解答：D。本题可采用特殊情况法解。设题意中的树是如下图所示的结构，则对应的二叉树中仅有前115个叶结点有右孩子。

共1895个中间结点??共116个叶结点7．对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是

A．95,22,91,24,94,71 B．92,20,91,34,88,35

C．21,89,77,29,36,38 D．12,25,71,68,33,34

解答：A。选项A中，当查到91后再向24查找，说明这一条路径之后查找的数都要比91小，后面的94就错了。

8．下列关于图的叙述中，正确的是

Ⅰ. 回路是简单路径

Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间

Ⅲ．若有向图中存在拓扑序列，则该图不存在回路

C．仅Ⅲ D．仅Ⅰ、Ⅲ A．仅Ⅱ B．仅Ⅰ、Ⅱ

解答：C。Ⅰ.回路对应于路径，简单回路对应于简单路径；Ⅱ．刚好相反；Ⅲ．拓扑有序的必要条件。故选C。

9．为提高散列（Hash）表的查找效率，可以采取的正确措施是

Ⅰ. 增大装填（载）因子

Ⅱ．设计冲突（碰撞）少的散列函数

Ⅲ．处理冲突（碰撞）时避免产生聚集（堆积）现象

A．仅Ⅰ B．仅Ⅱ C．仅Ⅰ、Ⅱ D．仅Ⅱ、Ⅲ

解答：B。III错在“避免”二字。

10．为实现快速排序算法，待排序序列宜采用的存储方式是

A．顺序存储 B．散列存储 C．链式存储 D．索引存储

解答：A。内部排序采用顺序存储结构。

11．已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是

A．1 B．2 C．4 D．5

解答：B。首先与10比较，交换位置，再与25比较，不交换位置。比较了二次。

12．下列选项中，描述浮点数操作速度指标的是

A．MIPS B．CPI C．IPC D．MFLOPS

解答：D。送分题。

13．float型数据通常用IEEE 754单精度浮点数格式表示。若编译器将float型变量x分配在一个32位浮点寄存器FR1中，且x=-8.25，则FR1的内容是

A．C104 0000H B．C242 0000H C．C184 0000H D．C1C2 0000H

解答：A。x的二进制表示为-1000.01﹦-1.000 01×2根据IEEE754标准隐藏最高位的“1”，又E-127=3，所以E=130=1000 0010（2）数据存储为1位数符+8位阶码（含阶符）+23位尾数。

故FR1内容为1 10000 0010 0000 10000 0000 0000 0000 000

即1100 0001 0000 0100 0000 0000 0000 0000，即C104000H

14．下列各类存储器中，不采用随机存取方式的是

A．EPROM B．CDROM C．DRAM D．SRAM

解答：B。光盘采用顺序存取方式。

15．某计算机存储器按字节编址，主存地址空间大小为64MB，现用4M×8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是

A．22位 B．23位 C．25位 D．26位

解答：D。64MB的主存地址空间，故而MAR的寻址范围是64M，故而是26位。而实际的主存的空间不能代表MAR的位数。

16．偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是．A．间接寻址 B．基址寻址 C．相对寻址 D．变址寻址

解答：A。间接寻址不需要寄存器，EA=(A)。基址寻址：EA=A+基址寄存器内同；相对寻址：EA﹦A+PC内容；变址寻址：EA﹦A+变址寄存器内容。

17．某机器有一个标志寄存器，其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt（无符号整数比较大于时转移）的转移条件是

A．CF?OF?1 B．SF?ZF?1 C．CF?ZF?1 D．CF?SF?1

解答：C。无符号整数比较，如A>B，则A-B无进位/借位，也不为0。故而CF和ZF均为0。

18．下列给出的指令系统特点中，有利于实现指令流水线的是

Ⅰ. 指令格式规整且长度一致 Ⅱ．指令和数据按边界对齐存放

Ⅲ．只有Load/Store指令才能对操作数进行存储访问

A．仅Ⅰ、Ⅱ B．仅Ⅱ、Ⅲ C．仅Ⅰ、Ⅲ D．Ⅰ、Ⅱ、Ⅲ

解答：D。指令定长、对齐、仅Load/Store指令访存，以上三个都是RISC的特征。均能够有效的简化流水线的复杂度。

19．假定不采用Cache和指令预取技术，且机器处于“开中断”状态，则在下列有关指令执行的叙述中，错误的是．．A．每个指令周期中CPU都至少访问内存一次

B．每个指令周期一定大于或等于一个CPU时钟周期

C．空操作指令的指令周期中任何寄存器的内容都不会被改变

D．当前程序在每条指令执行结束时都可能被外部中断打断

解答：C。会自动加1，A取指令要访存、B时钟周期对指令不可分割。

20．在系统总线的数据线上，不可能传输的是．A．指令 B．操作数

C．握手（应答）信号 D．中断类型号

解答：C。握手（应答）信号在通信总线上传输。

21．某计算机有五级中断L4～L0，中断屏蔽字为M4M3M2M1M0，Mi=1（0≤i≤4）表示对Li级中断进行屏蔽。若中断响应优先级从高到低的顺序是L4→L0→L2→L1→L3

，则L1的中断处理程序中设置的中断屏蔽字是

A．11110 B．01101 C．00011 D．01010

解答：D。高等级置0表示可被中断，比该等级低的置1表示不可被中断。

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。每秒200次查询，每次500个周期，则每秒最少200×500﹦10 0000个周期，10

0000÷50M=0.20%。

23．下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是

A．先来先服务 B．高响应比优先

C．时间片轮转 D．非抢占式短任务优先

解答：B。响应比=作业响应时间/作业执行时间 =(作业执行时间+作业等待时间)/作业执行时间。高响应比算法，在等待时间相同情况下，作业执行时间越少，响应比越高，优先执行，满足短任务优先。随着等待时间增加，响应比也会变大，执行机会就增大，所以不会产生饥饿现象。先来先服务和时间片轮转不符合短任务优先，非抢占式短任务优先会产生饥饿现象。

24．下列选项中，在用户态执行的是

A．命令解释程序 B．缺页处理程序

C．进程调度程序 D．时钟中断处理程序

解答：A。缺页处理程序和时钟中断都属于中断，在核心态执行。进程调度属于系统调用在核心态执行，命令解释程序属于命令接口，它在用户态执行。

25．在支持多线程的系统中，进程P创建的若干个线程不能共享的是

A．进程P的代码段 B．进程P中打开的文件

C．进程P的全局变量 D．进程P中某线程的栈指针

解答：D。进程中某线程的栈指针，对其它线程透明，不能与其它线程共享。

26．用户程序发出磁盘I/O请求后，系统的正确处理流程是

A．用户程序→系统调用处理程序→中断处理程序→设备驱动程序

B．用户程序→系统调用处理程序→设备驱动程序→中断处理程序

C．用户程序→设备驱动程序→系统调用处理程序→中断处理程序

D．用户程序→设备驱动程序→中断处理程序→系统调用处理程序

解答：B。输入／输出软件一般从上到下分为四个层次：用户层、与设备无关软件层、设备驱动程序以及中断处理程序。与设备无关软件层也就是系统调用的处理程序。所以争取处理流程为B选项。

27．某时刻进程的资源使用情况如下表所示。

进程

已分配资源

尚需分配

0 2 1

可用资源

R1 R2 R3

此时的安全序列是

A．P1,P2,P3,P4 B．P1,P3,P2,P4

C．P1,P4,P3,P2 D．不存在

解答：D。使用银行家算法得，不存在安全序列。

28．在缺页处理过程中，操作系统执行的操作可能是

Ⅰ. 修改页表 Ⅱ．磁盘I/O Ⅲ．分配页框

A．仅Ⅰ、Ⅱ B．仅Ⅱ C．仅Ⅲ D．Ⅰ、Ⅱ和Ⅲ

解答：D。缺页中断调入新页面，肯定要修改页表项和分配页框，所以I、ＩＩＩ可能发生，同时内存没有页面，需要从外存读入，会发生磁盘I/O。

29．当系统发生抖动（thrashing）时，可用采取的有效措施是

Ⅰ. 撤销部分进程

Ⅱ．增加磁盘交换区的容量

Ⅲ．提高用户进程的优先级

B．仅Ⅱ C．仅Ⅲ D．仅Ⅰ、Ⅱ A．仅Ⅰ

解答：A。在具有对换功能的操作系统中，通常把外存分为文件区和对换区。前者用于存放文件，后者用于存放从内存换出的进程。抖动现象是指刚刚被换出的页很快又要被访问为此，又要换出其他页，而该页又快被访问，如此频繁的置换页面，以致大部分时间都花在页面置换上。撤销部分进程可以减少所要用到的页面数，防止抖动。对换区大小和进程优先级都与抖动无关。

30．在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是

A．编辑 B．编译 C．链接 D．装载

解答：B。编译过程指编译程序将用户源代码编译成目标模块。源地址编译成目标程序时，会形成逻辑地址。

31．某文件占 10 个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100us，

将缓冲区的数据传送到用户区的时间是50us，CPU对一块数据进行分析的时间为50us。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是

A．1500us、1000us B．1550us、1100us

C．1550us、1550us D．2000us、2000us

解答：B。单缓冲区下当上一个磁盘块从缓冲区读入用户区完成时下一磁盘块才能开始读入，也就是当最后一块磁盘块读入用户区完毕时所用时间为１５０×１０＝１５００。加上处理最后一个磁盘块的时间５０为１５５０。双缓冲区下，不存在等待磁盘块从缓冲区读入用户区的问题，也就是１００×１０＋１００＝１１００。

32．有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示。

// 减1操作 // 加1操作

load R1，x // 取x到寄存器R1中 load R2，x

inc R1 dec R2

store x，R1 // 将R1的内容存入x store x，R2

两个操作完成后，x的值

A．可能为-1或3 B．只能为1

C．可能为0、1或2 D．可能为-1、0、1或2

解答：C。将P1中3条语句变为1,2,3，P2中3条语句编为4，5，6。则依次执行1,2,3,4,5得结果1，依次执行1,2,4,5,6,3得结果2，执行4，5，1，2，3，6得结果0。结果-1不可能得出，选C。

33．TCP/IP参考模型的网络层提供的是

A．无连接不可靠的数据报服务 B．无连接可靠的数据报服务

C．有连接不可靠的虚电路服务 D．有连接可靠的虚电路服务

解答：A。TCP/IP的网络层向上只提供简单灵活的、无连接的、尽最大努力交付的数据报服务。此外考察IP首部，如果是面向连接的，则应有用于建立连接的字段，但是没有；如果提供可靠的服务，则至少应有序号和校验和两个字段，但是IP分组头中也没有（IP首部中只是首部校验和）。因此网络层提供的无连接不可靠的数据服务。有连接可靠的服务由传输层的TCP提供。

34．若某通信链路的数据传输速率为2400bps，采用4相位调制，则该链路的波特率是

A．600波特 B．1200波特 C．4800波特 D．9600波特

解答：B。有4种相位，则一个码元需要由log24=2个bit表示，则波特率=比特率/2=1200波特。

35．数据链路层采用选择重传协议（SR）传输数据，发送方已发送了0～3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是

A．1 B．2 C．3 D．4

解答：B。选择重传协议中，接收方逐个地确认正确接收的分组，不管接收到的分组是否有序，只要正确接收就发送选择ACK分组进行确认。因此选择重传协议中的ACK分组不再具有累积确认的作用。这点要特别注意与GBN协议的区别。此题中只收到1号帧的确认，0、2号帧超时，由于对于1号帧的确认不具累积确认的作用，因此发送方认为接收方没有收到0、2号帧，于是重传这两帧。

36．下列选项中，对正确接收到的数据帧进行确认的MAC协议是

A．CSMA B．CDMA C．CSMA/CD D．CSMA/CA

解答：D。可以用排除法。首先CDMA即码分多址，是物理层的东西；CSMA/CD即带冲突检测的载波监听多路访问，这个应该比较熟悉，接收方并不需要确认；CSMA，既然CSMA/CD是其超集，CSMA/CD没有的东西，CSMA自然也没有。于是排除法选D。CSMA/CA是无线局域网标准802.11中的协议。CSMA/CA利用ACK信号来避免冲突的发生，也就是说，只有当客户端收到

网络上返回的ACK信号后才确认送出的数据已经正确到达目的地址。

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

255.255.255.0 192.168.1.2 D．192.168.2.0

解答：D。此题主要考察路由聚合。要使R1能够正确将分组路由到所有子网，则R1中需要有到192.168.2.0/25和192.168.2.128/25的路由。观察发现网络192.168.2.0/25和192.168.2.128/25的网络号的前24位都相同，于是可以聚合成超网192.168.2.0/24。从图中可以看出下一跳地址应该是192.168.1.2。

38．在子网192.168.4.0/30中，能接收目的地址为192.168.4.3的IP分组的最大主机数是

A．0 B．1 C．2 D．4

解答：C。首先分析192.168.4.0/30这个网络。主机号占两位，地址范围192.168.4.0/30~

192.168.4.3/30，即可以容纳（4-2=2）个主机。主机位为全1时，即192.168.4.3，是广播地址，因此网内所有主机都能收到，因此选C。

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)

解答：C。主机乙收到连接请求报文后，如同意连接，则向甲发送确认。在确认报文段中应把SYN位和ACK位都置1，确认号是甲发送的TCP段的初始序号seq=11220加1，即为ack=

11221，同时也要选择并消耗一个初始序号seq，seq值由主机乙的TCP进程确定，本题取seq=

11221与确认号、甲请求报文段的序号没有任何关系。

40．主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3个连续的TCP段，分别包含300字节、400字节和500字节的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1和第3个段，则主机乙发送给主机甲的确认序号是

A．300 B．500 C．1200 D．1400

解答：B。TCP段首部中的序号字段是指本报文段所发送的数据的第一个字节的序号。第三个段的序号为900，则第二个段的序号为900-400=500。而确认号是期待收到对方下一个报文段的第一个字节的序号。现在主机乙期待收到第二个段，故甲的确认号是500。

二、综合应用题：41～47小题，共70分。请将答案写在答题纸指定位置上。

41．（8分）已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A为上三角

矩阵，按行为主序（行优先）保存在如下的一维数组中。

4 6 ∞ ∞ ∞ 5 ∞ ∞ ∞ 4 3 ∞ ∞ 3 3

要求：

（1）写出图G的邻接矩阵A。

（2）画出有向带权图G。

（3）求图G的关键路径，并计算该关键路径的长度。

解答：

（1）图G的邻接矩阵A如下所示。

?0?????A???????????????05?????043?????0?3????03??????0??46（2）有向带权图G如下图所示。

4（3）关键路径为0?1?2?3?5（如下图所示粗线表示），长度为4+5+4+3=16。

542．（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）说明你所设计算法的时间复杂度和空间复杂度。

解答：

（1）算法的基本设计思想如下。

分别求出序列A和B的中位数，设为a和b，求序列A和B的中位数过程如下：

1）若a=b，则a或b即为所求中位数，算法结束。

2）若a

3）若a>b，则舍弃序列A中较大的一半，同时舍弃序列B中较小的一半，要求舍弃的

长度相等；

在保留的两个升序序列中，重复过程1）、2）、3），直到两个序列中只含一个元素时为止，较小者即为所求的中位数。

（2）算法的实现如下：

int M_Search(int A[],int B[],int n){

int s1=0,d1=n-1,m1,s2=1,d2=n-1,m2;

//分别表示序列A和B的首位数、末位数和中位数while(s1!=d1||s2!=d2){

m1=(s1+d1)/2;

m2=(s2+d2)/2;

if(A[m1]==B[m2])

return A[m1]; //满足条件1）if(A[m1]

else{ //元素个数为偶数s1=m1+1; //舍弃A中间点及中间点以前部分d2=m2;

}

else{ //满足条件3）if((s1+d1)%2==0) { //若元素个数为奇数d1=m1; //舍弃A中间点以后的部分且保留中间点s2=m2; //舍弃B中间点以前的部分且保留中间点}

else{ //元素个数为偶数d1=m1+1; //舍弃A中间点以后部分且保留中间点s2=m2; //舍弃B中间点及中间点以前部分}

}

return A[s1]

}

//舍弃B中间点以后部分且保留中间点（3）算法的时间复杂度为O(log2n)，空间复杂度为O(1)。

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）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出？上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？

解答：

（1） R1=134=86H, R5=90H, R6=7CH；

134=1000 0110B=86H；x-y=1000 0110B-1111 0110B=1001 0000B=90H；x+y=1000

0110B+1111 0110B=0111 1100B（溢出）

（2）m=-122,k1=-112

m=1000 0110B，做高位为符号位，则m的原码为1111 1010B=-122；n=1111 0110B

n的原码为1000 1001=-10；k1=m-n=-112。

（3）无符号数和有符号数都是以补码的形式存储，加减运算没有区别（不考虑溢出情况时），只是输出的时候若是有符号数的最高位是符号位。

减法运算求[-x]补的时候，是连同符号位一起按位取反末位加1，但是如果有溢出情况，这两者是有区别的，所以可以利用同一个加法器实现，但是溢出判断电路不同。

（4）判断方法是如果最高位进位和符号位的进位不同，则为溢出；“int k2=m+n;”会溢出；

三种方法可以判断溢出，双符号位、最高位进位、符号相同操作数的运算后与原操作数的符号不同则溢出

44．（12分）某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为16MB，主存（物理）地址空间大小为1MB，页面大小为4KB；Cache采用直接映射方式，共8行；主存与Cache之间交换的块大小为32B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44-a图、题44-b图所示，图中页框号及标记字段的内容为十六进制形式。

虚页号有效位页框号 … 行号有效位标记 …

0 0 0

1 06 …

1 020 …

1 1 1

1 04 …

0 - …

2 2 2

1 15 …

1 01D …

3 3 3

1 02 …

1 105 …

4 4 4

0 - …

1 064 …

5 5 5

1 2B …

1 14D …

6 6 6

0 - …

7 7 7

1 32 …

1 27A …

题44-a图页表的部分内容题44-b图 Cache的部分内容

请回答下列问题。

（1）虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？

（2）使用物理地址访问Cache时，物理地址应划分成哪几个字段？要求说明每个字段的位数及在物理地址中的位置。

（3）虚拟地址001C60H所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否Cache命中？要求说明理由。

（4）假定为该机配置一个4路组相联的TLB共可存放8个页表项，若其当前内容（十六进制）如题44-c图所示，则此时虚拟地址024BACH所在的页面是否存在主存中？要求说明理由。

组号有效位标记页框号有效位标记页框号有效位标记页框号有效位标记页框号

- - 1

001 15

- -

- - 1

012

- 013 2D 008 7E

题44-c图 TLB的部分内容

解答：

（1）24位、前12位；20位、前8位。

16M=224故虚拟地址24位，4K=212，故页内地址12位，所以虚页号为前12位；1M=220故物理地址20位，20-12=8，故前8位为页框号。

（2）

主存字块标记（12bit）、cache字块标记（3bit）、字块内地址（5bit）

物理地址20位，其中，块大小为32B=25B故块内地址5位；cache共8行，8=23，故字块标记为3位；20-5-2=12，故主存字块标记为12位。

（3）在主存中，04C60H, 不命中，没有04C的标记字段

001C60H中虚页号为001H=1，查页表知其有效位为1，在内存中；该物理地址对应的也表项中，页框号为04H故物理地址为04C60H；物理地址04C60H在直接映射方式下，对应的行号为4，有效位为1但是标记位为064H≠04CH故不命中。

（4）在，012的那个标记是对的。

思路：标记11位组地址1位页内地址12位，前12位为0000 0010 0100，组地址位为0，第0组中存在标记为012的页，其页框号为1F，故024BACH所在的页面存在主存中。

45．（8分）某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

cobegin

{

process 顾客i

{

从取号机获取一个号码；

等待叫号；

获取服务；

}

process 营业员

{

while（TRUE）

{

叫号；

为客户服务；

}

}coend

请添加必要的信号量和P、V（或wait()、signal()）操作，实现上述过程中的互斥与同步。

要求写出完整的过程，说明信号量的含义并赋初值。

解答：

semaphore seets = 10, // 有10个坐位的资源信号量mutex = 1, // 取号机互斥信号量haveCustom = 0; // 顾客与营业员同步，无顾客时营业员休息process 顾客{

P(seets); // 等空位P(mutex); // 申请使用取号机从取号机上取号;V(mutex); // 取号完毕V(haveCustom); // 通知营业员有新顾客到来等待营业员叫号;V(seets); // 离开坐位接受服务；

}

process 营业员{

while(True)

{

P(haveCustom); // 没有顾客则休息叫号;为顾客服务; }

}

46．（7分）某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。

（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需要FCB中设计哪些相关描述字段？

（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。

解答：

（1）连续更合适,因为一次写入不存在插入问题,连续的数据块组织方式完全可以满足一次性写入磁盘。同时连续文件组织方式减少了其他不必要的空间开销，而连续的组织方式顺序查找读取速度是最快的。

（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图网络拓扑

0000 00 21 27 21 51 ee 00 15 c5 c1 5e 28 08 00 45 00 .!|!Q... ..^(..E.

0010 01 ef 11 3b 40 00 80 06 ba 9d 0a 02 80 64 40 aa ...:@... .....d@.

0020 62 20 04 ff 00 50 e0 e2 00 fa 7b f9 f8 05 50 18 b ...P.. ..{...P.

0030 fa f0 1a c4 00 00 47 45 54 20 2f 72 66 63 2e 68 ......GE T /rfc.h

0040 74 6d 6c 20 48 54 54 50 2f 31 2e 31 0d 0a 41 63 tml HTTP /1.1..Ac

题 47-b图以太网数据帧（前80字节）

请参考图中的数据回答以下问题。

（1）Web服务器的IP地址是什么？该主机的默认网关的MAC地址是什么？

（2）该主机在构造题47-b图的数据帧时，使用什么协议确定目的MAC地址？封装该协议请求报文的以太网帧的目的MAC地址是什么？

（3）假设HTTP/1.1协议以持续的非流水线方式工作，一次请求-响应时间为RTT，页面引用了5个JPEG小图像，则从发出题47-b图中的Web请求开始到浏览器收到全部内容为止，需要多少个RTT？

（4）该帧所封装的IP分组经过路由器R转发时，需修改IP分组头中的哪些字段？

注：以太网数据帧结构和IP分组头结构分别如题47-c图、题47-d图所示。

6B 6B 2B 46-1500B 4B

目的MAC地址类型

题47-c图以太网帧结构

源MAC地址数据 CRC

比特 0 8 24 31

题47-d IP分组头结构

解答：

（1）

64.170.98.32 00-21-27-21-51-ee

以太网帧头部6+6+2=14字节，IP数据报首部目的IP地址字段前有4*4=16字节，从以太网数据帧第一字节开始数14+16=30字节，得目的IP地址40 aa 62 20(十六进制)，转换为十进制得64.170.98.32。以太网帧的前六字节00-21-27-21-51-ee是目的MAC地址，本题中即为主机的默认网关10.2.128.1端口的MAC地址。

（2）

ARP FF-FF-FF-FF-FF-FF

ARP协议解决IP地址到MAC地址的映射问题。主机的ARP进程在本以太网以广播的形式发送ARP请求分组，在以太网上广播时，以太网帧的目的地址为全1，即FF-FF

-FF-FF-FF-FF。

（3）

HTTP/1.1协议以持续的非流水线方式工作时，服务器在发送响应后仍然在一段时间内保持这段连接，客户机在收到前一个响应后才能发送下一个请求。第一个RTT用于请求web页面，客户机收到第一个请求的响应后(还有五个请求未发送)，每访问一次对象就用去一个RTT。故共1+5=6个RTT后浏览器收到全部内容。

（4）

源IP地址0a 02 80 64 改为65 0c 7b 0f

生存时间(TTL)减1

校验和字段重新计算

私有地址和Internet上的主机通信时，须有NAT路由器进行网络地址转换，把IP数据报的源IP地址(本题为私有地址10.2.128.100)转换为NAT路由器的一个全球IP地址(本题为101.12.123.15)。因此，源IP地址字段0a 02 80 64变为65 0c 7b 0f。IP数据报每经过一个路由器，生存时间TTL值就减1，并重新计算首部校验和。若IP分组的长度超过输出链路的MTU，则总长度字段、标志字段、片偏移字段也要发生变化。

注意，图 47-b中每行前4bit是数据帧的字节计数，不属于以太网数据帧的内容。

2012年全国硕士研究生入学统一考试

计算机科学与技术学科联考

计算机学科专业基础综合试题

一、单项选择题：第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。

1．求整数n(n≥0)阶乘的算法如下，其时间复杂度是。

int fact(int n){

if (n<=1) return 1;

return n*fact(n-1);

}

A. O(log2n) B. O(n) C. O(nlog2n) D. O(n2)

2．已知操作符包括?+?、?-?、?*?、?/?、?(?和?)?。将中缀表达式a+b-a*((c+d)/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是。

A．5

点。

A. 只有e

为。

A. 10 B. 20

C. 32

D. 33

D．O(n*e)

5．对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是。

A．O(n)

是。

A．存在，且唯一

C．存在，可能不唯一

B．存在，且不唯一

D．无法确定是否存在

B．O(e) C．O(n+e)

6．若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论B. 有e、b C. 有e、c D. 无法确定

4．若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数 B．7 C．8 D．11

3．若一棵二叉树的前序遍历序列为a, e, b, d, c，后序遍历序列为b, c, d, e, a，则根结点的孩子结7．对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点a到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是。

A．d,e,f

B．e,d,f C．f,d,e D．f,e,d

8．下列关于最小生成树的叙述中，正确的是。

Ⅰ．最小生成树的代价唯一

Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中

王道论坛（）原创并友情分享！~

Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同

Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同

A．仅Ⅰ

是。

B．仅Ⅱ C．仅Ⅰ、Ⅲ D．仅Ⅱ、Ⅳ

9．已知一棵3阶B-树，如下图所示。删除关键字78得到一棵新B-树，其最右叶结点中的关键字A．60 B．60, 62 C．62, 65