2023 年 全国 硕士 探讨 生 招生 考试 计算机 科学 与 技术 学科 联考 计算机 学科 专业 基础 综合 试题 一 、 单项 选择 题 ： 1 - 40 小 题 ， 每 小 题 2 分 ， 共 80 分 。 下列 每 题 给 出 的 四 个 选项 中 ， 只有 一个 选项 符合 试题 要求 。 1 . 设 n 是 描述 问题 规模 的 非 负 整数 , 下列 程序 段 的 时间 困难 度 是 x = 0 ; while ( n > = ( x + 1 ) * ( x + 1 ) ) x = x + 1 ; A . O ( \ log n ) B . O ( n ^ { 1 / 2 } ) C . O ( n ) D . O ( n ^ { 2 } ) 2 . 若 将 一 棵 树 T 转化 为 对应 的 二叉树 BT , 则 下列 对 BT 的 遍 历 中 , 其 遍 历 序列 与 T 的 后 根 遍 历 序列 相同 的 是 A . 先 序 遍 历 B . 中 序 遍 历 C . 后 序 遍 历 D . 按 层 遍 历 3 . 对 n 个 互不 相同 的 符号 进行 哈夫曼 编码 。 若 生成 的 哈夫曼 树 共有 115 个 结点 , 则 n 的 值 是 A . 56 B . 57C . 58 D . 604 . 在 随意 一 棵 非 空 平衡 二叉树 ( AVL 树 ) T1 中 , 删除 某 结点 v 之后 形成 平衡 二叉树 T _ { 2 } , 再 将 w 插入 T _ { 2 } 形成 平衡 二 又 树 T3 。 下列 关于 T1 与 T3 的 叙述 中 , 正确 的 是 I . 若 v 是 T1 的 叶 结点 , 则 T1 与 T _ { 3 } 可能 不 相同 . 若 v 不是 T1 的 叶 结点 , 则 T1 与 T3 确定 不 相同 . 若 v 不是 Ti 的 叶 结点 , 则 Ti 与 T3 确定 相同 A . 仅 IB . 仅 IIC . 仅 I 、 IID . 仅 I 、 III 5 . 下 图 所 示 的 AOE 网 表示 一 项 包含 8 个 活动 的 工程 。 活动 d 的 最 早 起先 时间 和 最 迟 起先 时间 分别 是 A . 3 和 7B . 12 和 12C . 12 和 14 D . 15 和 15d = 72 a = 34 g = 6 e = 6b = 42 % c = 83 h = 95 f = 106 . 用 有 向 无 环 图 描述 表达 式 ( x + y ) * ( ( x + y ) / x ) , 须要 的 顶点 个数 至少 是 A . 5B . 6C . 8D . 97 . 选择 一个 排序 算法 时 , 除 算法 的 时空 效率 外 , 下列 因素 中 , 还 须要 考虑 的 是 I . 数据 的 规模 II . 数据 的 存储 方式 III . 算法 的 稳定 性 V . 数据 的 初始 状态 A . 仅 IIIB . 仅 I 、 IIC . 仅 II 、 III 、 IVD . I 、 III 、 III 、 IV 8 . 现有 长度 为 11 且 初始 为 空 的 散 列表 HT , 散 列 函数 是 HI ( key ) = key \ % 7 , 接受 线性 探查 ( 线性 探测 再 散 列 ) 法 解决 冲突 将 关键 字 序列 87 , 40 , 30 , 6 , 11 , 22 , 98 , 20 依次 插入 到 HT 后 , HT 查找 失败 的 平均 查找 长度 是 A . 4B . 5 . 25 C . 6D . 6 . 299 . 设 主 串 T = “ abaabaabcabaabc ” , 模式 串 S = “ abaabc ” , 接受 KMP 算法 进行 模式 匹配 , 到 匹配 成功 时 为止 , 在 匹配 过程 中 进行 的 单个 字符 间 的 比较 次数 是 A . 9 B . 10C . 12 D . 1510 . 排序 过程 中 , 对 尚未 确定 最终 位置 的 全部 元素 进行 一 遍 处理 称为 一 “ 趟 ” 。 下列 序列 中 , 不行 能 是 快速 排序 其次 趟 结果 的 是 A . 5 , 2 , 16 , 12 , 28 , 60 , 32 , 72 B

2012 年 考研 计算机 统考 408 真题 一 、 单项 选择 题 1 . 求 整数 n ( n > = 0 ) 阶乘 的 算法 如下 , 其 时间 复杂 度 是 _ 1 _ 。 A . O ( logzn ) B . O ( n ) C . O ( nlog 2n ) D . O ( n * ) 2 . 已知 操作 符 包括 + ' 、 ' - 、 ' * ' 、 ' / ' 、 ' ( 和 ' ) ' 。 将 中缀 表达 式 a + b - a * ( ( c + d / e - f ) + g 转换 为 等价 的 后缀 表达 式 ab + acd + e / f - * - g + 时 , 用 栈 来 存放 暂时 还 不 能 确定 运算 次序 的 操作 符 , 若 栈 初始 为 空 , 则 转换 过程 中 同时 保存 在 栈 中 的 操作 符 的 最大 个数 是 2 2 A . 5 B . 7 C . 8 D . 11 3 . 若 一 棵 二叉树 的 前 序 遍 历 序列 为 a , e , b , d , c , 后 序 遍 历 序列 为 b , c , d , e , a , 则 根 结点 的 孩子 结点 _ 3 _ 。 A . 只有 e B . 有 e , b C . 有 e , c D . 无法 确定 4 . 若 平衡 二 叉 的 高度 为 6 , 且 所有 非 叶 结点 的 平衡 因子 均 为 1 , 则 该 平衡 二叉树 的 结点 总数 为 _ 4 。 A . 10 B . 20 C . 32 D . 33 5 . 对 有 n 个 结点 、 e 条 边 且 使用 邻接 表 存储 的 有 向 图 进行 广度 优先 遍 历 , 其 算法 时间 复杂 度 是 _ 5 _ 。 A . O ( n ) B . O ( e ) C . O ( n + e ) D . O ( n * e ) 6 . 若 用 邻接 矩阵 存储 有 向 图 , 矩阵 中 主 对 角 线 以下 的 元素 均 为 零 , 则 关于 该 图 拓扑 序列 的 结论 是 _ 6 _ 。 A . 存在 , 且 唯一 B . 存在 , 且 不 唯一 C . 存在 , 可能 不 唯一 D . 无法 确定 是否 存在 7 . 对 如下 有 向 图 带 权 图 , 若 采用 迪 杰斯特 位 ( Djikstra ) 算法 求 从 源点 a 到 其他 各 顶点 的 最 短 路径 , 则 得到 的 第 一 条 最 短 路径 的 目标 顶点 是 b , 第 二 条 最 短 路径 的 目标 顶点 是 c , 后续 得到 的 其余 最 短 路径 的 目标 顶点 依次 是 1 _ 0 3 b d 、 a C 1 5 ( ) C 4 A.d , e , f B . e , d , f C . f , d , e D . f , e , d 8 . 下列 关于 最小 生成 树 的 叙述 中 , 正确 的 是 _ 8 _ 。 1 . 最小 生成 树 的 代价 唯一 。 II . 所有权 值 最小 的 边 一定 会 出现 在 所有 的 最小 生成 树 中 。 III . 使用 普里姆 ( Prim ) 算法 从 不同 顶点 开始 得到 的 最小 生成 树 一定 相同 。 IV . 使用 普里姆 算法 和 克鲁 斯卡尔 ( Kruskal ) 算法 得到 的 最小 生成 树 总 不同 。 A . 仅 1 B . 仅 C . 仅 1 、 III D . 仅 II 、 IV 9 . 已知 一 颗 3 阶 B - 树 , 如下 图 所 示 。 删除 关键 字 78 得到 一 颗 新 B - 树 , 其 最 右 叶 结点 中 的 关键 字 是 _ 3 _ 。 45 1735 5565 10 21 37 47 6062 78 A . 60 B . 60 , 62 C . 62 , 65 D . 65 10 . 在 内部 排序 过程 中 , 对 尚未 确定 最终 位置 的 所有 元素 进行 一 遍 处理 称为 一 趟 排序 。 下列 排序 方法 中 , 每 一 趟 排序 结束 都 至

