新题库-数据结构题库及答案.pdf

《新题库-数据结构题库及答案.pdf》由会员分享，可在线阅读，更多相关《新题库-数据结构题库及答案.pdf（50页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、第 一 章 绪 论 一、选 择 题 1、数 据 结 构 是 一 门 研 究 非 数 值 计 算 的 程 序 设 计 问 题 中 计 算 机 的，以 及 它 们 之 间 的 B 和 运 算 等 的 学 科。（易）A、数 据 元 素 B、计 算 方 法 C、逻 辑 存 储 D、数 据 映 象 A、结 构 B、关 系 C、运 算 D、算 法 2、数 据 结 构 被 形 式 地 定 义 为（K,R）,其 中 K 是 D 的 有 限 集,R 是 K 上 的 B有 限 集。（易）A、算 法 B、数 据 元 素 C、数 据 操 作 D、逻 辑 结 构 A、操 作 B、映 象 C、存 储 D、关 系 3、在

2、数 据 结 构 中，从 逻 辑 上 可 以 把 数 据 结 构 分 成 C o（易）A、动 态 结 构 和 静 态 结 构 B、紧 凑 结 构 和 非 紧 凑 结 构 C、线 性 结 构 和 非 线 性 结 构 D、内 部 结 构 和 外 部 结 构 4、算 法 分 析 的 目 的 是 C,算 法 分 析 的 两 个 主 要 方 面 是 A。（中）A、找 出 数 据 结 构 的 合 理 性 B、研 究 算 法 中 的 输 入 和 输 出 的 关 系 C、分 析 算 法 的 效 率 以 求 改 进 D、分 析 算 法 的 易 懂 性 和 文 档 性 A、空 间 复 杂 度 和 时 间 复 杂 度

3、 B、正 确 性 和 简 单 性 C、可 读 性 和 文 档 性 D、数 据 复 杂 性 和 程 序 复 杂 性 5、计 算 机 算 法 指 的 是 C,它 必 须 具 备 输 入、输 出 和 B 等 5 个 特 性。（易）A、计 算 方 法 B、排 序 方 法 C、解 决 问 题 的 有 限 运 算 序 列 D、调 度 方 法 A、可 执 行 性、可 移 植 性 和 可 扩 充 性 B、可 行 性、确 定 性 和 有 穷 性 C、确 定 性、有 穷 性 和 稳 定 性D、易 读 性、稳 定 性 和 安 全 性 答 案：1、A,B 2、D,B 3、C 4、C,A 5、C,B二、名 词 解 释：

4、(易)1、数 据 2、数 据 元 素 3、数 据 对 象 4、数 据 结 构 5、数 据 类 型 6、算 法 答 案：1、数 据 是 对 客 观 事 物 的 符 号 表 示，在 计 算 机 科 学 中 是 指 所 有 能 输 入 到 计 算 机 中 被 计 算 机 程 序 处 理 的 符 号 的 总 称。2、数 据 元 素 数 据 的 基 本 单 位，在 计 算 机 程 序 中 通 常 做 为 一 个 整 体 进 行 考 虑 和 处 理。3、数 据 对 象：性 质 相 同 的 数 据 元 素 的 集 合。4、数 据 结 构：相 互 具 有 一 种 或 多 种 关 系 的 数 据 元 素 的 集

