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 b
2.
某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素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 d
3.下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是______。
a Null a Null a Null a b c b c b c b c Null A．
d B．
d C．
d Null D．
d 4.在右图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是______。 A．13，48C．24，53
B．24，48 D、24，90
24
13
37
53
90
5.在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是______。A．41 B．82 C．113 D．122
6.
对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．7
e a b c d 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 r4
B．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-Express
21.单级中断系统中，中断服务程序内的执行顺序是______。
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->VII
22.假定一台计算机的显示存储器用DRAM芯片实现，若要求显示分辨率为1600*1200，颜色深度为24位，
帧频为85HZ，显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约为______。A．245Mbps B．979MbpsC．1 958Mbps D．7 834Mbps
23.下列选项中，操作系统提供给应用程序的接口是_____。
A．系统调用C．库函数
Ⅰ用户登录成功
Ⅱ设备分配
B．中断 D．原语
Ⅲ启动程序执行 C．仅Ⅰ和Ⅲ
D．Ⅰ、Ⅱ和Ⅲ
24.下列选项中，导致创建新进程的操作是______。
A．仅Ⅰ和Ⅱ B．仅Ⅱ和Ⅲ数，则M、N分别是______。 A．0、1
B．1、0
C．1、2
D．2、0
25.设与某资源关联的信号量初值为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; }
2009至2019年计算机考研408历年真题及解析
