年全国研究生考试计算机统考试题及答案

年全国研究生考试计算机统考试题及答案一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是最符合题目要求的。1.若已知一个栈的入栈序列是1,2,3,...,n，其输出序列是,,,...A.iB.nC.nD.不确定2.在单链表中，已知指针p指向某结点，若要在p所指结点之前插入一个由s指向的新结点，则需要执行的语句序列是（）。A.p->next=s;s->next=p;B.s->next=p->next;p->next=s;C.s->next=p;p=s;D.以上都不对3.一棵完全二叉树有1001个结点，其叶子结点的个数是（）。A.500B.501C.251D.2504.在一棵非空二叉树的中序遍历序列中，根结点的右边（）。A.只有右子树上的所有结点B.只有右子树上的部分结点C.只有左子树上的所有结点D.只有左子树上的部分结点5.若一棵二叉树具有10个度为2的结点，则该二叉树中度为1的结点个数不确定，但度为0的叶子结点个数肯定是（）。A.9B.10C.11D.126.在一个无向图中，所有顶点的度数之和等于所有边数的（）倍。A.1B.2C.1/2D.47.用邻接表表示图进行广度优先遍历时，通常借助的辅助数据结构是（）。A.栈B.队列C.树D.图8.在最坏情况下，下列排序算法中时间复杂度最低的是（）。A.冒泡排序B.简单选择排序C.直接插入排序D.快速排序9.对包含n个元素的散列表进行查找，平均查找长度（ASL）取决于（）。A.散列函数B.装填因子C.处理冲突的方法D.散列表表长10.设有一个哈希表，当前表长为m，哈希函数为H(k)A.mB.m-1C.小于等于表长m的最大素数D.大于表长m的最小素数11.冯·诺依曼计算机中指令和数据均以二进制形式存放在存储器中，计算机区分它们是通过（）。A.指令译码器B.操作数的寻址方式C.指令周期的不同阶段D.程序计数器12.假定某计算机的Cache采用4路组相联映射方式，Cache容量为16KB，主存容量为4MB，块大小为64B。则主存地址中组号占用的位数为（）。A.6B.7C.8D.913.下列关于浮点数IEEE754标准的叙述中，错误的是（）。A.浮点数由符号位、阶码和尾数三部分组成B.阶码采用移码表示C.尾数采用原码表示D.规格化浮点数的尾数最高有效位为114.某计算机字长为32位，存储字长为32位，按字编址。如果采用32位字长指令，指令寄存器IR和程序计数器PC的位数分别为（）。A.32,32B.32,30C.30,32D.32,1615.在系统总线的数据线上，信息传输（）。A.只能从主设备传输到从设备B.只能从从设备传输到主设备C.可以双向传输D.既不能从主设备传输到从设备，也不能从从设备传输到主设备16.相对于微程序控制器，硬布线控制器的优点是（）。A.指令执行速度慢B.指令执行速度快C.修改指令功能方便D.设计简单，规整性好17.某计算机的指令流水线由5个段组成，各段经过的时间依次为10ns,20ns,30ns,20ns,10ns。则流水线的时钟周期和最大吞吐率分别为（）。A.10ns,100MIPSB.30ns,33.3MIPSC.30ns,100MIPSD.10ns,33.3MIPS18.下列I/O控制方式中，CPU效率最高的是（）。A.程序查询方式B.程序中断方式C.DMA方式D.通道方式19.操作系统作为用户与计算机硬件系统之间的接口，其功能不包括（）。A.管理计算机系统的硬件资源B.提供用户程序与计算机硬件系统的接口C.提供高效、安全的硬件资源使用机制D.直接执行用户编写的应用程序20.在操作系统中，进程是资源分配和调度的基本单位，而线程是（）。A.资源分配的基本单位B.调度的基本单位C.拥有资源的独立实体D.不可被调度的实体21.进程P0和P1共享一个变量V。进程P0对V执行V操作，进程P1对V执行P操作。若这两个进程并发执行，则可能发生的情况是（）。A.不会发生与时间有关的错误B.可能发生与时间有关的错误C.一定会发生死锁D.一定会发生饥饿22.在分页存储管理系统中，若页面大小增加一倍，则页表项的总数（）。A.增加一倍B.减少一倍C.不变D.可能增加也可能减少，取决于内存大小23.虚拟存储器的大小受限于（）。A.物理内存的大小B.辅助存储器的大小C.计算机的地址字长D.页表的大小24.在采用SPOOLing技术的系统中，用户的打印数据首先被送到（）。A.磁盘固定区域B.内存固定区域C.终端D.打印机25.文件系统中，文件访问控制信息主要存储在（）。A.文件控制块（FCB）B.索引结点C.超级块D.空闲块链表26.操作系统中的I/O软件层次中，负责与硬件具体细节打交道的是（）。A.用户级I/O软件B.设备独立性软件C.设备驱动程序D.中断处理程序27.在TCP/IP模型中，负责端到端可靠传输的是（）。A.网络接口层B.网际层C.传输层D.应用层28.在OSI参考模型中，物理层传输的数据单位是（）。A.比特B.帧C.分组D.报文29.下列关于以太网地址的描述中，错误的是（）。A.以太网地址通常称为MAC地址B.MAC地址长度为48位C.MAC地址由网络管理员手动分配D.MAC地址固化在网卡的ROM中30.在IP数据报头部中，首部长度字段占4位，因此IP首部的最大长度为（）字节。A.15B.60C.64D.25531.若路由器R1的路由表中存在到达网络N的路由，其下一跳为R2。R1收到一个目的地址属于N的数据报，但R2不可达。此时R1应采取的措施是（）。A.丢弃该数据报，不发送ICMP报文B.丢弃该数据报，并向源点发送ICMP目的不可达报文C.广播该数据报D.将该数据报缓存，等待R2恢复32.TCP协议中，采用三次握手建立连接的主要目的是（）。A.防止已失效的连接请求报文段突然又传送到了服务端B.确保传输数据的可靠性C.进行流量控制D.进行拥塞控制33.在滑动窗口协议中，若发送窗口大小为4，发送方已发送0~3号帧，收到2号帧的确认，此时发送窗口的状态是（）。A.0~3B.1~4C.2~5D.3~634.DNS协议主要用于实现（）功能。A.域名到IP地址的解析B.IP地址到域名的解析C.域名到MAC地址的解析D.MAC地址到域名的解析35.在CSMA/CD协议中，为了检测冲突，发送数据前需要先进行载波监听。若采用10Base-T以太网，其争用期为（）。A.51.2μsB.5.12μsC.10.24μsD.25.6μs36.下列应用层协议中，使用UDP传输的是（）。A.HTTPB.SMTPC.FTPD.DNS37.在网络层，IP地址00/26所在的子网网络地址是（）。A.B.4C.28D.9238.路由选择协议RIP属于（）。A.内部网关协议，距离向量算法B.内部网关协议，链路状态算法C.外部网关协议，距离向量算法D.外部网关协议，链路状态算法39.在HTTP协议中，表示持久连接的头部字段是（）。A.Connection:Keep-AliveB.Connection:closeC.Keep-Alive:timeout=5D.Content-Length40.关于HTTPS协议，下列说法正确的是（）。A.HTTPS使用TCP端口80B.HTTPS在HTTP之上加了SSL/TLS安全层C.HTTPS不需要数字证书D.HTTPS的数据传输是明文传输二、综合应用题：41～47小题，共70分。41.（10分）设散列表的长度为13，散列函数H(k)(1)试采用线性探测再散列解决冲突，构造散列表。(2)求在等概率查找情况下查找成功的平均查找长度。42.（15分）设计一个算法，判断一棵给定的二叉树是否是完全二叉树。假设二叉树采用二叉链表存储结构，结点结构为(lchild,data,rchild)。请用C或C++语言编写该算法，并分析算法的时间复杂度。43.（10分）某计算机采用16位定长指令字格式，CPU内部有1个16位通用寄存器R0，8个8位通用寄存器R1~R8（R1~R8也可以组成4个16位寄存器对：(R1,R2),(R3,R4),(R5,R6),(R7,R8)）。指令格式如下：|15141312|111098|76543210||Op|Reg|Disp|其中Op为操作码，Reg为寄存器编号，Disp为形式地址。现设计一条转移指令JMP，其功能为(P(1)若该指令为直接寻址，请写出执行该指令所需的微操作流程。(2)若该指令为相对寻址，请写出有效地址E的计算表达式。44.（11分）假设某计算机的CPU主频为1GHz，某程序包含4类指令，其CPI和指令条数如下表所示：|指令类型|CPI|指令条数||A|1|400,000||B|2|200,000||C|3|100,000||D|4|50,000|(1)计算该程序的CPU执行时间。(2)若优化后，指令A的CPI变为0.5（通过流水线技术），其他指令CPI不变，则CPU执行时间减少了多少百分比？45.（9分）某系统有3个进程P1、P2、P3，共享4个同类资源R。进程P1需3个，P2需2个，P3需2个。请利用银行家算法分析系统是否安全。若此时P1发出请求1个资源，系统是否应该分配？请说明理由。46.（8分）在页式存储管理中，某作业的页表如下所示。假设页面大小为4KB，内存物理地址为32位。|页号|块号|有效位||0|3|1||1|7|1||2|--|0||3|5|1|(1)逻辑地址4096对应的物理地址是多少？(2)逻辑地址8195对应的物理地址是多少？若访问时发生缺页中断，请说明。47.（7分）主机A向主机B发送一个包含1200字节数据的TCP报文段。TCP的首部为20字节，IP首部为20字节，以太网MAC帧头为18字节（含帧头帧尾）。假设网络链路的MTU为1000字节（指IP层的数据报最大长度，含IP首部）。(1)主机A需要将该数据封装成多少个IP数据报发送？(2)第一个IP数据报的数据字段长度是多少？该数据报分片后，每个分片的总长度是多少？参考答案与解析一、单项选择题1.【答案】C【解析】栈是后进先出（LIFO）的线性表。如果输出序列的第一个元素是n（即最后入栈的元素），说明1到n−1都先入栈了，然后n出栈。此时栈中元素从底到顶依次为1,2,...,2.【答案】D【解析】在单链表中，若要在给定结点p之前插入结点s，需要找到p的前驱结点。由于单链表没有前驱指针，必须从头结点开始遍历寻找p的前驱q，然后执行`q->next=s;s->next=p;`。选项A是在p之后插入；选项B也是在p之后插入；选项C仅仅修改了指针p的指向，并没有将s链接到链表中，导致后续结点丢失。因此A、B、C均错误，选D。3.【答案】B【解析】设为叶子结点数，为度为1的结点数，为度为2的结点数。完全二叉树中，只能是0或1。根据性质=+1。总结点数N=++代入=−1，得即2+若=0，则2若=1，则2故叶子结点个数为501。4.【答案】A【解析】中二叉树的中序遍历顺序是：左子树->根->右子树。因此，在遍历序列中，根结点左边的都是左子树的结点，根结点右边的都是右子树的结点。5.【答案】C【解析】对于任意一棵二叉树，度为0的结点数（叶子数）和度为2的结点数之间的关系为=+1。题目中=10，所以=6.【答案】B【解析】在无向图中，每条边连接两个顶点，对这两个顶点的度数各贡献1。因此，所有顶点的度数之和等于边数的2倍。7.【答案】B【解析】广度优先搜索（BFS）是一种层序遍历，需要先访问近邻，再访问远邻。这符合队列“先进先出”（FIFO）的特性。深度优先搜索（DFS）使用栈。8.【答案】D【解析】在最坏情况下：冒泡排序：O简单选择排序：O直接插入排序：O快速排序：O虽然它们在最坏情况下同阶，但通常在考试比较中，若选项涉及具体算法且需选“最低”或相对较好的，需注意常数因子。但这里严格按大O记号都是O()。不过，在部分教材语境下，若题目问“时间复杂度最低”，且选项均为O()，可能存在陷阱。但若从平均情况看，快速排序是O(nlogn)。题目限定“最坏情况下”。实际上，堆排序和归并排序在最坏情况下也是O自我修正：严格按照题目文字“最坏情况下”，A、B、C、D均为O(重新审视题目设定：题目明确“最坏情况下”。那么O(9.【答案】B【解析】哈希表的平均查找长度（ASL）取决于：哈希函数是否均匀（影响冲突概率）、处理冲突的方法（解决冲突的能力）以及装填因子α=10.【答案】C【解析】除留余数法中，为了减少冲突，模数p通常选择小于等于表长m的最大素数，或者是不包含小于20的质因数的合数。这样能使哈希函数的值分布更均匀。11.【答案】C【解析】冯·诺依曼结构计算机中，指令和数据不加区分地存储在内存中。CPU通过取指周期（Fetch）将内存中的内容取出到指令寄存器IR，此时将其视为指令；在执行周期（Execute）根据指令操作码将内存内容取出到通用寄存器，此时将其视为数据。因此，是通过指令周期的不同阶段来区分的。12.【答案】A【解析】Cache容量16KB=16×块大小64B。Cache块数=16×4路组相联，即每组4块。组数=256/组号需要lo13.【答案】C【解析】IEEE754标准中，尾数部分通常采用隐含的规格化表示。对于单精度，尾数域存储的是小数部分，隐含了最高位的1（对于正规化数）。虽然存储的是原码形式的小数部分，但说“尾数采用原码表示”通常指整个数值的表示方式，容易引起歧义。更准确地说，IEEE754的尾数部分是符号-幅度表示的一部分。但选项C说“尾数采用原码表示”在严格意义上是不够精确的，通常说尾数是纯小数，且隐含最高位。相比之下，选项A、B、D都是正确的描述。选项C中“尾数采用原码表示”是干扰项，因为标准的浮点数表示中，尾数通常与符号位配合，构成“符号-原码”或“符号-补码”，但IEEE754实际上是符号+阶码(移码)+尾数(原码小数)。实际上，IEEE754的尾数域就是原码的小数部分。修正：实际上IEEE754的尾数域确实是原码的小数部分。那哪个是错的？再看D：“规格化浮点数的尾数最高有效位为1”。在IEEE754中，正规化数的尾数隐含了一个前导1，即1.再看B：“阶码采用移码表示”。正确，偏置值为127或1023。再看C：“尾数采用原码表示”。在计算机组成原理中，原码通常指包含符号位的表示。而在IEEE754中，符号位是单独的，尾数域只是纯小数部分。因此说“尾数采用原码表示”略显不严谨，但常被接受。寻找更明显的错误：IEEE754中，尾数部分是无符号的纯小数（配合单独的符号位）。原码通常指S+重新确认：IEEE754标准规定：符号位：1位。阶码：移码。尾数：原码（对于非规格化数和0，特殊处理；对于规格化数，是1.是否存在更绝对的错误？选项D：“规格化浮点数的尾数最高有效位为1”。对于非零规格化数，是的。对于0，不是。但通常指一般情况。实际上，很多教材指出：IEEE754中，尾数采用原码表示。所以C是对的。那么错的是D？因为对于非规格化数（阶码全0），尾数最高有效位不是1。但题目说“规格化浮点数”，限定条件是对的。等等，再仔细看C。在IEEE754中，尾数是1.结论：选C。14.【答案】A【解析】指令寄存器IR用于存放当前正在执行的指令。若指令字长为32位，则IR应为32位。程序计数器PC用于存放下一条指令的地址。若按字编址，且指令字长32位（4字节），则PC每次加1。因为内存单元大小为32位，地址的编号是0,1,2...。所以PC的位数取决于内存单元的个数。题目未给出内存容量，但通常PC的宽度与地址总线宽度一致。这里题目说“字长32位，存储字长32位，按字编址”。这意味着一个地址对应一个32位的字。如果系统是32位系统，地址总线通常是32位的。因此PC是32位。选项中A最合理（32,32）。若按字节编址，PC需要能寻址字节，PC宽度需更大。但这里是按字编址，PC存储的是字地址。15.【答案】C【解析】系统总线的数据线用于传输数据信息。数据可以是CPU到存储器（写），也可以是存储器到CPU（读），或者是I/O设备与内存之间的传输（DMA）。因此，数据线上的信息是可以双向传输的。16.【答案】B【解析】硬布线控制器：采用组合逻辑电路设计，速度快（因为由硬件直接产生控制信号），但结构复杂，设计困难，不易修改或扩展指令系统。微程序控制器：将微指令写入控制存储器，通过读取微指令产生控制信号。速度较慢（因为要多访问一次控存），但规整性好，易于修改和扩充。因此，硬布线控制器的优点是速度快。17.【答案】B【解析】流水线的时钟周期取决于各段中执行时间最长的那个阶段，即瓶颈阶段。这里最大时间是30ns。最大吞吐率是指流水线达到稳定状态后，单位时间内能完成的任务数量。即=。Δt=IPS=33.3MIPS。18.【答案】D【解析】程序查询方式：CPU不断轮询，效率最低。程序中断方式：I/O操作时CPU可做其他事，但中断处理仍需CPU参与，适合中低速设备。DMA方式：数据传输不经过CPU，直接在内存和外存间进行，仅在开始和结束时需CPU干预，适合高速块传输。通道方式：通道具有独立执行I/O指令的能力，CPU只需发出I/O命令，通道完全接管I/O管理，CPU效率最高。19.【答案】D【解析】操作系统管理硬件资源（A对）。操作系统提供系统调用接口，作为用户程序与硬件之间的接口（B对）。操作系统提供保护机制（C对）。操作系统不直接执行用户编写的应用程序。用户应用程序由CPU执行，操作系统负责调度和提供环境，但不是执行者本身（在CPU指令执行层面）。且“直接执行”通常指CPU机器码执行，OS只是调度者。D错。20.【答案】B【解析】进程是资源分配的基本单位。线程是调度的基本单位（也称为轻量级进程）。线程不拥有系统资源（除必不可少的寄存器、栈等），而是共享其所属进程的资源。线程是可被调度的实体。21.【答案】B【解析】V操作是释放资源，P操作是申请资源。如果进程P1先执行P操作，申请资源成功，然后P0执行V操作，释放资源。这没问题。但如果P0先执行V操作，信号量值+1（假设初值为0，变为1）。然后P1执行P操作，信号量-1（变为0），申请成功。这种描述没有体现出互斥或同步的临界区保护。题目描述“P0对V执行V操作，P1对V执行P操作”，这实际上是简单的同步信号量。但是，如果题目隐含V是互斥信号量（初值为1），且操作涉及临界区：P0:V(S)(释放)P1:P(S)(申请)如果P0和P1并发，且原本S=0（被锁），P0执行V(S)唤醒P1，这是正确的同步。然而，如果V是普通的整型变量，且V操作是`V++`，P操作是`while(V<=0);V--`，那么并发执行`V++`和`V--`（或检查与自减）如果不加原子保护，会发生与时间有关的错误。题目语境：通常在OS考题中，V和P指的是信号量操作。信号量操作本身是原子的。再看题目：“进程P0对V执行V操作，进程P1对V执行P操作”。这看起来像是P1在等待P0发送信号。是否有陷阱？如果P1执P操作时，V值为0，P1阻塞。若P0此时还没运行，V值保持0。P1永远阻塞？不，P0迟早会运行。可能发生的情况：实际上，这种简单的同步模型如果不配合具体的临界区逻辑，很难说“一定”发生错误。但是，选项A“不会发生与时间有关的错误”是错误的。因为如果信号量实现不正确（非原子），就会发生。考虑互斥场景：如果V是互斥锁，初值为1。P0执行V(unlock)，P1执行P(lock)。如果P0不持有锁就V，会导致锁变量错误增加（如从1变2），破坏互斥语义。标准解释：PV操作必须成对出现用于临界区。如果P0只做V，P1只做P，且初值为0，这是简单的同步。但如果初值为1（互斥锁），P0误用V（释放未持有的锁），会导致V值变为2，P1申请后变为1，两个进程可能同时进入临界区（如果其他逻辑允许），从而发生错误。综上，这种不成对或乱序使用PV操作，很可能发生与时间有关的错误。选B。22.【答案】D【解析】页表项总数=逻辑地址空间大小/页面大小。逻辑地址空间大小取决于CPU的地址总线宽度（虚拟地址空间）。题目只说“页面大小增加一倍”，未提及逻辑地址空间是否变化。如果逻辑地址空间固定（例如32位地址空间），页面大小加倍，页数减半。但如果页面大小改变的同时，系统架构也变了（例如逻辑地址空间变了），则不确定。不过，通常此类题目默认逻辑地址空间不变。若如此，页表项总数减少。但是，选项中有“减少一倍”（即变为原来的1/2）。检查选项D：“可能增加也可能减少，取决于内存大小”。页表项总数取决于虚拟地址空间大小和页面大小，与物理内存大小无直接关系（虽然物理内存限制了能同时装入的页数，但不影响页表项的总数）。修正思路：页表项总数=。若页面大小×2，页数/2为何有D？题目问“页表项的总数”。页表是存储在内存中的。页表的大小=页表项总数×页表项大小。也许题目问的是“页表的大小”？不，是“页表项的总数”。如果是“页式存储管理系统”，通常指虚拟内存管理。虚拟地址空间是固定的。重新审题：“若页面大小增加一倍”。假设原页面4KB，现8KB。虚拟地址32位(4GB)。原页数=1M。现页数=512所以是减少了。选项B是“减少一倍”（即减半）。这在数学表述上“减少一倍”通常指变为0，但在口语中常指减半。严谨应为“减少为原来的一半”。再看D。如果题目隐含的是“物理页表项总数”（即物理内存能容纳的页框数对应的页表项？），那取决于物理内存。但通常指逻辑页表。权衡：选B还是D？在408历年真题中，类似题目通常选“减少”或“减少一半”。若B表述为“减少一倍”，虽不严谨但可能是预期答案。然而，如果逻辑地址空间可变（如从32位变为64位），则可能增加。但题目未给条件。最可能的情况：题目考察逻辑地址空间固定的情况。选B。但是，再看一眼选项D。“取决于内存大小”。如果是指“页表本身占用的内存大小”，那取决于页表项总数。这有点循环论证。另一种理解：如果系统是物理内存扩充，导致页面大小调整？结论：在常规操作系统理论中，虚拟地址空间由CPU架构决定，是固定的。页面大小变大，页数必然变少。选B。23.【答案】C【解析】虚拟存储器的大小取决于CPU能生成的虚拟地址范围。虚拟地址的位数决定了虚拟地址空间的大小。例如，32位CPU，虚拟地址空间为=4GB。这就是虚拟存储器的最大理论大小。物理内存和辅助存储器是实际容纳数据的硬件，但虚拟存储器的“编址空间”由地址字长决定。24.【答案】A【解析】SPOOLing(SimultaneousPeripheralOperationOnLine)技术的核心是输入井和输出井。输出井通常是在磁盘上开辟的固定区域。用户进程的打印数据不是直接送给打印机，而是先输出到“输出井”（磁盘缓冲区），然后由SPOOLing守护进程控制打印机从输出井中取出数据打印。25.【答案】A【解析】文件控制块（FCB）是操作系统为了管理文件而设置的数据结构，包含了文件的元数据（文件名、文件大小、文件位置、访问控制信息、创建时间等）。访问控制信息（读写权限等）是FCB的一部分。在Unix/Linux中，这部分信息被称为inode（索引结点），但inode也是FCB的一种实现形式（将文件名与描述分离）。广义上讲，都存储在文件控制块结构中。26.【答案】C【解析】I/O软件层次从高到低：用户级I/O软件->设备独立性软件->设备驱动程序->中断处理程序。设备驱动程序是直接与硬件控制器交互的软件，负责将上层通用的请求转换为硬件具体的命令和寄存器操作。27.【答案】C【解析】网络接口层（网络层）负责IP寻址和路由，不保证可靠性。传输层提供端到端的服务。TCP是传输层协议，提供面向连接的、可靠的字节流服务。28.【答案】A【解析】物理层传输的是比特流。数据链路层传输的是帧。网络层传输的是分组/数据报。传输层及以上传输的是报文或段。29.【答案】C【解析】MAC地址由网卡生产厂家在生产时烧录在网卡的ROM中，是全球唯一的（在理论范围内）。它不是由网络管理员手动分配的（IP地址才是）。30.【答案】B【解析】IP首部长度字段占4位，单位是4字节（32位字）。最大值为=15因此，IP首部的最大长度为15×固定首部为20字节，选项最大40字节用于选项。31.【答案】B【解析】当路由器检测到下一跳不可达时，它无法将数据报转发出去。根据ICMP协议机制，路由器应丢弃该数据报，并向源点发送一个“ICMP目的不可达”报文（具体代码可能是“主机不可达”或“网络不可达”），以便源主机知道传输失败。32.【答案】A【解析】“已失效的连接请求报文段”是指：客户端发送了连接请求SYN，但因故在网络节点滞留了。客户端超时重发了SYN，建立了连接，关闭连接后，那个滞留的旧SYN才到达服务端。如果不采用三次握手，服务端收到旧SYN后误以为是新的连接请求，于是发送确认ACK，建立连接，并一直等待客户端数据。客户端不理会，导致服务端资源浪费。三次握手可以防止这种情况：服务端收到旧SYN，回复SYN+ACK（seq=x,ack=y+1）。客户端收到后，发现ack=y+1不是自己期望的（或者自己并未处于连接请求状态），于是发送RST报文拒绝连接。33.【答案】B【解析】发送窗口大小为4，意味着可以连续发送4个帧而无需确认。已发送0~3号帧。此时窗口包含[0,1,2,3]。收到2号帧的确认（ACK2，表示2号及之前的帧都已正确接收）。此时，0号和1号帧也被确认了。窗口应该向右滑动，滑过0,1,2。新的窗口起始位置为3。窗口大小仍为4，所以新窗口包含[3,4,5,6]。但是，通常“收到2号帧的确认”意味着ACK=3（累积确认），或者ACK=2（表示期望收到2号）。标准TCP是累积确认，ACK2表示期望收到2，即1已收到。在滑动窗口习题中，通常“收到k号帧的确认”是指k号帧已妥收。若0~3已发，收到ACK2（表示0,1,2收到）。窗口左边界由0变为3。窗口内容变为3,4,5,6。选项B是1~4。这意味着只收到ACK0？或者窗口滑动逻辑不同？标准逻辑：窗口左边界=Max(已收到的确认序号)。若收到ACK2，左边界=2+1=3。窗口=[3,4,5,6]。检查选项：无3~6。重新理解：如果“收到2号帧的确认”是指ACK=2（期望收到2号），即0,1号收到。那么窗口左边界变为2。窗口=[2,3,4,5]。再理解：如果题目意思是“收到了对2号帧的确认”，即ACK=3。那么窗口左边界变为3。再看选项：A(0~3),B(1~4),C(2~5),D(3~6)。如果初始是0~3。若收到ACK1（确认0号），窗口变为1~4。选B。若收到ACK2（确认0,1），窗口变为2~5。选C。若收到ACK3（确认0,1,2），窗口变为3~6。选D。题目说“收到2号帧的确认”。通常指ACK指向2的下一个，即确认了2。所以应该是3~6。但是，如果题目表述为“收到了确认号为2的帧”，即ACK=2，表示0,1收到，窗口变为2~5。中文歧义：“收到2号帧的确认”="ReceivedacknowledgementforFrame2"。这意味着Frame2isacknowledged。所以ACK应该是3。然而，如果选项D是3~6，而B是1~4。通常这类题目可能考察的是ACK=1的情况？或者题目有误？假设题目是“收到确认号为2的报文”（ACK=2），则选C。假设题目是“收到2号帧的确认”（Frame2ACKed），则选D。观察选项分布：1,2,3,4,5,6都有。让我们假设最常见的情况：收到ACK2（表示期望收到2，即0,1收到）。窗口滑动2格。0~3->2~5。选C。理由：在很多教材中，确认号是期望收到的序号。如果收到ACK=2，说明0,1已妥。修正：题目原文“收到2号帧的确认”。更倾向于Frame2isdone。即ACK=3。对比真题：2011年真题类似题，若收到ACK1，窗口变为1~4。若收到ACK2，窗口变为2~5。这里题目明确说是“2号帧的确认”。如果是指ACK包中的确认号是2，则选C。如果是指确认了2号帧，则选D。倾向于选C，因为通常描述“收到ACKx”指的是收到确认号为x的报文。题目描述虽略有不同，但按ACK=2理解更符合“确认号”的考察点。再修正：让我们看数据流。发了0,1,2,3。收到ACK2。说明0,1到了。窗口应该从0开始，移过0,1。剩下2,3还在窗口内，新申请4,5。窗口[2,3,4,5]。即2~5。选C。34.【答案】A【解析】DNS(DomainNameSystem)的主要功能是将主机域名解析为IP地址。虽然它也支持反向解析（IP到域名），但主要功能是正向解析。35.【答案】A【解析】10Base-T以太网的争用期（即冲突窗口）是指发送方检测冲突的最长时间。对于10Mbps以太网，争用期通常定义为发送512比特所需的时间。512b36.【答案】D【解析】HTTP(80),SMTP(25),FTP(20/21)都使用TCP。DNS(53)主要使用UDP（虽然也可以使用TCP，但在标准查询中默认使用UDP）。37.【答案】B【解析】IP地址00。子网掩码/26，即92。192的二进制是11000000。100的二进制是01100100。前26位是网络号。第4字节前2位是子网号。100的前2位是01。01对应的十进制是64（即01000000）。所以子网网络地址是4。38.【答案】A【解析】RIP(RoutingInformationProtocol)是内部网关协议（IGP），用于自治系统内部。RIP采用距离向量算法。OSPF也是IGP，但采用链路状态算法。BGP是外部网关协议（EGP）。39.【答案】A【解析】HTTP/1.1默认支持持久连接（PersistentConnection）。使用`Connection:Keep-Alive`来保持连接。`Connection:close`表示关闭连接。40.【答案】B【解析】HTTPS使用TCP端口443（不是80）。HTTPS=HTTP+SSL/TLS，提供加密和身份认证。HTTPS需要数字证书来验证服务器身份。HTTPS数据是加密传输的，不是明文。二、综合应用题41.【答案】(1)散列表构造如下（线性探测）：表长13。H(16)=3H(74)=9H(60)=8H(43)=4H(54)=2H(90)=12H(46)=7H(31)=5H(29)=3(冲突)，探测4(冲突)，探测5(冲突)，探测6(空)->下标6H(40)=1下标:0123456789101112内容:-405416433129466074--90(2)查找成功的平均查找长度ASL：16:1次74:1次60:1次43:1次54:1次90:1次46:1次31:1次29:4次(3,4,5,6)40:1次总次数=1*9+4=13。元素个数=10。AS42.【答案】算法思想：完全二叉树的定义是：若深度为h，除第h层外，其他各层结点数都达到最大，且第h层的结点都集中在左边。在层序遍历（广度优先遍历）过程中，如果遇到了一个空结点，那么其后应该所有的结点都是空结点。如果在空结点之后又发现了非空结点，则不是完全二叉树。算法代码（C++）：```cppboolIsCompleteBinaryTree(BiTreeT){if(T==NULL)returntrue;//空树是完全二叉树std::queue<BiNode*>Q;Q.push(T);boolflag=false;//标记是否遇到过空结点while(!Q.empty()){BiNode*p=Q.front();Q.pop();if(p==NULL){flag=true;//遇到空结点，标记置为true}else{if(flag){//如果之前已经遇到过空结点，现在又遇到非空结点returnfalse;}//继续将左右孩子入队（包括空孩子也要入队，以保持层序结构）Q.push(p->lchild);Q.push(p->rchild);}}returntrue;}```时间复杂度分析：算法需要对二叉树的每个结点访问一次，且入队出队操作均为O(1)。设结点数为n空间复杂度取决于队列的最大长度，最坏情况下（最后一层结点最多），队列长度为O(43.【答案】(1)直接寻址方式下，有效地址E=微操作流程如下：1.取指：PC→MAR;2.分析周期：识别为JMP指令。3.执行周期：取形式地址：IR假设Disp是直接地址：I假设题目意指Disp存在内存单元中（直接寻址的一种定义，操作数在内存，Disp是内存地址）：IR.Di根据题目格式：指令包含Disp字段。对于转移指令，通常Disp是偏移量或绝对地址。若为直接寻址的绝对转移：微操作：IR.(2)相对寻址方式下，有效地址E的计算表达式为：E注：通常PC的值在执行该指令时已经指向下一条指令。如果Disp是相对于当前指令的偏移，则可能是(PC)44.【答案】(1)计算CPU执行时间：总指令数IC=400,平均CPI：C===CPU时间T主频1GHz，时钟周期=s=T=(2)优化后：指令A的CPI变为0.5。新总周期数=0.5=200000新CPU时间=1减少的百分比=×=×45.【答案】利用银行家算法分析：系统资源总数R=进程最大需求Max：P1:3,P2:2,P3:2。当前已分配Allocation：题目未给出已分配情况，假设初始状态为0（或者需要根据上下文推断，通常此类题目若未给出已分配，则假设初始时刻都未分配，或者需要计算“还需”）。修正：题目说“P1需3，P2需2，P3需2”。这是Max。假设当前Available=4。Need矩阵=Max矩阵。Need:P1(3),P2(2),P3(2)。安全性检查：1.尝试分配给P2：Available(4)>=P2.Need(2)。假设分配给P2，Availab