5、 合。5、数 据 类 型：是 具 有 相 同 性 质 的 计 算 机 数 据 的 集 合 及 在 这 个 数 据 上 的 一 组 运 算，是 和 数 据 结 构 密 切 相 关 的 概 念。6、算 法：对 特 定 问 题 求 解 步 骤 的 一 种 描 述，是 有 限 指 令 的 集 合。三、填 空 题 1、下 面 程 序 段 的 时 间 复 杂 度 是 0(m*n)o(易)fo r(i=0;i n;i+)fo r(j=0;jm;j+)2、下 面 程 序 段 的 时 间 复 杂 度 是 0(册)。(中)i=s=0w hile(sn)(i+;/*i=i+1*/s+=i;/*s=s+i*/3、下

6、面 程 序 段 的 时 间 复 杂 度 是 _ 0（/）。（易）s=0;fo r（i=0;i n;i+）fo r（j=0;j n;j+）s+=bi J;sum=s;4、下 面 程 序 段 的 时 间 复 杂 度 是 O d o g./）。（难）i=1；wi Ie（i=n）i=i*3;5、数 据 元 素 可 以 由 若 干 数 据 项 组 成，数 据 元 素 是 数 据 的 基 本 单 位，数 据 项 是 数 据 的 最 小 单 位。（易）6、数 据 结 构 分 为 两 部 分，即 逻 辑 结 构 和 一 物 理 结 构。（易）7、数 据 的 存 储 方 式 分 为 顺 序 存 储 和 链 式

7、存 储。（易）8、顺 序 存 储 是 一 种 随 机 存 取 的 存 储 方 式，是 用 一 组 _连 续 的 存 储 空 间 存 储 数 据，而 链 式 存 储 是 用 一 组 一 任 意 的 存 储 空 间 存 储 数 据。（易）四、简 答 题：1、什 么 是 算 法，其 基 本 性 质 是 什 么？（易）答 案：1、算 法 是 对 特 定 问 题 求 解 步 骤 的 一 种 描 述，是 有 限 指 令 的 集 合。其 基 本 性 质 如 下：1）有 穷 性：算 法 对 任 意 合 法 的 输 入 均 能 在 有 限 时 间、有 限 步 骤 后 完 成。2）确 定 性：算 法 的 每 一

8、步 骤 的 含 义 都 是 唯 一、确 定 的，对 于 相 同 的 输 入 均 能 得 到 相 同 的 输 出。3）可 行 性：算 法 的 每 一 个 步 骤 和 指 令 都 应 在 已 实 现 的 算 法 的 基 础 上 完 成。4）输 入：任 一 个 算 法 必 须 有 0 个 或 多 个 输 入。5）输 出：任 一 个 算 法 必 须 有 1个 或 多 个 输 出。2、算 法 的 要 求 是 什 么？（中）2、算 法 的 要 求 是：1）正 确 性：算 法 能 正 确 描 述 待 求 解 问 题 的 需 求，没 有 逻 辑 错 误，据 此 算 法 书 写 的 程 序,对 于 任 何 合

9、法 的 输 入，都 有 得 到 正 确 的、说 明 需 求 的 结 果。2）可 读 性：算 法 应 简 洁、明 晰，易 于 阅 读 和 理 解，便 于 算 法 的 移 植 和 交 流，有 利 于 增 加 算 法 的 生 命 力。3）健 壮 性：当 输 入 的 数 据 非 法 时，算 法 要 能 作 出 适 当 的 处 理，不 会 产 生 难 以 预 料 的 结 果。4）高 效 率 性：一 般 来 说，对 同 一 问 题 的 多 种 算 法，首 先 选 择 执 行 时 间 相 对 较 短、存 储 空 间 相 对 较 少 的 算 法，然 后 考 虑 易 于 实 现 的 算 法。3、结 构 共 分

10、几 类？其 各 自 的 性 质 是 什 么？（易）3、结 构 共 分 为 四 类，分 别 为：1）集 合：所 有 元 素 除 共 在 同 一 集 合 外，没 有 其 他 关 系。2）线 性 结 构：元 素 间 是 一 对 一 的 关 系。3）树 型 结 构：元 素 间 是 一 对 多 的 关 系。4）图 型 结 构：元 素 间 是 多 对 多 的 关 系。五、算 法 设 计 题：1、试 写 一 算 法，求 随 机 输 入 的 三 个 整 数 的 最 大 值。（中）2、随 机 从 键 盘 上 输 入 三 个 整 数 求 其 平 均 值 输 出。（易）答 案：1、i nt max（i nt x,i

11、 nt y,i nt z）i nt t;t=xy?x:y;t=tz?t:z;return t;2、ma i n（）i nt a,b,c;fI oat sum=0,ave;scanf（“%d%d%d，&a,&b,&c）;sum=a+b+c;ave=sum/3;pr i ntf（%.2fn”,ave）;第 二 章 线 性 结 构 一、判 断 题 1、线 性 表 的 逻 辑 顺 序 与 存 储 顺 序 总 是 一 致 的。（X）2、顺 序 存 储 的 线 性 表 可 以 按 序 号 随 机 存 取。（J）3、顺 序 表 的 插 入 和 删 除 一 个 数 据 元 素，每 次 操 作 平 均 只 有

12、近 一 半 的 元 素 需 要 移 动。（J）4、线 性 表 中 的 元 素 可 以 是 各 种 各 样 的，但 同 一 线 性 表 中 的 数 据 元 素 具 有 相 同 的 特 性，因 此 是 属 于 同 一 数 据 对 象。（J）5、在 线 性 表 的 顺 序 存 储 结 构 中，逻 辑 上 相 邻 的 两 个 元 素 在 物 理 位 置 上 并 不 一 定 紧 邻。（X）6、在 线 性 表 的 链 式 存 储 结 构 中，逻 辑 上 相 邻 的 元 素 在 物 理 位 置 上 不 一 定 相 邻。（J）7、线 性 表 的 链 式 存 储 结 构 优 于 顺 序 存 储 结 构。（义）8

13、、在 线 性 表 的 顺 序 存 储 结 构 中，插 入 和 删 除 时，移 动 元 素 的 个 数 与 该 元 素 的 位 置 有 关。（J）9、线 性 表 的 链 式 存 储 结 构 是 用 一 组 任 意 的 存 储 单 元 来 存 储 线 性 表 中 数 据 元 素 的。(J)10、在 单 链 表 中，要 取 得 某 个 元 素，只 要 知 道 该 元 素 的 指 针 即 可，因 此，单 链 表 是 随 机 存 取 的 存 储 结 构。（X）11、线 性 表 中，每 一 个 元 素 均 存 在 前 驱。（X）12、线 性 表 中，每 一 个 元 素 均 存 在 后 继。（X）13、线

14、性 表 中，存 在 唯 一 一 个 被 称 为 第 一 元 素 的 元 素。（J）14、线 性 表 中，存 在 唯 一 一 个 被 称 为 最 后 一 个 元 素 的 元 素。（J）15、线 性 结 构 是 一 种 一 对 一 的 结 构。（J）二、选 择 题：1、线 性 表 是（A）。（易）A、一 个 有 限 序 列，可 以 为 空；B、一 个 有 限 序 列，不 能 为 空；C、一 个 无 限 序 列，可 以 为 空；D、一 个 无 序 序 列，不 能 为 空。2、对 顺 序 存 储 的 线 性 表，设 其 长 度 为 n,在 任 何 位 置 上 插 入 或 删 除 操 作 都 是 等 概

15、 率 的。插 入 一 个 元 素 时 平 均 要 移 动 表 中 的（A）个 元 素。（易）A、n/2 B、（n+1）/2 C（n-1）/2 D、n3、线 性 表 采 用 链 式 存 储 时，其 地 址（D）。（易）A、必 须 是 连 续 的；B、部 分 地 址 必 须 是 连 续 的；C、一 定 是 不 连 续 的；D、连 续 与 否 均 可 以。4、用 链 表 表 示 线 性 表 的 优 点 是（C）。（易）A、便 于 随 机 存 取 B、花 费 的 存 储 空 间 较 顺 序 存 储 少 C、便 于 插 入 和 删 除 D、数 据 元 素 的 物 理 顺 序 与 逻 辑 顺 序 相 同

16、5、某 链 表 中 最 常 用 的 操 作 是 在 最 后 一 个 元 素 之 后 插 入 一 个 元 素 和 删 除 最 后 一 个 元 素，则 采 用（D）存 储 方 式 最 节 省 运 算 时 间。（易）A、单 链 表B、双 链 表 C、单 循 环 链 表 D、带 头 结 点 的 双 循 环 链 表 6、循 环 链 表 的 主 要 优 点 是（D）。（易）A、不 再 需 要 头 指 针 了 B、已 知 某 个 结 点 的 位 置 后，能 够 容 易 找 到 他 的 直 接 前 趋 C、在 进 行 插 入、删 除 运 算 时，能 更 好 的 保 证 链 表 不 断 开 D、从 表 中 的

17、任 意 结 点 出 发 都 能 扫 描 到 整 个 链 表 7、下 面 关 于 线 性 表 的 叙 述 错 误 的 是（B）。（易）A、线 性 表 采 用 顺 序 存 储，必 须 占 用 一 片 地 址 连 续 的 单 元；B、线 性 表 采 用 顺 序 存 储，不 便 于 进 行 插 入 和 删 除 操 作；C、线 性 表 采 用 链 式 存 储，不 必 占 用 一 片 地 址 连 续 的 单 元；D、线 性 表 采 用 链 式 存 储，便 于 进 行 插 入 和 删 除 操 作；8、单 链 表 中，增 加 一 个 头 结 点 的 目 的 是 为 了（C）。（易）A、使 单 链 表 至 少

18、有 一 个 结 点 B、标 识 表 结 点 中 首 结 点 的 位 置 C、方 便 运 算 的 实 现 D、说 明 单 链 表 是 线 性 表 的 链 式 存 储 9、若 某 线 性 表 中 最 常 用 的 操 作 是 在 最 后 一 个 元 素 之 后 插 入 一 个 元 素 和 删 除 第 一 个 元 素，则 采 用（D）存 储 方 式 最 节 省 运 算 时 间。（易）A、单 链 表 B、仅 有 头 指 针 的 单 循 环 链 表 C、双 链 表 D、仅 有 尾 指 针 的 单 循 环 链 表 10、若 某 线 性 表 中 最 常 用 的 操 作 是 取 第 i个 元 素 和 找 第 i

19、个 元 素 的 前 趋 元 素，则 采 用（B）存 储 方 式 最 节 省 运 算 时 间。（易）A、单 链 表 B、顺 序 表 C、双 链 表 D、单 循 环 链 表 11、一 个 向 量（一 种 顺 序 表）第 一 个 元 素 的 存 储 地 址 是 100,每 个 元 素 的 长 度 为 2,则 第 5 个 元 素 的 地 址 是 B。（易）A、110 B、108 C、100 D、12012、不 带 头 结 点 的 单 链 表 head为 空 的 判 定 条 件 是 A。（易）A、head 二 二 NULL;B、head-next=二 NULL;C head-next=二 head;D

20、head!二 NULL;13、带 头 结 点 的 单 链 表 head为 空 的 判 定 条 件 是 B。（易）A、head 二 二 NULL;B、head-next=二 NULL;C、head-next 二 二 head;D、head!=NULL;14、在 一 个 单 链 表 中，若 p 所 指 结 点 不 是 最 后 结 点，在 p 之 后 插 入 s 所 指 结 点，则 执 行 B_o（易）A、s-next=p;p-next=s;B、s-next=p-next;p-next=s;C、s-next=p-next;p=s;D p-next=s;s-next=p;15、在 一 个 单 链 表

21、中，已 知 q 所 指 结 点 是 p 所 指 结 点 的 前 驱 结 点，若 在 q 和 p 之 间 插 入 s 结 点，则 执 行 C。（易）A、s-nextz:p-next;p-next=s;B、p-next=s-next;s-next二 p;C、q-next=s;s-next=p;D、p-next=s;s-next二 q;16、从 一 个 具 有 n 个 结 点 的 单 链 表 中 查 找 其 值 等 于 x 结 点 时，在 查 找 成 功 的 情 况 下，需 平 均 比 较 口 _个 结 点。（易）A、n;B、n/2;C、（n-1）/2;D、（n+1）/2;17、给 定 有 n 个

22、结 点 的 向 量，建 立 一 个 有 序 单 链 表 的 时 间 复 杂 度 _C _。（易）A 0（1）;B、0（n）;C、0（n2）;D、0（nlog2n）;18、顺 序 存 储 结 构 是 一 种 _ A _ 的 存 储 结 构。（易）A、随 机 存 取 B、索 引 存 取 C、顺 序 存 取 D、散 列 存 取 19、在 以 下 的 叙 述 中，正 确 的 是 _ C 一。（易）A、线 性 表 的 顺 序 存 储 结 构 优 于 链 表 存 储 结 构B、线 性 表 的 顺 序 存 储 结 构 适 用 于 频 繁 插 入/删 除 数 据 元 素 的 情 况 C、线 性 表 的 链 表

23、 存 储 结 构 适 用 于 频 繁 插 入/删 除 数 据 元 素 的 情 况 D、线 性 表 的 链 表 存 储 结 构 优 于 顺 序 存 储 结 构 20、非 空 的 循 环 单 链 表 head的 尾 结 点（由 p 所 指 向）满 足 C_o（易）A、p-next=NULL B、p二 二 NULLC、p-next=head D p=head21、在 一 个 单 链 表 中，若 删 除 p 所 指 结 点 的 后 续 结 点，则 执 行 _A。（易）A、p-next二 p-next-next；B、p=p-next;p-next=p-next-next；C、p-next=p-next;

24、D、p=p-next-next；三、填 空 题 1 在 一 个 长 度 为 n 的 向 量 中 的 第 i个 元 素 ClWiWn）之 前 插 入 一 个 元 素 时，需 向 后 移 动 ni+1 个 元 素。（易）2、在 一 个 长 度 为 n 的 向 量 中 删 除 第 i个 元 素（1WiWn）时，需 向 前 移 动 个 元 素。（易）3、在 一 个 单 链 表 中 p 所 指 结 点 之 前 插 入 一 个 由 指 针 s 所 指 结 点，可 执 行 以 下 操 作:（易）s-next=_（1）;p-next=s;t二 p-data;p-data=（2）;s-data=（3）;4、在

25、线 性 表 L=（a1,a2,an）中，L 称 为 线 性 表 的,n称 为 线 性 表 的 _。（易）5、在 线 性 表 中 有（ai,aj）,称 ai为 aj的,称 aj为 ai的。（易）6、在 顺 序 表 中，若 第 一 个 元 素 所 在 的 地 址 为 Loc（a1）,每 个 元 素 在 内 存 中 占 有 L个 存 储 单 元，则 元 素 ai在 内 存 中 的 地 址 Loc（ai）;。（易）7、顺 序 表 是 一 种 存 取 的 存 储 结 构，其 元 素 的 逻 辑 位 置 与 物 理 位 置 一 一 对 应。（易）8、系 统 在 内 存 中 为 顺 序 表 提 供 一 组

26、的 存 储 空 间，为 单 链 表 提 供 一 组 的 存 储 空 间。（易）9、在 单 链 表 中，一 个 结 点 包 含 两 部 分 内 容，分 别 为 和 o（易）10、在 单 链 表 中，若 指 针 p 已 指 向 最 后 一 个 结 点，则 p 应 满 足 的 条 件 是 o（易）11、在 单 链 表 中，若 结 点 p 是 结 点 q 的 前 驱，应 满 足 的 条 件 是。（易）12、在 单 链 表 中，申 请 一 个 结 点 空 间 的 命 令 是，释 放 一 个 空 间 的 命 令 是 _。（易）13、在 双 向 链 表 中，每 个 结 点 有 两 个 指 针 域，一 个 为

27、,指 向；另 一 个 为，指 向 o（易）14、在 一 个 单 链 表 中 p 所 指 结 点 之 后 插 入 一 个 s 所 指 结 点 时，应 执 行 s-next=_ p.next 和 p-next=_s 的 操 作。（易）15、在 双 向 链 表 中，若 结 点 p 是 结 点 q 的 前 驱，现 要 删 除 结 点 q,需 要 完 成 的 操 作 是 p.next二 q.next；q.next,pr i or=q.pr i or；（易）16、在 双 向 链 表 中，若 在 结 点 p 之 前 插 入 一 个 新 结 点 s,需 要 完 成 的 操 作 有 一 s.pr i or二 p

28、.pr i o r；_ s.n e x t=p；_ p.pr i or.next二 s；_ p.pr i or二 s_;（易）答 案：1、2 n-i 3、（1）p-next（2）s-data（3）t4、名 字 长 度 5、直 接 前 驱 元 素 直 接 后 继 元 素 6、LOG（ai）=Loc（a1）+（i-1）*L 7、随 机 8、连 续 任 意 9、指 针 域 数 据 域 10、p.next-nu I I 11、p.next=q 12、ma I I oc 0 free 013、前 驱 指 针 域 prior后 继 指 针 域 next 四、算 法 设 计 题：1、在 一 顺 序 表 L

29、的 第 i个 元 素 前，插 入 一 新 元 素 X。（中）2、现 有 一 顺 序 表 L,其 值 非 递 增 有 序 排 列，现 插 入 一 新 元 素 x,要 求 插 入 后，L仍 保 持 非 递 增 有 序 排 列，试 写 其 算 法。（中）3、在 带 头 结 点 的 单 链 表 H 中 的 p 结 点 前 插 入 一 个 新 元 素 X。（中）4、已 知 单 链 表 LA、L A中 的 元 素 按 值 非 递 减 有 序 排 列，现 将 LA、LB归 并 成 一 个 新 表 L C,并 要 求 L C中 的 元 素 亦 非 递 减 有 序 排 列。（中）五、编 程 题：1、百 钱 百

30、鸡 问 题。（中）2、猎 人 与 狗 的 问 题：一 队 猎 人 一 队 狗，一 共 八 百 九，问 多 少 猎 人 多 少 狗。（中）四、五 题 答 案：四、算 法 题：1 i nt Insert_Sq（SqL i st L,i nt i,eIemtpx）两 队 并 成 一 队 走，数 头 一 共 三 百 六，数 脚 i f(i L.len+1)return 0;i f(L.I enmaxs i ze)return _1;for(j=L.len;j=i;j)L.elemj+1=L.eIemj;L.elemi=x;L.Ien+;return 1;3 i nt Insert_L(LNode*H,

31、LNode*p,e I emtp x)s=(LNode*)2、i nt Insert(SqL i st L,eIemtp x)if(L.Ien-maxsize)return-1;for(p二&L.e I em L.len-1;*p=x;p)*(p+1)=*p；*(p+1)=x;return 1;)s.data二 x;q二 H;while(q.next!=p)q=q.next;s.next二 p;ma I Ioc(s i zeof(LNode);q.next=s;return 1;4、vo i d Merge_L(LNode La,LNodeLb,LNode Lc)pa=La.next;pb=L

32、b.next;Lc=pc=La;while(pa&pb)五、编 程 题：1、ma i n()int x,y,z;for(x=1;x20;x+)for(y=1;y33;y+)z=100-x-y;i f(100=5*x+3*y+z/3.0)pr i ntf(%d,%d,%dn”,x,y,z);i f(pa.data=pb.data)pc.next=pa;pc=pa;pa=pa.next;e I sepc.next=pb;pc=pb;pb=pb.next;pc.next=pa?pa:pb;free(Lb);)2、ma i n()int x,y;for(x=1;x360;x+)y=360-x;if(2

33、*x+4*y=890)pr i ntf(“d,%d n”,x,y);第 三 章 栈 和 队 列 一、判 断 题：1、栈 和 队 列 都 是 限 制 存 取 点 的 线 性 结 构（易）2、栈 和 队 列 是 两 种 重 要 的 线 性 结 构。（易）3、带 头 结 点 的 单 链 表 形 式 的 队 列，头 指 针 F 指 向 队 列 的 头 结 点，尾 指 针 R 指 向 队 列 的 最 后 一 个 结 点（易）4、在 对 不 带 头 结 点 的 链 队 列 作 出 队 操 作 时，不 会 改 变 头 指 针 的 值。（易）答 案：14 V V X X二、选 择 题：1、一 个 栈 的 入

