作者：圣才电子书
出版社：圣才电子书
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
全国硕士研究生入学统一考试计算机科学与技术学科联考数据结构题库【历年真题＋章节题库＋模拟试题】试读：
第1部分 历年考研真题
2009年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合真题及详解
一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中。只有一个选项是最符合题目要求的。
1为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。
A．栈
B．队列
C．树
D．图【答案】B【解析】这类问题一般都先分析题目中的数据具有什么操作特性或是结构特性比如“先进后出”、“先进先出”等再判断其逻辑结构。栈和队列是操作受限的线性表，栈具有先进后出的特性而队列具有先进先出的特性。由于本题中先进入打印数据缓冲区的文件先被打印，因此打印数据缓冲区具有先进先出性，则它的逻辑结构应该是队列。
2设栈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．4【答案】C【解析】由于栈具有先进后出的特性，队列具有先进先出的特性，出队顺序即为人队顺序。在本题中，每个元素出栈S后立即进入队列Q，出栈顺序即为入队顺序，所以本题中队列的作用形同虚设，根据题意出队顺序即为出栈顺序。根据出栈顺序可以分析各个元素进出栈的过程：第一个出栈元素为b，表明栈内还有元素a，b出栈前的深度为2；第二个出栈元素为d，栈内元素为a和c，d出栈前的深度为3；c出栈后，剩余元素为a，c出栈前的深度为2；f出栈后，剩余元素为a和e，f出栈前的深度为3；e出栈后，剩余元素为a，e出栈前的深度为2；a出栈后，无剩余元素，a出栈前的深度为1；g出栈后，无剩余元素，g出栈前的深度为1。所以栈容量至少是3。
3给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3，1，7，5，6，2，4，则其遍历方式是（ ）。
A．LRN
B．NRL
C．RLN
D．RNL【答案】D【解析】对“二叉树”而言，一般有三条搜索路径：
①先上后下的按层次遍历；
②先左（子树）后右（子树）的遍历；
③先右（子树）后左（子树）的遍历。
其中第1种搜索路径方式就是常见的层次遍历，第2种搜索路径方式包括常见的先序遍历NLR、中序遍历LNR、后序遍历LRN，第3种搜索路径方式则是不常使用的NRL、RNL、RLN。本题考查的是第3种搜索路径方式的一种情况。根据遍历的序列以及树的结构图，可以分析出该遍历的顺序是先右子树再跟结点最后左子树，故答案为D。
4下列二叉排序树中，满足平衡二叉树定义的是（ ）。【答案】B【解析】平衡二叉树是指左右子树高度差（平衡因子）的绝对值不超过1的二叉树。A项中根结点的平衡因子是2；B项中每个结点的平衡因子的绝对值均不超过1；C项中根结点的平衡因子是－2；D项中根结点的平衡因子是3。
5已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是（ ）。
A．39
B．52
C．111
D．119【答案】C【解析】完全二叉树的一个特点是：叶子结点只能出现在最下层和次下层。题目中没有说明完全二叉树的高度，首先由完全二叉树的特点确定题目中树的高度。根据题意，一棵完全二叉树的第6层（设根为第1层）有8个叶结点，可知此二叉树的高度是6或7。题目中求二叉树的结点数最多的情况，因此此完全二叉树的高度为7。由于高度为7的完全二叉树的前6层是一棵满二叉树，根据二叉树的性质2可知，6高度为6的满二叉树的结点数是2－1＝63。又根据二叉树的性质1可5知，题目中二叉树的第6层结点数是2＝32个结点，已知有8个叶子结点，那么其余32－8＝24个结点均为分支结点，这些结点在第7层上最多有48个子结点（即叶子结点）。所以此二叉树的结点数最多可65达2－1＋（2－8）×2＝111。
6将森林转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的森林中，u和v可能具有的关系是（ ）。
Ⅰ．父子关系
Ⅱ．兄弟关系
Ⅲ．u的父结点与v的父结点是兄弟关系
A．只有Ⅰ
B．Ⅰ和Ⅱ
C．Ⅰ和Ⅲ
D．Ⅰ、Ⅱ和Ⅲ【答案】B【解析】首先，在二叉树中，若结点u是结点v的父结点的父结点，那么u和v的关系有如下4种情况：
接下来，根据森林与二叉树的转换规则，将这4种情况还原成森林中结点的关系。其中：
情况（1），在原来的森林中u是v的父结点的父结点；
情况（2），在森林中u是v的父结点；
情况（3），在森林中u是v的父结点的兄弟；
情况（4），在森林中u与v是兄弟关系。
由此可知，题目中的Ⅰ、Ⅱ是正确的。
7下列关于无向连通图特性的叙述中，正确的是（ ）。
Ⅰ．所有的顶点的度之和为偶数
Ⅱ．边数大于顶点个数减1
Ⅲ．至少有一个顶点的度为1
A．只有Ⅰ
B．只有Ⅱ
C．Ⅰ和Ⅱ
D．Ⅰ和Ⅲ【答案】A【解析】在图中，顶点的度TD（V）之和与边的数目满足关系式：i
其中，n为图的总结点数，e为总边数。因此，Ⅰ项正确。对于Ⅱ、Ⅲ项中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。（1）（2）
8下列叙述中，不符合m阶B树定义要求的是（ ）。
A．根结点最多有m棵子树
B．所有叶结点都在同一层上
C．各结点内关键字均升序或降序排列
D．叶结点之间通过指针链接【答案】D【解析】B树就是指B-树。根据B-树的定义，m阶B-树中每个结点最多有m个分支，因此，根结点最多有m棵子树，A项正确；B-树中所有叶结点都在最底层，位于同一层，B项正确；结点内各关键字互不相等且有序排列，C项正确。但是，所有叶子结点之间通过指针链接，是B＋树的定义，而B-树中没有。因此，D项是错误的。
9已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（ ）。
A．3，5，12，8，28，20，15，22，19
B．3，5，12，19，20，15，22，8，28
C．3，8，12，5，20，15，22，28，19
D．3，12，5，8，28，20，15，22，19【答案】A【解析】在堆中插入或删除一个元素后，将不再满足堆的性质。为了使其成为新堆，在输出堆顶元素后，需要调整剩余元素。具体过程如图（1）～（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。
10若数据元素序列11，12，13，7，8，9，23，4，5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是（ ）。
A．起泡排序
B．插入排序
C．选择排序
D．二路归并排序【答案】B【解析】经过两趟排序后，A项起泡排序的结果是两个最小或最大的元素放到了序列的最终位置；B项插入排序的结果是前三个数有序即可；C项选择排序结果是两个最小的元素在最前面按顺序排好；D项二路归并排序的结果是长度为4的子序列有序，即前4个数排好序，接下来的4个数排好序。显然题目中的元素序列只能是插入排序第二趟排序后的结果，因此，B项正确。
11冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是（ ）。
A．指令操作码的译码结果
B．指令和数据的寻址方式
C．指令周期的不同阶段
D．指令和数据所在的存储单元【答案】C【解析】在冯·诺依曼结构计算机中指令和数据均以二进制形式存放在同一个存储器中，CPU可以根据指令周期的不同阶段来区分是指令还是数据，通常在取指阶段取出的是指令，其他阶段（分析取数阶段、执行阶段）取出的是数据。所以，CPU区分指令和数据的依据是指令周期的不同阶段。
12一个C语言程序在一台32位机器上运行。程序中定义了3个变量x、Y和z，其中x和z为int型，Y为short型。当x＝127，Y＝－9时，执行赋值语句z＝x＋Y后，x、Y和z的值分别是（ ）。
A．x＝0000 007FH，Y＝FFFF FFF9H，z＝0000 0076H
B．x＝0000 007FH，Y＝FFFF FFF9H，z＝FFFF 0076H
C．x＝0000 007FH，Y＝FFFF FFF7H，z＝FFFF 0076H
D．x＝0000 007FH，Y＝FFFF FFF7H，z＝0000 0076H【答案】D【解析】当两个不同长度的数据，要想通过算术运算得到正确的结果，必须将短字长数据转换成长字长数据，这被称为“符号扩展”。例如，x和z为int型，数据长32位，Y为short型，数据长16位，因此首先应将y转换成32位的数据，然后再进行加法运算。运算采用补码的形式，而x的补码是0000 007FH，Y的补码是FFFF FFF7H，所以x＋Y＝0000 0076H。
13浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分75别为5位和7位（均含2位符号位）。若有两个数X＝2×29/32，Y＝2×5/8，则用浮点加法计算X＋Y的最终结果是（ ）。
A．0011 1110 0010
B．0011 1010 0010
C．0100 0001 0001
D．发生溢出【答案】D【解析】浮点数加、减运算一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤，难点在对阶、规格化、判溢出这三步。X和Ｙ的阶码不同，所以应该先对阶，对阶原则为：小阶向大阶看齐。因此将Y7对阶后得到：Y＝2×5/32，然后将尾数相加，得到尾数之和为：34/32。因为这是两个同号数相加，尾数大于1，则需要右规，阶码加1。由于阶码的位数为5位，且含两位符号位，即阶码的表示范围在－8～＋7之间。而阶码本身等于7，再加1就等于8。因此，最终结果发生溢出。
14某计算机的Cache共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32字节，按字节编址。主存129号单元所在主存块应装入到的Cache组号是（ ）。
A．0
B．2
C．4
D．6【答案】C【解析】首先根据主存地址计算所在的主存块号，然后根据组相联映射的映射关系K＝I mod Q （K代表Cache的组号，I代表主存的块号，Q代表Cache的组数）来计算Cache的组号。由于每个主存块大小为32字节，按字节编址，那么主存129号单元所在的主存块号是4，Cache共有16块，采用2路组相联映射方式（即每组2块），故Cache有8组，按照上面的公式可以计算得到Cache的组号＝4 mod 8＝4。
15某计算机主存容量为64 KB，其中ROM区为4 KB，其余为RAM区，按字节编址。现要用2 K×8位的ROM芯片和4 K×4位的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和RAM芯片数分别是（ ）。
A．1、15
B．2、15
C．1、30
D．2、30【答案】D【解析】主存储器包括RAM和ROM两部分，由于ROM区为4KB，则RAM区为60KB。存储容量的扩展方法有字扩展、位扩展、字和位同时扩展三种。选用2K×8位的ROM芯片，只需采用2片芯片进行字扩展便可得到4KB的ROM区；选用4K×4位的RAM芯片，需采用（60）/4*2片芯片进行字和位同时扩展便可得60KB的RAM区。
16某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第1字节为操作码字段，第2字节为相对位移量字段。假定取指令时，每取一个字节PC自动加1。若某转移指令所在主存地址为2000H，相对位移量字段的内容为06H，则该转移指令成功转移后的目标地址是（ ）。
A．2006H
B．2007H
C．2008H
D．2009H【答案】C【解析】相对寻址方式的有效地址EA＝（PC）＋D，其中PC为程序计数器，D为相对偏移量。主存按字节编址，取指令时，每取一个字节PC值自动加1。由于转移指令由两个字节组成，取出这条转移指令之后的PC值自动加2，为2002H，故转移的目标地址为2002H＋06H＝2008H。
17下列关于RISC的叙述中，错误的是（ ）。
A．RISC普遍采用微程序控制器
B．RISC大多数指令在一个时钟周期内完成
C．RISC的内部通用寄存器数量相对CISC多
D．RISC的指令数、寻址方式和指令格式种类相对CISC少【答案】A【解析】B项、C项、D项都是RISC的特点之一，所以它们都是正确的，只有A项是CISC的特点，因为RISC的速度快，所以普遍采用硬布线控制器，而非微程序控制器。
18某计算机的指令流水线由4个功能段组成，指令流经各功能段的时间（忽略各功能段之间的缓存时间）分别为90ns、80ns、70ns和60ns，则该计算机的CPU时钟周期至少是（ ）。
A．90ns
B．80ns
C．70ns
D．60ns【答案】A【解析】对于各功能段执行时间不同的指令流水线，计算机的CPU时钟周期应当以最长的功能段执行时间为准。
19相对于微程序控制器，硬布线控制器的特点是（ ）。
A．指令执行速度慢，指令功能的修改和扩展容易
B．指令执行速度慢，指令功能的修改和扩展难
C．指令执行速度快，指令功能的修改和扩展容易
D．指令执行速度快，指令功能的修改和扩展难【答案】D【解析】在同样的半导体工艺条件下，硬布线（组合逻辑）控制器的速度比微程序控制器的速度快。这是因为硬布线控制器的速度主要取决于逻辑电路的延迟，而微程序控制器增加了一级控制存储器，执行的每条微指令都要从控制存储器中读取，影响了速度。由于硬布线控制器一旦设计完成就很难改变，所以指令功能的修改和扩展难。因此，硬布线控制器的特点是指令执行速度快，指令功能的修改和扩展难。
20假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，总线时钟频率为10MHz，则总线带宽是（ ）。
A．10MB/s
B．20MB/s
C．40MB/s
D．80MB/s【答案】B【解析】因为一个总线周期占用2个时钟周期，完成一个32位数据的传送。总线时钟频率为10MHz，时钟周期为0.1μs，总线周期占用2个时钟周期，为0.2μs。一个总线周期中并行传输4字节信息，则总线带宽是4B÷0.2μs ＝20MB/s。
21假设某计算机的存储系统由Cache和主存组成。某程序执行过程中访存1000次，其中访问Cache缺失（未命中）50次，则Cache的命中率是（ ）。
A．5%
B．9.5%
C．50%
D．95%【答案】D【解析】Cache的命中率H＝N/（N＋N）,其中N为访问Cache的次1121数，N为访存主存的次数，程序总访存次数为N＋N，程序访存次212数减去失效次数就是访问Cache的次数N。所以根据公式可得：H1，＝（1000－50）/1000＝95%。
22下列选项中，能引起外部中断的事件是（ ）。
A．键盘输入
B．除数为0
C．浮点运算下溢
D．访存缺页【答案】A【解析】所谓外部中断是指由外部事件引起的中断，在这4个选项中，只有键盘输入是真正由外部事件引起的中断。
23单处理机系统中，可并行的是（ ）。
Ⅰ．进程与进程
Ⅱ．处理机与设备
Ⅲ．处理机与通道
Ⅳ．设备与设备
A．Ⅰ、Ⅱ和Ⅲ
B．Ⅰ、Ⅱ和Ⅳ
C．Ⅰ、Ⅲ和Ⅳ
D．Ⅱ、Ⅲ和Ⅳ【答案】D【解析】注意区分并发和并行。在单处理机系统中，进程只能并发。微观上同一时刻占用处理机的进程只有一个，因此，进程之间不是并行的。通道是独立于CPU控制的输入/输出的设备，处理机与通道两者是可以并行。显然，设备和设备之间也是可以并行的。
24下列进程调度算法中，综合考虑进程等待时间和执行时间的是（ ）。
A．时间片轮转调度算法
B．短进程优先调度算法
C．先来先服务调度算法
D．高响应比优先调度算法【答案】D【解析】时间片轮转法和先来先服务算法都是公平的方法，并未考虑进程等待时间和执行时间，而短进程优先考虑的是进程执行时间。最高响应比优先调度算法是最先执行响应比最高的进程（响应比＝1＋等待时间/估计运行时间）。该算法综合了先来先服务（FCFS）和短作业优先（SJF）算法，FCFS只考虑每个作业的等待时间，而未考虑执行时间的长短。SJF只考虑执行时间的长短，而未考虑等待时间的长短，HRRN算法则同时考虑执行时间和等待时间。
25某计算机系统中有8台打印机，由K个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K最小值是（ ）。
A．2
B．3
C．4
D．5【答案】C【解析】死锁的抽屉原理一般描述是：将5个苹果放进4个抽屉，那么，必然有1个抽屉中至少有2个苹果。计算机系统的资源分配充分体现了这一原理。考察进程运行的特点，只要有一个进程能够运行，则运行结束后必然会归还资源，其余的进程也就会得到满足从而可以执行（这里考虑的资源主要是可重用的资源，不可重用的资源会消失，就不可用上述方法分析）。所以最少需要4个进程竞争使用，每个进程占用2台打印机，此时会产生死锁。
26分区分配内存管理方式的主要保护措施是（ ）。
A．界地址保护
B．程序代码保护
C．数据保护
D．栈保护【答案】A【解析】对于连续分配算法，无论固定分区或动态分区方法，程序都必须全部调入内存，不同的进程放于不同的内存块中，相互之间不可越界，因此需要进行界地址保护。通常的界地址保护方法采用软硬件结合的方法。考生要注意本题与虚拟存储方法的区别。
27一个分段存储管理系统中，地址长度为32位，其中段号占8位，则最大段长是（ ）。8
A．2字节16
B．2字节24
C．2字节32
D．2字节【答案】C【解析】段内位移的最大值就是最大段长。段号长度占了8位，剩下2432－8＝24位是段内位移空间，因此最大段长为2B。
28下列文件物理结构中，适合随机访问且易于文件扩展的是（ ）。
A．连续结构
B．索引结构
C．链式结构且磁盘块定长
D．链式结构且磁盘块变长【答案】B【解析】连续结构的优点是结构简单，缺点是不易于文件扩展，不易随机访问。链式结构的优点是文件易于扩展，缺点是不易随机访问。索引结构的优点是具有链式结构的优点并克服了它的缺点，可随机存取，易于文件扩展。
29假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求，序列为35，45，12，68，110，180，170，195，采用SCAN调度（电梯调度）算法得到的磁道访问序列是（ ）。
A．110，170，180，195，68，45，35，12
B．110，68，45，35，12，170，180，195
C．110，170，180，195，12，35，45，68
D．12，31，45，68，110，170，180，195【答案】A【解析】SCAN算法类似电梯工作原理，即朝一个固定方向前进，经过的磁道有访问请求则马上服务，直至到达一端顶点，再掉头往回移动以服务经过的磁道，并这样在两端之间往返。因此，当磁头从105道向序号增加的方向移动时，便会服务所有大于105的磁道号（从小到大的顺序）；往回返时又会按照从大到小的顺序进行服务。注意与循环扫描算法的区别，所以SCAN算法的访问序列是：110，170，180，195，68，45，35，12。
30文件系统中，文件访问控制信息存储的合理位置是（ ）。
A．文件控制块
B．文件分配表
C．用户口令表
D．系统注册表【答案】A【解析】文件控制块是文件存在的标志，文件的相关信息（基本信息、存取控制信息以及使用信息）都存储在文件控制块中，系统对文件的管理全是依靠文件控制块里的信息。
31设文件F1的当前引用计数值为1，先建立F1的符号链接（软链接）文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的引用计数值分别是（ ）。
A．0、1
B．1、1
C．1、2
D．2、1【答案】B【解析】为了使文件实现共享，通常在使用该形式文件系统的文件索引节点中设置一个链接计数字段，用来表示链接到本文件的用户目录项的数目（引用计数值），这是共享的一种方法。当新文件建立时，一般默认引用计数值为1。硬链接可以看作是已存在文件的另一个名字，新文件和被链接文件指向同一个节点，引用计数值加1。当删除被链接文件时，只是把引用计数值减1，直到引用计数值为0时，才能真正删除文件。软链接又叫符号链接，在新文件中只包含了被链接文件的路径名，新文件和被链接文件指向不同的节点。建立软链接文件时，文件的引用计数值不会增加。在这种方式下，当被链接文件删除时，新文件仍然是存在的，只不过是不能通过新文件的路径访问被链接文件而已。因此，在本题中，当建立F2时，F1和F2的引用计数值都为1。当再建立F3时，F1和F3的引用计数值就都变成了2。当后来删除F1时，F3的引用计数值为2－1＝1。F2的引用计数值仍然保持不变，所以F2和F3的引用计数值分别是：1，1。
32程序员利用系统调用打开I/O设备时，通常使用的设备标识是（ ）。
A．逻辑设备名
B．物理设备名
C．主设备号
D．从设备号【答案】A【解析】设备管理具有设备独立性的特点，操作系统以系统调用方式提供给应用程序使用逻辑设备名来请求使用某类设备时，调用中使用的是逻辑设备名，例如LPT1或COM1等。而操作系统内部管理设备使用的是设备编号。
33在OSI参考模型中，自下而上第一个提供端到端服务的层次是（ ）。
A．数据链路层
B．传输层
C．会话层
D．应用层【答案】B【解析】题目中指明了这一层能够实现端到端传输，也就是端系统到端系统的传输，数据链路层主要负责传输路径上相邻结点间的数据交付，这些结点包括了交换机和路由器等数据通信设备，这些设备不能被称为端系统，因此数据链路层不满足题意。题目中指明了这一层能够实现传输，会话层只是在两个应用进程之间建立会话而已，应用层只是提供应用进程之间通信的规范，都不涉及传输。所以本题答案应该是B项。在OSI模型中网络层提供的是主机到主机的通信服务。
34在无噪声情况下，若某通信链路的带宽为3kHz，采用4个相位，每个相位具有4种振幅的QAM调制技术，则该通信链路的最大数据传输速率是（ ）。
A．12 kbps
B．24 kbps
C．48 kbps
D．96 kbps【答案】B【解析】首先要根据信道有无噪声来确定是否采用奈奎斯特定理。解题难点在于离散数值的确定，先确定调制技术的码元数，此处为4个相位乘以4种振幅，共16种，即该通信链路的最大数据传输速率＝2×3×log 2（4×4）＝6×4＝24kbps。
35数据链路层采用后退N帧（GBN）协议，发送方已经发送了编号为0～7的帧。当计时器超时，若发送方只收到0、2、3号帧的确认，则发送方需要重发的帧数是（ ）。
A．2
B．3
C．4
D．5【答案】C【解析】后退N帧协议，即GO-BACK—N策略的基本原理是，当接收方检测出失序的信息帧后，要求发送方重发最后一个正确接收的信息帧之后的所有未被确认的帧；或者当发送方发送了N个帧后，若发现该N帧的前一个帧在计时器超时后仍未返回其确认信息，则该帧被判为出错或丢失，此时发送方就不得不重新发送出错帧及其后的N帧。本题收到3号帧的确认，说明0，1，2，3号帧已经收到，丢失的是4，5，6，7号帧，共4帧。因此答案为C项。
36以太网交换机进行转发决策时使用的PDU地址是（ ）。
A．目的物理地址
B．目的IP地址
C．源物理地址
D．源IP地址【答案】A【解析】交换机会监测发送到每个端口的数据帧，通过数据帧中的有关信息（源结点的MAC地址、目的结点的MAC地址），就会得到与每个端口所连接结点的MAC地址，并在交换机的内部建立一个“端口-MAC地址”映射表。建立映射表后，当某个端口接收到数据帧后，交换机会读取出该帧中的目的结点的MAC地址，并通过“端口-MAC地址”的对应关系，迅速将数据帧转发到相应的端口，注意这里的交换机工作在数据链路层，因此关于IP地址的选项是不对的，因此答案为A。
37在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps，电缆中的信号传播速度是200000km/s。若最小数据帧长度减少800bit，则最远的两个站点之间的距离至少需要（ ）。
A．增加160m
B．增加80m
C．减少160m
D．减少80m【答案】D【解析】以太网采用CSMA/CD访问协议，在发送的同时要进行冲突检测，这就要求在能检测出冲突的最大时间内数据包不能够发送完毕，否则冲突检测不能有效地工作。所以，当发送的数据包太短时必须进行填充。最小帧长度＝碰撞窗口大小×报文发送速率，本题最小数据帧长度减少800b，那么碰撞的窗口也要减少，因此距离也要减少，89从而（800×2×10）/（1×10）＝160m，由于时间延时存在两倍的关系，因此减少的距离为80m。
38主机甲和主机乙间已建立一个TCP连接，主机甲向主机乙发送了两个连续的TCP段，分别包含300字节和500字节的有效载荷，第一个段的序列号为200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是（ ）。
A．500
B．700
C．800
D．1000【答案】D【解析】TCP使用滑动窗口流控协议，窗口大小的单位是字节，本题中分别包含300字节和500字节的有效载荷，第一个段的序列号为200，那么确认序列号为200＋300＋500＝1000。
39一个TCP连接总是以1KB的最大段发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT（往返时间）时间内的TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定应答时，拥塞窗口大小是（ ）。
A．7KB
B．8KB
C．9KB
D．16KB【答案】C【解析】回顾TCP流量控制和拥塞控制（慢启动）的知识点，从第一个MSS开始，每次发送成功，拥塞窗口值翻倍，四次以后，应该为16，但是由于拥塞阈值变为16/2＝8，故三次成功后为8，以后为线性增长，故为8＋1＝9，答案为C。
40FTP客户和服务器间传递FTP命令时，使用的连接是（ ）。
A．建立在TCP之上的控制连接
B．建立在TCP之上的数据连接
C．建立在UDP之上的控制连接
D．建立在UDP之上的数据连接【答案】A【解析】对于FTP，为了保证可靠性，选择TCP。FTP应用需要建立两条TCP连接：一条为控制连接，另一条为数据连接。FTP服务器打开21号端口，被动的等待客户的连接建立请求。客户则以主动方式与服务器建立控制连接，客户通过控制连接将命令传给服务器，而服务器则通过控制连接将应答传给客户，命令和响应都是以NVTASCII形式表示的。
二、综合应用题：41～47小题。共70分。
41（10分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
①该最短路径初始时仅包含初始顶点，令当前顶点为初始顶点；
②选择离υ最近且尚未在最短路径中的顶点ν，加入到最短路径中，修改当前顶点υ＝ν；
③重复步骤②，直到υ是目标顶点时为止。请问上述方法能否求得最短路径？若该方法可行，请证明之；否则请举例说明。
解：题目中方法不一定能（或不能）求得最短路径。举例说明：
图（a）中，假设初始顶点1到目标顶点4之间有一条边，权值x＝2。显然图（a）中这顶点1和顶点4之间的最短路径长度为2。若按照题目中给定的方法找到的路径为初始顶点1经过中间结点2、3到目标顶点4，即初始顶点1—2—3一目标顶点4，所经过的边的权值分别为y＝1、y＝1、y＝1。显然，y＋y＋y＝3大于2。因此按照题目123123中给定的方法所求得的路径并不是这两个顶点之间的最短路径。
图（b）中，假设初始顶点为1、目标顶点为4，欲求从顶点1到顶点4之间的最短路径。显然，按照题目中给定的方法无法求出顶点1到顶点4的路径，而事实上顶点1到顶点4的最短路径为1到4。
42（15分）已知一个带有表头结点的单链表，结点结构为，假设该链表只给出了头指针1ist。在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第k个位置上的结点（k为正整数）。若查找成功，算法输出该结点的data域的值，并返回1；否则，只返回0。要求：（1）描述算法的基本设计思想；（2）描述算法的详细实现步骤；（3）根据设计思想和实现步骤，采用程序设计语言描述算法（使用C或C＋＋或JAVA语言实现），关键之处请给出简要注释。
解：（1）算法的基本设计思想定义两个指针变量p和q，初始时均指向头结点的下一个结点。p指针沿链表移动；当p指针移动到第k个结点时，q指针开始与p指针同步移动；当p指针移动到链表最后一个结点时，因为p和q相隔k，故q指针所指元素为倒数第k个结点。以上过程对链表仅进行一遍扫描。（2）算法的详细实现步骤
①count＝0，p和q指向链表表头结点的下一个结点；
②若p为空，转⑤；，
③若count等于k，则q指向下一个结点；否则，count＝count＋1；
④p指向下一个结点，转步骤②；
⑤若count等于k，则查找成功，输出该结点的data域的值，返回1；否则，查找失败，返回0；
⑥算法结束。（3）算法实现
43（8分）某计算机的CPU主频为500MHz，CPI为5（即执行每条指令平均需要5个时钟周期）。假定某外设的数据传输率为0.5 MB/s，采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。请回答下列问题，要求给出计算过程。（1）在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少？（2）当该外设的数据传输率达到5MB/s时，改用DMA方式传送数据。假定每次DMA传送块大小为5000B，且DMA预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O时间占整个CPU时间的百分比是多少？（假设DMA与CPU之间没有访存冲突）
解：（1）已知主频为500MHz，则时钟周期＝1÷500MHz ＝2ns，因为CPI＝5，所以每条指令平均5×2＝10ns。又已知每中断一次传送32位（4个字节），数据传输率为0.5MB/s，所以传送时间＝4÷O.5MB/s＝8μs。CPU用于该外设I/O共需20条指令（中断服务程序包括18条指令＋其他开销折合2条指令），花费时间＝20×10＝200ns。CPU用于该外设I/O的时间占整个CPU时间的百分比＝200/8000×100%＝0.025×100%＝2.5%。（2）改用DMA方式传送数据，数据传输率为5MB/s，传送5000B的时间＝5000B÷5MB/s＝1ms。预处理和后处理的总开销时间＝500×2ns＝1μs。CPU用于该外设I/O时间占整个CPU时间的百分比＝预处理和后处理的总开销时间÷传送数据的时间＝1/1000×100%＝0.001×100%＝0.1%。
44（13分）某计算机字长16位，采用16位定长指令字结构，部分数据通路结构如下图所示，图中所有控制信号为1时表示有效，为0时表示无效，例如控制信号MDRinE为1表示允许数据从DB打入MDR，MDRin为1表示允许数据从内总线打入MDR。假设MAR的输出一直处于使能状态。加法指令“ADD（R1），R0”的功能为（R0）＋（（R1））一（R1），即将R0中的数据与R1的内容所指主存单元的数据相加，并将结果送入R1的内容所指主存单元中保存。
下表给出了上述指令取指和译码阶段每个节拍（时钟周期）的功能和有效控制信号，请按表中描述方式用表格列出指令执行阶段每个节拍的功能和有效控制信号。
解：执行阶段每个节拍（时钟周期）的功能和有效控制信号见下表。
45（7分）三个进程P1、P2，P3互斥使用一个包含N（N＞0）个单元的缓冲区。P1每次用produce（）生成一个正整数并用put（）送入缓冲区某一空单元中；P2每次用getodd（）从该缓冲区中取出一个奇数并用countodd（）统计奇数个数；P3每次用geteven（）从该缓冲区中取出一个偶数并用counteven（）统计偶数个数。请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义。要求用伪代码描述。
解：定义信号量S1控制P1与P2之间的同步；S2控制P1与P3之间的同步；empty控制生产者与消费者之间的同步；mutex控制进程间互斥使用缓冲区，程序如下：
46（8分）请求分页管理系统中，假设某进程的页表内容如下表所示：
页面大小为4KB，一次内存的访问时间是100ns，一次快表（TLB）的访问时间是10ns，处理一次缺页的平均时间为108ns（已含更新TLB和页表的时间），进程的驻留集大小固定为2，采用最近最少使用置换算法（LRU）和局部淘汰策略。假设①TLB初始为空；②地址转换时先访问TLB，若TLB未命中，再访问页表（忽略访问页表之后的TLB更新时间）；③有效位为0表示页面不在内存，产生缺页中断，缺页中断处理后，返回到产生缺页中断的指令处重新执行。设有虚地址访问序列2362H、1565H、25A5H，请问：（1）依次访问上述三个虚地址，各需多少时间？给出计算过程。（2）基于上述访问序列，虚地址1565H的物理地址是多少？请说明理由。8
解：（1）210ns；10ns；110ns。
页面大小为4KB，因此，虚地址的低12位是页内偏移，其余高位是页号。
访问虚地址2362H，虚页号为2，页内偏移362H。查找TLB，TLB初始为空，未命中，耗时10ns；访问页表，2号页面所在页框号为254H，耗时100ns；计算得到的物理地址254362H，访问内存，耗时100ns。因此，总共用时10＋100＋100＝210ns。
访问虚地址1565H，虚页号为1，页内偏移565H。查找TLB，未命中，耗时10ns；访问页表，有效位是0，未命中，耗时100ns；产生缺页中断，进行缺页中断处理，耗时108ns；采用LRU置换算法，虚页1装入页帧号101H，缺页中断处理完后，再次访问页表，命中，耗时100ns；计算得到物理地址101565H，再次访问内存，耗时100ns。88因此，总共用时10＋100＋10＋100≈10ns。
访问虚地址25A5H，虚页号为2，页内偏移5A5H。查找TLB，命中，耗时10ns；虚页2对应的页帧为254H，因此计算得物理地址为2545A5H，访问内存，耗时100ns。因此，总共用时10＋100＝110ns。（2）当访问虚地址1565H时，产生缺页中断，合法驻留集为2，必须从页表中淘汰一个页面，根据题目的置换算法，应淘汰0号页面，因此1565H的对应的页框号为101H，故可知虚地址1565H的物理地址为101565H。
47（9分）某公司网络拓扑图如下图所示，路由器R1通过接口E1、E2分别连接局域网1、局域网2，通过接口10连接路由器R2，并通过路由器R2连接域名服务器与互联网。R1的10接口的IP地址是202.118.2.1；R2的10接口的IP地址是202.118.2.2，11接口的IP地址是130.11.120.1，E0接口的IP地址是202.118.3.1；域名服务器的IP地址是202.118.3.2。
R1和R2的路由表结构为：（1）将IP地址空间202.118.1.0/24划分为两个子网，分配给局域网1、局域网2，每个局域网分配的地址数不少于120个，请给出子网划分结果。说明理由或给出必要的计算过程。（2）请给出R1的路由表，使其明确包括到局域网1的路由、局域网2的路由、域名服务器的主机路由和互联网的路由。（3）请采用路由聚合技术，给出R2到局域网1和局域网2的路由。
解：（1）把IP地址空间202.118.1.0/24划分为2个等长的字网。两个局域网的IP地址数都不能少于120个，所以划分子网后，IP中主机所占的位数不能少于7位，要划分为两个子网又子少需要1位。可以将IP地址空间202.118.1.0/24的最后一个字节，划分为1位和7位两个部分，高一位表示子网号，低7位表示主机号，故划分结果为:
①子网1：子网地址为202.118.1.0，子网掩码为255.255.255.128（或者子网1：202.118.1.0/25）。
②子网2：子网地址为202.118.1.128，子网掩码为255.255.255.128（或者子网1：202.118.1.128/25）。地址分配方案：子网1分配给局域网1，子网2分配给局域网2；或子网1分配给局域网72，子网2分配给局域网1。每个子网可分配的地址数为2－2＝126大于120满足题目要求。（2）·填写到局域网1和局域网2的路由。两个局域网的网络地址和掩码在问题（1）已经求出来了，分别为202.118.1.0/25和202.118.1.128/25。则R1路由表应该填入的网络地址为202.118.1.0和202.118.1.128，掩码为255.255.255.128和255.255.255.0。由于两个局域网是分别直接连接到路由器R1的E1口、E2口上的，因此，下一跳地址填写直接路由（Direct）。接口填写E1、E2。
·填写到域名服务器的路由。由于图6给出了域名服务器的IP地址为202.118.3.2，而该地址为主机地址，因此掩码为255.255.255.255。同时，路由器R1要到DNS服务器，就需要通过路由器R2的接口L0才能到达，因此下一跳地址填写L0的IP地址（202.118.2.2）。
·填写互联网路由。本题的实质是编写默认路由，默认路由叫做“0/0”路由，因为路由的IP地址是0.0.0.0，而子网掩码也是0.0.0.0。同时路由器R1连接的网络需要通过路由器R2的L0口才能到达互联网络，因此下一跳地址填写L0的IP为202.118.2.2。
综合以上叙述，所填写的路由表如下表所示：
参考答案一（若子网1分配给局域网1。子网2分配给局域网2）
参考答案二（若子网1分配给局域网2，子网2分配给局域网1）（3） 填写R2到局域网1和局域网2的路由表2。局域网1和局域网2的地址可以聚合为202.118.1.0/24，而R2去往局域网1和局域网2都是同一条路径。因此，路由表里面只需要填写到202.118.1.0/24网络的路由即可，如下表所示：
R2路由表
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【答案】D【解析】4个选项所给序列的进、出栈操作序列分别为：
选项A：Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop
选项B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop
选项C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop
选项D：Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop
按照题目要求，不允许连续三次进行退栈操作，所以选项D所给序列为不可能得到的出栈顺序。
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【答案】C【解析】根据题意，队列两端都可以输入数据元素，但是只能在一端输出数据元素，这种队列为输出受限的双端队列。本题解题方法分别判断每个选项如何入队和出队，从而得出不可能的情况。
假设L代表从左端入队，R代表从右端入队，出队都是从左端L出。四个选项所给序列的进队操作序列分别为：
选项A：aL（或aR），bL，cR，dR，eR
选项B：aL（或aR），bL，cR，dL，eR
选项C：不可能出现
选项D：aL（或aR），bL，cL，dR，eL
3下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。【答案】D【解析】线索二叉树利用二叉链表的空链域来存放结点的前驱和后继信息，解题思路较简单。题中所给二叉树的后序序列为dbca。结点d无前驱和左子树，左链域空，无右子树，右链域指向其后继结点b；结点b无左子树，左链域指向其前驱结点d；结点c无左子树，左链域指向其前驱结点b，无右子树，右链域指向其后继结点a。所以正确选项为D。
4在下图所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（ ）。
A．13、48
B．24、48
C．24、53
D．24、90【答案】C【解析】题目中，插入48以后，树根结点的平衡因子由－1变为－2，失去平衡。这属于RL（先右后左）型平衡旋转，需做两次（先右旋后左旋转）旋转操作。过程如下图所示：
显然，在调整后的新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是24，53。
5在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则树T的叶结点个数是（ ）。
A．41
B．82
C．113
D．122【答案】B【解析】根据二叉树的性质3的推广公式：N＝l＋N＋2N＋…＋（m023－1）N可直接在将数据带入公式，即N＝l＋N＋2N＋3N4＝l＋1×m0231＋2×10＋3×20＝82。树T的叶子结点的个数是82。如果考生不能熟练掌握二叉树的性质3的推广公式，得到本题的正确答案将费时费力。因此，需要熟练掌握二叉树的性质及推广。
6对n（n≥2）个权值均不相同的字符构成哈夫曼树。下列关于该哈夫曼树的叙述中，错误的是（ ）。
A．该树一定是一棵完全二叉树
B．树中一定没有度为1的结点
C．树中两个权值最小的结点一定是兄弟结点
D．树中任一非叶结点的权值一定不小于下一层任一结点的权值【答案】A【解析】哈夫曼树为带权路径长度最小的二叉树，但不一定是完全二叉树，选项A错误；哈夫曼树中没有度为1的结点，选项B正确；构造哈夫曼树时，最先选取两个权值最小的结点作为左右子树构造一棵新的二叉树，C正确；哈夫曼树中任一非叶结点P的权值为其左右子树根结点权值之和，其权值不小于其左右子树根结点的权值，在与结点P的左右子树根结点处于同一层的结点中，若存在权值大于结点P权值的结点Q，那么结点Q与其兄弟结点中权值较小的一个应该与结点P作为左右子树构造新的二叉树，由此可知，哈夫曼树中任一非叶结点的权值一定不小于下一层任一结点的权值。
7若无向图G＝（V，E）中含7个顶点，则保证图G在任何情况下都是连通的，则需要的边数最少是（ ）。
A．6
B．15
C．16
D．21【答案】C【解析】要保证无向图G在任何情况下都是连通的，即任意变动图G中的边，G始终保持连通。首先需要图G的任意6个结点构成完全连通子图G，需n（n－l）/2＝6×（6—1）/2＝15条边，然后再添加一条边1将第7个结点与G连接起来，共需l6条边。本题非常容易错误地选择1选项A，主要原因是对“保证图G在任何情况下都是连通的”的理解，分析选项A，在图G中，具有7个顶点6条边并不能保证其一定是连通图，即有n－1条边的图不一定是连通图。分析选项D，图G有7个顶点21条边，那么图G一定是无向完全图，无向完全图能保证其在任何情况下都是连通的，但是这不符合题目中所需边数最少的要求。
8对下图进行拓扑排序，可以得到不同的拓扑序列的个数是（ ）。
A．4
B．3
试读结束[说明：试读内容隐藏了图片]