1 中科大复试准备 数据结构->操作系统->计算机网络->通信原理->微机原理-> 软件工程，编译原理，数据库 2 数 据 结 构 1. 时 间 复 杂 度 时 间 复 杂 度 是 指 执 行 算 法 所 需 要 的 计 算 工 作 量 ， 因 为 整 个 算 法 的 执 行 时 间 与 基 本 操 作 重 复 执 行 的 次 数 成 正 比 ， 所 以 将 算 法 中 基 本 操 作的 次 数 作 为 算 法 时 间 复 杂 度 的 度 量 ， 一 般 情 况 下 ， 按 照 基 本 操 作 次 数 最 多 的 输 入 来 计 算 时 间 复 杂 度 ， 并 且 多 数 情 况 下 我 们 去 最 深 层 循环 内 的 语 句 所 描 述 的 操 作 作 为 基 本 操 作 。 2. 循 环 队 列 的 顺 序 表 中 ， 为 什 么 要 空 一 个 位 置 ？ 这 是 为 了 用 来 区 分 队 空 与 队 满 的 情 况 。 如 果 不 空 一 个 位 置 ， 则 判 断 队 空 和 队 满 的 条 件 是 一 样 的 。 3. 什 么 是 二 叉 排 序 树 ？ 以 及 它 的 原 理 ， 算 法 。（二 叉 排 序 树 的 查找过程） 二 叉 排 序 树 又 称 二 叉 查 找 树 ， 它 或 者 是 一 颗 空 树 ， 或 者 满 足 一 下 性 质 的 二 叉 树 ： ① 若左子树 不 空 ， 则 左子树 上所 有结点的 值均小于根节点的 值； ② 若右子树 不 空 ， 则 右子树 上所 有结点的 值均大于根节点的 值； ③ 左右子树 也分 别是 二 叉 排 序 树 。 原 理 步骤： 若根结点的 关键字值等于查 找 的 关键字， 成 功 。 否 则 ， 若小于根结点的 关键字值， 递 归 查 左子树 。 若大于根结点的 关键字值， 递 归 查 右子树 。 若子树 为 空 ， 查 找 不 成 功 。 4. 哈夫曼树 定义： 给 定n 个 权 值作 为n 个 叶 子结点， 构 造 一 棵 二 叉 树 ， 若带 权 路 径 长 度 达 到 最 小， 称 这 样 的 二 叉 树 为 最 优 二 叉 树 ， 也称 为 哈 夫 曼 树(Huffman tree)。 构 造方法 ： 假 设 有 n 个 权 值， 则 构 造 出 的 哈 夫 曼 树 有 n 个 叶 子结点。 n 个 权 值分 别设 ...
VIP