34、栈 序 列 a,b,c,d,e,则 栈 的 不 可 能 的 输 出 序 列 是 _ C _。A、edcba B、decba C、dceab D abode2、若 已 知 一 个 栈 的 入 栈 序 列 是 1,2,3,，n,其 输 出 序 列 为 p1,p2,p3,pn,若 p1=n,则 pi 为 _ C_ oA、i B、n=i C、n-i+1 D、不 确 定 3、栈 结 构 通 常 采 用 的 两 种 存 储 结 构 是 _ A _。A、顺 序 存 储 结 构 和 链 式 存 储 结 构 C 链 表 存 储 结 构 和 数 组 B、散 列 方 式 和 索 引 方 式 D、线 性 存 储 结

35、构 和 非 线 性 存 储 结 构 4、判 定 一 个 顺 序 栈 ST（最 多 元 素 为 mO）为 空 的 条 件 是 B_o A、top!=0 B、top=0 C、top!=m0 D、top=m0-15、判 定 一 个 顺 序 栈 ST（最 多 元 素 为 mO）为 栈 满 的 条 件 是 _ D _。A、top!=0 B、top=二 0 C、top!=m0 D top=二 mO76、队 列 操 作 的 原 则 是（A）A、先 进 先 出 B、后 进 先 出 C、只 能 进 行 插 入 D、只 能 进 行 删 除 7、向 一 个 栈 顶 指 针 为 HS的 链 栈 中 插 入 一 个 s

