2011年12月考研的408试题，本篇为小题部分，大题见下一篇。
声明：
- 0x和0b分别表示十六进制和二进制数，其余为十进制数。
- exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
- 乘除号用最朴素的×÷，分数用/，参与计算的英文字母变量用手写体。
- {}里的斜体为补充文字，另外对原题一些容易误会的文字做了修改。
- 图片使用亿图图示等工具绘制。
- 点击查看答案按钮有惊喜。
一、单项选择：
第1~40小题，每小题2分，共80分。
DataStructure
🧑🏫🫵「1」求自然数n阶乘的算法如下，其时间复杂度是（）？
int fact(int n)
{
if (n <= 1) return 1;
return n * fact(n-1);
}
🧑🏫🫵「2」已知操作符包括“+-×÷()”六个。将中缀表达式“a+b-a×((c+d)÷e-f)+g”转换为等价的后缀表达式ab+acd+e÷f-×-g+时，用栈来存放暂时还不能确定运算次序的操作符，若栈初始为空，则转换过程中同时保存在栈中的操作符的最大个数是（）？
🧑🏫🫵「3」若一棵二叉树的前序遍历序列为a,e,b,d,c，后序遍历序列为b,c,d,e,a，则根结点的孩子结点（）？
🧑🏫🫵「4」若平衡二叉树的高度为6，且所有非叶结点的平衡因子均为1，则该平衡二叉树的结点总数为（）？
🧑🏫🫵「5」对有n个顶点，e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是（）？
🧑🏫🫵「6」若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为0，则关于该拓扑序列的结论是（）？
🧑🏫🫵「7」如右图所示的有向带权图，若采用迪杰斯特拉算法求从源点a到其它各顶点的最短路径，则得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余各最短路径的目标顶点依次是（）？
🧑🏫🫵「8」下列关于最小生成树的叙述中，正确的是（）？
i'最小生成树的代价唯一。 ii'所有权值最小的边一定会出现在所有最小生成树中。
iii'使用普利姆算法从不同顶点开始得到的最小生成树一定相同。
iv'使用普利姆算法和克鲁斯卡尔算法得到的最小生成树总不相同。
🧑🏫🫵「9」已知一棵3阶B-T，如下图所示。删除关键字78得到一棵新B-T，其最右叶结点中的关键字是（）？
🧑🏫🫵「10」在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟都能确定一个元素最终位置的方法是（）？
i'选择排序 ii'希尔排序 iii'快速排序 iv'堆排序 v'二路归并排序
🧑🏫🫵「11」对一待排序序列分别进行直接插入排序和折半插入排序，两者之间可能的不同之处是（）？
ComputerOrganization
🧑🏫🫵「12」假定基准程序A在某计算机上的运行时间为100s，其中90s为CPU时间，其余为 I/O时间。若CPU速度提高50%，I/O速度不变，则运行基准程序A所耗费的时间是（）？
🧑🏫🫵「13」假定编译器规定int和short型长度分别为32位和16位，执行下列C语言语句得到y的机器数为（）？
unsigned short x = 65530;
unsigned int y = x;
🧑🏫🫵「14」IEEE754单精度浮点数格式，即float类型能表示的最大正整数是（）？
🧑🏫🫵「15」某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int型和short型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下，若record变量首地址为0xC008，则地址0xC008中的内容及record.c的地址分别为（）？
struct {
int a;
char b;
short c;
} record;
record.a = 273;🧑🏫🫵「16」下列关于闪存"Flash Memory"的叙述中，错误的是（）？
🧑🏫🫵「17」假设某计算机按字编址，Cache有4个块，Cache和Memory之间交换的块大小为1个字。若Cache的内容初始为空，采用2路组相联映射方式和LRU替换策略。访问的主存地址依次为0,4,8,2,0,6,8,6,4,8时，命中Cache的次数是（）？
🧑🏫🫵「18」某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7,3,12,5,6个微命令，则操作控制字段至少有（）？
🧑🏫🫵「19」某同步总线的时钟频率为100MHz，宽度为32位，地址／数据线复用，每传输一个地址或数据占用一个时钟周期。若该总线支持突发传输方式，则一次“主存写”总线事务传输128位数据所需要的时间至少是（）？
🧑🏫🫵「20」下列关于USB总线特性的描述中，错误的是（）？
🧑🏫🫵「21」下列选项中，在I/O总线的数据线上传输的信息包括（）？
i'I/O接口中的命令字 ii'I/O接口中的状态字 iii'中断类型号
🧑🏫🫵「22」响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括（）？
i'关中断 ii'保存通用寄存器的内容 iii'形成中断服务程序入口地址并送PC
OperatingSystem
🧑🏫🫵「23」下列选项中，不可能在用户态发生的事件是（）？
🧑🏫🫵「24」中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是（）？
🧑🏫🫵「25」下列关于虚拟存储器的叙述中，正确的是（）？
🧑🏫🫵「26」操作系统的I/O子系统通常由四个层次组成，每层明确定义了与邻近层次的接口。其合理的层次组织排列顺序是（）？
🧑🏫🫵「27」假设5个进程P0,P1,P2,P3,P4共享三类资源R1,R2,R3，这些资源总数分别为(18,6,22)。T0时刻的资源分配情况如下表所示,此时存在的一个安全序列是（）？
| 进程 | 已分配资源 | 资源最大需求 | ||||
| R1 | R2 | R3 | R1 | R2 | R3 | |
| P0 | 3 | 2 | 3 | 5 | 5 | 10 |
| P1 | 4 | 0 | 3 | 5 | 3 | 6 |
| P2 | 4 | 0 | 5 | 4 | 0 | 11 |
| P3 | 2 | 0 | 4 | 4 | 2 | 5 |
| P4 | 3 | 1 | 4 | 4 | 2 | 4 |
🧑🏫🫵「28」若一个用户进程通过read系统调用读取一个磁盘文件中的数据，则下列关于此过程的叙述中，正确的是（）？
i'若该文件的数据不在内存中，则该进程进入睡眠等待状态。 ii'请求read系统调用会导致CPU从用户态切换到核心态。 iii'read系统调用的参数应包含文件的名称。
🧑🏫🫵「29」一个多道批处理系统中仅有P1和P2两个作业，P2比P1晚5ms到达，它们的计算和I/O操作顺序如下，若不考虑调度和切换时间，则完成两个作业需要的时间最少是（）？
P1：计算 60ms，I/O 80ms，计算 20ms。
P2：计算 120ms， I/O 40ms， 计算 40ms。
🧑🏫🫵「30」若某单处理器多进程系统中有多个就绪态进程，则下列关于处理机调度的叙述中，错误的是（）？
🧑🏫🫵「31」下列关于进程和线程的叙述中，正确的是（）？
🧑🏫🫵「32」下列选项中，不能改善磁盘设备I/O性能的是（）？
ComputerNetWork
🧑🏫🫵「33」在TCP/IP体系结构中，直接为ICMP提供服务的协议是（）？
🧑🏫🫵「34」在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是（）？
🧑🏫🫵「35」以太网的MAC协议提供的是（）？
🧑🏫🫵「36」两台主机之间的数据链路层采用后退N帧协议传输数据，数据传输速率为16Kbps，单向传播时延为270ms，数据帧长度范围是128~512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率达到最高，帧序号的比特数至少为（）？
🧑🏫🫵「37」下列关于IP路由器功能的描述中，正确的是（）？
i'运行路由协议，设置路由表。 ii'监测到拥塞时，合理丢弃IP分组。
iii'对收到的IP分组头进行差错校验，确保传输的IP分组不丢失。
iv'根据收到的IP分组的目的IP地址，将其转发到合适的输出线路上。
🧑🏫🫵「38」地址解析协议ARP提供的功能是（）？
🧑🏫🫵「39」某主机的IP地址为180.80.77.55，子网掩码为255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是（）？
🧑🏫🫵「40」若用户1与用户2之间发送和接收电子邮件的过程如下图所示，则图中①②③阶段分别使用的应用层协议可以是（）？
