1 数据结构大全 一、概论 二、线性表 三、栈和队列 四、串 五、多维数组和广义表 十、文件 六、树 七、图 八、排序 九、查找 2 一 、 概 论 1、 评 价 一 个 算 法 时 间 性 能 的 主 要 标 准 是 ( 算 法 的 时 间 复 杂 度 )。 2、 算 法 的 时 间 复 杂 度 与 问 题 的 规 模 有 关 外 ， 还 与 输 入 实 例 的 ( 初 始 状 态 )有 关 。 3、 一 般 ， 将 算 法 求 解 问 题 的 输 入 量 称 为 ( 问 题 的 规 模 )。 4、 在 选 择 算 法 时 ， 除 首 先 考 虑 正 确 性 外 ， 还 应 考 虑 哪 三 点 ? 答 ： 选 用 的 算 法 首 先 应 该 是 "正 确 "的 。 此 外 ， 主 要 考 虑 如 下 三 点 ： ① 执 行 算 法 所 耗 费 的 时 间 ； ② 执行 算 法 所 耗 费 的 存 储 空 间 ， 其 中 主 要 考 虑 辅 助 存 储 空 间 ； ③ 算 法 应 易 于 理 解 ， 易 于 编 码 ， 易 于 调 试等 等 。 6、 下 列 四 种 排 序 方 法 中 ， 不 稳 定 的 方 法 是 ( D ) A、 直 接 插 入 排 序 B、 冒 泡 排 序 C、 归 并 排 序 D、 直 接 选 择 排 序 7、 按 增 长 率 由 小 至 大 的 顺 序 排 列 下 列 各 函 数 ： 2100, (3/2)n ， (2/3)n ， n n ,n 0.5 , n ! ， 2n ， lgn , n lgn , n 3/2 答 ： 常 见 的 时 间 复 杂 度 按 数 量 级 递 增 排 列 ,依 次 为 : 常 数 0(1)、 对 数 阶0(lo g2n )、 线形阶0(n )、 线形对数 阶0(n lo g2n )、 平方 阶0(n 2)立方 阶0(n 3)、 …、 k 次 方 阶0(n k)、 指数 阶0(2n )。 显然， 时 间 复 杂 度 为 指数 阶0(2n )的 算 法 效率 极低， 当n 值稍大 时 就无法 应 用 。 先 将 题 中 的 函 数 分成如 下 几类： 常 数 阶： 2100 对 数 阶： lgn K 次 方 阶： n 0.5、 n 3/2 指数 阶 (按 指数 由 小 到大 排 )： n lgn 、 (3/2)n 、 2n 、 n !、 n n 注意： (2/3)n 由 于 底数 小 于 1， 所 以是 一 个 递 减函 数 ， 其 数 量 级 应 小 于 常 数...
