王道2020-408题目.pdf

C、b,f,e,d,c,aD、b,c,eB、4，5，1，2，3A、(b,f)(b,d)(a,e)(c,e)(b,e)B、关键路径是从原点到汇点路径长度最长的路径；选择题：1、将一个 10X10 对称矩阵 M 的上三角部分的元素mij(1ij10)按列优先存入 C 语言的一位数组 N 中，元素m7,2在 N 中的下标是：A、15B、162、对 空栈 S 进行 Push 和D、23pop 操 作，入 栈 序 列 a,b,c,d,e 经过Push,Push,Pop,Push,Pop,Push,Push,Pop操作后得到的出栈序列是：A、b,a,cB、b,a,eC、b,c,a3、对与任意一棵高度为 5 且有 10 个节点的二叉树，若采用顺序存储结构保存，每个结点占1 个存储单元（仅存放结点的数据信息），则存放该二叉树需要的存储单元数量至少是：B、16C、15D、104、已知森林F及与之对应的二叉树T，若F的先根遍历序列是a,b,c,d,e,f，后根遍历序列是b,a,d,f,e,c则T 的后遍历序列是：A、b,a,d,f,e,cB、b,d,f,e,c,aD、f,e,d,c,b,a5、下列给定的关键字输入序列中，不能生成如下二叉排序树的是：A、4，5，2，1，3C、4，2，5，3，1 D、4，2，1，3，56、修改递归方式实现的图的深度优先搜索（DFS）算法，将输出（访问）定点信息的语句移到退出递归前（即执行输出语句后立刻退出递归）。采用修改后的算法遍历有向无环图 G，若输出结果中包含G 中的全部顶点，则输出的顶点序列是G的：A、拓扑有序序列D、深度优先搜索序列C、广度优先搜索序列7、已知无向图G如下所示，使用克鲁斯卡尔（Kruskal）算法求图G的最小生成树，加入到最小生成树中的边依次是：B、(b,f)(b,d)(b,e)(a,e)(e,c)?（不确定最后一个括号的内容）C、(a,e)(b,e)(c,e)(b,d)(b,f)D、(a,e)(c,e)(b,e)(b,f)(b,d)8、若使ADE 网估算工程进度则下列叙述中正确的是：A、关键路径是从原点到汇点边数最多的一条路径；C、增加任一关键活动的时间不会延长工程的工期；D、缩短任一关键活动的时间将会缩短工程的工期。42513B、逆拓扑有序序列A、31C、22D、都由DRAM 存储器组成。B、I,IIIB、6，9A、自陷是通过陷阱指令预先设定的一类外部中断事件；9、下列关于大根堆（至少含 2 个元素）的叙述中正确的是：I可以将堆看成一颗完全二叉树；II、可采用顺序存储方式保存堆；III、可以将堆看成一棵二叉排序树；IV、堆中的次大值一定在根的下一层。选项没写10、依次将关键字5，6，9，13，8，2，12，15插入初始为空的4阶B树后，根节点中包含的关键字是：A、8C、8，13D、9，1211、对大部分元素已有序的数组进行排序时，直接插入排序比简单选择排序效率更高，其原因是：I、直接插入排序过程中元素之间的比较次数更少；II、直接插入排序过程中所需要的辅助空间更少；III、直接插入排序过程中元素的移动次数更少。B、IIIC、I,IID、I,II,III12、下列给出的部件中其位数（宽度）一定与机器字长相同的是：I、ALU；II、指令寄存器；III、通用寄存器；IV、浮点寄存器A、I,IIC、II,IIID、II,III,IV13、已知带符号整数用补码表示，float型数据用IEEE 754 标准表示，假定变量 x的类型只能是int或float。当 x的机器数为C8000000H时，x的值可能是：B、-216;C、217；D、25227；14、在按字节编址，采用小端方式的 32 位计算机中，按边界对齐方式为以下C语言结构型变量a 分配存储空间。Struct recordshortx1;intx2;a;若a的首地址为2020 FE00H，a的成员变量x2的机器数为1234 0000H，则其中34H所在存储单元的地址是：A、2020 FE03H；B、2020 FE04H；C、2020 FE05H；15、下列关于 TLB 和 Cache 的叙述中错误的是：A、命中率与程序局部性有关；B、缺失后都需要去访问主存；C、缺失处理都可以由硬件实现；16、某计算机采用 16 位定长指令字格式，操作码位数和寻址方式位数固定，指令系统有48 条指令，支持直接、间接、立即、相对4 种寻址方式，单地址指令中直接寻址方式可寻址范围是：B、01023；C、-128127；D、-512511；17、下列给出的处理器类型中理想情况下 CPI 为 1 的是：I、单周期CPU；II、多周期CPU；III、基本流水线CPU；IV超标量流水线CPU A、I，II；B、II,III;C、II,IV;D、III,IV；18、下列关于“自陷”（Trap，也称陷阱）的叙述中错误的是：B、自陷可用于实现程序调试时的断点设置和单步跟踪；C、自陷发生后 CPU 将转去执行操作系统内核相应程序；D、自陷处理完成后返回到陷阱指令的下一条指令执行。A、0225；D、2020FE06H；A、-7227;A、I表项包含F的属性；A、索引分配；C、19.2B、在系统打开文件表中仅有一个B、一旦可屏蔽中断请求信号有效，CPU 将立即响应；C、在整个数据块的传送过过程中，CPU 不可以访问主存储器；B、存在安全序列P2,P1,P3;19、QPI 总线是一种点对点全工双周同步串行总线，总线上的设备可同时接收和发送信息，每个方向可同时传输 20 位信息（16位数据+4 位校验位），每个QPI数据包有 80 位信息，分2 个时钟周期传送，每个时钟周期传递 2次，因此QPI 总线带宽为每秒传送次数*2B*2。若QPI时钟频率为2.4GHz，则总线带宽为：A、4.8B、9.6D、38.4（单位GB/s）20、下列事件中属于外部中断事件的是：I、访存时缺页；确定）；III、网络数据包到达选项暂无II、定时器延时（不21、外部中断包括不可屏蔽中断（NMI）和可屏蔽中断，下列关于外部中断的叙述中错误的是：A、CPU 处于关中断状态时也能响应 NMI 请求；C、不可屏蔽中断的优先级比可屏蔽中断的优先级高；D、可通过中断屏蔽字改变可屏蔽中断的处理优先级。22、若设备采用周期挪用 DMA 方式进行输入输出，每次 DMA 传送的数据块大小为512字节，相应的I/O接口中有一个32 位数数据缓冲寄存器，对于数据输入过程，下列叙述中错误的是：A、每准备好32位数据，DMA 控制器就发出一次总线请求；B、相对于CPU，DMA 控制器的总线使用权的优先级更高；D、数据块传送结束时，会产生“DMA 传送结束”的中断请求。23、若多个进程共享同一个文件 F，则下列叙述中正确的是：A、个进程只能用“读”方式打开文件 F；C、各进程的用户打开文件表中关于 F 的表项内容相同；D、进程关闭F时系统删除F 在系统打开文件表中的表项。24、下列选项中支持文件长度可变，随机访问的磁盘存储空间分配方式是：B、链接分配；C、连续分配；D、动态分区分配。25、下列与中断相关的操作中，由操作系统完成的是：I、保存被中断程序的中断点；II、提供中断服务；III、初始化中断向量表；IV、保存中断屏蔽字；A、I,II;B:I,II,IV;C III,IV;26、下列与进程调度有关的因素中在设计多级反馈队列调度算法时需要考虑的是：I就绪队列的数量；II 就绪队列的优先级；III 各就绪队列的调度算法；IV 进程在就绪队列间的迁移条件；A、I,II;B、III,IV；C、II,III,IV;27、某系统中有 A,B 两类资源各 6 个，t 时刻资源分配及需求情况如下表所示进程A 已分配数量B 已分配数量A 需求总量B 需求总量P12344P22131P31234t 时刻安全检测结果是：A、存在安全序列P1,P2,P3;C、存在安全序列P2,P3,P1;D I,II,III,IVD II,III,IV.B、需要为每条虚电路预分配带宽；B、232；B、父进程与子进程共享虚拟地址空间；D、更换物理设备后必须修改访问该设备的应用程序。（缺一个选项）D、不存在安全序列。28、下列因素影响请求分页系统有效（平均）访存时间的是：I、缺页率；II、磁盘读写时间；III、内存访问时间；IV执行缺页处理程序的CPU时间；A、II,III；B、I,IV；C、I,III,IV；29、下列关于父进程与子进程的叙述中错误的是：A、父进程与子进程可以并发执行；C、父进程与子进程有不同的进程控制块；D、父进程与子进程不能同时使用同一临界资源。30、对于具备设备独立性的系统下列叙述中错误的是：A、可以使用文件名访问物理设备；B、用户程序使用逻辑设备与物理设备之间的映射关系；31、某文件系统的目录由文件名和索引节点号构成。若每个目录项长度为 64字节，其中 4 个字节存放索引节点号，60 个字节存放文件名。文件名由小写英文字母构成，则该文件系统能创建的文件数量的上限为：A、226；C、260；D、264；32、下列准则中实现临界区互斥机制必须遵循的是：I、两个进程不能同时进入临界区；II、允许进城访问空闲的临界资源；III、进程等待进入临界区的时间是有限的；IV、不能进入临界区的执行态进程立即放弃CPU。A、I,IV；B、II,III;33、下图描述的协议要素是I、语法；D、I,III,IV；II、语义；III、时序A、仅I；B、仅II；D、I,II和III；34、下列关于虚电路网络的叙述中错误的是：A、可以确保数据分组传输顺序；C、建立虚电路时需要进行路由选择；D、依据虚电路号（VCID）进行数据分组转发。C仅III；C、I,II,III;D、I,II,III,IV。C、4000；D、40%D、48ms；C、4，2；A、IFS1;35、下图所示的网络冲突域和广播域的个数分别是：A、2，2；B、2，4；D、4，4；36、假设主机采用停-等协议向主机乙发送数据帧，数据帧长与确认帧长均为1000B。数据传输速率是10kbps，单项传播延时是200ms。则甲的最大信道利用率：A、80%；B、66.7%；C、44.4%；37、某IEEE 802.11无线局域网中主机H与AP之间发送或接收CSMA/CA帧的过程如下图所示，在H或AP 发送帧前所等待的帧间间隔时间（IFS）中最长的是：B、IFS2;C、IFS3;D、IFS4；38、若主机甲与主机乙已建立一条 TCP 连接，最大段长（MSS）为1KB，往返时间（RTT）为2ms，则在不出现拥塞的前提下，拥塞窗口从 8kB增长到20KB所需的最长时间是：A、4ms；B、8ms；C、24ms;39、若主机甲与主机乙建立 TCP连接时发送的SYN段中的序号为1000，在断开连接时，甲发送给乙的 FIN 段中的序号为 5001，则在无任何重传的情况下，甲向乙已经发送的应用层数据的字节数为：A、4002；B、4001；D、3999；40、假设下图所示网络中的本地域名服务器只提供递归查询服务，其他域名的服务器均只提供迭代查询服务；局域网内主机访问 Internet 上各服务器的往返时间（RTT）均为 10ms，忽略其他各种时延，若主机 H 通过超 链接http:/ Web页index.html，则从点击超链接开始到浏览器接收到 index.html 页面为止，所需最短、最长时间分别是：A、10ms，40ms；B、10ms,50ms；C、20ms,40ms；大题：41、定义三元组（a,b,c）（a,b,c均为正数）的距离D=|a-b|+|b-c|+|c-a|.给定3个非空整数集合S1,S2,S3,按升序分别存储在 3 个数组中。请设计一个尽可能高效的算法，计算并输出所有可能的三元组（a,b,c）（aS1,bS2,cS3）中的最小距离。例如 S1=-1,0,9,S2=-25，-10，10，11，S3=2，9，17，30，41。则最小距离为2，相应的三元组为（9，10，9），要求：（1）给出算法的基本设计思想；（2）根据设计思想，采用 C或C+语言描述算法，关键之处给出注释；（3）说明你所设计算法的时间复杂度和空间复杂度。42、若任一个字符的编码都不是其他字符编码的前缀，则称这种编码具有前缀特性。现有某字符集（字符个数2）的不等长编码，每个字符的编码均为二进制的0，1序列，最长为L 位，且具有前缀特性。请回答下列问题：（1）哪种数据结构适宜保存上述具有前缀特性的不等长编码？（2）基于你所设计的数据结构，简述从 0/1 串到字符串的译码过程；（3）简述判定某字符集的不等长编码是否具有前缀特性的过程。43、有实现x*y的两个C 语言函数如下：Unsigned umul(unsigned x,unsigned y)return x*y;Int imul(int x,int y)return x*y;假定某计算机 M 中 ALU 只能进行加减运算和逻辑运算。请回答：（1）若M 的指令系统中没有乘法指令，但有加法、减法和位移等指令，则在 M上也能实现上述两个函数中的乘法运算，为什么？（2）若M 的指令系统中有乘法指令，则基于 ALU、位移器、寄存器以及相应控制逻辑实现乘法指令时，控制逻辑的作用是什么？（3）针对以下 3种情况：（a）没有乘法指令；（b）有使用ALU 和位移器实现的乘法指令；（c）有使用阵列乘法器实现的乘法指令，函数 umul()在哪种情况下执行时间最长？哪种情况下执行的时间最短？说明理由（4）n 位整数乘法指令可保存 2n 位乘积，当仅取低 n 位作为乘积时，其结果可D、20ms,50ms;能会发生溢出。当 n=32,x=231-1，y=2 时，带符号整数乘法指令和无符号整数乘法指令得到的 x*y 的 2n 位乘积分别是什么（用十六进制表示）？此时函数umul()和 imul()的返回结果是否溢出？对于无符号整数乘法运算，当仅取乘积的低n 位作为乘法结果时，如何用2n 位乘积进行溢出判断？44、假定主存地址为32位，按字节编址，指令Cache和数据Cache与主存之间均采用8 路组相联映射方式，直写（Write Through）写策略和LRU 替换算法，主存块大小为64B，数据区容量各为32KB。开始时Cache均为空，请回答下列问题：（1）Cache 每一行中标记（Tag）、LRU 位各占几位？是否有修改位？（2）有如下 C 语言程序段：for(k=0;k1024;k+)Sk=2*sk;若数组S及其变量k均为int型，int型数据占4B，变量k 分配在寄存器中，数组s 在主存中的起始地址为 0080 00C0H，则该程序段执行过程中，访问数组 S的数据Cache 缺失次数为多少？（3）若CPU 最先开始的访问操作是读取主存单元 0001003H（或者0001 0003H？好像记错了）中的指令，简要说明从 Cache 中访问该指令的过程，包括 Cache缺失处理过程。45、现有5个操作A、B、C、D和E，操作C必须在A和B 完成后执行，操作E必须在C和D完成后执行，请使用信号量的wait(),signal(),操作（P、V操作）描述上述操作之间的同步关系，并说明所用信号量及其初值。46、某 32 位系统采用基于二级页表的请求分页存储管理方式，按字节编址，页目录项和页表项长度均为 4 字节，虚拟地址结构如下：页目录号（10 位）页号（10 位）页内偏移量（12 位）某C程序中数组a10241024的起始虚拟地址为 1080 000H（1080 0000H？可能记错），数组元素占4 字节，该程序运行时，其进程的页目录起始物理地址为0020 1000H，请回答下列问题：（1）数组元素 a12的虚拟地址是什么？对应的页目录号和页号分别是什么？对应的页目录项的物理地址是什么？若该目录项中存放的页框号为 00301H，则a12所在页对应的页表项的物理地址是什么？（2）数组a 在虚拟地址空间中所占区域是否必须连续？在物理地址空间中所占区域是否必须连续？（3）已知数组a按行优先方式存放，若对数组a 分别按行遍历和按列遍历，则哪一种遍历方式的局部性更好？47、某校园网有两个局域网，通过路由器 R1、R2和R3互联后接入Internet，S1和S2 为以太网交换机，局域网采用静态IP 地址配置，路由器部分接口以及各主机的IP 地址如图所示：假设 NAT 转换表结构为：请回答下列问题：（1）为使H2和H3能够访问Web服务器（使用默认端口号），需要进行什么配置？（2）若H2主动访问Web服务器时，将HTTP请求报文封装到IP 数据报P中发送，则H2发送P的源IP地址和目的IP 地址分别是？经过R3 转发后，P的源IP 地址和目的IP地址分别是？经过R2转发后，P的源IP地址和目的IP地址分别是？