2008年12月考研的408试题，网上能找到的最早的408试题，本篇为小题部分，大题见下一篇。
声明：
- 0x和0b分别表示十六进制和二进制数，其余为十进制数。
- exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
- 乘除号用最朴素的×÷，分数用/，参与计算的英文字母变量用手写体。
- {}里的斜体为补充文字，另外对原题一些容易误会的文字做了修改。
- 图片使用亿图图示绘制。
一、单项选择：
第1~40小题，每小题2分，共80分。
DataStructure
「1」、为解决计算机主机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机依次从缓冲区中取出数据。该缓冲区的逻辑结构应该是（）？
【B】先入先出，符合队列的特点。
「2」、设堆栈S和队列Q的初始状态均为空，元素a,b,c,d,e,f,g依次进入堆栈S。若每个元素出栈后立即进入队列Q，且7个元素出队的顺序是b,d,c,f,e,a,g，则堆栈S的容量至少是（）？
【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」、将普通树转换为对应的二叉树，若在二叉树中，结点u是结点v的父结点的父结点，则在原来的树中，u和v的关系可能是（）？
i'父子关系 ii'兄弟关系 iii'u的父结点与v的父结点是兄弟关系
【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个变量x,y,z，其中x和z为int型，y为short型。当x=127,y=-9时，执行赋值语句z=x+y后，x,y,z的值分别是（）？
【D】32位机器上int型占4B，short型占2B，变量的值以补码形式存放，首先可以确定x=0x0000007F,y=0xFFF7，short转为int是符号位扩展，z=0x0000007F+0xFFFFFFF7=0x00000076。用十进制也可计算得z=127-9=118=0x00000076。
「13」、浮点数加减法运算过程一般包括对阶、尾数运算、规格化、舍入和判断溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位，均含2位的符号位。若有两个数X=exp(7)×29/32,Y=exp(5)×5/8，则用浮点加法计算X+Y的最终结果二进制是（）？
【D】①对阶，阶码小的向大的看齐，Y=exp(7)×5/32。②尾数运算，X+Y=exp(7)×34/32。阶码非符号只有3位，仅能表示到7，显然exp(7)×34/32已发生溢出。
「14」、某计算机的Cache共有16块，采用2路组相联映射方式（即每组2块）。每个主存块大小为32B，按字节编址。主存129号单元所在主存块应装入到的Cache组号是（）？
【C】Cache共8组，每组2块。主存129号单元所在主存块号为129/32=4，4%8=4，因此该主存块应被装入到Cache第4组2个块的任一块中。
「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。若某转移指令所在主存地址为0x2000，相对位移量字段的内容为0x06，则该转移指令转移成功后的目标地址是（）？
【C】取完该转移指令后PC=0x2002，再跳转后PC=0x2008。
「17」、下列关于RISC的叙述中，错误的是（）？
【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'处理机与通道 iv'设备与设备
【D】单处理机只有一条指令流水线，显然不能让进程与进程并行。
「24」、下列进程调度算法中，综合考虑进程等待时间和执行时间的是（）？
【D】响应比=(等待时间+执行时间)÷执行时间。
「25」、某计算机系统中有8台打印机，有k个进程竞争使用，每个进程最多需要3台打印机。该系统可能会发生死锁的K的最小值是（）？
【C】易错题。根据组合数学中的鸽笼原理，考虑最极端的情况。给k个进程各分配2台打印机，那么只要还有多的打印机就不会死锁，于是k=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」、设文件F1的当前引用计数值为1，先建立F1的软链接文件F2，再建立F1的硬链接文件F3，然后删除F1。此时，F2和F3的文件计数值分别是（）？
【B】易错题。建立软链接时，引用计数值直接复制过来，删除源文件软链接是不可知的，下次通过软链接访问源文件时将由系统提示失效，故F2保留了F1的引用计数值1。建立硬链接时，引用计数值加1，删除源文件时，硬链接的引用计数值减1，当文件的引用计数值减为0时才是真正删除了该文件，F3的引用计数值还是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号端口，用来传输文件数据。