1 . 为 处理 计算机 与 打印 机 之间 速度 不 匹配 的 问题 , 一般 设置 一 种 打印 数据 缓冲 区 , 主机 将要 输出 的 数据 依次 写入 该 缓冲 区 , 而 打印 机 则 依次 从 该 缓冲 区 中 取出 数据 。 该 缓冲 区 的 逻辑 构造 应该 是 A . 栈 B . 队列 C . 树 D . 图 2 . 设 栈 S 和 队列 Q 的 初始 状态 均 为 空 , 元素 abcdefg 依次 进入 栈 S 。 若 每 个 元素 出 栈 后 立即 进入 队列 Q , 且 7 个 元素 出 队 的 顺序 是 bdcfeag , 则 栈 S 的 容量 至少 是 A . 1 B . 2C . 3D . 43 . 给定 二叉树 图 所 示 。 设 N 代表 二叉树 的 根 , L 代表 根 结点 的 左 子 树 , R 代表 根 结点 的 右 子 树 。 若 遍 历 后 的 结点 序列 为 3 , 1 , 7 , 5 , 6 , 2 , 4 , 则 其 遍 历 方式 是 1234567 A . LRNB . NRLC . RLND . RNL 4 . 下列 二 叉 排序 树 中 , 满足 平衡 二叉树 定义 的 是 A . B . C . D . 5 . 已知 一 棵 完全 二叉树 的 第 6 层 ( 设 根 为 第 1 层 ) 有 8 个 叶 结点 , 则 完全 二叉树 的 结点 个数 最 多 是 A . 39 B . 52 C . 111 D . 1196 . 将 森林 转换 为 相应 的 二叉树 , 若 在 二叉树 中 , 结点 u 是 结点 v 的 父 结点 的 父 结点 , 则 在 原来 的 森林 中 , u 和 v 可能 具有 的 关系 是 I . 父子 关系 II . 弟兄 关系 III . u 的 父 结点 与 v 的 父 结点 是 弟兄 关系 A . 只有 IIB . I 和 IIC . I 和 IIID . I 、 II 和 III 7 . 下列 有关 无 向 连通 图 特征 的 论述 中 , 正确 的 是 I . 全部 顶点 的 度 之 和 为 偶数 II . 边 数 不 小于 顶点 个数 减 1 III . 至少 有 一 种 顶点 的 度 为 1A . 只有 IB . 只有 IIB . 只有 IID . I 和 IIII 8 . 下列 论述 中 ， 不 符合 m 阶 B 树 定义 要求 的 是 A . 根 节点 最 多 有 m 棵 子 树 B . 全部 叶 结点 都 在 同 一 层 上 C . 各 结点 内 关键 字 均 升 序 或 降 序 排列 D . 叶 结点 之间 经过 指针 链接 9 . 已知 关键 序列 5 , 8 , 12 , 19 , 28 , 20 , 15 , 22 是 小 根 堆 ( 最小 堆 ) , 插入 关键 字 3 , 调整 后 得到 的 小 根 堆 是 A . 3 , 5 , 12 , 8 , 28 , 20 , 15 , 22 , 19 B . 3 , 5 , 12 , 19 , 20 , 15 , 22 , 8 , 28 C . 3 , 8 , 12 , 5 , 20 , 15 , 22 , 28 , 19 D . 3 , 12 , 5 , 8 , 28 , 20 , 15 , 22 , 1910 . 若 数据 元素 序列 11 , 12 , 13 , 7 , 8 , 9 , 23 , 4 , 5 是 采用 下列 排序 措施 之一 得到 的 第 二 趟 排序 后 的 成果 , 则 该 排序 算法 只能 是 A . 起泡 排序 B . 插入 排序 C . 选择 排序 D . 二 路 归并 排序 11 . 冯 · 诺依曼 计算机 中 指令 和 数据 均 以 二进制 形式 寄存 在 存储 器 中 , CPU 辨别 它们 的 根据 是 A . 指令 操作 码 的 译码 成果 B . 指令 和 数据 的 寻址 方式 C . 指令 周期 的 不同 阶段 D . 指令 和 数据 所在 的 存储 单元 12 . 一 种 C 语言 程序 在 一 台 32 位 机器 上 运营 。 程序 中

1 、 下列 对 顺序 存储 的 有序 表 ( 长度 为 n ) 实现 给定 操作 的 算法 中 平均 时间 复杂 度 为 O ( 1 ) 的 是 DA 、 查找 包含 指定 值 元素 的 值 B 、 插入 包含 指定 值 元素 的 算法 C 、 删除 第 i 个 元素 的 算法 D 、 获取 第 i 个 值 的 算法 2 、 现有 非 空 双向 链表 L ， 其 结点 结构 为 prer 、 data 、 next 。 prer 是 指 向前 直接 前驱 结点 的 指针 ， next 是 指向 直接 后继 结点 的 指针 。 若 要 在 L 中 指针 p 所 指向 的 结点 （ 非 尾 结点 ） 之后 插入 指针 s 指向 的 新 结点 ， 则 在 执行 了 语句 序列 ： “ s - > next = p - > next ; p - > next = s ” ， 后 ， 还要 执行 A 、 s - > next - > prer = p ; 3 、 若 采用 三元 组 表 存储 结构 存储 系数 矩阵 M 。 则 除 三元 组 外 ， 下列 数据 中 还 需要 保存 的 是 （ ） I . M 的 行 数 IIM 中 包含 非 零 元素 的 行 数 III . M 的 列 数 IVM 中 包含 非 零 元素 的 列 数 A . 仅 I 和 IIIB . 仅 I 和 IVC . 仅 II 和 IVD ， I , II , III , IV 4 、 在 有 6 个 字符 组成 的 字符 集 S 中 ， 各个 字符 出现 的 频次 分别 为 3 , 4 , 5 , 6 , 8 , 10 ， 为 S 构造 的 哈夫曼 树 的 加权 平均 长度 为 （ ） A . 2 . 4B . 2 . 5C . 2 . 67 D . 2 . 755 、 已知 一 棵 二叉树 的 树 形 如 图 ， 若 其 后 序 遍 历 为 f , d , b , e , c , a ， 则 其 先 序列 为 （ ） A . aedfbcB . acebdfC . cabefdD . dfebac 6 、 已知 无 向 连通 图 G 中 各 边 的 权 值 均 为 1 ， 下列 算法 中 一定 能够 求 出 图 G 中 从 某 顶点 到 其余 各个 顶点 最 短 路径 的 是 （ ） I . 普利姆 算法 II 克鲁斯 卡尔 算法 III . 图 的 广度 优先 搜索 A . 仅 IB . 仅 IIIC . 仅 II 和 ID ， I , II , III 7 、 下列 关于 非 空 B 树 的 叙述 中 ， 正确 的 是 插入 操作 可能 增加 树 的 高度 删除 操作 一定 会 导致 叶 结点 的 变化 查找 某 关键 字 一定 是 要 查找 到 叶 结点 插入 的 新 关键 字 最终 位于 叶 结点 中 A 、 仅 1 B 、 仅 12C 、 仅 34 D 、 仅 1248 、 对 含有 600 个 元素 的 有序 顺序 表 进行 折半 查找 ， 关键 字 之间 的 比较 次数 最 多 是 （ ） A . 9 B . 10C . 30D . 3009 、 现有 长度 为 5 ， 初始 为 空 的 散 列表 HT ， 散 列表 函数 H ( K ) = ( k + 4 ) % 5 用 线性 探查 再 散 列 法 解决 冲突 。 若 将 关键 字 序列 20 , 22 , 12 , 25 依次 插入 HT 中 ， 然后 删除 关键 字 25 ， 则 HT 中 查找 失败 的 平均 查找 长度 A 、 1 B 、 1 . 6 C 、 1 . 8 D 、 2 . 210 、 下列 排序 算法 中 ， 不 稳定 的 是 （ ） I . 希尔 排序 II 归并 排序 III . 快速 排序 IV . 堆 排序 V . 基数 排序 A . 仅 I 和 IIB . 仅 II 和 VC . 仅 I ， III ， IVD ， III , IVV 11 、 使用 快速 排序 算法 对 数据 进行

