2018年12月考研的408试题，本篇为小题部分，大题见下一篇。
声明：
- 0x和0b分别表示十六进制数和二进制数，其余为十进制数。
- 0y和0c分别表示十六进制形式补码和二进制形式补码。
- exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
- 乘除号用最朴素的×÷，分数用/，⌊⌋⌈⌉分别是向上向下取整。
- 参与计算的英文字母变量用手写体。
- 对原题一些容易误会的文字做了修改。
- 图片使用亿图图示等绘制。
一、单项选择：
第1～40小题，每小题2分，共80分。
DataStructure
🤓✍️「1」、设n是描述问题规模的正整数，下列程序段的时间复杂度是（）？
int x = 0;
while (n >= (x + 1) * (x + 1))
x = x + 1;
🤓✍️「2」、若将一棵普通树T转化为对应的二叉树B，则下列对B的遍历中，其遍历序列与T的后根遍历序列相同的是（）？
🤓✍️「3」、对𝓃个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则𝓃的值是（）？
🤓✍️「4」、在任意一棵非空平衡二叉树T1中，删除某结点v之后形成平衡二叉树T2，再将v插入T2形成平衡二叉树T3。下列关于T1与T3的叙述中，正确的是（）？
Ⅰ꙳若v是T1的叶结点，则T1与T3可能不相同。
Ⅱ꙳若v不是T1的叶结点，则T1与T3一定不同。
Ⅲ꙳若v不是T1的叶结点，则T1与T3一定相同。
🤓✍️「5」、下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是（）？
🤓✍️「6」、用有向无环图描述表达式(𝓍+𝓎)×((𝓍+𝓎)÷𝓍)，需要的顶点个数至少是（）？
🤓✍️「7」、选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是（）？
Ⅰ꙳数据的规模 Ⅱ꙳数据的存储方式 Ⅲ꙳算法的稳定性 Ⅳ꙳数据的初始状态
🤓✍️「8」、现有长度为11且初始为空的散列表H，散列函数是𝒉(𝓀ℯ𝓎)=𝓀ℯ𝓎%7，采用线性探查法解决冲突。将关键字序列87,40,30,6,11,22,98,20依次插入H后，H查找失败的平均查找长度是（）？
🤓✍️「9」、设主串T="abaabaabcabaabc"，模式串S="abaabc"，采用KMP算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是（）？
🤓✍️「10」、排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟。下列序列中，不可能是快速排序第二趟结果的是（）？
🤓✍️「11」、设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是（）？
ComputerOrganization
🤓✍️「12」、下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是（）？
🤓✍️「13」、考虑以下C语言代码，执行上述程序段后，si的值是（）？
unsigned short usi = 65535;
short si = usi;
🤓✍️「14」、下列关于缺页处理的叙述中，错误的是（）？
🤓✍️「15」、某机器采用大端方式，按字节编址。某指令中操作数的机器数为0x1234FF00，该操作数采用基址寻址方式，形式地址用补码表示为0yFF12，基址寄存器的内容为0xF0000000，则该操作数的最低有效字节所在的地址是（）？
🤓✍️「16」、下列有关处理器时钟脉冲信号的叙述中，错误的是（）？
🤓✍️「17」、某指令功能为R[r2]←R[r1]+M[R[r0]]，其两个源操作数分别采用寄存器立即·寄存器间接寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是（）？
Ⅰ꙳通用寄存器组GPRs Ⅱ꙳算术逻辑单元ALU Ⅲ꙳主存储器Memory Ⅳ꙳指令译码器ID
🤓✍️「18」、在采用“取指·译码＼取数·执行·访存·写回”5段流水线的处理器中，执行如下指令序列，其中s0,s1,s2,s3,t2表示寄存器编号，下列指令对中，不存在数据冒险的是（）？
I1: add s2, s1, s0 ; R[s2]←R[s1]+R[s0]
I2: load s3, 0(t2) ; R[s3]←M[R[t2]+0]
I3: add s2, s2, s3 ; R[s2]←R[s2]+R[s3]
I4: store s2, 0(t2) ; M[R[t2]+0]←R[s2]
🤓✍️「19」、假定一台计算机采用3通道存储器总线，配套的内存条型号为DDR3-1333，即内存条所接插的存储器总线的工作频率为1333MHz，总线宽度为64位，则存储器总线的总带宽大约是（）？
🤓✍️「20」、下列关于磁盘存储器的叙述中，错误的是（）？
🤓✍️「21」、某设备以中断方式与CPU进行数据交换，CPU主频为1GHz，设备接口中的数据缓冲寄存器为32b，设备的数据传输率为50KBps。若每次中断开销为1000个时钟周期，则CPU用于该设备输入／输出的时间占整个CPU时间的百分比最多是（）？
🤓✍️「22」、下列关于DMA方式的叙述中，正确的是（）？
Ⅰ꙳DMA传送前由设备驱动程序设置传送参数。
Ⅱ꙳数据传送前由DMA控制器请求总线使用权。
Ⅲ꙳数据传送由DMA控制器直接控制总线完成。
Ⅳ꙳DMA传送结束后的处理由中断服务程序完成。
OperatingSystem
🤓✍️「23」、下列关于线程的描述中，错误的是（）？
🤓✍️「24」、下列选项中，可能会将进程唤醒的事件是（）？
Ⅰ꙳I/O结束 Ⅱ꙳某进程退出临界区 Ⅲ꙳当前进程的时间片用完
🤓✍️「25」、下列关于系统调用的叙述中，正确的是（）？
Ⅰ꙳在执行系统调用服务程序的过程中，CPU处于内核态。
Ⅱ꙳操作系统通过提供系统调用避免用户程序直接访问外设。
Ⅲ꙳不同的操作系统为应用程序提供了统一的系统调用接口。
Ⅳ꙳系统调用是操作系统内核为应用程序提供服务的接口。
🤓✍️「26」、下列选项中，可用于文件系统管理空闲磁盘块的数据结构是（）？
Ⅰ꙳位图 Ⅱ꙳索引结点 Ⅲ꙳空闲磁盘块链 Ⅳ꙳文件分配表
🤓✍️「27」、系统采用二级反馈队列调度算法进行进程调度。①就绪队列Q1采用时间片轮转调度算法，时间片为10ms；②就绪队列Q2采用短进程优先调度算法；③系统优先调度Q1中的进程，当Q1为空时系统才会调度Q2中的进程；④新创建的进程首先进入Q1；⑤Q1中的进程执行一个时间片后，若未结束则转入Q2。若当前Q1,Q2为空，系统依次创建进程P1,P2后即开始进程调度，P1,P2需要的CPU时间分别为30ms,20ms，则进程P1,P2在系统中的平均等待时间为（）？
🤓✍️「28」、在分段存储管理系统中，用共享段表描述所有被共享的段。若进程P1,P2共享段S，下列叙述中，错误的是（）？
🤓✍️「29」、某系统釆用LRU页面置换算法和局部置换策略，若系统为进程P预分配了4个页框，进程P访问页面号的序列为0,1,2,7,0,5,3,5,0,2,7,6，则进程访问上述页的过程中，产生页面置换的总次数是（）？
🤓✍️「30」、下列关于死锁的叙述中，正确的是（）？
Ⅰ꙳可以通过剥夺进程资源解除死锁。 Ⅱ꙳死锁的预防方法能确保系统不发生死锁。
Ⅲ꙳银行家算法可以判断系统是否处于死锁状态。
Ⅳ꙳当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态。
🤓✍️「31」、某计算机主存按字节编址，采用二级分页存储管理，地址结构为：［页目录号10位｜页面号10位｜页内偏移12位］，虚拟地址0x2050 1225对应的页目录号·页面号分别是（）？
🤓✍️「32」、在下列动态分区分配算法中，最容易产生内部碎片的是（）？
ComputerNetWork
🤓✍️「33」、OSI七层参考模型的自下而上第5层完成的主要功能是（）？
🤓✍️「34」、100BaseT快速以太网使用的导向传输介质是（）？
🤓✍️「35」、对于滑动窗口协议，若分组序号采用3比特编号，发送窗口大小为5，则接收窗口最大是（）？
🤓✍️「36」、假设一个采用CSMA/CD协议的100Mbps局域网，最小帧长是128B，则在一个冲突域内两个站点之间的单向传播时延最多是（）？
🤓✍️「37」、若将101.200.16.0/20划分为5个子网，尽量不浪费，则子网最少可分配的IP地址数是（）？
🤓✍️「38」、客户端通过一个TCP连接向服务器发送数据的部分过程如下图👇。客户端在t0时刻第一次收到确认序列号ack_seq=100的段，并发送序列号seq=100的段，但发生丢失。若TCP支持快速重传，则客户端重新发送seq=100段的时刻是（）？
🤓✍️「39」、若主机甲主动发起一个与主机乙的TCP连接，甲乙选择的初始序列号分别为2018和2046，则第三次握手TCP段的确认序列号是（）？
🤓✍️「40」、下列关于网络应用模型的叙述中，错误的是（）？
