logo资料库

王道2013年最后8套模拟题答案（前四套）.pdf

发布时间：2022-06-22 发布人：admin 分类：说明书 资料大小：1.37M 资料格式：pdf 举报 版权申诉
第1页 / 共54页
第2页 / 共54页
第3页 / 共54页
第4页 / 共54页
第5页 / 共54页
第6页 / 共54页
第7页 / 共54页
第8页 / 共54页
资料共54页，剩余部分请下载后查看
    王道模拟试题（一）答案 一、 单项选择题 1． D。 【解析】考查时间复杂度。该程序片段的基本语句为“y++;”，设其执行次数为 k 次，则 (k-1+1)*(k-1+1)≤n＜(k+1)*(k+1)，有 k2≤n
    RR 旋转的过程如上图所示，将 A 的右孩子 C 向左上旋转代替 A 成为根结点，将 A 结点 向左下旋转成为 C 的左子树的根结点，而 C 的原来的左子树 E 则作为 A 的右子树。 注意：平衡旋转的操作都是在插入操作后，引起不平衡的最小不平衡子树上进行的，只要 将这个最小不平衡子树调整平衡，则其上级结点也将恢复平衡。 6． A。 【解析】考查特殊二叉树的性质。对于 I，可能最后一层的叶结点个数为奇数，即倒数第 二层上有非叶结点的度为 1。对于 II，显然满足。对于 III，可能存在非叶结点只有一个孩子 结点。对于 IV，根据哈夫曼树的构造过程可知所有非叶结点度均为 2。对于 V，可能存在非 叶结点只有一个孩子结点。因此选 A。 注意：在哈夫曼树中没有度为 1 的结点。 7． C。 【解析】考查二叉树的特点。结点最少时的情况如下图所示。除根结点层只有 1 个结点 外，其他各层均有两个结点，结点总数=2*(100-1)+1=199。 8． D。 【解析】考查拓扑排序。拓扑排序的方法：1）从 AOV 网中选择一个没有前驱的顶点（入 度为 0），并输出它；2）从 AOV 网中删去该顶点，以及从该顶点发出的全部有向边；3）重 复上述两步，直到剩余的网中不再存在没有前驱的顶点为止。选项 D 中，删去 a、b 及其对 应的出边后，c 的入度不为 0，此有边，故不是拓扑序列。选项 A、B、D 均为拓扑序列。 解答本类题时，建议读者根据边集合画出草图。 9． D。 【解析】考查图的性质。在无向图中，一条边连接两个顶点，故所有顶点的度之和等于 ，故可求得度为 2 边数的 2 倍。由于在具有 n 个顶点 e 条边的无向图中，有 TD vi = 2e 的顶点数为 7 个，从而最多有 16 个顶点。 n i=1 10．D。 【解析】本题考查 B 树的性质。m 阶 B 树根结点至少有两棵子树，且这两棵子树可以是 空树，其他非叶结点至少有 m/2 棵子树，I 错误。II 为 B+树的性质。B 树又称多路平衡查找 树，叶结点都在同一层次上，可以看出是查找失败结点。结点的分裂不一定会使树高增 1， 如图 1 所示，只有当结点的分裂传到根结点，并使根结点也分裂，才会导致树高度增 1，如 图 2 所示。 『98』 100
    图 1 结点分裂不导致树高增 1（3 阶 B 树） 图 2 结点分裂导致树高增 1（3 阶 B 树） 11． A。 【解析】考查各种排序算法的性质。本题即分析排序算法的执行过程中，能否划分成多 个子序列进行并行的排序。快速排序在一趟划分成两个子序列后，各子序列又可并行排序； 归并排序的各个归并段可以并行排序，因此 II 和 V 满足并行性，而其他选项不能满足这样的 性质，故选 A。 12．C。 【解析】本题考查各种字长的区别与联系。指令字长通常取存储字长的整数倍，如果指 令字长等于存储字长的 2 倍，则需要 2 次访存，取指周期等于机器周期的 2 倍，如果指令字 长等于存储字长，取指周期等于机器周期，故 I 错误、II 正确。指令字长取决于操作码的长 度、操作数地址的长度和操作数地址的个数，与机器字长没有必然的联系，但为了硬件设计 方便，指令字长一般取字节或存储字长的整数倍，III 正确。指令字长一般取字节或存储字长 的整数倍，IV 错误。 注意：指令字长是指指令中包含二进制代码的位数；机器字长是 CPU 一次能处理的数 据长度，通常等于内部寄存器的位数；存储字长是一个存储单元存储的二进制代码（存储 字）的长度。 13．A。 【解析】考查小端方式的存储。小端方式是先存储低位字节，后存储高位字节。假设存 储该十六进制数的首地址是 0x00，则各字节的存储分配情况如下图所示。 地址 内容 0x00 87H 0x01 56H 0x02 34H 0x03 12H 注意：大端方式是先存储高位字节，后存储低位字节。小端方式和大端方式的区别是 字中的字节的存储顺序不同，采用大端方式进行数据存放符合人类的正常思维。 14．A。 【解析】本题考查无符号数的逻辑移位运算。A1B6H 作为无符号数，使用逻辑右移。1010 0001 1011 0110 右移一位得 0101 0000 1101 1011，即 50DBH。 注意：无符号数的移位方式为逻辑移位，不管是左移还是右移，都是添 0。 15．D。 【解析】本题考查ROM和RAM的特点。CD-ROM属于光盘存储器，是一种机械式的存储 『99』 302050 52插入60后，溢出302050 52 60结点分裂30 5220605030 522060 6850插入7030 522060 68 7050结点分裂30 52 6820705060再分裂20705060523068
    器，和ROM有本质的区别，I错误。Flash存储器是E2PROM的改进产品，虽然它也可以实现随 机存取，但从原理上讲仍属于ROM，而且RAM是易失性存储器，II错误。DRAM的读出方式并 不是破坏性的，读出后不需再生，III错误。SRAM采用双稳态触发器来记忆信息，因此不需要 再生；而DRAM采用电容存储电荷的原理来存储信息，只能维持很短的时间，因此需要再生， IV正确。 注意：通常意义上的ROM只能读出，不能写入。信息永久保存，属非易失性存储器。 ROM和RAM可同作为主存的一部分，构成主存的地址域。ROM的升级版：EPROM、EEPROM、 Flash。 16．D。 【解析】本题考查 Cache 与主存的映射原理。由于 Cache 被分为 64 个块，那么 Cache 有 64 行，采用直接映射，一行相当于一组。故而该标记阵列每行存储 1 个标记项，其中主存标 记项为 12bit（212=4096，是 Cache 容量的 4096 倍，那么就是地址长度比 Cache 长 12 位）， 加上 1 位有效位，故而为 64×13bit。 注意：主存-Cache 地址映射表（标记阵列）中内容：映射的 Cache 地址（直接映射不需 要因为 Cache 地址唯一，组相联只需要组号）、主存标记（命中判断）、有效位。如下图所 示。 17．A。 【解析】本题考查转移指令的执行。根据汇编语言指令 JMP * -9，即要求转移后的目标地 址为 2000H-09H=1FF7H，但因为 CPU 取出该指令后 PC 值已修改为 2002H，故转移指令的第 二字节的内容应为-11（十进制），写成补码为 F5H。 18．D。 【解析】本题考查运算器的组成。数据高速缓存是专门存放数据的 Cache，不属于运算器。 注意：运算器应包括算术逻辑单元、暂存寄存器、累加器、通用寄存器组、程序状态 字寄存器、移位器等。控制器应包括指令部件、时序部件、微操作信号发生器(控制单元)、 中断控制逻辑等，指令部件包括程序计数器(PC)、指令寄存器(IR)和指令译码器(ID)。 19．A。 【解析】考查流水线的性能分析。当 m 段流水稳定后，每个时钟周期流出一条指令，平 均每个指令周期流出 m 条指令，与具备 m 个并行部件的 CPU 的吞吐能力相等。 『100』
    20．D。 【解析】本题考查地址总线。地址总线的位数和实际存储单元个数是无关的，如 32 位的 地址线，可以仅仅用 2GB 的内存。而 MAR 的位数和其是相关的，一般这二者是相等的。 注意：地址总线的位数和最大存储单元个数相关，也和 MAR 的位数相关。地址总线的 宽度决定了 CPU 可以访存的最大物理地址空间。如 32 位的地址线，按字节寻址的可寻址 的最大容量为 232bit=4GB。 21．A。 【解析】本题考查中断的性能分析。因为传输率为 50KB/s，以 16bit 为传输单位，所以传 输一个字的时间为 1000ms/25000=0.04ms=40us。又由于每次传输的开销（包括中断）为 100 个节拍，处理器的主频为 50MHz，即传输的开销时间为 100*(1/50)=2us。则磁盘使用时占用 处理器时间的比例为 2/40=5%。 22．C。 【解析】本题考查通道的工作原理。通道方式是 DMA 方式的进一步发展，通道实际上也 是实现 I/O 设备和主存之间直接交换数据的控制器。通道的基本工作过程如下图。 CPU 通过执行 I/O 指令负责启停通道，以及处理来自通道的中断实现对通道的管理，因 此通道和程序（即 CPU）并没有完全并行，B 错误。而在设备工作时，它只与通道交互，此 时程序与其并行工作，C 正确。而 A、D 显然错误。 23．B。 【解析】本题考查用户态与和心态。设定定时器的初值属于时钟管理的内容，需要在内 核态运行；Trap 指令是用户态到内核态的入口，可以在用户态下运行；内存单元复位属于存 储器管理的系统调用服务，关闭中断允许位属于中断机制，它们都只能运行在内核态下。 24．D。 【解析】本题考查进程调度的时机。读者应掌握不能进行进程调度与切换的情况（处理 中断的过程、访问临界区、原子操作）；及应该进行进程调度与切换的情况。运行着的进程 由于时间片用完、或者运行结束、或者需要等待事件的发生（例如等待键盘响应）、或者出 错、或者自我阻塞等均可以激活调度程序进行重新调度，选择一个新的就绪进程投入运行。 新进程加入到就绪队列不是引起调度的直接原因，当 CPU 正在运行其它进程时，该进程仍需 等待。即使在采用高优先级优先调度算法的系统中，一个最高优先级的进程进入就绪队列， 仍需要考虑是否允许抢占，当不允许抢占时仍需等待。 『101』
    25．A。 【解析】本题考查进程的执行。两个进程运行过程的甘特图如下： A B CPU 20ms CPU 25ms IO1 30ms CPU 20ms IO2 20ms CPU IO1 20ms 30ms IO1 30ms CPU 20ms IO2 20ms CPU 10ms IO2 20ms CPU 45ms 可知进程 A 先运行结束，故选 A。 26．A。 【解析】本题考查进程的同步与互斥。进程 P0 和 P1 写为： P0： ① if(turn!=-1) turn=0; P1： ④ if(turn!=-1) turn=1; ② if(turn!=0) goto retry; ⑤ if(turn!=1) goto retry; ③ turn=-1; 当执行顺序为 1、2、4、5、3、6 时，P0，P1 将全部进入临界区，所以不能保证进程互 斥进入临界区。当顺序执行 1、4、(2、1、5、4)、(2、1、5、4)、…时，P0 和 P1 进入无限等 待，即出现“饥饿”现象。 ⑥ turn=-1; 27．B。 【解析】本题考查各存储分配方法的特点。固定分区存在内部碎片，当程序小于固定分 区大小时，也占用了一个完整的内存分区空间，导致分区内部有空间浪费，这种现象称内部 碎片。凡涉及到页的存储分配管理，每个页的长度都一样（对应固定），所以会产生内部碎 片，虽然页的碎片比较小，每个进程平均产生半个块大小的内部碎片。段式管理中每个段的 长度都不一样（对应不固定），所以只会产生外部碎片。 28．D。 【解析】本题考查虚拟存储管理的原理。按需调页适合具有较好的局部性的程序。堆栈 只在栈顶操作，栈底的元素很久都用不着，显然对数据的访问具有局部性。线性搜索即顺序 搜索，显然也具有局部性。矢量运算就是数组运算，数组是连续存放的，所以数组运算就是 邻近的数据的运算，也满足局部性。二分搜索先查找中间的那个元素，如果没找到，再查找 前半部分的中间元素或后半部分的中间元素，依此继续查找，显然每次搜寻的元素不都是相 邻的，二分搜索是跳跃式的搜索，所以不满足局部性，不适合“按需调页”的环境。 注意：要使得按需调页有效，要紧紧抓住按需调页被提出的前提，那就是程序运行的 局部性原理。 29．A。 【解析】本题考查缺页中断的计算。进程的工作集是 2 个页框，其中一个页框始终被程 序代码占用，所以可供数据使用的内存空间只有一个页框。在虚空间以行为主序存放，每页 存放 128 个数组元素，所以每一行占一页。程序 1 访问数组的方式为先行后列，每一次访问 都是针对不同的行，所以每一次都会产生缺页中断，一共 128＊128 次。程序 2 访问数组的 方式是先列后行，每次访问不同行时会产生缺页中断，一共 128 次。 『102』
    30．D。 【解析】本题考查文件系统的多个知识点。文件系统使用文件名进行管理，也实现了文 件名到物理地址的转换，A 错误。多级目录结构中，对文件的访问通过路径名和文件名进行， B 错误。文件被划分的物理块的大小是固定的，通常和内存管理中的页面大小一致，C 错误。 逻 辑记录是文件中按信息在逻辑上的独立含义来划分的信息单位，它是对文件进行存取操作的 基本单位，D 正确。 31．A。 【解析】本题考查文件的物理结构。对于 I，索引顺序文件如果存放在磁带上，则无法实 现随机访问，也就失去了索引的意义。对于 IV，在顺序文件的最后添加新的记录时，则不必 须复制整个文件。 32．A。 【解析】本题考查 I/O 软件的层次结构。在 I/O 子系统的层次结构中，设备驱动程序与硬 件（设备控制器）直接相关，负责具体实现系统对设备发出的操作命令或者通过设备状态寄 存器来读取设备的状态。用户级 I/O 软件是实现设备与用户交互的接口，它主要是一些库函 数。设备独立性软件是用于实现用户程序与设备驱动器的统一接口、设备命令、设备保护、 以及设备分配与释放等。中断处理层主要负责对中断的处理。 33．A。 【解析】此题引用了 OSI/RM 中服务访问点的概念，但考查的却是 TCP/IP 参考模型的知 识。在 TCP/IP 参考模型中，网络接口层的 SAP 是 MAC 地址；在网际层（也可称为网络层） 使用的是 IP 协议，其 SAP 便是 IP 地址；而传输层使用的主要协议为 TCP 和 UDP，TCP 使 用的 SAP 是 TCP 的端口号，UDP 使用的 SAP 是 UDP 的端口号。在 Internet 数据帧中，地址 “0x000F781C6001”是一个 48 位的物理地址，因此该地址属于数据链路层的服务访问点。 34．B。 【解析】本题考查奈奎斯特定理的应用。题干中已说明是有噪声的信道，因此应联系到 香农定理，而对于无噪声的信道，则应联系到奈奎斯特定理。奈奎斯特就是在采样定理和无 噪声的基础上，提出了奈氏准则：Cmax=f 采样×log2N=2f×log2N，其中 f 表示带宽。而香农公式 给出了有噪声信道的容量：Cmax=W×log2(1+S/N)，其中 W 为信道的带宽。它指出，想提高信 息的传输速率，应设法提高传输线路的带宽或者设法提高所传信号的信噪比。首先计算信噪 比 S/N=0.62/0.02=31；带宽 W=3.9-3.5=0.4MHz，由香农公式可知最高数据传输率 V=W×log2(1+ S/N) = 0.4×log2(1+31)=2Mbps。 35．A。 【解析】本题考查简单停止-等待协议机制。在停止等待协议中，如果在规定时间内没有 收到接收方的确认帧信息，发送方就会重新发送该帧，也就是发送了重复帧。为了避免因为 重复帧引起不必要的错误，简单停止-等待协议采用了帧序号机制，即：在规定的时间内未接 收到确认帧，即重新发送；此时接收到的帧为重复帧，而序号与前面一帧是相同的。接收端 连续接收到的帧如果序号相同，则认为是重复帧；如果帧序号不同，则理解为仅仅是内容相 同的不同的帧。 『103』
    36．A。 【解析】本题考查 CSMA 协议的各种监听。采用随机的监听延迟时间可以减少冲突的可 能性但其缺点也是很明显的：即使有多个站点有数据要发送，因为此时所有站点可能都在等 待各自的随机延迟时间，而媒体仍然可能处于空闲状态，这样就使得媒体的利用率较为低下， 故 I 错误。1-坚持 CSMA 的优点是：只要媒体空闲，站点就立即发送；它的缺点在于：假如 有两个或两个以上的站点有数据要发送，冲突就不可避免，故 II 错误。按照 P-坚持 CSMA 的规则，若下一个时槽也是空闲的，则站点同样按照概率 P 的可能性发送数据，所以说如果 处理得当 P 坚持型监听算法还是可以减少网络的空闲时间的，故 III 错误。 CSMA 有三种类型：①非坚持 CSMA：一个站点在发送数据帧之前，先对媒体进行检 测。如果没有其它站点在发送数据，则该站点开始发送数据。如果媒体被占用，则该站点 不会持续监听媒体而等待一个随机的延迟时间后再监听。②1-坚持 CSMA：当一个站点要发 送数据帧时，它就监听媒体，判断当前时刻是否有其他站点正在传输数据。如果媒体忙的 话，该站点等待直至媒体空闲。一旦该站点检测到媒体空闲，就立即发送数据帧。如果产 生冲突，则等待一个随机时间再监听。之所以叫“1-坚持”，是因为当一个站点发现媒体空闲 的时候，它传输数据帧的概率是 1。③P-坚持 CSMA：当一个站点要发送数据帧时，它先检 测媒体。若媒体空闲，则该站点以概率 P 的可能性发送数据，而有 1-P 的概率会把发送数 据帧的任务延迟到下一个时槽。P-坚持 CSMA 是非坚持 CSMA 和 1-坚持 CSMA 的折中。 37．B 。 【解析】考查 IP 分组。标识字段在 IP 分组进行分片时，其值就被复制到所有的数据报片 的标识字段中，但其值不变，故 I 无变化。路由器分片后，标志字段的 MF、DF 字段均应发 生相应的变化，而且由于数据部分长度发生变化，片偏移字段也会发生变化，故 II、III 均会 发生变化。总长度字段是指首部和数据部分之和的长度，它不是指未分片前的数据报长度， 而是指分片后的每一个分片的首部长度与数据长度的总和，所以 IV 会发生变化。而首部检 验和字段需要对整个首部进行检验，一旦有字段发生变化它也会发生改变，所以 V 也会发生 变化。 38．B。 【解析】本题考查子网划分与子网掩码。不同子网之间需通过路由器相连，子网内的通 信则无需经过路由器转发，因此比较各主机的子网号即可。将子网掩码 255.255.192.0 与主机 129.23.144.16 进行“与”操作，得到该主机网络地址为 129.23.128.0，再将该子网掩码分别与四 个候选答案的地址进行“与”操作，只有 129.23.127.222 的网络地址不为 129.23.128.0。因此该 主机与 129.23.144.16 不在一个子网中，需要通过路由器转发信息。 39．C。 【解析】本题考查 TCP 传输的性能分析。发送时延 t1=65535×8÷(1×109)s，往返时延 t2=2 ×0.01s，当达到最大吞吐量时信道接收到确认之后立刻发送下一报文段，时间间隔 t=t1+t2。 所以最大吞吐量为 65535×8÷(t1+t2)≈26.2Mbps。 40．B。 【解析】本题考查 TCP 的拥塞控制。此类题往往综合四种拥塞控制算法，解题时或画出 拥塞窗口变化曲线图，或列出拥塞窗口大小变化序列，尤其要注意在拐点处的变化情况。在 『104』
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料