参考答案 - 跨考网校.pdf

参考答案参考答案 1 1 1 1 B B B B 分析 显而易见 双链表最节省 2 2 2 2 C C C C 分析 当a c d同时在 S 中及a e f同时在 S 中时 栈的存储量达 到最大值 因此容量至少为3 3 3 3 3 C C C C 分析 快速解题 无论哪种入队方式 即先从左边入队还是先从右边入 队 a和b都应该相邻 这是出队序列合理的必要条件 只有选项C所给序列 中a与b不相邻 可以确定正确选项为 C 四个选项所给序列的进队操作序列分别为 L 代表左入 R 代表右入 A aL 或 aR bL cR dR eR B aL 或 aR bL cR dL eR C 不可能出现 D aL 或 aR bL cR dR eL 4 C4 C4 C4 C 分析 插入48以后 该二叉树根结点的平衡因子由 1变为 2 失去平衡 进行平衡调整 过程如下图 5 5 5 5 B B B B 分析 根据平衡二叉树的定义 任意结点左右子树的高度差的绝对值不 超过 1 选项A C D 的根结点左右子树差都不满足定义 6 A6 A6 A6 A 分析 哈夫曼树为带权路径长度最小的二叉树 不一定是完全二叉树 哈夫曼树中没有度为 的 结点 B 正确 构造哈夫曼树时 最先选取两个权 值最小的结点作为左右子树构造一棵新的二叉树 C 正确 哈夫曼树中任 一非叶结点 P 的权值为其左右子树根结点权值之和 其权值不小于其左右子 树 根结点的权值 在与结点 P 的左右子树根结点处于同一层的结点中 若存在权值大于结点 P 权值的结 点 Q 那么结点 Q 与其兄弟结点中权值 较小的一个应该与结点 P 作为左右子树构造新的二叉树 综上 可知 哈夫 曼树中任一非叶结点的权值一定不小于下一层任一结点的权值 7 C7 C7 C7 C 分析 要保证无向图 G 在任何情况下都是连通的 即任意变动图 G 中 的边 G 始终保持连通 首 先需要 G 的任意六个结点构成完全连通子图 G1 需 15 条边 然后再添一条边将第 7 个结点与 G1 连 接起来 共需 16 条边 8 D8 D8 D8 D 分析 D 项是 B 树的特点 而不是 B 树的特点 9 B9 B9 B9 B 分析 折半查找法在查找不成功时和给定值进行比较的关键字个数最多 为 1 即折半查找判定树 的高度 在本题中 n 16 故比较次数最多为 5 10101010 A A A A 图 a 原始堆 图 b 插入 3图 c 调整结束 11 A11 A11 A11 A 本题考查冒泡排序算法的执行过程 1 1 1 12 2 2 2 C C C C 指令与数据都是以同样的方式存储在计算机存储器中 处理器先读入指 令 根据指令再 读 写数据 1 1 1 13 3 3 3 D D D D 分析 从常识上看也大体上可以知道这个结果是全选 优化 一般就是 对性能的提高 自然会使得计算机在执行程序时的用时缩短 理论上来看 程序执行时间 程序指令数 每 条指令时钟 CPI 时钟周期 T 提高时钟频 率可以缩短时钟周期 编译优化可能减少程序的指令数或者优化指令结构 优 化数据通路结构有可能减少指令时钟 14 D14 D14 D14 D z 显然应该是正确的 对于 16 进制负数的补码换算 可以用 FFFG 去减 去负数绝对值 其中 G 表示 16 只要算到最右边一个非 0 位即可 1 1 1 15 5 5 5 B B B B 分析 首先应当明确 int float double 表达数据的精度是提高的 并且从低 到高的转换一般不损失精度 而从高到低的转换可能损失精度 此 题中需要找出结果为真的 按照前面说的规则 很容易就可以判断出 一定是真 此时便可以写出结果 但出于 严谨 我们继续判断 而 因为 先将一个浮点型书转换为整数 后又转为浮点型 那么精 度一定会有损失 必为假 看上去是相等的 但在计算机的执行中 需要考虑到位数的限 制 按题目的说明 IEEE754 表示的 float 和 double 分别有 7 位和 15 位的 有效位 本题中 d f 超过 double 的有效位数 15 位 因此在 d f 中 f 将被忽略 则左边 等式的结果应当为 0 d d 0 16 A16 A16 A16 A 分析 RAM 即为随机存储器 存储单元的内容可按需随意取出或存入 按 照存储信息的 不 同 随 机 存 储 器 又 分 为 静 态 随 机 存 储 器 StaticRAM SRAM 和 动 态 随 机 存 储 器 DynamicRAM DRAM 其中动态随机存储器需要每隔一段时间刷新一次 ROM 是只读存储器 是一种只能读出事先所存数据的固态半导体存储器 其特性是一旦 储存资料就无法再将之改变或删除 通常用在不需经常变更资 料的电子或电脑系统中 资料并且不会因为电源关闭而消失 RAM 断电会失去信息 而 RAM 不会 所以 I 对 RAM 和 ROM 都是随机存储方式 Cache 需要具有信息的输入和输出 而 ROM 只可读 不可输入 所以不 可以作为 Cache 只有动态的 RAM 才需要刷新 1 1 1 17 7 7 7 D D D D 这类计算注意单位一致 位或字节或字 芯片数 总要求容量 单片容量 ROM 4KB 2KB 2 RAM 64K 4K 8b 4K 4b 30 1 1 1 18 8 8 8 A A A A RISC 讲究的是指令的短小精悍 大多在一个时钟周期内完成 所有操作 数都在寄存器 内 所以需要较多的寄存器 相对来说寻址方式较少 指令的 格式 种类也较少 微程序需 要多次读控制存储器 CM 即使用 Cache 执行 也比较慢 简单控制还是直接用组合逻辑较好 1 1 1 19 9 9 9 D D D D 分析 Cache 是物理主存块的副本 TLB 是页表的副本 即一个是内存内 容的副本 一个是地址的副本 Cache 中有的主存中必定有 TLB 中有的也 表中也必定有 D 中在 Cache 中命中在 Page 不命中 即表示主存中没有 这是不可能的 所以错误 20202020 A A A A 分析 所谓可见 就是程序员可以对其进行主动的修改 知道这个 本题 便很容易解答 IR MAR MDR 是 CPU 的内部工作寄存器 在程序执行的过程中是自动赋 值的 程序员无 法对其操作 而 PC 程序计数器中 存放的是下一条需要执 行的指令 因而程序员可以通过 转移指令 调动子程序等指令来改变其内容 解答本题 需要对程序指令在 CPU 中的执行 过程有清晰的理解和记忆 2 2 2 21 1 1 1 D D D D 分析 A 中 CRT 是纯平显示器的缩写 CPI 是每条指令执行周期数 RAM 是随机存储 器 D 中各项均为总线标准 22222222 D D D D 微程序相当于软件 每条指令相当于若干条微指令 就要读若干次控制存 储器 CM 自 然就比较慢 但存储器的内容修改方便 所以扩展相对容易 而 硬布线相当于硬件 刚好相 反 执行块 修改难 2 2 2 23 3 3 3 B B B B 2 个时钟 4 字节 每个时钟周期 2 字节 2B 10MHz 20MB s 2 2 2 24 4 4 4 B B B B 分析 本题中提到的在单级中断系统中 不允许中断嵌套 因而 整个中 断处理的过程 为 考研中应当按照这个顺序理解 1 关中断 2 保存断 点 3 识别中断源 4 保存 现场 5 中断事件处理 6 恢复现场 7 开 中断 8 中断返回 其中 1 3是由硬件完 成 其余的由中断服务程序完成 25 B25 B25 B25 B 分析 信号量用来表示某资源的当前可用数量 当信号量 K 0 时 表示 此资源还有 K 个相关资源可用 没有等待该资源的进程 而当信号量K B k 2 则 A k 2 A k 都大于 B 0 B k 2 1 且 B k 2 B k 都大于 B 0 B k 2 1 第 k 大的整数不可能在 B 0 B k 2 1 舍弃 B 0 B k 2 1 类似地 第 k 大的整数也不可能在 A k 2 1 A k 中 舍弃之 这样得到两 个新的序列 A 0 A k 2 和 B k 2 B k 再对它们递归处理 3 如果 A k 2 120 满足要求 所以两个子网 的子网掩码都为 1111111111111111 11111111 10000000 即 255 255 255 128 所划分的两个子网的网络地址分别为 202 118 1 00000000 和202 118 1 10000000 为了理解方便我将最后一个字节用二进制表示 这样可以看清楚子网的划分过 程 即 202 118 1 0 和 202 118 1 128 综上 划分结果为 子网 1 202 118 1 0 子网掩码为 255 255 255 128 子网 2 202 118 1 128 子网掩码为 255 255 255 128 或者写成 子网 1 202 118 1 0 25 子网 2 202 118 1 128 25 2 下面分 2 种情况 a 假设子网 1 分配给局域网 1 子网 2 分配给局域网 2 路由器 R1 到局域网 1 和 局域网 2 是直接交付的 所以下一跳 IP 地址可以不写 打一横即可 接口 分别是从 E1 E2 转 发 出 去 路 由 器 R1 到 域 名 服 务 器 是 属 于 特 定 的 路 由 所 以 子 网 掩 码 应 该 为255 255 255 255 只有和全 1 的子 网掩码相与之后才能 100 保证和目的网络地址一样 从而 选择该特定路由 而路 由器 R1 到域名服务器应该通过接口 L0 转发出去 下一跳 IP 地址应 该是路由器 R2 的 L0 接口 即 IP 地址为 202 118 2 2 路由器 R1 到互联网属于默认路由 记 住就好 课本 127 页 而前面我们已经提醒过 默认路由的目的网络 IP 地址和 子网掩码都 是 0 0 0 0 而路由器 R1 到互联网应该通过接口 L0 转发出去 下一 跳 IP 地址应该是路由器 R2 的 L0 接口 即 IP 地址为 202 118 2 2 故详细答 案见下表 目的网络地址子网掩码下一跳 IP 地址接口 202 118 1 0255 255 255 128 E1 202 118 1 128255 255 255 128 E2 202 118 3 2255 255 255 255202 118 2 2L0 0 0 0 00 0 0202 118 2 2L0 b 假设子网 1 分配给局域网 2 子网 2 分配给局域网 1 中间过程几乎一 样 答案请看下表 目的网络地址子网掩码下一跳 IP 地址接口 202 118 1 128255 255 255 128 E1 202 118 1 0255 255 255 128 E2 202 118 3 2255 255 255 255202 118 2 2L0 0 0 0 00 0