考研真题-408统考-计算机研究生考试真题 - Dotcpp编程

Dotcpp / 试卷列表

试卷分类

考研真题

编号试卷名称

题数

编号试卷名称

题数

最新题目更多

（本题 9 分）某公司在承建国家重大工程项目时，工程部需要较长时间驻扎在偏远山区，工程部网络需要连接公司总部网络。假设综合考虑方案的技术可行性、安全性与经济成本等因素后，决定租用我国自主建设的天通一号卫星通信链路，连接工程部网络的路由器 R1 和公司总部网络的路由器 R2，如图所示。S1 和 S2 为千兆以太网交换机；TR1 和 TR2 是卫星信号地面收发设备，实现全双工调制解调。天通一号卫星轨道高度是 36000km，电磁波信号传播速度为 300000km/s。租用的卫星链路为 R1 和 R2 之间提供对称全双工信道，每个方向的数据传输速率为 200kb/s。请回答下列问题：（1）若忽略卫星信号中继以及 TR1 和 TR2 调制解调的时间开销，则 R1 到 R2 之间卫星链路的单向传播时延是多少？主机 H 向总部服务器传输数据时可以达到的最大吞吐量是多少？若忽略各层协议数据包的首部开销以及以太网内的传播时延，则主机 H 向总部服务器上传一个 4000B 大小的工程进度报告文件，至少需要多长时间？（3 分）（2）现需要基于 GBN 滑动窗口协议为卫星链路设计单向可靠的数据链路层协议 SLP，支持 R1 向 R2 发送数据，SLP 数据帧长为 1500B，忽略 ACK 帧长度。若要求 SLP 的单向信道利用率不低于 80%，则 SLP 的发送窗口至少为多少？SLP 帧的序号字段至少需要多少位？（3 分）（3）若公司总部为工程部网络分配的 IP 地址空间是 10.10.10.0/24，工程部进一步将该 IP 地址空间分配给 3 个子网，其中生活区子网可分配 IP 地址数不少于 120 个，作业区子网和管理区子网可分配 IP 地址数均不少于 60 个，且主机 H 已正确配置了 IP 地址，则作业区子网、管理区子网和生活区子网的子网地址分别是什么（给出 CIDR 地址形式）？（3 分）
（本题 8 分）某系统中进程的虚拟地址空间包括内核区、用户栈、运行时堆、可读写数据段、只读代码段等区域，其布局如图所示，图中阴影部分表示未占用区域。现有 C 语言程序的部分代码如下：char*ptr; void main() { int length; ptr=(char *)malloc(100); scanf("%s", ptr); length=strlen(ptr); printf("length=%d\n", length); free(ptr); }请回答下列问题：（1）上述程序执行时，其进程控制块位于哪个区域？执行 scanf () 等待键盘输入时，该进程处于什么状态？（2 分）（2）main () 函数的代码位于哪个区域？其直接调用的哪些函数的功能需要通过执行驱动程序实现？（3 分）（3）变量 ptr 被分配在哪个区域？若变量 length 没有被分配在寄存器中，则会被分配在哪个区域？ptr 指向的字符串位于哪个区域？（3 分）
（本题 7 分）甲、乙、丙三人一起植树，甲负责挖树坑，乙负责将树苗放入树坑中并填土，丙负责为新种的树苗浇水。植树的步骤依次为：挖树坑、放树苗、填土和浇水。现有铁锹和水桶各 1 个，铁锹用于挖树坑和填土，水桶用于浇水。当树坑的数量小于 3 时，甲才可以挖树坑。假设初始时树坑的数量为 0，铁锹和水桶均可用。请定义尽可能少的信号量，用 wait ()、signal () 操作描述植树过程中三人之间的同步或互斥关系，并说明所用信号量的作用及其初值。
（本题 11 分）对于题 43 中计算机 M 和程序 P，假定 P 的部分机器级代码如（a）图所示，其中，R0~R4 为通用寄存器，SEXT 表示按符号扩展；M 中补码除法器逻辑结构如（b）图所示。请回答下列问题：（1）若执行题（a）图中 idiv 指令的除运算时，d [i]=0x87654321、x=0xff，则补码除法器中寄存器 R、Q 和 Y 的初始内容分别是什么（用十六进制表示）？题（b）图中哪个部件包含计数器？在补码除法器执行过程中，由 ALUop 所控制的 ALU 运算有哪几种？（6 分）（2）假设 idiv 指令执行过程中会检测并触发除法异常，则执行 idiv 指令时，哪些情况下会发生除法异常（要求给出此时 d [i] 和 x 的十六进制表示机器数）？发生除法异常时，在异常响应过程中 CPU 需要完成哪些操作？（5 分）
（本题 12 分）现有 C 语言程序 P 的部分代码如图所示。假定运行程序 P 的计算机 M 字长为 32 位，按字节编址，数据 Cache 的数据区大小为 32KB，采用 8 路组相联映射方式，主存块大小为 64B，Cache 的命中时间为 2 个时钟周期，缺失损失为 200 个时钟周期；采用页式虚拟存储管理方式，页大小为 4KB。数组 d 的起始虚拟地址 VA₃₁~VA₀为 01800020H。请回答下列问题：（1）主存地址中 Cache 组号字段和块内地址字段分别占几位？虚拟地址中哪些位可作为 Cache 索引？（3 分）（2）d [100] 的虚拟地址为多少？d [100] 所在主存块对应的 Cache 组号是多少？（2 分）（3）假定执行 for 语句时对应代码已在 Cache，变量 i 和 x 已装入寄存器，数组 d 已调入主存但不在 Cache，则 d [0] 在其所在主存块内的偏移量是多少（用十六进制表示）？for 语句执行过程中，访问数组 d 的 Cache 缺失率和数组元素的平均访问时间分别是多少（Cache 缺失率的计算结果要求用百分比表示，保留两位小数）？（5 分）（4）数组 d 分布在几个页中？若执行 for 语句时对应代码已在主存，但数组 d 还未调入主存，则执行 for 语句过程中，访问数组 d 所引起的缺页次数是多少？（2 分）
（本题 10 分）某工程包含 12 个活动，使用下图所示的 AOE 网描述，图中各边上标注了活动及其持续时间。请回答下列问题（活动均用活动名表示）：（1）完成该工程的最短时间是多少？哪些活动是关键活动？（3 分）（2）若以最短时间完成工程，则与活动 e 同时进行的活动可能有哪些？（3 分）（3）时间余量最大的活动是哪个？其时间余量是多少？（2 分）（4）假设工程从时刻 0 启动，因某种原因，活动 b 在时刻 6 开始。为了保证工程不延期，在其他活动持续时间均不变的情况下，b 的持续时间最多是多少？若不改变 b 的持续时间，则压缩哪个活动的持续时间也能保证工程不延期？（2 分）
（本题 13 分）设有两个长度均为 n 的一维整型数组 A 和 res，对数组 A 中的每个元素 A [i]，计算 A [i] 与 A [j]（0≤i≤j≤n-1）乘积的最大值，并将其保存到 res [i] 中。例如，若 A [ ]={1,4,-9,6}，则得到 res [ ]={6,24,81,36}。现给定数组 A，请设计一个时间和空间上尽可能高效的算法 calMulMax，求 res 中各元素的值。函数原型为：void calMulMax (int A [ ],int res [ ],int n)。要求如下：（1）给出算法的基本设计思想。（4 分）（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。（7 分）（3）说明你所设计算法的时间复杂度和空间复杂度。（2 分）
网络空间是继陆海空天之后的“第五疆域”，网络技术是网络疆域建设与治理的基础。路由算法与协议是网络核心技术之一，对其准确认知、合理选择与应用，对于网络建设十分重要。假设现有互联网中的 4 个自治系统如题 47 图所示。其中，AS1 运行内部网关协议RIP；AS3 规模较小，自治系统内任意两个主机间通信，经过路由器数量不超过 15 个；AS4 规模较大，自治系统内任意两个主机间通信，经过路由器数量可能超过 20 个。请回答下列问题。（1）若仅有RIP 和OSPF 内部网关协议供选择，则AS4 应该选择哪个协议？（2）若 AS3 中的某主机向本自治系统内另一主机发送 1 个 IP 分组，为确保该 IP 分组能够被正常接收，则该IP 分组的初始TTL 值应该至少设置为多少？（3）假设AS1 中的路由器同一时刻启动，启动后立即构建并交换初始距离向量，之后，每隔 30s交换一次最新的距离向量。则从交换初始距离向量时刻算起，R11~R16 路由器均获到达网络210.2.4.0/24 的正确路由，至少需多长时间？（4）R44向R13 通告到达网络 136.5.16.0/20 路由时，由BGP 协议哪类会话完成？通过哪个BGP报文通告？R13 通过BGP 协议的哪类会话将该网络可达性信息通告给R14和R15？（5）若 R14 和 R15 均收到分别由 R11、R12、R13 通告的到达网络 136.5.16.0/20 的可达性信息为：则在无策略约束情况下，R14和R15 更新路由表后，各自路由表中到达网络 136.5.16.0/20 路由的下一跳分别是什么（用路由器名称表示）？
计算机系统中的进程之间往往需要相互协作以完成一个任务。在某网络系统中，缓冲区B 用于存放一个数据分组，对B 的操作有C1、C2和C3。C1 将一个数据分组写入B 中，C2从B 中读出一个数据分组，C3对B 中的数据分组进行修改。要求B 为空时才能执行C1，B 非空时才能执行C2和C3。（1）假设进程P1和P2 均需要执行C1，实现C1 的代码是否为临界区？为什么？（2）假设B 初始为空，进程P1执行C1 一次，进程P2执行C2 一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2 之间的同步或互斥关系，说明所用信号量的作用及其初值。（3）假设B 初始不为空，进程P1和P2 各执行C3 一次。请定义尽可能少的信号量，并用wait()、signal()操作描述进程P1和P2 之间的同步或互斥关系，说明所用信号量的作用及其初值。
某计算机按字节编址，采用页式虚拟存储管理方式，虚拟地址和物理地址的长度均为 32位，页表项的大小为 4 字节，页大小为 4MB，虚拟地址结构如下。进程P 的页表起始虚拟地址为B8C0 0000H，被装载到从物理地址 6540 0000H 开始的连续主存空间中。请回答下列问题，要求答案用十六进制表示。（1）若CPU 在执行进程P 的过程中，访问虚拟地址 1234 5678H 时发生了缺页异常，经过缺页异常处理和MMU 地址转换后得到的物理地址是BAB4 5678H，在此次缺页异常处理过程中，需要为所缺页分配页框并更新相应的页表项，则该页表项的虚拟地址和物理地址分别是什么？该页表项中的页框号更新后的值是什么？（2）进程P 的页表所在页的页号是什么？该页对应的页表项的虚拟地址是什么？该页表项中的页框号是什么？
对于题 43 中的计算机M，C 语言程序P 包含的语句“sum+=a[i];”在M 中对应的指令序列S 如下。slli r4, r2, 2 //R[r4]←R[r2]<<2 add r4, r3, r4 //R[r4]←R[r3]+R[r4] lw r5, 0(r4) //R[r5]←M[R[r4]+0] add r1, r1, r5 //R[r1]←R[r1]+R[r5]已知变量i、sum 和数组a 都为int 型，通用寄存器r1~r5 的编号为 01H～05H。请回答下列问题。（1）根据指令序列S 中每条指令的功能，写出存放数组a 的首地址、变量i 和sum 的通用寄存器编号。（2）已知M 为小端方式计算机，采用页式存储管理方式，页大小为 4KB。若执行到指令序列S中第 1 条指令时，i = 5且r1和r3 的内容分别为 0000 1332H 和 0013DFF0H，从地址 0013DFF0H 开始的存储单元内容如题 44 图所示，则执行“sum+=a[i];”语句后，a[i]的地址、a[i]和sum 的机器数分别是什么（用十六进制表示）？a[i]所在页的页号是多少？此次执行中，数组a至少存放在几页中？（3）指令“slli r4, r2, 2”的机器码是什么（用十六进制表示）？若数组a 改为short 类型，则指令序列S 中slli 指令的汇编形式应是什么？
假定计算机M 字长为 32 位，按字节编址，采用 32 位定长指令字，指令add、slli 和 lw 的格式、编码和功能说明如题 43 图（a）所示。其中，R[x]表示通用寄存器x 的内容，M[x]表示地址为x 的存储单元内容，shamt 为移位位数，imm 为补码表示的偏移量。题 43 图（b）给出了计算机M 的部分数据通路及其控制信号（用带箭头虚线表示），其中，A 和B 分别表示从通用寄存器rs1和rs2 中读出的内容；IR[31:20]表示指存器中的高 12 位；控制信号Ext 为 0、1 时扩展器分别实现零扩展、符号扩展，ALUctr 为 000、001、010 时ALU 分别实现加、减、逻辑左移运算。请回答下列问题。（1）计算机M 最多有多少个通用寄存器？为什么shamt 字段占 5 位？（2）执行add 指令时，控制信号ALUBsrc 的取值应是什么？若rs1和rs2 寄存器内容分别是8765 4321H 和 9876 5432H，则add 指令执行后，ALU 输出端F、OF 和CF 的结果分别是什么？若该add 指令处理的是无符号整数，则应根据哪个标志判断是否溢出？（3）执行slli 指令时，控制信号Ext 的取值可以是 0 也可以是 1，为什么？（4）执行lw 指令时，控制信号Ext、ALUctr 的取值分别是什么？（5）若一条指令的机器码是A040A103H，则该指令一定是lw 指令，为什么？若执行该指令时，R[01H]=FFFF A2D0H，则所读取数据的存储地址是什么？
将关键字序列 20, 3, 11, 18, 9, 14, 7 依次存储到初始为空、长度为 11 的散列表HT 中，散列函数H(key) = (key×3)%11。H(key)计算出的初始散列地址为H0，发生冲突时探查地址序列是H1 , H2 , H3 , …，其中，Hk =(H0 + k2)%11，k = 1, 2, 3, …。请回答下列问题。（1）画出所构造的HT，并计算HT 的装填因子。（2）给出在HT 中查找关键字 14 的关键字比较序列。（3）在HT 中查找关键字 8，确认查找失败时的散列地址是多少？
2023 年 10 月 26 日，神舟十七号载人飞船发射取得圆满成功，再次彰显了中国航天事业的辉煌成就。载人航天工程是包含众多子工程的复杂系统工程，为了保证工程的有序开展，需要明确各子工程的前导子工程，以协调各子工程的实施。该问题可以简化、抽象为有向图的拓扑序列问题。已知有向图G 采用邻接矩阵存储，类型定义如下。typedef struct //图的类型定义 { int numVertices, numEdges;//图的顶点数和有向边数 char VerticesList[MAXV];//顶点表，MAXV为已定义常量 int Edge[MAXV][MAXV];//邻接矩阵 }MGraph;请设计算法int uniquely(MGraph G)，判定G 是否存在唯一的拓扑序列，若是，则返回1，否则返回 0。要求如下。（1）给出算法的基本设计思想。（2）根据设计思想，采用C 或C++语言描述算法，关键之处给出注释。
甲乙双方均采用后退N帧协议(GBN)进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000B。Sx, y和Rx, y分别表示甲方和乙方发送的数据帧，其中x是发送序号，y是确认序号(表示希望接收对方的下一帧序号)；数据帧的发送序号和确认序号字段均为3比特。信道传输速率为100Mbps，RTT=0.96ms。下图给出丁甲方发送数据帧和接收数据帧的两种场景，其中t0为初始时刻，此时甲方的发送和确认字号均为0，t1时刻甲方有足够多的数据待发送。请回答下列问题。（1）对于图(a)，t0时刻到t1时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少?正确接收的是哪几个帧(请用Sx, y形式给出)?（2）对于图(a)，从t1时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧?其中第一个帧和最后一个帧分别是哪个(请用Sx, y形式给出)?（3）对于图(b)，从t1时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧?重发的第一个帧是哪个(请用Sx, y形式给出)?（4）甲方可以达到的最大信道利用率是多少?答：（1）t0时刻到t1时刻期间，甲方可以断定乙方已正确接收了3个数据帧，(1分)分别是S0,0、S1,0、S2,0。(1分)R3,3说明乙发送的数据帧确认号是3，即希望甲发送序号3的数据帧，说明乙已经接收了序号为 0~2的数据帧。（2）从t1时刻起，甲方最多还可以发送5个数据帧，(1分)其中第一个帧是S5,2，(1分)最后一个数据帧是S1,2。(1分)发送序号3位，有8个序号。在GBN协议中，序号个数>=发送窗口+1，所以这里发送窗口最大为7。此时已发送了S3,0 和 S4,1，所以最多还可以发送5个帧。（3）甲方需要重发3个数据帧（1分），重发的第一个帧是S2,3。(1分）在GBN协议中，接收方发送了N帧后，检测出错，则需要发送出错帧及其之后的帧。S2,0超时，所以重发的第一帧是S2。已收到乙的R2帧，所以确认号应为3。（4）甲方可以达到的最大信道利用率是：U=发送数据的时间/从开始发送第一帧到收到第一个确认帧的时间 = N * Td /(Td + RTT + Ta)。U是信道利用率，N是发送窗口的最大值，Td是发送一数据帧的时间，RTT是往返时间，Ta是发送一确认帧的时间。这里采用捎带确认，Td=Ta。
某进程中有3个并发执行的线程thread1、thread2和thread3，其伪代码如下所示。//复数的结构类型定义 typedef struct { float a; float b; } cnum; cnum x, y, z; //全局变量 //计算两个复数之和 cnum add(cnum p, cnum q) { cnum s; s.a = p.a+q.a; s.b = p.b+q.b; return s; }thread1 { cnum w; w = add(x, y); … } thread2 { cnum w; w = add(y, z), … }thread3 { cnum w; w.a = 1; w.b = 1; z = add(z, w); y = add(y, w); … }请添加必要的信号量和P、V(或wait( )、signal( ))操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。答：先找出线程对在各个变量上的互斥、并发关系。如果是一读一写或两个都是写，那么这就是互斥关系。每一个互斥关系都需要一个信号量进行调节。semaphore mutex_y1=1；//mutex_y1用于thread1与thread3对变量y的互斥访问。(1分)semaphore mutex_y2=1；//mutex_y2用于thread2与thread3对变量y的互斥访问。(1分)semaphore mutex_z=1； //mutex_z用于变量z的互斥访问。(1分)互斥代码如下：(5分)thread1{ cnum w； wait(mutex_y1)； w=add(x，y)； signal(mutex_y1)； ……}thread2{ cnum w： wait(mutex_y2)： wait(mutex_z)； w=add(y，z)； signal(mutex_z)； signal(mutex_y2)； ……}thread3{ cnum w； w.a=1； w.b=1； wait(mutex_z)； z=add(z，w)； signal(mutex_z)； wait(mutex_y1)； wait(mutex_y2)； y=add(y，w)； signal(mutex_y1)； signal(mutex_y2)； ……}
假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式如下：页目录号（10位）页表索引（10位）页内偏移量（12位）请针对题43的函数f1和题44中的机器指令代码，回答下列问题。（1）函数f1的机器指令代码占多少页？（2）取第1条指令(push ebp)时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项(编号从0开始)？（3）M的I/O采用中断控制方式。若进程P在调用f1之前通过scanf( )获取n的值，则在执行scanf( )的过程中，进程P的状态会如何变化?CPU是否会进入内核态？答：（1）函数f1的代码段中所有指令的虚拟地址的高20位相同，因此f1的机器指令代码在同一页中，仅占用1页。（1分）页目录号用于寻找页目录的表项，该表项包含页表的位置。页表索引用于寻找页表的表项，该表项包含页的位置。（2）push ebp指令的虚拟地址的最高10位（页目录号）为 00 0000 0001，中间10位（页表索引）为00 0000 0001，所以，取该指令时访问了页目录的第1个表项，（1分）在对应的页表中访问了第1个表项。（1分）（3）在执行scanf( )的过程中，进程P因等待输入而从执行态变为阻塞态。(1分)输入结束时，P被中断处理程序唤醒，变为就绪态。(1分)P被调度程序调度，变为运行态。(1分)CPU状态会从用户态变为内核态。(1分)
在按字节编址的计算机M上，题43中f1的部分源程序(阴影部分)与对应的机器级代码(包括指令的虚拟地址)如下： int fl(unsigned n)1 00401020 55 push ebp ...... ... ...... for(unsigned i=0; i<=n-1; i++) ...... ... ......20 0040105E 39 4D F4 cmp dword ptr[ebq-0Ch],ecx ...... ... ...... { power *= 2; ...... ... ......23 00401066 D1 E2 shl edx,1 ...... ... ...... return sum; ...... ... ......35 0040107F C3 ret }其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。请回答下列问题。（1）计算机M是RISC还是CISC？为什么？（2）f1的机器指令代码共占多少字节？要求给出计算过程。（3）第20条指令cmp通过i减n-1实现对i和n-1的比较。执行f1(0)过程中，当i=0时，cmp指令执行后，进/借位标志CF的内容是什么？要求给出计算过程。（4）第23条指令shl通过左移操作实现了power*2运算，在f2中能否也用sh1指令实现power*2？为什么？答：（1）M为CISC。(1分)M的指令长短不一，不符合RISC指令系统特点。(1分)（2）f1的机器代码占96 B。(1分)因为f1的第一条指令“push ebp”所在的虚拟地址为0040 1020H，最后一条指令“ret”所在的虚拟地址为0040 107FH，所以，f1的机器指令代码长度为0040 107FH-0040 1020H+1 = 60H = 96个字节。(1分)（3）CF=1。(1分)cmp指令实现i与n-1的比较功能，进行的是减法运算。在执行f1(0)过程中，n=0，当i=0时， i=0000 0000H，并且n-1=FFFF FFFFH。因此，当执行第20条指令时，在补码加/减运算器中执行“0减FFFF FFFFH”的操作，即0000 0000H+0000 0000H+1=0000 0001H，此时，进位输出C=0，减法运算时的借位标志CF=C⊕1=1。(2分)（4）f2中不能用shl指令实现power*2。(1分)因为 shl 指令用来将一个整数的所有有效数位作为一个整体左移；而f2中的变量power是float型，其机器数中不包含最高有效数位，但包含了阶码部分，将其作为一个整体左移时并不能实现“乘2”的功能，因而f2中不能用shl指令实现power*2。(2分)浮点数运算比整型运算要复杂，耗时也较长。
已知，计算f(n)的C语言函数f1如下：int f1(unsigned n){ int sum=1, power=1; for(unsigned i=0;i<=n-1;i++){ power *= 2; sum += power; } return sum; }将f1中的int都改为float，可得到计算f(n)的另一个函数f2。假设unsigned和int型数据都占32位，float采用IEEE754单精度标准。请回答下列问题。（1）当n=0时，f1会出现死循环，为什么？若将f1中的变量和n都定义为int型，则f1是否还会出现死循环？为什么？（2）f1(23)和f2(23)的返回值是否相等？机器数各是什么(用十六进制表示)？（3）f1(24)和f2(24)的返回值分别为33 554 431和33 554 432.0，为什么不相等？（4）f(31)=232-1，而f1(31)的返回值却为-1，为什么？若使f1(n)的返回值与f(n)相等，则最大的n是多少？（5）f2(127)的机器数为7F80 0000H，对应的值是什么？若使f2(n)的结果不溢出，则最大的n是多少？若使f2(n)的结果精确(无舍入)。则最大的n是多少？答：（1）由于i和n是unsigned型，故“i<=n-1”是无符号数比较，n=0时，n-1的机器数为全1，值是232-1，为unsigned型可表示的最大数，条件“i<=n-1”永真，因此出现死循环。(2分)若i和n改为int类型，则不会出现死循环。(1分)因为“i<=n-1”是带符号整数比较，n=0时，n-1的值是-1，当i=0时条件“i<=n-1”不成立，此时退出for循环。(1分)（2）f1(23)与f2(23)的返回值相等。（1分）f(23) = 223+1-1 = 224-1，它的二进制形式是24个1。int占32位，没有溢出。float有1个符号位，8个指数位，23个底数位，23个底数位可以表示24位的底数。所以两者返回值相等。f1(23)的机器数是 00FF FFFFH。（1分）f2(23)的机器数是 4B7F FFFFH。（1分）显而易见前者是24个1，即 0000 0000 1111 1111 1111 1111 1111 1111（2），后者符号位是 0，指数位为 23+127(10) = 1001 0110（2），底数位是 111 1111 1111 1111 1111 1111（2）。（3）当n=24时，f(24) = 1 1111 1111 1111 1111 1111 1111 B，而float型数只有24位有效位，舍入后数值增大，所以f2(24)比f1(24)大1。(1分)（4）显然f(31)已超出了int型数据的表示范围，用f1(31)实现时得到的机器数为32个1，作为int型数解释时其值为-1，即f1(31)的返回值为-1。(1分)因为int型最大可表示数是0后面加31个1，故使f1(n)的返回值与f(n)相等的最大n值是30。(1分)（5）IEEE 754标准用“阶码全1、尾数全0”表示无穷大。f2返回值为float型，机器数7F80 0000H对应的值是+∞。(1分)当n=126时，f(126) = 2127-1 = 1.1…1×2126，对应阶码为127+126=253，尾数部分舍入后阶码加1，最终阶码为254，是IEEE 754单精度格式表示的最大阶码。故使f2结果不溢出的最大n值为126。(1分)当n=23时，f(23)为24位1，float型数有24位有效位，所以不需舍入，结果精确。故使f2获得精确结果的最大n值为23。(1分)
使用Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。（1）对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。（2）图G的MST是唯一的吗？（3）对任意的带权连通图，满足什么条件时，其MST是唯一的？答：（1）Prim算法属于贪心策略。算法从一个任意的顶点开始，一直长大到覆盖图中所有顶点为止。算法每一步在连接树集合S中顶点和其他顶点的边中，选择一条使得树的总权重增加最小的边加入集合S。当算法终止时，S就是最小生成树。①S中顶点为A，候选边为(A,D)、(A,B)、(A,E)，选择(A,D)加入S。②S中顶点为A、D，候选边为(A,B)、(A,E)、(D,E)、(C,D)，选择(D,E)，加入S。③S中顶点为A、D、E，候选边为(A,B)、(C,D)、(C,E)，选择(C,E)加入S。④S中顶点为A、D、E、C，候选边为(A,B)、(B,C)，选择(B,C)加入S。⑤S就是最小生成树。依次选出的边为：(A，D),(D，E),(C，E),(B，C) （4分）（2）图G的MST是唯一的。（2分）第一小题的最小生成树包括了图中权值最小的四条边，其他边都比这四条边大，所以此图的MST唯一。（3）当带权连通图的任意一个环中所包含的边的权值均不相同时，其MST是唯一的。
请设计一个算法，将给定的表达式树(二叉树)转换为等价的中缀表达式(通过括号反映操作符的计算次序)并输出。例如，当下列两棵表达式树作为算法的输入时，输出的等价中缀表达式分别为(a+b) * (c * (-d)和(a * b)+(-(c-d))。二叉树结点定义如下：typedef struct node{ char data[10]; //存储操作数或操作符 struct node *left, *right; }BTree;请回答下列问题。（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。答：（1）算法的基本设计思想表达式树的中序序列加上必要的括号即为等价的中缀表达式。可以基于二叉树的中序遍历策略得到所需的表达式。(3分)表达式树中分支结点所对应的子表达式的计算次序，由该分支结点所处的位置决定。为得到正确的中缀表达式，需要在生成遍历序列的同时，在适当位置增加必要的括号。显然，表达式的最外层(对应根结点)及操作数(对应叶结点)不需要添加括号。（2）算法实现(10分)void BtreeToE(BTree *root) { BtreeToExp(root,1); //根的高度为1 } void BtreeToExp(BTree *root, int deep) { if(root == NULL) return; else if(root->left == NULL && root->right == NULL)//若为叶结点 printf("%s",root->data);//输出操作数 else { if(deep>1) printf("(");//若有子表达式则加1层括号 BtreeToExp(root->left，deep+1); printf("%s",root->data); //输出操作符 BtreeToExp(root->right,deep+1); if(deep>1) printf(")");//若有子表达式则加1层括号 } }
某公司网络如题47图所示。IP地址空间192.168.1.0/24被均分给销告部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU=1500B，技术部子网的MTU=800B。请回答下列问题。（1）销售部子网的广播地址是什么？技术部子网的子网地址是什么？若每个主机仅分配一个IP地址，则技术部子网还可以连接多少台主机？（2）假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？答：（1）广播地址是网络地址中主机号全1的地址（主机号全0的地址，代表网络本身）。销售部和技术部均分配了192.168.1.0/24的IP地址空间，IP地址的前24位为子网的网络号。于是在后8位中划分部门的子网，选择前1位作为部门子网的网络号。令销售部子网的网络号为0，技术部子网的网络号为1，则技术部子网的完整地址为 192.168.1.128；令销售部子网的主机号全1，可以得到该部门的广播地址为192.168.1.127。每个主机仅分配一个IP地址，计算目前还可以分配的主机数，用技术部可以分配的主机数，减去已分配的主机数，技术部总共可以分配计算机主机数为27-2 = 126（减去全0和全1的主机号）。已经分配了208-129+1 = 80个，此外还有1个IP地址分配给了路由器的端口(192.168.1.254)，因此还可以分配126-80-1=45台。（2）判断分片的大小，需要考虑各个网段的MTU，而且注意分片的数据长度必须是8B的整数倍。由题可知，在技术部子网内，MTU = 800B，IP分组头部长20B，最大IP分片封装数据的字节数为⌊(800-20)/8⌋×8 = 776。至少需要的分片数为⌈(1500-20)/776⌉ = 2。第1个分片的偏移量0；第2个分片的偏移量为 776/8 = 97。
某文件系统采用索引节点存放文件的属性和地址信息，簇大小为4KB。每个文件索引节点占64B，有11个地址项，其中直接地址项8个，一级、二级和三级间接地址项各1个，每个地址项长度为4B。请回答下列问题。（1）该文件系统能支持的最大文件长度是多少？(给出计算表达式即可)（2）文件系统用1M（1M=220）个簇存放文件索引结点，用512M个簇存放文件数据。若一个图像文件的大小为5600B，则该文件系统最多能存放多少个这样的图像文件?（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文件系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？答：（1）簇大小为4KB，每个地址项长度为4B，故每簇有4KB/4B = 1024个地址项。最大文件的物理块数可达8+1×1024+1×10242+1×10243，每个物理块（簇）大小为4KB，故最大文件长度为(8+1×1024+1×10242+1×10243)×4KB = 32KB+4MB+4GB+4TB。（2）文件索引节点总个数为1M×4KB/64B = 64M，5600B的文件占2个簇，512M个簇可存放的文件总个数为512M/2 = 256M。可表示的文件总个数受限于文件索引节点总个数，故能存储64M个大小为5600B的图像文件。（3）文件F1大小为6KB＜4KB×8 = 32KB，故获取文件F1的最后一个簇的簇号只需要访问索引节点的直接地址项。文件F2大小为40KB，4KB×8＜40KB＜4KB×8+4KB×1024，故获取F2的最后一个簇的簇号还需要读一级索引表。综上，需要的时间不相同。
请根据题44图给出的虚拟储管理方式，回答下列问题。（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？（2）寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。（3）为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段？答：（1）由图可知，地址总长度为32位，高20位为虚页号，低12位为页内地址。且虚页号高10位为页目录号，低10位为页号。展开成二进制则表示为：0000 0001 1000 0000 0110 0000 0000 1000 B故十六进制表示为0180 6008H。（2）PDBR为页目录基址地址寄存器（Page-Directory Base Register），其存储页目录表物理内存基地址。进程切换时，PDBR的内容会变化；同一进程的线程切换时，PDBR的内容不会变化。每个进程的地址空间、页目录和PDBR的内容存在一一对应的关系。进程切换时，地址空间发生了变化，对应的页目录及其起始地址也相应变化，因此需要用进程切换后当前进程的页目录起始地址刷新PDBR。同一进程中的线程共享该进程的地址空间，其线程发生切换时，地址空间不变，线程使用的页目录不变，因此PDBR的内容也不变。（3）改进型 CLOCK 置换算法需要用到使用位和修改位，故需要设置访问字段（使用位）和修改字段（脏位）。
某计算机采用页式虚拟存储管理方式，按字节编址。CPU进行存储访问的过程如题44图所示。根据题44图回答下列问题。（1）主存物理地址占多少位？（2）TLB采用什么映射方式？TLB用SRAM还是DRAM实现？（3）Cache采用什么映射方式？若Cache采用LRU替换算法和回写(Write Back)策略，则Cache每行中除数据(Data)、Tag和有效位外，还应有哪些附加位？Cache总容量是多少？Cache中有效位的作用是什么？（4）若CPU给出的虚拟地址为0008 C040H，则对应的物理地址是多少？是否在Cache中命中？说明理由。若CPU给出的虚拟地址为0007 C260H，则该地址所在主存块映射到的Cache组号是多少？答：（1）物理地址由实页号和页内地址拼接，因此其位数为16+12 = 28；或直接可得20+3+5 = 28。（2）TLB采用全相联映射，可以把页表内容调入任一块空TLB项中，TLB中每项都有一个比较器，没有映射规则，只要空闲就行。TLB采用静态存储器SRAM，读写速度快，但成本高，多用于容量较小的高速缓冲存储器。（3）图中可以看到，Cache中每组有两行，故采用 2 路组相联映射方式。因为是2路组相联并采用LRU替换算法，所以每行（或每组）需要1位LRU位；因为采用回写策略，所以每行有1位修改位（脏位），根据脏位判断数据是否被更新，如果脏位为1则需要写回内存。28 位物理地址中Tag字段占20位，组索引字段占3位，块内偏移地址占5位，故Cache共有23 = 8组，每组2行，每行有25 = 32B；故Cache总容量为8×2×(20+1+1+1+32×8) = 4464位 = 558字节。Cache中有效位用来指出所在Cache行中的信息是否有效。（4）虚拟地址分为两部分：虚页号、页内地址；物理地址分为两部分：实页号、页内地址。利用虚拟地址的虚页号部分去查找TLB表（缺失时从页表调入），将实页号取出后和虚拟地址的页内地址拼接，就形成了物理地址。虚页号008CH恰好在TLB表中对应实页号 0040H（有效位为1，说明存在），虚拟地址的后3位为页内地址040H，则对应的物理地址是 0040040H。物理地址为0040040H，其中高20位00400H为标志字段，低5位00000B为块内偏移量，中间3位010B为组号2，因此将00400H与Cache中的第2组两行中的标志字段同时比较，可以看出，虽然有一个Cache行中的标志字段与00400H相等，但对应的有效位为0，而另一Cache行的标志字段与00400H不相等，故访问Cache不命中。因为物理地址的低12位与虚拟地址低12位相同，即为0010 0110 0000B。根据物理地址的结构，物理地址的后八位01100000B的前三位011B是组号，因此虚拟地址0007 C260H所在的主存映射到Cache组号为3。
假定计算机的主频为500MHz，CPI为4。现有设备A和B，其数据传输率分别为2MB/s和40MB/s，对应I/O接口中各有一个32位数据缓冲寄存器。请回答下列问题，要求给出计算过程。（1）若设备A采用定时查询I/O方式，每次输入/输出都至少执行10条指令。设备A最多间隔多长时间查询一次才能不丢失数据？CPU用于设备A输入/输出的时间占CPU总时间的百分比至少是多少？（2）在中断I/O方式下，若每次中断响应和中断处理的总时钟周期数至少为400，则设备B能否采用中断I/O方式？为什么？（3）若设备B采用DMA方式，每次DMA传送的数据块大小1000B，CPU用于DMA预处理和后处理的总时钟周期数为500，则CPU用于设备B输入/输出的时间占CPU总时间的百分比最大是多少？答：（1）程序定时向缓存端口查询数据，由于缓存端口大小有限，必须在传输完端口大小的数据时访问端口，以防止部分数据没有被及时读取而丢失。设备A准备32位数据所用时间为4B/2MB=2µs，所以最多每隔2µs必须查询一次，每秒的查询次数至少是1s/2µs=5×105，每秒CPU用于设备A输入/输出的时间至少为5×105×10×4 = 2×107个时钟周期，占整个CPU时间的百分比至少是2×107/500M = 4%。（2）中断响应和中断处理的时间为400×（1/500M）=0.8µs，这时只需判断设备B准备32位数据要多久，如果准备数据的时间小于中断响应和中断处理的时间，那么数据就会被刷新、造成丢失。经过计算，设B准备32位数据所用时间为4B/40MB=0.1µs，因此，设备B不适合采用中断I/O方式。（3）在DMA方式中，只有预处理和后处理需要CPU处理，数据的传送过程是由DMA控制。设备B每秒的DMA次数最多为40MB/1000B=40000，CPU用于设备B输入/输出的时间最多为40000×500 = 2×107个时钟周期，占CPU总时间的百分比最多为2×107/500M = 4%。
拟建设一个光通信骨干网络连通BJ、CS、XA、QD、JN、NJ、TL和WH等8个城市，题42图中无向边上的权值表示两个城市间备选光纤的铺设费用。请回答下列问题。（1）仅从铺设费用角度出发，给出所有可能的最经济的光纤铺设方案（用带权图表示），并计算相应方案的总费用。（2）题42图可采用图的哪一种存储结构？给出求解问题（1）所使用的算法名称。（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机H1直接连接在TL的路由器上，主机H2直接连接在BJ的路由器上。若H1向H2发送一个TTL=5的IP分组，则H2是否可以收到该IP分组？答：（1）为了求解最经济的方案，可以把问题抽象为求无向带权图的最小生成树。可以采用手动Prim算法或Kruskal算法作图。注意本题最小生成树有两种构造，如下图所示。方案的总费用为16。（2）存储题中的图可以采用邻接矩阵（或邻接表）。构造最小生成树采用Prim算法（或kruskal算法）。（3）TTL=5，即IP分组的生存时间（最大传递距离）为5，方案1中TL和BJ的距离过远，TTL=5不足以让IP分组从H1传送到H2，因此H2不能收到IP分组。而方案2中TL和BJ邻近，H2可以收到IP分组。
给定一个含n(n≥1)个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如,数组{-5, 3, 2, 3}中未出现的最小正整数是1；数组{1, 2, 3}中未出现的最小正整数是4。要求：（1）给出算法的基本设计思想。（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。答：（1）题目要求算法时间上尽可能高效，因此采用空间换时间的办法。分配一个用于标记的数组B[n]，用来记录A中是否出现了1~n中的正整数，B[0]对应正整数1，B[n-1]对应正整数 n，初始化B中全部为0。由于A中含有n个整数，因此可能返回的值是1~n+1，当A中n个数恰好为1~n 时返回n+1。当数组A中出现了小于等于0或者大于n的值时，会导致1~n中出现空余位置，返回结果必然在1~n中，因此对于A中出现了小于等于0或者大于n的值可以不采取任何操作。经过以上分析可以得出算法流程：从A[0]开始遍历A，若0<A[i]<=n，则令 B[A[i]-1]=1；否则不做操作。对A遍历结束后，开始遍历数组B，若能查找到第一个满足B[i]==0 的下标i，返回i+1即为结果，此时说明A中未出现的最小正整数在1~n之间。若B[i]全部不为0，返回i+1（跳出循环时 i=n，i+1等于n+1），此时说明A中未出现的最小正整数是n+1。（2）int findMissMin(int A[],int n) { int i,*B;//标记数组 B=(int *)malloc(sizeof(int)*n); //分配空间 memset(B,0,sizeof(int)*n);//赋初值为0 for(i=0; i<n; i++) if(A[i]>0&&A[i]<=n)//若A[i]的值介于1~n，则标记数组B B[A[i]-1]=1; for(i=0; i<n; i++) //扫描数组B，找到目标值 if (B[i]==0) break; return i+1;//返回结果 }（3）时间复杂度：遍历A一次，遍历B一次，两次循环内操作步骤为O(1)量级，因此时间复杂度为O(n)。空间复杂度：额外分配了B[n]，空间复杂度为O(n)。
某网络拓扑如题 47 图所示，其中 R 为路由器，主机 H1～H4 的 IP 地址配置以及 R 的各接口 IP 地址配置如图中所示。现有若干以太网交换机（无 VLAN 功能）和路由器两类网络互连设备可供选择。请回答下列问题：（1）设备 1、设备 2 和设备 3 分别应选择什么类型的网络设备？（2）设备 1、设备 2 和设备 3 中，哪几个设备的接口需要配置 IP 地址？为对应的接口配置正确的 IP 地址。（3）为确保主机 H1～H4 能够访问 Internet，R 需要提供什么服务？（4）若主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，网络中哪几个主机会接收该数据报？【答案解析】（1）以太网交换机（无 VLAN 功能）连接的若干 LAN 仍然是一个网络（同一个广播域），路由器可以连接不同的 LAN、不同的 WAN 或把 WAN 和 LAN 互联起来，隔离了广播域。IP 地址 192.168.1.2/26 与 192.168.1.3/26 的网络前缀均为 192.168.1.0，视为 LAN1。IP 地址192.168.1.66/26 与 192.168.1.67/26 的网络前缀均为 192.168.1.64，视为 LAN2。所以设备 1 为路由器，设备 2、3 为以太网交换机。（2）设备 1 为路由器，其接口应配置 IP 地址。IF1 接口与路由器 R 相连，其相连接口的 IP 地址为 192.168.1.253/30，253 的二进制表示形式为 11111101，故 IF1 接口的网络前缀也应为 192.168.1.111111，已分配 192.168.1.253，去除全 0 全 1，IF1 接口的 IP 地址应为 192.168.1.254。LAN1 的默认网关为 192.168.1.1，LAN2 的默认网关为 192.168.1.65，网关的 IP 地址是具有路由功能的设备的 IP 地址，通常默认网关地址就是路由器中的 LAN 端口地址，设备 1 的 IF2、IF3 接口的 IP 地址分别设置为 192.168.1.1 和 192.168.1.65。（3）私有地址段：C 类 192.168.0.0~192.168.255.255，即 H1～H4 均为私有 IP 地址，若要能够访问 Internet，R 需要提供 NAT 服务，即网络地址转换服务。（4）主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，主机号全为 1，为本网络的广播地址，由于路由器可以隔离广播域，只有主机 H4 会接收到数据报。
对于题 45，若计算机 M 的主存地址为 32 位，釆用分页存储管理方式，页大小为 4KB，则第 1 行的 push 指令和第 30 行的 ret 指令是否在同一页中（说明理由）？若指令 Cache 有 64 行，采用 4 路组相联映射方式，主存块大小为 64B，则 32 位主存地址中，哪几位表示块内地址？哪几位表示 Cache 组号？哪几位表示标记（tag）信息？读取第 16 行的 call 指令时，只可能在指令 Cache 的哪一组中命中（说明理由）？【答案解析】因为页大小为 4KB，所以虚拟地址的高 20 位为虚拟页号。第 1 行的 push 指令和第 30 行的 ret 指令的虚拟地址的高 20 位都是 00401H，因此两条指令在同一页中。指令 Cache 有 64 块，采用 4 路组相联映射方式，故指令 Cache 共有 64/4 = 16 组，Cache 组号共 4 位。主存块大小为 64B，故块内地址为低 6 位。综上所述，在 32 位主存地址中，低 6 位为块内地址，中间 4 位为组号，高 22 位为标记。因为页大小为 4KB，所以虚拟地址和物理地址的最低 12 位完全相同，因而 call 指令虚拟地址 0040 1025H 中的 025H = 0000 0010 0101B 为物理地址的低 12 位，对应的 7～10 位为组号，故对应的 Cache 组号为 0。