2008年12月考研的408试题，是408综合科目的第一年，本篇为小题部分，大题见下一篇。
声明：
- ℍ和𝔹分别表示十六进制和二进制数，其余为十进制数。
- exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
- 乘除号用最朴素的×÷，分数用/，⌊⌋⌈⌉分别是向上向下取整。
- 英文字母变量用的是手写体，题干某些描述较真题有修改。
一、单项选择：
第1～40小题，每小题2分，共80分。
DataStructure
№1✍️ 为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机依次从缓冲区中取出数据。该缓冲区的逻辑结构应该是（🔠）？
【B】先入先出，符合队列的特点。
№2✍️ 设堆栈𝐒和队列𝐐的初始状态均为空，元素a,b,c,d,e,f,g依次进入堆栈𝐒。若每个元素出栈后立即进入队列𝐐，且7个元素出队的顺序是b,d,c,f,e,a,g，则堆栈𝐒的容量至少是（🔠）？
【C】出队顺序即出栈顺序，情况应是这样，a入栈，b入栈，b出栈，c入栈，d入栈，｛栈中元素3个｝d出栈，c出栈，e入栈，f入栈，f出栈，e出栈，｛栈中元素3个｝，a出栈，g入栈，g出栈。
№3✍️ 给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列是3,1,7,5,6,2,4，则其遍历方式是（🔠）？
【D】{3},1,{7,5,6,2,4}可确定是“右根左”的遍历顺序。
№4✍️ 下列二叉排序树中，满足平衡二叉树定义的是（🔠）？
【B】平衡二叉树定义中，每个结点的左右子树高度相差最多为1，只有选项B符合。
№5✍️ 一棵完全二叉树，根为第1层，已知其第6层有8个叶结点，则该完全二叉树的结点个数最多是（🔠）？
【C】完全二叉树只在最后1层和倒数第2层有叶结点，前5层可以确定共1+2+4+8+16＝31个结点，该完全二叉树结点数最少31+8＝39个，最多的情况是第6层有24个度为2，8个度为0的结点，共31+32+24×2＝111个。
№6✍️ 将普通树转换为对应的二叉树，若在二叉树中，结点𝑢是结点𝑣的父结点的父结点，则在原来的树中，𝑢和𝑣的关系可能是（🔠）？
i꙳父子关系 ii꙳兄弟关系 iii'𝑢的父结点与𝑣的父结点是兄弟关系
【B】普通树转二叉树的规则为〔①每个分支结点只保留第一个孩子；②其余的孩子依次变为左边兄弟的右孩子〕，〔①在转化来的二叉树中左孩子原本是长子；②右孩子原本是次弟〕。森林转二叉树的规则是〔①每棵普通树先转二叉树；②只保留第一棵树的根；③其余的根都变为左边根的右孩子〕。
№7✍️ 下列关于无向连通图特性的叙述中，正确的是（🔠）？
i꙳所有顶点的度之和为偶数 ii꙳边数大于顶点个数减1 iii'至少有一个顶点的度为1
【A】无向图中顶点的度指与该顶点相关的边数，无向图中没有入度和出度的区分；i꙳所有顶点的度之和为边数×2，一定是偶数。ii꙳边数最少的时候就是等于顶点数减1。iii꙳无向完全连通图中，两两顶点之间都有一条边，不存在度为1的顶点。
№8✍️ 下列叙述中，不符合m阶B-树定义要求的是（🔠）？
【D】选项D是B+树定义的要求。
№9✍️ 已知关键字序列5,8,12,19,28,20,15,22是小根堆，插入关键字3，调整后得到的小根堆是（🔠）？
【A】
№10✍️ 若数据元素序列11,12,13,7,8,9,23,4,5是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是下面的（🔠）？
【B】先排除选项AC，冒泡排序和选择排序第二趟都会有2个元素处于最终位置，但该序列中无论升序降序都不存在2个元素处于最终位置上。再说二路归并排序，第一趟排序结束都可以得到若干两两有序的子序列，但该序列中没有。插入排序在第二趟结束后能保证前面3个元素是有序的，该序列符合。
ComputerOrganization
№11✍️ 冯诺依曼计算机中的指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是（🔠）？
【C】取指阶段取出的是指令，执行阶段去取的是数据。
№12✍️ 一个C语言程序在一台32位机器上运行。程序中定义了3个变量𝑥,𝑦,𝑧，其中𝑥和𝑧为int型，𝑦为short型。当𝑥=127,𝑦=-9时，执行赋值语句𝑧=𝑥+𝑦后，𝑥,𝑦,𝑧的值分别是（🔠）？
【D】32位机器上int型占4B，short型占2B，变量的值以补码形式存放，首先可以确定𝑥＝ℍ0000_007F,𝑦＝ℍFFF7，short转为int是符号位扩展，𝑧＝ℍ0000_007F+ℍFFFF_FFF7＝ℍ0000_0076。用十进制也可计算得𝑧＝127-9＝118＝ℍ0000_0076。
№13✍️ 浮点数加减法运算过程一般包括对阶、尾数运算、规格化、舍入、判断溢出等步骤。设浮点数的阶数和尾数均采用补码表示，且位数分别为5位和7位，均含2位的符号位。若有两个数𝑥=exp(7)×29/32,𝑦=exp(5)×5/8，则用浮点加法计算𝑥+𝑦的最终结果二进制是（🔠）？
【D】 ➊对阶，阶数小的向大的看齐，𝑦＝exp(7)×5/32；➋尾数运算，𝑥+𝑦＝exp(7)×34/32；➎判断溢出，阶数非符号只有3位，仅能表示到7，显然exp(7)×34/32已发生溢出。
№14✍️ 某计算机的Cache共有16块，采用2路组相联映射方式。每个主存块大小为32B，按字节编址。主存129号单元所在主存块应装入到的Cache组号是（🔠）？
【C】Cache共8组，每组2块。主存129号单元所在主存块号为⌈129÷32⌉＝4，4％8＝4，因此该主存块应被装入到Cache组号4的任一块中。
№15✍️ 某计算机主存容量为64KB，其中ROM区为4KB，其余为RAM区，按字节编址。现要用2K×8b的ROM芯片和4K×4b的RAM芯片来设计该存储器，则需要上述规格的ROM芯片数和RAM芯片数分别是（🔠）？
【D】ROM区4KB，用ROM芯片设计，需(4K×8b)÷(2K×8b)＝2；RAM区60KB，用RAM芯片设计，需(60K×8b)÷(4K×4b)＝30。
№16✍️ 某计算机字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节PC自动+1。若某转移指令所在主存地址为ℍ2000，相对位移量字段的内容为ℍ06，则该转移指令转移成功后的目标地址是（🔠）？
【C】取完该转移指令后PC＝ℍ2002，再跳转后PC＝ℍ2008。
№17✍️ 下列关于RISC"ReducedInstructionSetComputer"的叙述中，错误的是（🔠）？
【A】概念题，选项BCD都是RISC的特点。RISC“精简指令集计算机”，通常采用硬布线逻辑，每条指令的执行过程是直接由处理器内部的硬件电路完成，很少采用由一系列微指令组成的微程序控制。
№18✍️ 某计算机的指令流水线由四个功能段组成，指令流经各功能段的时间｛忽略各功能段之间的缓存时间｝分别为90ns,80ns,70ns,60ns，则该计算机的CPU时钟周期至少是（🔠）？
【A】简单题。应以执行时间最长的为准。
№19✍️ 相对于微程序控制器，硬布线控制器的特点是（🔠）？
【D】概念题。微程序控制器中，每条指令采用一系列微指令组成，这些微指令序列被预先存储在微程序存储器中，方便在有需要时修改和扩展；硬布线逻辑的每条指令都交由电路实现，比较快，要修改和扩展指令集通常得重新设计处理器的电路。
№20✍️ 假设某系统总线在一个总线周期中并行传输4字节信息，一个总线周期占用2个时钟周期，时钟频率｛真题此处叫总线时钟频率难以理解｝为10MHz，则总线带宽是（🔠）？
【B】由题意可知，时钟周期＝1/10MHz，总线周期＝2×1÷10MHz，总线带宽＝4B×10MHz÷2＝20MB/s。
№21✍️ 假设某计算机的存储系统由Cache和Memory组成，某程序执行过程中需访存1000次，其中访问Cache缺失｛未命中｝50次，则Cache的命中率是（🔠）？
【D】Cache缺失率为50/1000＝5%，命中率就是95%。
№22✍️ 下列选项中，能引起外部中断的事件是（🔠）？
【A】BCD都是来自CPU内部异常的事件，只有选项A是由外部设备引起的。
OperatingSystem
№23✍️ 单处理机系统中，可并行的是（🔠）？
i꙳进程与进程 ii꙳处理机与设备 iii꙳处理机与通道 iii꙳设备与设备
【D】单处理机只有一条指令流水线，显然不能让进程与进程并行。
№24✍️ 下列进程调度算法中，综合考虑进程等待时间和执行时间的是（🔠）？
【D】响应比＝(等待时间+执行时间)÷执行时间。
№25✍️ 某计算机系统中有8台打印机，有𝑘个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的𝑘的最小值是（🔠）？
【C】易错题。根据组合数学中的鸽笼原理，考虑最极端的情况。给𝑘个进程各分配2台打印机，那么只要还有多的打印机就不会死锁，于是𝑘＝8/2＝4时，4个进程各占有2台打印机，都无法被分配到第3台打印机，发生死锁。
№26✍️ 分区分配内存管理方式的主要保护措施是（🔠）？
【A】分区分配内存管理方式中有一个界地址寄存器，用于检查要访问的地址是否越界，错误的地址会引起越界中断。
№27✍️ 一个分段存储管理系统中，按字节编址｛真题中应该漏了这个条件｝，地址长度为32位，其中段号占8位，则最大段长是（🔠）？
【C】段内偏移占32-8＝24位，按字节编址的话1个地址为1字节，最大段长为exp(24)×1B。
№28✍️ 下列文件物理结构中，适合随机访问且易于文件扩展的是（🔠）？
【B】连续结构不易于扩展，链式结构不适合随机访问。索引结构结合了数组和链表的优点。
№29✍️ 假设磁头当前位于第105道，正在向磁道序号增加的方向移动。现有一个磁道访问请求序列为35,45,12,68,110,180,170,195，采用SCAN调度算法得到的磁道访问序列是（🔠）？
【A】SCAN调度算法类似于风扇摇头。先选择磁头当前移动方向且磁头所在磁道最近的请求作为服务对象{110,170,180,195}，到达磁盘边界后改变方向，响应另一端的请求{68,45,35,12}，如此往复。
№30✍️ 文件系统中，文件访问控制信息存储的合理位置是（🔠）？
【A】概念题。文件控制块中通常包含文件的基本信息、访问控制信息、使用信息。
№31✍️ 设文件𝐅𝟷的当前引用计数值为1，先建立𝐅𝟷的软链接文件𝐅𝟸，再建立𝐅𝟷的硬链接文件𝐅𝟹，然后删除𝐅𝟷。此时，𝐅𝟸和𝐅𝟹的文件计数值分别是（🔠）？
【B】易错题。建立软链接时，引用计数值直接复制过来，删除源文件软链接是不可知的，下次通过软链接访问源文件时将由系统提示失效，故𝐅𝟸保留了𝐅𝟷的引用计数值1。建立硬链接时，引用计数值加1，删除源文件时，硬链接的引用计数值减1，当文件的引用计数值减为0时才是真正删除了该文件，𝐅𝟹的引用计数值还是1。
№32✍️ 程序员利用系统调用打开I/O设备时，通常使用的设备标识是（🔠）？
【A】对程序员来说，肯定是使用简单的逻辑设备名，程序执行时由操作系统完成逻辑设备名转实体设备名。
ComputerNetWork
№33✍️ 在OSI参考模型中，自下而上第一个提供端到端服务的层次是（🔠）？
【B】概念题。OSI参考七层模型中，自下而上依次是“物链网输会示用”，传输层提供端到端间的通信。
№34✍️ 在无噪声情况下，若某通信链路的带宽为3KHz，采用4个相位，每个相位具有4中振幅的QAM技术，“正交振幅调制”"QuadratureAmplitudeModulation"，则该通信链路的最大数据传输速率是（🔠）？
【B】题目所给的QAM技术可以为每个信号提供4×4＝16种变化，也就可以携带log(16)＝4个比特的信息。由奈氏准则，信息的最大传输速率为2×3KHz×4bit＝24Kbps。
№35✍️ 数据链路层采用GBN，即后退N帧协议，发送方已发送了编号为0～7的帧。当计时器超时时，若发送方只收到0,2,3号帧的确认，则发送方需要重发的帧数是（🔠）？
【C】后退N帧协议中，接收窗口大小为1，且采用累积确认，收到3号帧的确认就代表0,1,2,3都已被正确接收，需重传4,5,6,7号帧，共4个。未收到1号帧的确认只能说1号帧的确认帧在返回途中丢失，也没有1这个选项，迷惑性不大。
№36✍️ 以太网交换机进行转发决策时使用的PDU地址是（🔠）？
【A】转发往目的主机肯定用的是目的地址，先排除选项CD，交换机工作在数据链路层，只能使用MAC地址。
№37✍️ 在一个采用CSMA/CD协议的网络中，传输介质是一根完整的电缆，传输速率为1Gbps，电缆中的信号传播速度是200,000km/s。若最小帧长度减少800bit，则最远的两个站点之间的距离至少需要（🔠）？
【D】采用CSMA/CD协议的网络中，某台主机帧发送完毕后就不再针对该帧检测碰撞，因此最小帧长要满足发送完之前能检测到来自距离最远站点的碰撞，最小帧长减少最远距离肯定也要减少的，主机最多经过两个距离最远站点的传播时延就可检测到碰撞。最小帧长𝐿｛单位bit｝和最远距离𝐷｛单位m｝之间满足关系：𝐿÷(1×10^9b/s)＝2×𝐷÷(2×10^8m/s)，显然，最远距离需减少80m。
№38✍️ 主机甲与主机乙之间建立一个TCP连接，主机甲向主机乙发送两个连续的TCP段，分别包含300B和500B的有效载荷，第一个段的序列号为200，主机乙正确接收到两个段后，发送给主机甲的确认序列号是（🔠）？
【D】TCP是面向字节流的，四个选项迷惑性不大。确认序号是接收端下一次期望接收到的字节序号，因此主机乙发送给主机甲的确认序列号是200+300+500＝1000。
№39✍️ 一个TCP连接总是以1KB的最大段长发送TCP段，发送方有足够多的数据要发送。当拥塞窗口为16KB时发生了超时，如果接下来的4个RTT时间内TCP段的传输都是成功的，那么当第4个RTT时间内发送的所有TCP段都得到肯定回答时，拥塞窗口大小是（🔠）？
【C】由题意，发送超时时，慢开始门限ssthresh＝8，发送方拥塞窗口cwnd＝1，执行慢开始算法，1→2→4→8，花费3个RTT，而后转为拥塞避免算法，8→9→10→···，第4个RTT结束后，拥塞窗口大小为9KB。
№40✍️ FTP客户端和服务端间传递FTP命令时，使用的连接是（🔠）？
【A】概念题。FTP要保证可靠传输，文件内容不能丢了，须基于TCP。FTP控制连接使用21号端口，用来传递连接请求、传送请求等命令；FTP数据连接使用20号端口，用来传输文件数据。