一 、 选择 题 1 . 下列 说法 正确 的 是 ： （ A ） A . 计算机 网络 是 指 将 计算机 与 通信 设备 互相 连接 ， 以便 实现 资源 共享 和 信息 传递 B . 因特网 是 由 全球 范围 的 许多 互联网 所 组成 C . 互联网 是 指 将 一个 计算机 与 另 一个 计算机 互相 连接 D . 局域 网 是 指 建立 在 地理 上 相邻 范围 内 的 计算机 互联网 2 . 下列 关于 OSI 参考 模型 的 描述 ， 不 正确 的 是 （ B ） A . 会话 层 是 在 用户 端 进行 处理 的 B . 物理 层 对 物理 设备 和 媒体 有着 直接 的 控制 作用 C . 表示 层 的 主要 功能 是 数据 的 转换 编码 格式 D . 应用 层 是 网络 服务 与 最终 用户 之间 的 接口 层 3 . 下列 不 属于 传输 层 服务 的 是 （ B ） A . 可靠 数据 传输 B . 数据 的 加密 与 解密 C . 数据 的 传输 D . 会话 复用 与 分解 4 . 以下 说法 中 错误 的 是 （ C ） A . 在 计算机 网络 中 ， 争 用 的 信道 采用 的 信道 访问 方式 有 ALOHA 和 CSMA 等 B . 网络 互 连 设备 将 LAN 、 MAN 或 WAN 连接 起来 ， 是 构成 因特网 的 重要 组成 部分 C . OnlySpanningTree 协议 能 防止 环路 的 产生 D . 使 许多 网络 硬件 实例 连接 在 一起 的 设备 是 集 线 器 5 . 在 因特网 中 使用 UDP 协议 工作 的 是 （ D ） A . 聊天 室 、 网游 B . 电流 新 箱 C . WWW D . 文件 传输 6 . 在 因特网 中 使用 TCP 协议 时 ， 对 应用 程序 定义 的 应用 层 报文 的 是 （ A ） A . 数据 B . 数据 包 C . 分组 D . 标志 7 . 对于 计算机 网络 技术 而 言 ， 下列 说法 中 不 正确 的 是 （ D ） A . 不同 网络 的 协议 实现 方式 基本 上 是 相同 的 B . 应用 层 、 传输 层 与 网络 层 的 选择 和 设计 对 网络 性能 有 很 大 影响 C . 控制 层 和 接口 层 在 各种 网络 技术 中都 有着 不同 的 应用 D . 不同 网络 技术 还 包括 不同 的 硬件 设备 8 . 对于 目前 主宰 全球 互联网 的 因特网 ， 以下 说法 中 正确 的 是 （ B ） A . 其 标志 是 一个 专门 为 因特网 设计 的 网络 操作 系统 B . 目前 主要 的 国际 互联网 是 以 IP 、 TCP 、 UDP 协议 为 主 C . 用户 要 想 上网 就 必须 安装 一个 Internet Explorer D . 安全 隧道 协议 是 PPTP 和 L2 T P 9 . 下面 是 数据 链路 层 提供 的 服务 的 描述 ， 不 正确 的 一 项 是 （ B ） A . 封装 成 帧 B . 可靠 传输 C . 差错 侦测 与 纠正 D . 透明 传输 10 . 下列 选项 中 属于 计算机 网络 骨干 网 的 是 （ C ） A . 以太网 B . 局域 网 C . 国际 互联网 D . 广域 网 二 、 简答 题 1 . 计算机 网络 的 拓扑 结构 有 哪些 ？ 简述 各自 特点 。 2 . TCP / IP 模型 和 OSI 模型 分别 有 几 层 ？ 其 各 层 分别 是 什么 ？ 3 . 什么 是 TCP 的 三 次 握

研究 生 考试 考研 计算机 学科 专业 基础 ( 408 ) 复习 试卷 ( 答案 在 后面 ) 一 、 单项 选择 题 （ 本 大 题 有 40 小 题 ， 每 小 题 2 分 ， 共 80 分 ） 1 、 下列 对 顺序 存储 的 有序 表 （ 长度 为 n ） 实现 给定 操作 的 算法 中 平均 时间 复杂 度 为 O ( 1 ) 的 是 A . 查找 包含 指定 值 元素 的 值 B . 插入 包含 指定 值 元素 的 算法 C . 删除 第 i 个 元素 的 算法 D . 获取 第 i 个 值 的 算法 2 、 现有 非 空 双向 链表 L ， 其 结点 结构 为 PrevDataNext 。 Prev 是 指 向前 直接 前驱 结点 的 指针 ， Next 是 指向 直接 后继 结点 的 指针 。 若 要 在 L 中 指针 p 所 指向 的 结点 （ 非 尾 结点 ） 之后 插入 指针 s 指向 的 新 结点 ， 则 在 执行 了 语句 序列 ： “ s - > Next = p - > Next ; p - > Next = s ” 后 ， 还 需要 执行 3 、 若 元素 a , b , c , d , e , f 依次 进 栈 ， 允许 进 栈 、 退 栈 操作 交替 进行 ， 但 不 允许 连续 三 次 进行 退 栈 操作 ， 则 不 可能 得到 的 出 栈 序列 是 A.d , c , e , b , f , aB . c , b , d , a , e , fC . b , c , a , e , f , dD . a , f , e , d , c , b4 、 下列 关于 计算机 系统 中 的 总线 说法 错误 的 是 ： A . 数据 总线 用于 传输 数据 信息 。 B . 地址 总线 决定 了 CPU 可以 直接 访问 的 主 存 空间 大小 。 C . 控制 总线 用于 传输 控制 信号 和 其他 命令 。 D . 总线 宽度 决定 了 数据 传输 的 速度 。 5 、 在 二叉树 的 遍 历 方法 中 ， 若 按照 访问 根 节点 、 左 子 树 、 右 子 树 的 顺序 进行 访问 ， 则 属于 哪 种 遍 历 ？ A . 前 序 遍 历 B . 中 序 遍 历 C . 后 序 遍 历 D . 层次 遍 历 6 、 在 计算机 网络 中 ， TCP 协议 的 主要 功能 是 什么 ？ A . 提供 无 连接 的 服务 B . 提供 面向 连接 的 可靠 数据 传输 服务 C . 负责 数据 报 的 路由 选择 D . 在 物理 链路 上 实现 比特 流 的 透明 传输 7 、 在 计算机 组成 原理 中 ， 以下 哪 种 存储 器 具有 随机 访问 的 特性 ？ A . 随机 存取 存储 器 （ RAM ） B . 只读 存储 器 （ ROM ） C . 磁盘 D . 光盘 8 、 在 数据 结构 中 ， 以下 哪 种 数据 结构 支持 高效 的 二 分 查找 ？ A . 队列 B . 链表 C . 栈 D . 二 叉 搜索 树 9 、 在 计算机 网络 中 ， 以下 哪 种 协议 用于 在 传输 层 提供 端到端 的 通信 ？ A . TCP （ 传输 控制 协议 ） B . IP （ 互联网 协议 ） C . HTTP （ 超 文本 传输 协议 ） D . SMTP （ 简单 邮件 传输 协议 ） 10 、 在 计算机 系统 中 ， 以下 哪 种 存储 器 的 访问 速度 最 快 ？ A . 硬盘 （ HDD ） B . 固态 硬盘 （ SSD ） C . 内存 （ RAM ） D . 硬盘 阵列 （ RAID ） 11 、 以下 哪个 术语 描述 的 是 在 计算机 系统 中 ， 将