36、 所 指 结 点 时，则 执 行 2。（不 带 空 的 头 结 点）（易）A、HS一 next=s;C、s一 next=HS;HS二 s;B、s一 next二 HSnext;HS一 D、s next二 HS;HS二 HS一 next二 s;next;8、从 一 个 栈 顶 指 针 为 HS的 链 栈 中 删 除 一 个 结 点 时，用 x 保 存 被 删 结 点 的 值，则 执 行 B。（不 带 空 的 头 结 点）（中）A、x=HS;HS=HSnext;B、x=HSdata;c、HS=HSnext;x=HS data;D、x=HS data;HS=HSnext;9、一 个 队 列 的 数 据

37、 入 列 序 列 是 1,2,3,4,则 队 列 的 出 队 时 输 出 序 列 是 _ C _。（易）A、4,3,2,1 B、1,2,3,4C、1,4,3,2 D、3,2,4,110、判 定 一 个 循 环 队 列 QU（最 多 元 素 为 m）为 空 的 条 件 是 _ C _。（中）A、rear-front=m B、rear-front_1=mC、fronts-rear D、front二 二 rear+111、判 定 一 个 循 环 队 列 QU（最 多 元 素 为 m,m=Maxsi ze-1）为 满 队 列 的 条 件 是 A、（rear-front）+Maxs i ze）%Maxs

