数 据 结 构 应 用 题 答 案 第 2 章 线 性 表 1.设 指 针 变 量 p 指 向 双 向 链 表 中 结 点 A， 指 针 变 量 q 指 向 被 插 入 结 点 B， 要 求 给 出 在 结 点 A的 后 面 插 入 结 点 B 的 操 作 序 列 （ 设 双 向 链 表 中 结 点 的 两 个 指 针 域 分 别 为 llink 和 rlink）。 答 ： 操 作 序 列 如 下 ： q->rlink = p->rlink ; p->rlink = q ; q->rlink->llink = q ; q->llink = p ; 注 意 答 案 不 唯 一 第 3 章 栈 和 队 列 1 .设 有 编 号 为 1 ， 2 ， 3 ， 4 的 四 辆 列 车 ， 顺 序 进 入 一 个 栈 式 结 构 的 车 站 ， 具 体 写 出 这 四 辆 列车 开 出 车 站 的 所 有 可 能 的 顺 序 。 答 ： 共 计 14 种 ， 分 别 是 ： 1234， 1243， 1324， 1342， 1432， 2134， 2143， 2341， 2314， 2431， 3214， 3241， 3421， 4321 2.如 果 输 入 序 列 为 1， 2， 3， 4， 5， 6， 试 问 能 否 通 过 栈 结 构 得 到 以 下 两 个 序 列 ： 4， 3， 5，6， 1， 2 和 1， 3， 5， 4， 2， 6； 请 说 明 为 什 么 不 能 或 如 何 才 能 得 到 。 答 ：（ 1） 不 能 得 到 4 ， 3 ， 5 ， 6 ， 1 ， 2 ； 因 为 1 ， 2 ， 3 ， 4 入 栈 后 ； 4 ， 3 出 栈 ； 得 到 序 列 4 ，3 ； 栈 中 还 有 1 ， 2 ； 5 入 栈 后 即 出 栈 ， 得 到 序 列 4 ， 3 ， 5 ； 6 入 栈 后 即 出 栈 ， 得 到 序 列 4 ， 3 ，5 ， 6 ； 此 时 ， 栈 中 还 有 1 ， 2 ； 必 须 2 先 出 栈 ， 然 后 1 再 出 栈 ， 1 不 可 能 在 2 之 前 出 栈 。 故 而得 不 到 该 序 列 。 （ 2） 能 得 到 输 出 顺 序 为 1， 3， 5， 4， 2， 6 的 序 列 。 得 到 的 操 作 如 下 ： 1 入 栈 后 即 出 栈 ， 得到 序 列 1； 2， 3 入 栈 后 3 即 出 栈 ， 得 到 序 列 1， 3； 4， 5 入 栈 后 ， 5 出 栈 ， 4 出 栈 ， 得 到 序 列1， 3， 5， 4； 2 出 ...