一 、 选择 题 1 . （ 2010 年 试题 第 1 题 ） 若 元素 a , b , c , d , e , f 依次 进 栈 ， 允许 进 栈 、 退 栈 操作 交替 进行 ， 但 不 允许 连续 三 次 进行 退 栈 操作 ， 则 不 可能 得到 的 出 栈 序列 是 （ D ） A.d ， c ， e ， b ， f ， aB ． c ， b ， d ， a ， e ， fC . b ， c ， a ， e ， f ， dD ． a ， f ， e ， d ， c ， b 翔 高 辅导 书 ） 《 模拟 试题 （ 十 ） 》 第 2 题 有 A , B , C , D , E5 个 元素 按 次序 入 栈 ， 在 各种 可能 的 出 栈 次序 中 ， 以 元素 C , D 最先 出 栈 的 序列 中 ， 下列 正确 的 一 组 是 （ B ） A . CDBAECDABEB . CDEBACDBEAC . CDEABCDABED . CEBAECDAEB 命中 情况 ： 均 是 考查 对 堆栈 的 基本 操作 ， 并且 都 在 基本 操作 的 基础 上 添加 了 限制 条件 。 命中 类型 ： 直接 命中 （ 2 分 ） 2 . （ 2010 年 试题 第 3 题 ） 下列 线索 二叉树 中 （ 用 虚线 表示 线索 ） ， 符合 后 序 线索 树 定义 翔 高 辅导 书 ） 《 习题 精编 》 第 44 页 综合 应用 题 题 第 1 题 设 一 棵 二叉树 如下 图 所 示 ： （ 4 ） 试 画 出 该 二叉树 的 一 棵 后 序 线索 二叉树 。 命中 情况 ： 均 是 考查 线索 二叉树 的 概念 ， 并且 都 是 后 序 线索 二叉树 。 命中 类型 ： 直接 命中 （ 2 分 ） 3 . （ 2010 年 试题 第 4 题 ） 在下 图 所 示 的 平衡 二叉树 中 ， 插入 关键 宇 48 后 得到 一 棵 新 平衡 二叉树 。 在 新 平衡 二叉树 中 ， 关键 字 37 所在 结点 的 左 、 右 子 结点 中 保存 的 关键 字 分别 是 翔 高 辅导 书 ） 《 习题 精编 》 第 48 页 综合 应用 题 第 3 题 设 结点 序列 F = { 18 ， 36 ， 30 ， 42 ， 45 ， 48 ， 60 } ， 用 平衡 二叉树 插入 算法 将 F 中 的 结点 依次 插入 ， 建立 一 棵 平衡 二叉树 ， 试 画 出 这 棵 树 的 建立 的 过程 。 命中 情况 ： 均 是 考查 平衡 二叉树 的 建立 ， 如何 旋转 达到 平衡 。 命中 类型 ： 间接 命中 （ 2 分 ） 4 . （ 2010 年 试题 第 5 题 ） 在 一 棵 度 为 4 的 树 T 中 ， 若 有 20 个 度 为 4 的 结点 , 10 个 度 为 3 的 结点 ， 1 个 度 为 2 的 结点 ； 10 个 度 为 1 的 结点 ， 则 树 T 的 叶 结点 个数 是 （ B ） A ． 41 B ． 82 C ． 113 D ． 122 （ 翔 高 辅导 书 ） 《 习题 精编 》 第 42 页 单项 选择 题 第 2 题 树 L 中 度 为 1 ， 3 ， 5 ， 7 和 9 的 结点 个数 分别 为 10 ， 8 ， 6 ， 4 ， 2 ， 则 树 L 中 的 叶子 的 个数 是 （ A ） A . 81 B . 110C . 111 D . 109 命中 情况 ： 均 是 考查 树 的 基本 概念 。 命中 类型 ： 直接 命中 （ 2 分 ） 5 . （ 2010 年 试题 第 6 题 ） 对 n （ n2 ） 个 权 值 均 不 相同 的 字符 构造 哈夫曼 树 。 下列 关于 该 哈夫曼 树 的 叙述 中 ， 错

1 . 在 Word 中 ， 单击 下面 四 个 常用 工具 栏 中 的 按钮 ， 可以 打开 一个 下拉 列表 ， 该 按钮 是 ： ( A ) 显示 比例 ( B ) 拼写 检查 ( C ) 帮助 ( D ) 新建 2 . 在 Word 窗口 的 工作 区 中 , 闪烁 的 垂直 条 表达 : ( A ) 鼠标 位置 ( B ) 插入 点 ( C ) 键盘 位置 ( D ) 按钮 位置 3 . 在 Word 中 , 不 打印 却 想 查看 要 打印 的 文献 是否 符合 规定 , 可 单击 : ( A ) “ 打印 预览 ” 按钮 ( B ) “ 文献 ” 按钮 ( C ) “ 新建 ” 按钮 ( D ) “ 文献 名 ” 按钮 4 . 下列 操作 中 , 执行 不 能 选取 所有 文档 。 ( A ) 执行 “ 编辑 ” 菜单 中 的 “ 全 选 ” 命令 或 按 Ctrl + A 组合 键 ( B ) 将 光标 移 到 文档 的 左边 空白 处 , 当 光标 变为 一个 空心 箭头 时 , 按住 Ctrl 键 , 单击 鼠标 ( C ) 将 光标 移 到 文档 的 左边 空白 处 ， 当 光标 变为 一个 空心 箭头 时 ， 连续 三 击 鼠标 ( D ) 将 光标 移 到 文档 的 左边 空白 处 , 当 变为 一个 空心 箭头 时 , 双击 鼠标 5 . 把 单词 cta 改成 cat , 再 把 teh 改成 the 后 , 单击 “ 撒 消 上 一次 ” 按钮 会 显示 ： ( A ) cta ( B ) cat ( C ) teh ( D ) the 6 . 下列 操作 中 , 执行 不 能 在 Word 文档 中 插入 图片 。 ( A ) 执行 " 插入 " 菜单 中 的 " 图片 " 命令 ( D ) 使用 剪切 板 粘贴 其他 文献 的 部分 图形 或 所有 图形 ( C ) 使用 " 插入 " 菜单 中 的 " 文献 " 命令 ; ( D ) 使用 " 插入 " 菜单 中 的 " 对象 " 命令 7 . 要 改变 文档 中 单词 的 字体 ， 必须 : ( A ) 把 插入 点 置于 单词 的 首 字符 前 , 然后 选择 字体 ( B ) 选择 整个 单词 然后 选择 字体 ( C ) 选择 所 要 的 字体 然后 选择 单词 ( D ) 选择 所 要 的 字体 然后 单击 单词 一次 8 . Word 把 格式 化 分为 等 3 类 。 ( A ) 字符 、 段落 和 句子 格式 化 ( B ) 字符 、 句子 和 页面 格式 化 ( C ) 句子 、 页面 格式 和 段落 格式 化 ( D ) 字符 、 段落 和 页面 格式 化 9 . 在 Word 中 , 进行 段落 格式 设立 的 功能 最 全面 的 工具 是 : ( A ) 制表 位 对话 框 ( B ) 水平 标尺 ( C ) 段落 对话 框 ( D ) 正文 排列 对话 框 10 . 双击 文档 中 的 图片 ， 产生 的 效果 是 ： ( A ) 弹 出 快捷 菜单 ( B ) 启动 图形 编辑 器 进入 图形 编辑 状态 , 并 选中 该 图形 ( C ) 选中 该 图形 ( D ) 将 该 图形 加 文本 框 11 . 页面 设立 对话 框 由 四 个 部分 组成 , 不 属于 页面 对话 框 的 是 : ( A ) 版面 ( B ) 纸张 大小 ( C ) 纸张 来源 ( D ) 打印 12 . 要 删除 分 节 符 , 可 将 插入 点 置于 双 点 线 上 , 然后 按 : ( A ) Esc 键 ( B ) Tab 键 ( C ) 回车 键 ( D ) Del 键 13 . 在 表格 中 可以 像 对待 其他 文本 同样 ， 格式 化 每 个 单元 格 里 的 文本 。 ( A ) 通过 单击 常用

研究 生 考试 考研 计算机 学科 专业 基础 ( 408 ) 自 测试 卷 ( 答案 在 后面 ) 一 、 单项 选择 题 （ 本 大 题 有 40 小 题 ， 每 小 题 2 分 ， 共 80 分 ） 1 、 考研 计算机 学科 专业 基础 ( 408 ) 单项 选择 题 ： 在 操作 系统 进程 管理 中 ， 以下 哪 一 种 状态 不是 进程 可能 的 状态 ？ A 、 运行 状态 B 、 就绪 状态 C 、 挂 起 状态 D 、 完成 状态 2 、 考研 计算机 学科 专业 基础 ( 408 ) 单项 选择 题 ： 一个 二叉树 的 高度 定义 为 从 根 节点 到 叶子 节点 的 最长 路径 中 的 节点 个数 。 对于 以下 哪个 二叉树 ， 其 高度 为 3 ？ A 、 1 / \ 2 3 / \ / \ 4 5 6 7 B 、 1 / \ 2 3 / \ \ 4 5 6 C 、 1 / \ 2 3 D 、 1 / \ 2 3 \ 4 \ 5 3 、 考研 计算机 学科 专业 基础 ( 408 ) 单项 选择 题 ： 在 一个 文本 编辑 器 中 ， 关于 以下 哪 种 数据 结构 是 新 的 一 行 的 前 一个 字符 特有 的 ？ A 、 栈 B 、 队列 C 、 链表 D 、 散 列表 4 、 在 计算机 网络 中 ， OSI 模型 中 的 “ 会话 层 ” 主要 负责 ： A ) 数据 表示 的 转换 B ) 两 个 实体 间 的 会话 管理 C ) 网络 层 协议 之间 的 接口 D ) 进行 端到端 的 错误 恢复 和 流量 控制 5 、 计算机 网络 中 的 数据 链路 层 的 主要 功能 是 ： A ) 确保 正确 顺序 、 无 错 、 完整 地 向 另 一 网络 层 传送 数据 B ) 在 连接 的 网络 层 实体 之间 传送 数据 C ) 处理 物理 地址 和 提供 物理 层 与 网络 层 之间 的 接口 D ) 以上 说法 均 不对 6 、 在 以下 数据 结构 中 ， 具有 高效 查找 ， 但 不 直接 支持 顺序 访问 和 插入 操作 的 是 ： A ) 链表 B ) 栈 C ) 哈希 表 D ) 队列 7 、 下列 关于 时间 复杂 度 的 表述 中 ， 正确 的 是 ： A 、 大 O 记号 用于 描述 算法 时间 复杂 度 的 上界 B 、 时间 复杂 度 只能 表示 算法 运行 时间 的 大小 ， 但 不 能 反映 算法 运行 时间 的 具体 数值 C 、 算法 的 时间 复杂 度 与 问题 规模 呈 线性 关系 D 、 通常 认为 算法 的 时间 复杂 度 为 O ( n ) 和 O ( nlogn ) 属于 同 一 级别 8 、 以下 哪个 语言 不 支持 动态 内存 分配 ： A 、 C 语言 B 、 Java 语言 C 、 C++ 语言 D 、 Python 语言 9 、 在 计算机 科学 中 ， 以下 哪个 概念 不 属于 数据 结构 ： A 、 数 组 B 、 栈 C 、 数据 库 管理 系统 D 、 树 10 、 关于 TCP / IP 协议 族 中 的 传输 层 协议 TCP ， 下列 说法 错误 的 是 ： A . TCP 提供 可靠 的 数据 传输 服务 B . TCP 使用 三 次 握手 建立 连接 C . TCP 不 支持 多 路 复用 功能 D . TCP 通过 滑动 窗口 机制 实现 流量 控制 11 、 在 数据 库 系统 中 ， 事务 的 ACID 特性 是 指 原子 性

