2009年12月考研的408试题，本篇为小题部分，大题见下一篇。
声明：
- 0x和0b分别表示十六进制和二进制数，其余为十进制数。
- exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
- 乘除号用最朴素的×÷，分数用/，参与计算的英文字母变量用手写体。
- {}里的斜体为补充文字，另外对原题一些容易误会的文字做了修改。
- 图片使用亿图图示绘制。
一、单项选择：
第1~40小题，每小题2分，共80分。
DataStructure
「1」、若元素a,b,c,d,e,f依次进栈，允许进栈退栈操作交替进行，但不允许连续三次退栈操作，则不可能得到的出栈序列是（）？
【D】D中子序列af表明bcde全在栈中，接下来只能进行四次退栈操作。
「2」、某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素a,b,c,d,e依次入此队列再出队，则不可能得到的出队序列是（）？
【C】仅允许一端出队那么可以只考虑5个元素的入队方式，不可能把c塞在ab中间。
「3」、下列线索二叉树中，虚线表示线索，符合后序树定义的是（）？
【D】选项中所给二叉树的后序序列均是dbca。d左指针空-连前驱空，d右指针空-连后继结点b；b左指针空-连前驱结点d，b右指针-有右孩子；c左指针空-连前驱结点b，c右指针空-连后继结点a；a左指针-有左孩子，a右指针-有右孩子。
「4」、在右图所示的平衡二叉树中，插入关键字48后得到一棵新的平衡二叉树。在新平衡二叉树中，关键字37所在结点的左右孩子中保存的关键字分别是（）？
【C】平衡二叉树也叫AVLT，是任一结点左右子树高度差不超过1的二叉搜索树。当插入关键字48为关键字37的右孩子时，会引起关键字24的不平衡，需先右旋再左旋。
「5」、在一棵度为4的树T中，若有20个度为4的结点，10个度为3的结点，1个度为2的结点，10个度为1的结点，则T的叶结点个数是（）？
【B】设叶结点个数为𝓀，由树中全部结点个数的两种计算方式可得，20+10+1+10+𝓀=1+20×4+10×3+1×2+10×1，𝓀=82。
「6」、对n{n是大于1的正整数}个权值均不同的字符构造成哈夫曼树。下列关于哈夫曼树的叙述中，错误的是（）？
【A】概念题。哈夫曼树是带权路径最小的二叉树，大多情况下不是完全二叉树。
「7」、若无向图G=(V,E)中含有7个顶点，要保证G在任何情况下都是连通的，则需要的边数最少是（）？
【C】任意变动G中的边，G还是连通的。让G中的6个顶点构成完全连通子图，需6×5÷2=15条边，再添1条边连向第7个顶点。
「8」、对右图进行拓扑排序，可以得到不同的拓扑序列的个数是（）？
【B】abced，aebcd，abecd，共3个。
「9」、已知一个长度为16的顺序表L，其元素按关键字有序排列。若采用折半查找寻找一个L中不存在的元素，则关键字的比较次数最多是（）？
【B】考折半查找寻找失败的比较次数，记住公式：⌊log16⌋+1=5。
「10」、采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，正确的是（）？
【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】每趟排序后都有一个大元素位于后面的位置上不再变动，比较符合冒泡排序。BCD都不符合。
ComputerOrganization
「12」、下列选项中，能缩短程序执行时间的措施是（）？
i'提高CPU时钟频率 ii'优化数据通路结构 iii'对程序进行编译优化
【D】最难确定的就是i'了，i'指令完成时间与CPU时钟周期密切相关，通常指令都能在一个时钟周期内完成，提高CPU时钟频率，各指令的完成时间也会被缩短，也就能够缩短程序执行时间；ii'数据在功能部件之间的流通路径称为数据通路，优化数据通路结构可以使得程序更快获得各个步骤需要的操作数，从而缩短程序执行时间；iii'编译优化后可以得到更优的指令序列，属于软件层次的缩短程序执行时间。
「13」、假定有4个整数用8位补码分别表示r1=0xFE,r2=0xF2,r3=0x90,r4=0xF8，若将运算结果存放在一个8位寄存器中，则下列运算中会发生溢出的是（）？
【B】用十进制真数做。8位寄存器补码能存的数：{-128,...,+127}，r1=-2,r2=-14,r3=-112,r4=-8，显然r2×r3会发生溢出。
「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
【B】先排除ii'，f转int型肯定会丢失小数点后面的4位数；再排除iv'，(d+f)-d已经是IEEE754双精度浮点数了，跟f不相等。i'和iii'没问题，先往高的转再转回原类型，不会超出表示范围也不会丢失精度。
「15」、假定用若干个2K×4bit的芯片组成一个8K×8bit的存储器，则地址0x0B1F所在芯片的最小地址是（）？
【D】8K×8bit存储器需要4行2列的2K×4bit存储芯片来组成。每行占去2K个地址，各行存储芯片的地址分配为：
第1行，{0x0000,,0x07FF}； 第2行，{0x0800,,0x0FFF}；
第3行，{0x1000,,0x17FF}； 第4行，{0x1800,,0x1FFF}；
于是地址0x0B1F在第2行芯片，最小地址是0x0800。
「16」、下列有关RAM和ROM的叙述中，正确的是（）？
i'RAM是易失性存储器，ROM是非易失性存储器。
ii'RAM和ROM都采用随机存取方式进行信息访问。
iii'RAM和ROM都可用作Cache。
iv'RAM和ROM都需要进行刷新。
【A】概念题。i'ii'都正确，iii'一般Cache用高速SRAM制作，iv'只有DRAM使用的电容需要刷新，SRAM和ROM都不用。
「17」、下列命中组合情况中，一次访存过程中不可能发生的是（）？
【D】TLB是Page的小副本，TLB的内容就是从Page里获取的，TLB命中必然Page命中。TLB和Page是逻辑地址向物理地址转变的表，Cache是加速访存的部件，是否命中Cache与是否命中TLB或Page无关。
「18」、下列寄存器中，汇编语言程序员可见的是（）？
【B】汇编语言中，可以使用JMP等指令改变PC的值。
「19」、下列选项中，不会引起指令流水线阻塞的是（）？
【A】数据旁路技术，直接将执行结果送到其它指令需要的地方，而不是放入寄存器再被取走，就是用于提高流水线效率的。
「20」、下列选项中的英文缩写均为总线标准的是（）？
【D】总线标准现大纲已删，大致知道即可。CRT(Common Runtime Environment), CPI(Clock cycles Per Instruction), MIPS(Million Instructions Per Second), RAM(Random Access Memory)跟总线无关；PCI(Peripheral Component Interconnect), PCI-E(Peripheral Component Interconnect Express), ISA(Industry Standard Architecture), EISA(Extended Industry Standard Architecture), VESA(Video Electronics Standards Association), SCSI(Small Computer System Interface), USB(Universal Serial Bus)是总线标准。
「21」、单级中断系统中，中断服务程序内的执行顺序是（）？
i'保护现场 ii'开中断 iii'关中断 iv'保存断点
v'中断事件处理 vi'恢复现场 vii'中断返回
【A】概念题。单中断系统不允许中断嵌套，中断处理过程为：①关中断{确保后续操作不被打断}；②保存断点{程序计数器的值入栈区}；③生成中断向量地址；④保护现场{保存各寄存器的内容}；⑤中断事件处理；⑥恢复现场；⑦开中断；⑧中断返回{改回程序计数器}；其中①②③是由硬件自动完成的中断隐指令，④⑤⑥⑦⑧是中断服务程序做的。
「22」、假定一台计算机的显示存储器用DRAM芯片来实现，若要求显示分辨率为1600×1200，颜色深度为24bit，帧频为85Hz，显存总带宽的50%用来刷新屏幕，则需要的显存总带宽至少约（）？
【D】看单位也应知道咋算。1帧含1600×1200×24b，1s有85帧，且这85帧只占显示带宽的50%，显存总带宽1600×1200×24b×85÷50%=7833.6×exp10(6)bps≈7834Mbps。
OperatingSystem
「23」、下列选项中，操作系统提供给应用程序的接口是（）？
【A】首先排序BD。系统调用能完成特定的功能，应用程序通过系统调用来请求获得操作系统内核的服务。库函数是系统调用的上层，由中高级编程语言提供，目的是隐藏访管指令的细节，使系统调用更抽象方便。
「24」、下列选项中，导致创建新进程的操作是（）？
i'用户登录成功 ii'设备分配 iii'启动程序执行
【C】ii'分配设备时操作系统通过设置一些数据结构将设备与相应的进程关联起来，不用创建新进程。i'用户登录成功后，系统将为该终端创建一个新进程管理该用户活动，iii'启动程序执行时典型的引起创建进程的事件。
「25」、设与某资源关联的信号量初值为3，当前值为1。若M表示该资源的可用个数，N表示等待该资源的进程数，则M,N分别是（）？
【B】题意说明该资源已被占用2个，还有1个可用，当信号量小于0时才表示有进程在等待该资源。
「26」、下列选项中，降低进程优先级的合理时机是（）？
【A】进程时间片用完，应降低其优先级让别的进程能被调度上处理机运行一会儿。
「27」、进程P0和P1的共享变量定义及其初值为
bool flag[2] = {false, false}; int turn = 0;
若进程P0和P1访问临界资源的类C伪代码实现如下：
void P0() |void P1()
{ |{
while (true) | while (true)
{ | {
flag[0] = true; turn = 1; | flag[1] = true; turn = 0;
while (flag[1] && turn == 1) ;| while (flag[0] && turn == 0) ;
/* CriticalSection; */ | /* CriticalSection; */
flag[0] = false; | flag[1] = false;
} | }
} |}则并发执行进程P0和P1时产生的情形是（）？
【D】所给的就是皮特森算法，表达意图但还是先谦让，能互斥进入临界区，不会饥饿。
「28」、某基于动态分区存储管理的计算机，其主存容量为55MB，初始空闲，采用最佳适配{Best Fit}算法，分配和释放的顺序为：分配15MB，分配30MB，释放15MB，分配8MB，分配6MB，此时主存中最大空闲分配区的大小是（）？
【B】最佳适配算法：每次为作业分配内存时，找到满足需要的最小空闲分区给予。如下图所示。
「29」、某计算机采用二级页表的分页存储管理方式，按字节编址，页大小为exp(20)B，页表项大小为2B，逻辑地址结构为：[页目录号|页号|页内偏移量]。逻辑地址空间大小为exp(16)页，则能表示整个逻辑地址空间的页目录表中包含表项的个数至少是（）？
【B】1页可以满满塞下exp(10)B÷2B=exp(9个)页表项，此时需要exp(16)÷exp(9)=exp(7)=128个塞满页表项的页表才能表示题目所给的逻辑地址空间，即页目录表得包含128个页表项。逻辑地址结构中，页内偏移量20位，页号9位，页目录号至少7位，当然本题没有用到这些。
「30」、设文件索引结点中有7个地址项，其中4个地址项是直接地址索引，2个地址项是一级间接地址索引，1个地址项是二级间接地址索引，每个地址项大小为4B。若磁盘索引块和磁盘数据块大小均为256B，则可表示的单个文件最大长度是（）？
【C】一个磁盘索引块包含256B÷4B=64个直接地址索引，单个文件索引结点可指向4+2×64+1×64×64=4228个磁盘数据块，单个文件最大4228×256B=1057KB。
「31」、设置当前工作目录的主要目的是（）？
【C】为的就是缩短文件路径，加快检索。
「32」、本地用户通过键盘登录系统时，首先获得键盘输入信息的程序是（）？
【B】键盘是典型的通过中断方式工作的外设，键盘敲下后发起中断，操作系统内核响应中断，通过中断处理程序将输入信息传给上层。
ComputerNetWork
「33」、下列选项中，不属于网络体系结构所描述的内容是（）？
【C】概念题。网络体系结构是抽象的，非具体的。
「34」、在下图所示的采用存储-转发方式的分组交换网络中，所有链路的数据传输率为100Mbps，分组大小为1000B，其中分组头大小为20B。若主机H1向主机H2发送一个大小为980,000B的文件，则在不考虑分组拆装时间和传播时延的情况下，从H1发送开始到H2接收完为止，需要的时间至少是（）？
【C】分组中的数据大小是1000B-20B=980B，文件要拆为980000B÷980B=1000个分组，发送时延是1000×1000B÷100Mbps=80ms，再加2个路由器的单分组转发时延2×1000B÷100Mbps=0.16ms，共80.16ms，题干明确说了不考虑链路的传播时延。
「35」、某自治系统内采用路由信息协议RIP，若该自治系统内的路由器R1收到其邻居路由器R2的距离矢量，距离矢量中包含信息<net1, 16>，则能得出的结论是（）？
【D】RIP规定跳数16表示不可达，R2到不了，R1也不能经R2到。
「36」、若路由器R因为拥塞丢弃IP分组，则此时R可向发出该IP分组的源主机发送的ICMP报文类型是（）？
【C】简单题。
「37」、某网络的IP地址空间为192.168.5.0/24，采用定长子网划分，子网掩码为255.255.255.248，则该网络中的最大子网个数和每个子网内的最大可分配地址个数分别是（）？
【B】248=0b11111000，注意到子网可分配IP地址要去掉全0和全1可直接选定B，6=exp(3)-2。
「38」、下列网络设备中，能过抑制广播风暴的是（）？
i'中继器 ii'集线器 iii'网桥 iv'路由器
【D】考认识网络设备。中继器和集线器工作在物理层，不隔离冲突域，也不隔离广播域；网桥工作在数据链路层，隔离冲突域，不隔离广播域；路由器工作在网络层，既隔离冲突域，也隔离广播域。
「39」、主机甲和主机乙之间已建立TCP连接，TCP最大段长度为1000B。若主机甲的当前拥塞窗口为4000B，在主机甲向主机乙连续发送两个最大段后，成功收到主机乙发送的第一个段的确认段，确认段中通告的接收窗口大小为2000B，则此时主机甲还可以向主机乙发送的最大字节数是（）？
【A】主机甲的发送窗口大小应为MIN(4000B, 2000B)=2000B，由于主机甲还没收到第二个最大段的确认段，故只能再发1000字节。
「40」、若本地域名服务器无缓存，当采用递归方法解析另一网络某主机域名时，用户主机、本地域名服务器发送到的域名请求消息数分别为（）？
【A】考DNS域名解析过程。递归方式下，用户主机发给本地域名服务器，本地域名服务器发给其他根域名服务器，其他根域名服务器继续。