38、 i ze=mA_ o（易）B、rear-front-1=m C、front二 二 rear D、front二 二 rear+112、循 环 队 列 用 数 组 A0,m-l存 放 其 元 素 值，已 知 其 头 尾 指 针 分 别 是 front和 rear,则 当 前 队 列 中 的 元 素 个 数 是 _ A _。（中）A、（rear-front+m）%m B、rear-front+1C、rear-front-1 D、rear-front13、栈 和 队 列 的 共 同 点 是 _ C _。A、都 是 先 进 后 出 B、都 是 先 进 先 出 C、只 允 许 在 端 点 处 插 入 和

39、 删 除 元 素 D、没 有 共 同 点 14、栈 操 作 的 原 则 是（B）（易）A、先 进 先 出 B、后 进 先 出 C、只 能 进 行 插 入 D、只 能 进 行 删 除 15、在 顺 序 栈 中，判 断 栈 s 为 空 的 条 件 是（D）（中）A、t.base=NULL B、st.top=st.stacks i zeC、st.top-st.base=st.stacksize D、s*t.top st.base16、在 顺 序 栈 中，判 断 栈 s 满 的 条 件 是（C）（易）A、st.base=NULL B、st.top=st.stacks i zeC、st.top-st.b

40、ase=st.stacks i ze D、st.top=st.base答 案：1-5 CCABD 6-10 ACBCC 11-15 AACBD 16 C三、填 空 题：1、栈 和 队 列 都 是 结 构，对 于 栈 只 能 在 一 插 入 和 删 除 元 素；对 于 队 列 只 能 在 插 入 元 素 和 删 除 元 素。（易）2、向 一 个 长 度 为 n 的 顺 序 表 的 第 i个 元 素（1WiWn+1）之 前 插 入 一 个 元 素 时，需 向 后 移 动 个 兀 素。（易）3、向 一 个 长 度 为 n 的 顺 序 表 中 删 除 第 i个 元 素（1 W i W n）时，需 向

