2010年12月考研的408试题，本篇为小题部分，大题见下一篇。
声明：
- 0x和0b分别表示十六进制和二进制数，其余为十进制数。
- exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
- 乘除号用最朴素的×÷，分数用/，参与计算的英文字母变量用手写体。
- {}里的斜体为补充文字，另外对原题一些容易误会的文字做了修改。
- 图片使用亿图图示绘制。
一、单项选择：
第1~40小题，每小题2分，共80分。
DataStructure
「1」、设N是描述问题规模的正整数，下面程序片段的时间复杂度是（）？
k = 2;
while (k < N / 2)
k = 2 * k;
【A】k以2的指数增长，在log(N)步左右就可大于N/2。
「2」、元素a,b,c,d,e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则所有可能的出栈序列中，以d开头的序列个数是（）？
【B】d,c,b,a,的出栈次序是确定的，e可以选择在其中一元素后面出栈。
「3」、已知循环队列存储在一维数组A[0,,,n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若队列初始时为空，且要求第一个进队的元素存储在A[0]处，则初始时front和rear的值分别是（）？
【B】插入第一个元素后，front不变，rear加1，且都要指向A[0]，那么front和rear原应为0,n-1。
「4」、若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（）？
【C】设叶结点𝓀个，度为2的结点𝓀-1个，完全二叉树中度为1的结点个数只能是0或1，此处应是1个，总结点个数2𝓀=768，𝓀=384。
「5」、若一棵二叉树的前序遍历序列和后序遍历序列分别为1,2,3,4和4,3,2,1，则该二叉树中序遍历序列不会是（）？
【C】先排除AD，当二叉树长得极右时，中序遍历序列同前序遍历序列，当二叉树长得极左时，中序遍历序列同后序遍历序列。B可以画出来。C由“中序+前序”确定的树，和“中序+后序”确定的树不是同一棵。
「6」、已知一棵有2011个结点的普通树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是（）？
【D】普通树转二叉树的规则为“每个分支结点只保留第一个孩子、其余的孩子依次变为左边兄弟的右孩子”，“在转化来的二叉树中左孩子原本是长子、右孩子原本是次弟”。转二叉树后无右孩子的只有每个分支结点的最后一个孩子，再加1个根结点。题中共2011-116=1895个分支结点。
「7」、对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是（）？
【A】A中先查到91，又查到94是不合理的。
「8」、下列关于图的叙述中，正确的是（）？
i'回路是简单路径。 ii'存储稀疏图，用邻接矩阵比邻接表更省空间。
iii'若有向图中存在拓扑序列，则该图不存回路。
【C】概念题。
「9」、为提高散列表的查找效率，可以采用的正确措施是（）？
i'增大装填因子。 ii'设计冲突少的散列函数。
iii'处理冲突时避免产生堆积现象。
【D】应该减少装填因子，牺牲空间换取时间。
「10」、为实现快速排序算法，待排序序列宜采用的存储方式是（）？
【D】大多数内部排序采用顺序存储为宜。
「11」、已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是（）？
【B】回忆大根堆的插入，如图。
ComputerOrganization
「12」、下列选项中，描述浮点数操作速度指标的是（）？
【D】MPFLOPS-"Million Floating Point Operations Per Second"-“每秒多少百万次浮点运算”。ABC中的I都是"Instructions"-“指令”。
「13」、float型数据通常用IEEE754单精度浮点数格式表示。若编译器将float型变量x分配到一个3位浮点数寄存器FR1中，且x=-8.25，则FR1的内容是（）？
【A】IEEE754规定单精度浮点数，1位符号，8位阶数，23位尾数，阶数用移码，尾数用原码。负数，数符位就是1；8.25=0b1000.01=0b1.00001×exp(3)，阶数3+127=0b10000010，尾数藏高位1补低位0，
FR1的内容应是：0b 1 10000010 00001000000000000000000 = 0x C104 0000。
「14」、下列各类存储器中，不采用随机存取方式的是（）？
【B】CDRM是只读光盘，光盘类似磁盘，采用顺序存取方式。
「15」、某计算机存储器按字节编址，主存地址空间大小为64MB，现用4MB×8b的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是（）？
【D】主存有64M个地址，log(64M)=26位。主存储器实际大小32MB是迷惑项，MAR位数并不由这个决定。
「16」、偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是（）？
【A】间接寻址不需要寄存器，EA=Mem[A]。基址寻址EA=A+基址寄存器(BR)内容；相对寻址EA=A+程序计数器(PC)内容；变址寻址EA=A+变址寄存器(IX)内容。
「17」、某机器有一个标志寄存器，其中有进位／借位标志CF，零标志ZF，符号标志SF和溢出标志OF，条件转移指令bgt{无符号整数比较大于时转移}的转移条件是（）？
【C】指令bgt发生转移相当于两无符号数的差为正，a-b>0，显然，无进位／借位CF=0，不为零ZF=0，用不到SF和OF。
「18」、下列给出的指令系统特点中，有利于实现指令流水线的是（）？
i'指令格式规整且长度一致。 ii'指令和数据按边界对齐存放。
iii'只有Load/Store指令才能对操作数进行存储访问。
【D】这三个都是RISC的特点。i'能大大简化指令译码的复杂度；ii'能保证在一个存取周期内取完指令和数据，其它流水段不用多余的等待；iii'取数操作简化且时长固定，有得于和其它流水段对齐。
「19」、假定不采用Cache和指令预取技术，且机器处于开中断状态。在下列有关指令执行的叙述中，错误的是（）？
【C】C，起码在取指完成后PC++。A，至少要访存取指令；B，一个时钟周期CPU只能完成一个动作；D，指令执行完要检查中断。
「20」、在系统总线的数据线上，不可能传输的是（）？
【C】握手信号在通信总线上传输。指令，操作数，中断类型号都在数据总线上传输。
「21」、某计算机有五级中断L4-L0，中断屏蔽字为M4M3M2M1M0，Mi=1表示对Li级中断进行屏蔽 若中断响应优先级从高到低的顺序是L4→L0→L2→L1→L3，则L1的中断处理程序中设置的中断屏蔽字（）？
【D】易错题。L1只能屏蔽L1和L3中断，其中断屏蔽字M3和M1置1。C选项迷惑性很强。
「22」、某计算机处理器主频为50MHz，采用定时查询方式控制设备A的I/O，查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间，为保证数据不丢失，每秒需对其查询至少 200次，则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是（）？
【C】该处理器一秒有50×exp10(6)个时钟周期，查询程序用在设备A的I/O上200×500=10000个，占比0.20%。
「23」、下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是（）？
【B】响应比=（等待时间+执行时间）÷执行时间，通常是最优调度算法。
OperatingSystem
「24」、下列选项中，在用户态执行的是（）？
【A】在Windows中的命令提示符就是一种命令解释程序，是面向用户的。缺页处理，时钟中断处理，进程调度都是操作系统内核提供的功能。
「25」、在支持多线程的系统中，进程P创建的若干线程不能共享的是（）？
【D】这是线程独享的。
「26」、用户程序发出磁盘I/O请求后，系统的正确处理流程是（）？
【B】概念题。考I/O软件层次从上至下的四个层次，系统调用处理程序即设备独立性软件。
「27」、某时刻进程的资源使用情况如下表所示，此时的安全序列是（）？
| 进程 | 已分配资源 | 尚需分配 | 可用资源 | ||||||
| R1 | R2 | R3 | R1 | R2 | R3 | R1 | R2 | R3 | |
| P1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
| P2 | 1 | 2 | 0 | 1 | 3 | 2 | |||
| P3 | 0 | 1 | 1 | 1 | 3 | 1 | |||
| P4 | 0 | 0 | 1 | 2 | 0 | 0 | |||
【D】使用银行家算法，资源R2怎样都不够。
「28」、在缺页处理过程中，操作系统执行的操作可能是（）？
i'修改页表 ii'磁盘I/O iii'分配页框
【D】①启动磁盘I/O，从磁盘调入所缺的页面；②为新调入的页面分配页框，然后修改页表。
「29」、不系统发生进程抖动时，可以采取的有效措施是（）？
i'撤销部分进程。 ii'增加磁盘交换区的容量。 iii'提高用户进程的优先级。
【A】抖动现象是指进程的页面刚被换出外存很快又要被访问换入，如此频繁地置换页面，以致大部分时间都花在置换页面上，导致系统性能下降。ii'内存页框数不够，并不是磁盘交换区容量不够；iii'提高用户进程的优先级也不会配给更多的页框。
「30」、在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成逻辑地址的阶段是（）？
【B】源代码文件编译成多个模块，各模块内形成了各自的逻辑地址；然后各模块经链接形成整个程序的线性地址，{为了和编译时的逻辑地址作区分引入的概念}；最后经装载形成物理地址。
「31」、某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100us，将缓冲区的数据传送到用户区的时间是50us，CPU对一块数据进行分析的时间为5Ous。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是（）？
【B】如图，单缓冲区200us+9×150us=1550us，双缓冲区200us+9×100us=1100us。
「32」、有两个并发执行的进程P1和P2，共享初值为1的变量x。P1对x加1，P2对x减1。加1和减1操作的指令序列分别如下所示，两个操作完成后，x的值（）？
// load/store a, b => b的内容送给a
// P1 // P2
load R1, x ① |load R2, x ④
inc R1 ② |dec R2 ⑤
store x, R1 ③ |store x, R2 ⑥【C】给P1P2的三条语句分别编号，①②③④⑤⑥->x的值依旧为1，①②④⑤⑥③->x的值为2，④⑤①②③⑥->x的值为0，-1是不可能得到的。
ComputerNetWork
「33」、TCP/IP参考模型的网络层提供的是（）？
【A】概念题。TCP/IP参考模型的网络层使用的是互联网协议IP，无连接不可靠。有连接可靠都是应用层的TCP实现，有连接——三次握手四次挥手，可靠——差错检测和超时重传等。
「34」、若某通信链路的数据传输速率为2400bps，采用四相位调制，则该链路的波特率数值是（）？
【A】在调制解调器中，波特率指每秒传输的信号调制变化数目，采用四相位即有4种变化，1个码元传log(4)=2比特，波特率=比特率÷2，1200。
「35」、数据链路层采用选择重传协议传输数据，发送方已发送了0~3号数据帧，现已收到1号帧的确认，而O,2号帧依次超时，则此时需要重传的帧数是（）？
【B】选择重传协议中，接收窗口大小不为1，不采用累积确认，O,2号帧依次超时就重传O,2号帧。3号帧未提及，不考虑。
「36」、下列选项中，对正确接收到的数据帧进行确认的MAC协议是（）？
【D】CSMA/CA，载波监听-多址接入-碰撞避免，是无线局域网标准802.11中的协议，确认帧是避免碰撞的机制之一。
「37」、某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP分组正确地路由到图中所有的子网， 则在R1中需要增加的一条路由（目的网络，子网掩码，下一跳）是（）？
【D】路由聚合，192.168.2.0/25+192.168.2.128/25=192.168.2.0/24。
「38」、在子网192.168.4.0/30中能接收目的地址为192.168.4.3的IP分组的最大主机数是（）？
【C】考CIDA子网划分，子网192.168.4.0/30把最后的0拆成二进制来看，6位子网号2位主机号，再减去子网网络地址和子网广播地址，给主机的地址就exp(2)-2=2个。
「39」、主机甲向主机乙发送一个(SYN=1, seq=11220)的TCP段，期望与主机乙建立TCP连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的TCP段可能是（）？
【C】在乙发回的确认TCP段中，同步位SYN和确认位ACK都是1，确认号ack=甲发来的初始序号+1=11221，初始序号seq由乙任选。
「40」、主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3个连续的TCP段，分别包含300B,400B,500B的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1段 和第3段，则主机乙发送给主机甲的确认序号是（）？
【B】主机乙发回的是对第1段的确认，并期待收到第2段的起始字节序号，900-400=500。