一 、 单项 选择 题 第 01 ~ 40 小 题 , 每 小 题 2 分 , 共 80 分 。 下列 每 题 给 出 的 四 个 选项 中 , 只有 一个 选项 最 符合 试题 要求 。 01 . 已知 头 指针 h 指向 一个 带头 结点 的 非 空 单 循环 链表 , 结点 结构 为 datanext 其中 next 是 指向 直接 后继 结点 的 指针 , p 是 尾 指针 , q 是 临时 指针 。 现 要 删除 该 链表 的 第 一 个 元素 , 正确 的 语句 序列 是 ( ) 。 02 . 已知 初始 为 空 的 队列 Q 的 一端 仅 能 进行 入队 操作 , 另外 一端 既 能 进行 入队 操作 又 能 进行 出 队 操作 。 若 Q 的 入队 序列 是 1 , 2 , 3 , 4 , 5 , 则 不 能 得到 的 出 队 序列 是 ( ) 。 A . 5 , 4 , 3 , 1 , 2B . 5 , 3 , 1 , 2 , 4C . 4 , 2 , 1 , 3 , 5D . 4 , 1 , 3 , 2 , 503 . 已知 二维 数 组 A 按 行 优先 方式 存储 , 每 个 元素 占用 1 个 存储 单元 。 若 元素 A [ 0 ] [ 0 ] 的 存储 地址 是 100 , A [ 3 ] [ 3 ] 的 存储 地址 是 220 , 则 元素 A [ 5 ] [ 5 ] 的 存储 地址 是 ( ) 。 A . 295 B . 300C . 301 D . 30604 . 某 森林 F 对应 的 二叉树 为 T , 若 T 的 先 序 遍 历 序列 是 a , b , d , c , e , g , f , 中 序 遍 历 序列 是 b , d , a , e , g , c , f , 则 F 中 树 的 棵 数 是 ( ) 。 A . 1 B . 2C . 3D . 405 . 若 某 二叉树 有 5 个 叶 结点 , 其 权 值 分别 为 10 , 12 , 16 , 21 , 30 , 则 其 最小 的 带 权 路径 长度 ( WPL ) 是 ( ) 。 A . 89 B . 200C . 208 D . 28906 . 给定 平衡 二叉树 如下 图 所 示 , 插入 关键 字 23 后 , 根 中 的 关键 字 是 ( ) 。 20163025402021 年 计算机 408 统考 真题 第 1 页 , 共 9 页 A . 16B . 20C . 23 D . 2507 . 给定 如下 有 向 图 ， 该 图 的 拓扑 有序 序列 的 个数 是 ( ) 。 ABFCEDA . 1 B . 2C . 3D . 408 . 使用 Dijkstra 算法 求 下 图 中 从 顶点 1 到 其余 各 顶点 的 最 短 路径 ， 将 当前 找到 的 从 顶点 1 到 顶点 2 , 3 , 4 , 5 的 最 短 路径 长度 保存 在 数 组 dist 中 , 求 出 第 二 条 最 短 路径 后 , dist 中 的 内容 更新 为 ( ) 。 1626315528622436 A . 26 , 3 , 14 , 6B . 25 , 3 , 14 , 6C . 21 , 3 , 14 , 6D . 15 , 3 , 14 , 609 . 在 一 棵 高度 为 3 的 3 阶 B 树 中 , 根 为 第 1 层 , 若 第 2 层 中 有 4 个 关键 字 , 则 该 树 的 结点 个数 最 多 是 ( ) 。 A . 11 B . 10C . 9D . 810 . 设 数 组 S [ ] = { 93 , 946 , 372 , 9 , 146 , 151 , 301 , 485 , 236 , 327 , 43 , 892 } , 采用 最低 位 优先 ( 基数 排序 将 S 排列 成 升 序 序列 。 第 1 趟 分配 、 收集 后 , 元素 372 之前 、 之后 紧邻 的 元素 分别 是 ( ) 。 A . 43 , 892 B . 236 , 301 C . 301 , 892 D . 485 , 30111 . 将 关键 字 6 , 9 , 1 , 5 , 8 , 4 , 7 依次 插入 到 初始 为 空 的 大根 堆 H 中 , 得到 的 H 是 ( ) 。 A . 9 , 8 , 7 , 6 , 5 , 4 , 1 B . 9 , 8 , 7 , 5 , 6 , 1 , 4C . 9 , 8 , 7 , 5 , 6 , 4 , 1D . 9 , 6 , 7 , 5 , 8 , 4 , 112 .

2023 计算机 408 试题 及 答案 参考 答案

计算机 科学 与 技术 学科 联考 计算机 学科 专业 基础 综合 试题 一 、 单项 选择 题 ： 1 ~ 40 小 题 ， 每 小 题 2 分 ， 共 80 分 。 下列 每 题 给 出 的 四 个 选项 中 ， 只有 一个 选项 符合 试题 要求 。 1 . 设 n 是 描述 问题 规模 的 非 负 整数 ， 下列 程序 段 的 时间 复杂 度 是 x = 0 ； A . O ( logn ) B . O ( n 1 / 2 ) C . O ( n ) D . O ( n2 ) 2 . 若 将 一 棵 树 T 转化 为 对应 的 二 又 树 BT ， 则 下列 对 BT 的 遍 历 中 ， 其 遍 历 序列 与 T 的 后 根 遍 历 序列 相同 的 是 A . 先 序 遍 历 B . 中 序 遍 历 C . 后 序 遍 历 D . 按 层 遍 历 3 . 对 n 个 互不 相同 的 符号 进行 哈夫曼 编码 。 若 生成 的 哈夫曼 树 共有 115 个 结点 ， 则 n 的 值 是 A . 56 B . 57C . 58 D . 604 . 在 任意 一 棵 非 空 平衡 二 又 树 ( AVL 树 ) T1 中 ， 删除 某 结点 v 之后 形成 平衡 二 又 树 T2 ， 再 将 w 插入 T2 形成 平衡 二 又 树 T3 。 下列 关于 T1 与 T3 的 叙述 中 ， 正确 的 是 I . 若 v 是 T1 的 叶 结点 ， 则 T1 与 T3 可能 不 相同 . 若 v 不是 T1 的 叶 结点 ， 则 T1 与 T3 一定 不 相同 . 若 v 不是 T1 的 叶 结点 ， 则 T1 与 T3 一定 相同 A . 仅 IB . 仅 IIC . 仅 I 、 D . 仅 I 、 5 . 下 图 所 示 的 AOE 网 表示 一 项 包含 8 个 活动 的 工程 。 活动 d 的 最 早 开始 时间 和 最 迟 开始 时间 分别 是 A . 3 和 7B . 12 和 12C . 12 和 14 D . 15 和 156 . 用 有 向 无 环 图 描述 表达 式 ( x + y ) * ( ( x + y ) / x ) ， 需要 的 顶点 个数 至少 是 A . 5B . 6C . 8D . 97 . 选择 一个 排序 算法 时 ， 除 算法 的 时空 效率 外 ， 下列 因素 中 ， 还 需要 考虑 的 是 I . 数据 的 规模 . 数据 的 存储 方式 . 算法 的 稳定 性 V . 数据 的 初始 状态 A . 仅 B . 仅 I 、 C . 仅 、 、 IVD . I 8 . 现有 长度 为 11 且 初始 为 空 的 散 列表 HT ， 散 列 函数 是 H ( key ) = key % 7 ， 采用 线性 探查 ( 线性 探测 再 散 列 ) 法 解决 冲突 将 关键 字 序列 87 ， 40 ， 30 ， 6 ， 11 ， 22 ， 98 ， 20 依次 插入 到 HT 后 ， HT 查找 失败 的 平均 查找 长度 是 A . 4B . 5 . 25 C . 6D . 6 . 299 . 设 主 串 T = “ abaabaabcabaabc ” ， 模式 串 S = “ abaabc ” ， 采用 KMP 算法 进行 模式 匹配 ， 到 匹配 成功 时 为止 ， 在 匹配 过程 中 进行 的 单个 字符 间 的 比较 次数 是 A . 9 B . 10C . 12 D . 1510 . 排序 过程 中 ， 对 尚未 确定 最终 位置 的 所有 元素 进行 一 遍 处理 称为 一 “ 趟 ” 。 下列 序列 中 ， 不 可能 是 快速 排序 第 二 趟 结果 的 是 A . 5 ， 2 ， 16 ， 12 ， 28 ， 60 ， 32 ， 72 B . 2 ， 16 ， 5 ， 28 ， 12 ， 60 ， 32 ， 72 C . 2 ， 12 ， 16 ， 5 ， 28 ， 32 ， 72 ， 60D . 5 ， 2 ， 12 ， 28 ， 16 ， 32 ， 72 ， 601

单项选择题：1~40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合试题要求。 1.设n是描述问题规模的非负整数，下列程序段的时间复杂度是x=0； A.O(log n)B.O(n1/2)C.O(n)D.O(n2)2.若将一棵树T转化为对应的二又树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是A.先序遍历B.中序遍历C.后序遍历D.按层遍历3.对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是A.56 B.57 C.58 D.60 4.在任意一棵非空平衡二又树(AVL树)T1中，删除某结点v之后形成平衡二又树T2，再将w插入T2形成平衡二又树T3。 综合应用题：41~47小题，共70分。41.(13分)设线性表L=(a1，a2，a，an-2，a-1，a。)采用带头结点的单链表保存，链表中结点定义如下：typedef struct node { int data； 请设计一个空间复杂度为O(1)且时间上尽可能高效的算法，重新排列L中的各结点，得到线性表L'=(a1，an，a2，an-1，a3，an-2)。要求：(1)给出算法的基本设计思想(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。 (3)说明你所设计的算法的时间复杂度。 42.(10分)请设计一个队列，要求满足：初始时队列为空；入队时，允许增加队列占用空间；出队后，出 单项选择题扇区号为(530×2)%200=60。 将簇号转换成磁盘物理地址的过程由磁盘驱动程序完成。 45.【答案要点】(1)计算f(l0)需要调用函数f1共10次执行第16行call 指令会递归调用f1。 (2)第12行jle指令是条件转移指令。第16行call指令、第20行jmp指令、第30行ret指令一定会使程序跳转执行。 (3)第16行call指令的下一条指令的地址为0040 综合应用题41.【答案要点】(1)算法的基本设计思想：算法分3步完成。第1步，采用两个指针交替前行，找到单链表的中间结点；第2步，将单链表的后半段结点原地逆置；第3步，从单链表前后两段中依次各取一个结点，按要求重排。 1025H+5=0040 102AH，故第17行指令的虚拟地址是0040 102AH。call指令采用相对寻址方式，即目标地址=(PC)+偏移量，call指令的目标地址为0040 1000H，所以偏移量=目标地址-(PC)=00401000H-0040 102AH=FFFF FFD6H。根据第16行call指令的偏移量字段为D6 FF FF FF，可确定M采用小端方式。 (4)因

研究 生 考试 考研 计算机 学科 专业 基础 ( 408 ) 自 测试 卷 ( 答案 在 后面 ) 一 、 单项 选择 题 （ 本 大 题 有 40 小 题 ， 每 小 题 2 分 ， 共 80 分 ） 1 . 数据 结构 基本 概念 中 ， 下列 关于 树 的 说法 正确 的 是 ： A . 树 是 一 种 特殊 的 图 B . 树 中 的 每 个 节点 有 且 仅 有 一个 父 节点 C . 树 是 一 种 具有 层次 结构 的 数据 组织 方式 D . 树 中 的 每 个 节点 可以 有 多 个子 节点 2 . 在 计算机 网络 模型 中 ， 下列 哪个 层次 负责 定义 数据 格式 和 加密 等 安全 相关 的 问题 ？ A . 应用 层 B . 表示 层 C . 会话 层 D . 传输 层 3 . 下列 哪个 算法 是 用于 解决 “ 字符 串 匹配 ” 问题 的 经典 算法 ？ A . 冒泡 排序 B . 快速 排序 C . KMP 算法 D . 二 分 查找 4 . 关于 数据 库 系统 的 描述 ， 以下 哪 项 是 错误 的 ？ A . 数据 库 系统 提供 数据 独立 性 B . 数据 库 系统 减少 数据 冗余 C . 数据 库 系统 避免 存储 冗余 数据 D . 数据 库 系统 允许 用户 自 定义 数据 类型 5 . 以下 哪个 不是 关系 型 数据 库 管理 系统 （ RDBMS ） 的 特征 ？ A . 数据 结构 化 B . 数据 独立 性 C . 数据 共享 性 D . 数据 冗余 6 . 在 计算机 网络 模型 中 ， 以下 哪 项 不是 OSI 参考 模型 的 层次 ？ A . 物理 层 B . 数据 链路 层 C . 网络 层 D . 应用 层 7 . 在 计算机 网络 中 ， 以下 哪个 协议 是 用于 在 网络 设备 之间 传输 数据 的 ？ A . HTTPB . FTPC . TCPD . UDP 8 . 在 操作 系统 原理 中 ， 下列 哪个 不是 进程 的 特征 ？ A . 动态 性 B . 静态 性 C . 并发 性 D . 互斥 性 9 . 在 数据 库 管理 系统 中 ， 以下 哪个 关键 字 用于 唯一 标识 一个 元 组 ？ A . 唯一 索引 B . 主键 C . 外 键 D . 候选 键 10 . 在 计算机 网络 中 ， 以下 哪个 协议 是 用于 在 网络 设备 之间 传输 数据 的 ？ A . HTTPB . FTPC . TCPD . UDP 11 . 下列 哪个 关键 字 用于 定义 一个 类 的 私有 成员 ？ A . publicB . privateC . protectedD . friend 12 . 在 数据 库 管理 系统 中 ， 以下 哪个 概念 用于 描述 数据 之间 的 关联 关系 ？ A . 数据 库 设计 B . 数据 模型 C . 关系 模型 D . 数据 字典 13 、 计算机 网络 中 ， 用于 将 数据 包 从 一个 网络 节点 传送 到 另 一个 网络 节点 的 协议 是 ： A . HTTPB . TCPC . IPD . FTP 14 、 以下 哪 种 数据 结构 最 适合 实现 关联 数 组 （ 即 可以 存储 键 值 对 的 数 组 ） ？ A . 链表 B . 栈 C . 队列 D . 哈希 表 15 、 关于 操作 系统 中 的 进程 调度 ， 以下 哪 种 调度 算法 是 专 为 实时 系统 设计 的 ？ A . 先 来 先 服务 （ FCFS ） B . 短 作业 优先 （ SJF ） C . 优先 级 调度 D . 时间 片 轮转 16 . 在 计算机 网络 中 ， 以下 哪

2021 年 考研 计算机 统考 《 408 计算机 学科 专业 基础 综合 》 考研 真题 一 、 历年 热点 考研 真题 某 计算机 的 指令 流水 线 由 4 个 功能 段 组成 ， 指令 流经 各 功能 段 的 时间 （ 忽略 各 功能 段 之间 的 缓存 时间 ） 分别 为 90 ns 、 80 ns 、 70 ns 和 60 ns ， 则 该 计算机 的 CPU 时钟 周期 至少 是 （ 　 　 ） 。 A ． 90 ns B ． 80 ns C ． 70 ns D ． 60 ns 【 答案 】 A 查看 答案 【 解析 】 对于 各 功能 段 执行 时间 不同 的 指令 流水 线 ， 计算机 的 CPU 时钟 周 期 应当 以 最长 的 功能 段 执行 时间 为 准 。 19 相对 于 微 程序 控制 器 ， 硬 布线 控制 器 的 特点 是 （ 　 　 ） 。 A ． 指令 执行 速度 慢 ， 指令 功能 的 修改 和 扩展 容易 B ． 指令 执行 速度 慢 ， 指令 功能 的 修改 和 扩展 难 C ． 指令 执行 速度 快 ， 指令 功能 的 修改 和 扩展 容易 D ． 指令 执行 速度 快 ， 指令 功能 的 修改 和 扩展 难 【 答案 】 D 查看 答案 【 解析 】 在 同样 的 半导体 工艺 条件 下 ， 硬 布线 （ 组合 逻辑 ） 控制 器 的 速度 比 微 程序 控制 器 的 速度 快 。 这 是 因为 硬 布线 控制 器 的 速度 主要 取 决 于 逻辑 电路 的 延迟 ， 而 微 程序 控制 器 增加 了 一级 控制 存储 器 ， 执行 的 每 条 微 指令 都 要 从 控制 存储 器 中 读 取 ， 影响 了 速度 。 由于 硬 布线 控制 器 一旦 设计 完成 就 很 难 改变 ， 所以 指令 功能 的 修 改 和 扩展 难 。 因此 ， 硬 布线 控制 器 的 特点 是 指令 执行 速度 快 ， 指令 功能 的 修改 和 扩 展 难 。 20 假设 某 系统 总线 在 一个 总线 周期 中 并行 传输 4 字节 信息 ， 一个 总线 周期 占用 2 个 时钟 周期 ， 总线 时钟 频率 为 10 MHz ， 则 总线 带宽 是 （ 　 　 ） 。 A ． 10 MB / s B ． 20 MB / s C ． 40 MB / s D ． 80 MB / s 【 答案 】 B 查看 答案 【 解析 】 因为 一个 总线 周期 占用 2 个 时钟 周期 ， 完成 一个 32 位 数据 的 传送 。 总线 时钟 频率 为 10 MHz ， 时钟 周期 为 0 . 1 μ s ， 总线 周期 占用 2 个 时钟 周期 ， 为 0 . 2 μ s 。 一个 总线 周期 中 并行 传输 4 字节 信息 ， 则 总线 带宽 是 4B ÷ 0 . 2 μ s ＝ 20 MB / s 。 21 假设 某 计算机 的 存储 系统 由 Cache 和 主 存 组成 。 某 程序 执行 过程 中 访存 1000 次 ， 其中 访问 Cache 缺失 （ 未 命中 ） 50 次 ， 则 Cache 的 命中 率 是 （ 　 　 ） 。 A ． 5 % B ． 9 . 5 % C ． 50 % D ． 95 % 【 答案 】 D 查看 答案 【 解析 】 Cache 的 命中 率 H ＝ N1 / （ N1 ＋ N2

研究 生 考试 考研 计算机 学科 专业 基础 ( 408 ) 复习 试题 ( 答案 在 后面 ) 一 、 单项 选择 题 （ 本 大 题 有 40 小 题 ， 每 小 题 2 分 ， 共 80 分 ） 1 、 在 计算机 科学 中 ， 下列 哪个 术语 表示 将 数据 从 一 种 格式 转换 为 另 一 种 格式 的 过程 ？ A 、 编译 B 、 解释 C 、 转换 D 、 编码 2 、 以下 哪个 组件 是 计算机 系统 中 的 输入 设备 ？ A 、 中央 处理 器 （ CPU ） B 、 内存 （ RAM ） C 、 硬盘 驱动 器 （ HDD ） D 、 鼠标 3 、 下列 哪个 操作 系统 以 其 轻 量 级 和 实时 性 著称 ？ A 、 WindowsB 、 LinuxC 、 macOSD 、 VxWorks 4 、 关于 计算机 硬件 系统 的 组成 ， 以下 说法 错误 的 是 ： A 、 中央 处理 器 （ CPU ） 负责 执行 指令 ， 控制 计算机 的 运行 。 B 、 内存 （ RAM ） 用于 临时 存储 数据 和 指令 ， 断电 后 数据 会 丢失 。 C 、 硬盘 （ HDD ） 是 计算机 的 主要 存储 设备 ， 断电 后 数据 不会 丢失 。 D 、 显卡 （ GPU ） 主要 负责 图形 图像 的 处理 ， 不 参与 指令 的 执行 。 5 、 以下 哪个 概念 不是 数据 库 管理 系统 （ DBMS ） 的 基本 功能 ？ A 、 数据 定义 B 、 数据 操纵 C 、 数据 查询 D 、 数据 恢复 6 、 在 计算机 网络 中 ， 以下 哪 种 协议 主要 用于 实现 传输 层 的 可靠 传输 ？ A 、 TCP （ 传输 控制 协议 ） B 、 IP （ 互联网 协议 ） C 、 HTTP （ 超 文本 传输 协议 ） D 、 SMTP （ 简单 邮件 传输 协议 ） 7 、 在 计算机 网络 中 ， 以下 哪个 协议 负责 在 网络 层 中 实现 数据 包 的 路由 选择 ？ A . HTTPB . FTPC . TCPD . IP 8 、 以下 哪 种 编程 语言 属于 面向 对象 编程 语言 ？ A . CB . JavaC . PythonD . Assembly 9 、 在 计算机 系统 中 ， 内存 的 地址 空间 通常 分为 以下 哪 几 个 部分 ？ A . 程序 代码 区 、 数据 区 、 堆栈 区 B . 输入 输出 区 、 文件 系统 区 、 用户 程序 区 C . 硬盘 区 、 光盘 区 、 网络 区 D . 系统 区 、 用户 区 、 共享 区 10 、 下列 关于 数据 结构 的 说法 正确 的 是 ： A . 数 组 是 一 种 线性 数据 结构 ， 只能 顺序 存储 。 B . 链表 与 数 组 相比 ， 在 插入 和 删除 元素 时 效率 更 高 。 C . 栈 是 一 种 可以 随时 插入 和 删除 的 线性 表 。 D . 队列 允许 在任 一端 插入 和 删除 元素 。 11 、 在 计算机 网络 中 ， 传输 层 协议 的 主要 功能 不 包括 ： A . 提供 端到端 的 通信 服务 。 B . 处理 不同 主机 之间 的 数据 包 路由 。 C . 进行 错误 检测 和 流量 控制 。 D . 确定 数据 段 的 顺序 并 确保 其 可靠 传输 。 12 、 在 操作 系统 中 ， 用于 实现 进程 互斥 访问 临界 资源 的 技术 称为 ： A . 死锁 预防 机制 。 B

I.批处理系统允许多个用户与计算机直接交互批处理系统分为单道批处理系统和多道批处理系统.中断技术使得多道批处理系统的Io设备可与CPU并行工作A.仅、B.仅C.仅1、D.仅1、24.某单CPU系统中有输入和输出设备各1台,现有3个并发执行的作业,每个作业的输入计算和输出时间均分别为2ms、3ms和4ms,且都按输入、计算和输出的顺序执行,则执行完3个作业需要的时间最少是A.15msB.17msC.22msD.27ms25.系统中有3个不同的临界资源R1、R2和R3,被4个进程p1、p2、p3及p4共享。各进程对资源的需求为:p1申请R1和R2,p2申请R2和R3,p3申请R1和R3,p4申请R2。若系统出现死锁,则处于死锁状态的进程数至少是A1B.2C.3D.426.某系统采用改进型CLOCK置换算法,页表项中字段A为访问位,M为修改位。A=0表示页最近没有被访问,A=1表示页最近被访问过。M=0表示页没有被修改过,M=1表示页被修改过。按(A,M)所有可能的取值,将页分为四类:(0,0)、(1,0)、(0,1)和(1,1),则该算法淘汰页的次序为A.(0,0),(0,1),(1,0),(1,1)B.(0,0),(1,0),(0,1),(1,1)C.(0,0),(0,1),(1,1),(1,0)D.(0,0),(1,1),(0,1),(1,0)27.使用

研究 生 考试 考研 计算机 学科 专业 基础 ( 408 ) 复习 试题 ( 答案 在 后面 ) 一 、 单项 选择 题 （ 本 大 题 有 40 小 题 ， 每 小 题 2 分 ， 共 80 分 ） 1 、 关于 算法 的 时间 复杂 度 ， 下列 说法 正确 的 是 ： A 、 算法 的 时间 复杂 度 只 与 输入 数据 的 规模 有关 ， 与 算法 本身 的 执行 时间 无关 。 B 、 算法 的 时间 复杂 度 只 与 算法 本身 的 执行 时间 有关 ， 与 输入 数据 的 规模 无关 。 C 、 算法 的 时间 复杂 度 通常 用 大 O 符号 表示 ， 可以 精确 地 描述 算法 执行 时间 。 D 、 算法 的 时间 复杂 度 表示 算法 运行 所 需 时间 的 最小 值 。 2 、 以下 哪 种 数据 结构 最 适合 用于 实现 快速 查找 功能 ？ A 、 链表 B 、 栈 C 、 队列 D 、 散 列表 3 、 以下 哪个 语句 表示 的 是 递归 调用 ？ A 、 f ( n ) = 2 * f ( n - 1 ) + 1 B 、 f ( n ) = 1 ， 当 n = 1 ； f ( n ) = f ( n - 1 ) + 1 ， 当 n > 1 C 、 f ( n ) = n * f ( n - 1 ) ， 当 n > 1 ； f ( 1 ) = 1D 、 f ( n ) = 1 ， 当 n = 1 ； f ( n ) = n * f ( n - 1 ) + 1 ， 当 n > 14 、 在 计算机 系统 中 ， 以下 哪个 组件 负责 将 高级 语言 编写 的 程序 转换 为 机器 语言 ？ A . 中央 处理 器 （ CPU ） B . 磁盘 驱动 器 C . 运算 器 D . 汇编 器 5 、 在 计算机 网络 中 ， 以下 哪 种 协议 负责 在 传输 层 提供 端到端 的 数据 传输 服务 ？ A . TCP / IPB . HTTPC . FTPD . DNS 6 、 在 数据 库 系统 中 ， 以下 哪 种 数据 结构 用于 存储 具有 多级 层次 关系 的 实体 ？ A . 队列 B . 栈 C . 树 D . 链表 7 、 在 计算机 科学 中 ， 下列 哪 种 数据 结构 最 适合 用于 实现 一个 队列 （ FIFO ） 操作 ？ A . 链表 B . 栈 C . 树 D . 顺序 表 8 、 下列 哪个 概念 与 计算机 中 的 “ 缓存 ” 最 相似 ？ A . 数据 库 B . 存储 器 C . 磁盘 D . 缓存 9 、 在 计算机 网络 中 ， 以下 哪 种 协议 用于 在 传输 层 提供 端到端 的 数据 传输 服务 ？ A . TCP （ 传输 控制 协议 ） B . UDP （ 用户 数据 报 协议 ） C . IP （ 互联网 协议 ） D . HTTP （ 超 文本 传输 协议 ） 10 、 下列 关于 计算机 系统 层次 结构 的 说法 中 ， 正确 的 是 ： A . 硬件 层次 直接 对应 物理 层次 ， 软件 层次 直接 对应 逻辑 层次 B . 硬件 层次 包括 物理 层 、 数据 链路 层 、 网络 层 、 传输 层 、 会话 层 、 表示 层 和 应用 层 C . 软件 层次 包括 物理 层 、 数据 链路 层 、 网络 层 、 传输 层 、 会话 层 、 表示 层 和 应用 层 D . 硬件 层次 包括 应用 层 、 表示 层 、 会话 层 、 传输 层 、 网络 层 、 数据 链路 层 和 物理 层 11 、 在 计算机 网络 中 ， 以下 哪个 协议 主要 用于 实现 数据 在 网

一、单项选择题1.以下函数的时间简单度是_1_。 } A.O(logn)B.O(n 1/2)C.O(n)D.O(nlogn)2.以下关于栈的表达中,错误的选项是2 c I.承受非递归方式重写递归程序时必需使用栈II.函数调用时,系统要用栈保存必要的信息III.只要确定了入栈的次序，即可确定出栈次序IV.栈是一种受限的线性表,允许在其两端进展操作A.仅I B.仅I、II、III C.仅I、III、IV D.仅II、III、IV 3.适用于压缩存储稀疏矩阵的两种存储构造是3。A.三元组表和十字链表_ B.三元组表和邻接矩阵C.十字链表和二叉链表D.邻接矩阵和十字链表4.要使一棵非空二叉树的先序序列与中序序列一样, 其全部非叶结点须满足的条件是4。A.只有左子树B.只有右子树C. 结点的度均为1 D.结点的度均为2 5.一棵二叉树的树形如以下图所示,其后序序列为e,a,c,b,d,g,f,树中与结点a同层的结点是5 0 A.c B.已知字符集\{ a,b,c,d,e,f,g,h \} ,假设各字符的哈夫曼编码依次是0100,10,0000,0101,001,011,11,0001, ,则编码序列0100011001001011110101的译码结果是_。afeefgd 7.无向图G含有16条边,其中度为4的顶点个数为3,度为3的

研究 生 考试 考研 计算机 学科 专业 基础 ( 408 ) 自 测试 卷 ( 答案 在 后面 ) 一 、 单项 选择 题 （ 本 大 题 有 40 小 题 ， 每 小 题 2 分 ， 共 80 分 ） 1 、 下列 关于 算法 的 叙述 中 ， 正确 的 是 _ 。 A . 算法 就是 程序 B . 数据 结构 是 算法 的 核心 C . 算法 的 核心 在于 排序 和 查找 D . 设计 算法 时 只 需要 考虑 数据 结构 的 表现 形式 2 、 算法 分析 和 算法 时间 复杂 度 最 本质 的 思想 就是 _ 。 A . 从不 考虑 问题 的 规模 入手 研究 算法 B . 从 问题 的 规模 入手 研究 算法 C . 假设 最终 结果 相同 ， 研究 运行 算法 的 速度 D . 研究 算法 流程 图 上 各 操作 所 花 的 时间 总和 3 、 下列 有关 基本 算法 的 性质 叙述 中 ， 正确 的 一 条 是 _ 。 A . 算法 可以 由 若干 个子 算法 得到 B . 算法 是 问题 求得 解 的 一个 计算 过程 C . 算法 是 应用 于 计算机 上 ， 或 只 应用 于 计算机 上 的 问题 的 解法 D . 算法 只是 指 问题 的 解法 4 . 哪 种 算法 通常 用于 解决 问题 ， 当 问题 空间 是 可 穷举 且 最 优 解 已知 时 ？ A . 贪心 算法 B . 回溯 算法 C . 分支 限界 算法 D . 动态 规划 5 . 在 操作 系统 中 ， 哪个 过程 优先 级 最高 ？ A . 用户 进程 B . 实时 进程 C . 作业 控制 进程 D . 批 处理 进程 6 . 在 数据 结构 中 ， 以下 哪个 是 树 的 一个 常见 属性 ？ A . 双向 链表 B . 无 环 图 C . 分支 结构 D . 线性 链表 7 、 关于 线性 表 的 存储 结构 ， 下列 说法 错误 的 是 ： A . 数 组 是 一 种 线性 表 存储 结构 B . 数 组 的 元素 之间 按 顺序 存储 C . 数 组 的 访问 效率 较 高 ， 常数 时间 复杂 度 O ( 1 ) D . 链表 是 一 种 非 顺序 存储 结构 8 、 下列 关于 二叉树 的 描述 ， 错误 的 是 ： A . 二叉树 每 个 节点 最 多 有 两 个 孩子 节点 B . 二叉树 中 ， 空 节点 个数 不 超过 非 空 节点 个数 C . 二叉树 是 一个 对比 高效 的 数据 结构 D . 二叉树 可以 用来 实现 堆 结构 9 、 下列 关于 快 排 算法 的 描述 ， 正确 的 是 ： A . 快 排 算法 的 时间 复杂 度 为 O ( n log n ) B . 快 排 算法 的 空间 复杂 度 为 O ( 1 ) C . 快 排 算法 在 最 坏 情况 下 时间 复杂 度 为 O ( n ) ² D . 快 排 算法 不 稳定 排序 10 、 单项 选择 题 A ) TransistorB ) DiodeC ) Op - AmpD ) MOSFET 11 、 单项 选择 题 A ) IEEE 802 . 11 acB ) USB 3 . 2 C ) DDR 4 SDRAMD ) PCIe 4 . 012 、 单项 选择 题 A ) Markov ChainB ) Hidden Markov ModelC ) PageRankD ) Neural Network 13 、 下列 哪个 数据 结构 可以 用 避免 单一 链 的 操作 不 适合 运用 到 循环 依赖 关系 的 场景 ? A . 树 形 结构 B . 栈 C . 队列 D . 图 14 、 以下 哪 种 排序 算法 的 平均