41、前 移 动 个 元 素。（易）4、向 栈 中 压 入 元 素 的 操 作 是 o（易）5、对 栈 进 行 退 栈 时 的 操 作 是 o（易）6、在 一 个 循 环 队 列 中，队 首 指 针 指 向 队 首 元 素 的。（易）7、从 循 环 队 列 中 删 除 一 个 元 素 时，其 操 作 是。（易）8、在 具 有 n 个 单 元 的 循 环 队 列 中，队 满 时 共 有 一 个 元 素。（易）9、一 个 栈 的 输 入 序 列 是 12345,则 栈 的 输 出 序 列 43512是。（易）10、一 个 栈 的 输 入 序 列 是 12345,则 栈 的 输 出 序 列 12345是。

42、（易）11、队 列 的 基 本 性 质 是；栈 的 基 本 性 质 是 o（易）12、在 一 个 链 栈 中，若 栈 顶 指 针 等 于 NULL则 为,在 一 个 链 队 中，若 队 首 指 针 与 队 尾 指 针 的 值 相 同，则 表 示 该 队 列 为 或 该 队 列 _。（易）13、向 一 个 栈 顶 指 针 为 top的 链 栈 中 插 入 一 个 新 结 点*P,应 执 行 和 操 作。（易）14、栈 的 顺 序 存 储 结 构 即 顺 序 栈，是 利 用 来 依 次 存 放 自 栈 底 至 栈 顶 的 数 据 元 素；当 栈 为 非 空 时，栈 顶 指 针 tOp始 终 指 向

43、 015、从 数 据 结 构 的 角 度 看，栈 和 队 列 是 两 类 线 性 表。（易）答 案：1.线 性、栈 顶、队 尾、队 首 4.先 移 动 栈 顶 指 针，后 存 入 元 素 6.前 一 个 位 置 8.n-1 9.不 可 能 的 12、栈 空 空 队 只 有 一 个 元 素 2.n-i+1 3.n-i5.先 取 出 元 素，后 移 动 栈 顶 指 针 7.先 移 动 队 首 元 素，后 取 出 元 素 1 0.可 能 的 11、FIFO LIFO13 p-next=top top=p14、一 组 地 址 连 续 的 存 储 单 元 栈 顶 元 素 的 下 一 位 置 15、受 限

44、 的 线 性 表 四、算 法 题：1、输 入 一 个 任 意 的 非 负 十 进 制 整 数,输 出 与 其 等 值 的 八 进 值 数。（中）答 案：vo i d convers i on()Ini tStack(s);scanf(%d,&N);while(N)push(s,N%d);N=n/8;wh i I e(!empty(s)pop(s,e);pr i ntf(%dn,e);五、编 程 题：1、从 键 盘 上 输 入 一 个 大 写 字 母，要 求 改 用 小 写 字 母 输 出。(中)2、输 入 一 个 圆 的 半 径，求 其 周 长 及 面 积 并 输 出。答 案：1、ma i n

45、()char c;scanf(“c”，&c);2#definet PI 3.14c=c+32;pr i ntf(%cn,c);)ma i n()f I oat r,s,c;scanf(,&r);s=P I*r*r;p r in t f（as=%.2f,c=%.2 fnw,s,c）;c=2*PI*r;第 四 章 串 和 广 义 表 一、判 断 题：1、空 串 是 由 空 白 字 符 组 成 的 串（易）2、串 的 定 长 顺 序 结 构 是 用 一 组 地 址 连 续 的 存 储 单 元 存 储 串 值 的 字 符 序 列，按 照 预 定 义 的 大 小，为 每 个 定 义 的 串 变 量 分

46、配 一 个 固 定 长 度 的 存 储 区。（易）3、串 的 堆 分 配 存 储 表 示 是 用 一 组 地 址 连 续 的 存 储 单 元 存 储 串 值 的 字 符 序 列，但 它 们 的 存 储 空 间 是 在 程 序 执 行 过 程 中 动 态 分 配 得 到 的。（易）4、如 果 一 个 串 中 的 所 有 字 符 均 在 另 一 串 中 出 现，那 么 则 说 明 前 者 是 后 者 的 子 串。（易）5、串 是 由 有 限 个 字 符 构 成 的 连 续 序 列，串 长 度 为 串 中 字 符 的 个 数，子 串 是 主 串 中 字 符 构 成 的 有 限 序 列。（易）6、广

47、义 表 的 表 头 一 定 是 列 表。（易）7、广 义 表 的 表 尾 一 定 是 列 表。（易）8、空 串 的 长 度 为 零。（易）9、广 义 表 的 元 素 即 可 以 是 原 子，也 可 以 是 子 表。（易）10、广 义 表 中 的 子 表 与 串 中 的 子 串 的 含 义 一 样。（易）11、广 义 表 A=（）,为 空 表，其 长 度 为 0。（易）12、由 于 广 义 表 的 元 素 可 以 是 列 表，所 以 可 以 将 广 义 表 转 化 为 一 个 树 型 结 构 答 案：1-5 X V V X X 6-10 X V V V X 11-12 J J二、选 择 题：1、

48、以 下 叙 述 中 正 确 的 是 o（易）A、串 是 一 种 特 殊 的 线 性 表 B、串 的 长 度 必 须 大 于 零 C、串 中 无 素 只 能 是 字 母 D、空 串 就 是 空 白 串2、空 串 与 空 格 串 是 相 同 的，这 种 说 法 o（易）A、正 确 B、不 正 确 3、串 是 一 中 特 殊 的 线 性 表，其 特 殊 性 体 现 在 一。（易）A、可 以 顺 序 存 储 B、数 据 元 素 是 一 个 字 符 C、可 以 链 接 存 储 D、数 据 元 素 可 以 是 多 个 字 符 4、设 有 两 个 串 p 和 q,求 q 在 P 中 首 次 出 现 的 位

49、置 的 运 算 称 作。（易）A、连 接 B、模 式 匹 配 C、求 子 串 D、求 串 长 5、设 串 s1=ABCDEFG,s2=PQRST,函 数 con（x,y）返 回 x 和 y 串 的 连 接 串，subs（s,i,）返 回 串 s 的 从 序 号 i的 字 符 开 始 的 J个 字 符 组 成 的 子 串，len（s）返 回 串 s的 长 度，则 con（subs（s1,2,len（s2）,subs（s1,len（s2）,2）的 结 果 串 是。（中）A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF6、设 串 的 长 度 为 n,则 它 的 子 串 个 数

50、 为 o（易）A、n B、n（n+1）C、n（n+1）/2 D n（n+1）/2+17、下 列 那 些 为 空 串（）（易）A、S=B、S=C、S=“6 D、S=“0”8、S1=ABCD”，S2=“CD”贝 l j S2 在 S3 中 的 位 置 是）（易）A、1 B、2 C、3 D、49、串 是 一 种 特 殊 的 线 性 表，其 特 殊 性 体 现 在（）0（易）A、可 以 顺 序 存 储 B、C、可 以 链 接 存 储 D、10、串 是（）o（易）A、少 于 一 个 字 母 的 序 列 C、不 少 于 一 个 字 符 的 序 列 11、串 的 长 度 是（）o（易）A、串 中 不 同 字