数据结构期末考试试卷3.pdf

《数据结构期末考试试卷3.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试试卷3.pdf（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、习 题 1一、单 项 选 择 题 1.数 据 结 构 是 指()oA.数 据 元 素 的 组 织 形 式 B.数 据 类 型 C.数 据 存 储 结 构 D.数 据 定 义 2.数 据 在 计 算 机 存 储 器 内 表 示 时，物 理 地 址 与 逻 辑 地 址 不 相 同 的，称 之 为()0A.存 储 结 构 B.逻 辑 结 构 C.链 式 存 储 结 构 D.顺 序 存 储 结 构 3.树 形 结 构 是 数 据 元 素 之 间 存 在 一 种()oA.一 对 一 关 系 B.多 对 多 关 系 C.多 对 一 关 系 D.一 对 多 关 系 4.设 语 句 x+的 时 间 是 单 位

2、 时 间，则 以 下 语 句 的 时 间 复 杂 度 为()。for(i=1;i=n;i+)for(j=i;j=n;j+)x+;A.0(1)B.0()C.O(n)D.0()5.算 法 分 析 的 目 的 是(1),算 法 分 析 的 两 个 主 要 方 面 是(2)o(1)A.找 出 数 据 结 构 的 合 理 性 B.研 究 算 法 中 的 输 入 和 输 出 关 系 C.分 析 算 法 的 效 率 以 求 改 进 D.分 析 算 法 的 易 懂 性 和 文 档 性(2)A.空 间 复 杂 度 和 时 间 复 杂 度 B.正 确 性 和 简 明 性c.可 读 性 和 文 档 性 D.数 据

3、复 杂 性 和 程 序 复 杂 性 6.计 算 机 算 法 指 的 是（1）,它 具 备 输 入，输 出 和（2）等 五 个 特 性。（1）A.计 算 方 法 B.排 序 方 法 C.解 决 问 题 的 有 限 运 算 序 列 D.调 度 方 法（2）A.可 行 性，可 移 植 性 和 可 扩 充 性 B.可 行 性，确 定 性 和 有 穷 性 C.确 定 性，有 穷 性 和 稳 定 性 D.易 读 性，稳 定 性 和 安 全 性 7.数 据 在 计 算 机 内 有 链 式 和 顺 序 两 种 存 储 方 式，在 存 储 空 间 使 用 的 灵 活 性 上，链 式 存 储 比 顺 序 存 储

4、要（）oA.低 B.高 C.相 同 D.不 好 说 8.数 据 结 构 作 为 一 门 独 立 的 课 程 出 现 是 在（）年。A.1946 B.1953 C.1964 D.19689.数 据 结 构 只 是 研 究 数 据 的 逻 辑 结 构 和 物 理 结 构，这 种 观 点（）。A.正 确 B.错 误 C.前 半 句 对，后 半 句 错 D.前 半 句 错，后 半 句 对 10.计 算 机 内 部 数 据 处 理 的 基 本 单 位 是（）。A.数 据 B.数 据 元 素 C.数 据 项 D.数 据 库 二、填 空 题 1.数 据 结 构 按 逻 辑 结 构 可 分 为 两 大 类，分

5、 别 是?_ 和 2.数 据 的 逻 辑 结 构 有 四 种 基 本 形 态，分 别 是、和3.线 性 结 构 反 映 结 点 间 的 逻 辑 关 系 是 _的，非 线 性 结 构 反 映 结 点 间 的 逻 辑 关 系 是 的。4.一 个 算 法 的 效 率 可 分 为 效 率 和 _效 率。5.在 树 型 结 构 中，树 根 结 点 没 有 结 点，其 余 每 个 结 点 的 有 且 只 有 个 前 趋 驱 结 点；叶 子 结 点 没 有 结 点；其 余 每 个 结 点 的 后 续 结 点 可 以 6.在 图 型 结 构 中，每 个 结 点 的 前 趋 结 点 数 和 后 续 结 点 数

6、可 以 7.线 性 结 构 中 元 素 之 间 存 在 关 系；树 型 结 构 中 元 素 之 间 存 在 关 系；图 型 结 构 中 元 素 之 间 存 在 关 系。8.下 面 程 序 段 的 时 间 复 杂 度 是 _ ofor(i=0;in;i+)for(j=0;jn;j+)AiU=O;9.下 面 程 序 段 的 时 间 复 杂 度 是,i=s=O;while(sn)i+；s+=i;10.下 面 程 序 段 的 时 间 复 杂 度 是 s=0;for(i=0;in;i+)for(j=0;jn;j+)s+=Bij;sum=s;11.下 面 程 序 段 的 时 间 复 杂 度 是 _，i=1

7、；while(i=n)i=i*3;12.衡 量 算 法 正 确 性 的 标 准 通 常 是 13.算 法 时 间 复 杂 度 的 分 析 通 常 有 两 种 方 法，即 和 的 方 法，通 常 我 们 对 算 法 求 时 间 复 杂 度 时，采 用 后 一 种 方 法。三、求 下 列 程 序 段 的 时 间 复 杂 度。1.x=0;for(i=1;in;i+)for(j=i+1;j=n;j+)x+;2.x=0;for(i=1;in;i+)for(j=1;j=n-i;j+)x+;3.int i,j,k;for(i=0;in;i+)for(j=0;j=n;j+)ciD=O;for(k=0;k=O)

8、&Ai!=k)j；return(i);5.fact(n)if(n=1)return(1);elsereturn(n*fact(n-1);习 题 1参 考 答 案一、单 项 选 择 题 1.A 2.C 3.D 4.B 5.C、A 6.C、B 7.B 8.D 9.B 10.B二、填 空 题 1.线 性 结 构，非 线 性 结 构 2.集 合，线 性，树，图 3.一 对 一,一 对 多 或 多 对 多 4.时 间，空 间 5.前 趋，一，后 继，多 6.有 多 个 7.一 对 一，一 对 多，多 对 多 8.0()9.0()10.0()11.O(log n)12.程 序 对 于 精 心 设 计 的

9、典 型 合 法 数 据 输 入 能 得 出 符 合 要 求 的 结 果。13.事 后 统 计，事 前 估 计 三、算 法 设 计 题 1.0()2.0()3.0(n)4.0(n)5.O(n)习 题 2一、单 项 选 择 题1.线 性 表 是 OA.一 个 有 限 序 列，可 以 为 空 B.一 个 有 限 序 列，不 可 以 为 空 C.一 个 无 限 序 列，可 以 为 空 D.一 个 无 限 序 列，不 可 以 为 空 2.在 一 个 长 度 为 n 的 顺 序 表 中 删 除 第 i 个 元 素(0=inext=s;s-prior=p;p-next-prior=s;s-next=p-ne

10、xt;B.C.D.s-prior=p;p-next=s;p-next=s;s-prior=p;s-prior=p;s-next=p-next;p-next-prior=s;p-next-prior=s;s-next=p-next;s-next=p-next;p-next-prior=s;p-next=s;6.设 单 链 表 中 指 针 p 指 向 结 点 m,若 要 删 除 m 之 后 的 结 点(若 存 在)，则 需 修 改 指 针 的 操 作 为 OA.p-next=p-next-next;B.p=p-next;C.p=p-next-next;D.p-next=p;7.在 一 个 长 度

11、为 n 的 顺 序 表 中 向 第 i 个 元 素(0 in+l)之 前 插 入 一 个 新 元 素 时，需 向 后 移 动 个 元 素。A.n-i B.n-i+l C.n-i-1 D.i8.在 一 个 单 链 表 中，已 知 q 结 点 是 p 结 点 的 前 趋 结 点，若 在 q 和 p之 间 插 入 s 结 点，则 须 执 行A.s-next=p-next;p-next=sB.q-next=s;s-next=pC.p-next=s-next;s-next=pD.p-next=s;s-next=q9.以 下 关 于 线 性 表 的 说 法 不 正 确 的 是 oA.线 性 表 中 的 数

12、 据 元 素 可 以 是 数 字、字 符、记 录 等 不 同 类 型。B.线 性 表 中 包 含 的 数 据 元 素 个 数 不 是 任 意 的。C.线 性 表 中 的 每 个 结 点 都 有 且 只 有 一 个 直 接 前 趋 和 直 接 后 继。D.存 在 这 样 的 线 性 表：表 中 各 结 点 都 没 有 直 接 前 趋 和 直 接 后 继。10.线 性 表 的 顺 序 存 储 结 构 是 一 种 的 存 储 结 构。A.随 机 存 取 B.顺 序 存 取 C.索 引 存 取 D.散 列 存 取 11.在 顺 序 表 中，只 要 知 道,就 可 在 相 同 时 间 内 求 出 任 一

13、 结 点 的 存 储 地 址。A.基 地 址 B.结 点 大 小 C.向 量 大 小 D.基 地 址 和 结 点 大 小 12.在 等 概 率 情 况 下，顺 序 表 的 插 入 操 作 要 移 动 结 点。A.全 部 B,一 半 C.三 分 之 一 D.四 分 之 13.在 运 算 中，使 用 顺 序 表 比 链 表 好。A.插 入 B.删 除 C.根 据 序 号 查 找 D.根 据 元 素 值 查 找 14.在 一 个 具 有 n 个 结 点 的 有 序 单 链 表 中 插 入 一 个 新 结 点 并 保 持 该 表 有 序 的 时 间 复 杂 度 是 _ OA.0(1)B.O(n)C.O

14、(n2)D.O(log2n)1 5.设 有 一 个 栈，元 素 的 进 栈 次 序 为 A,B,C,D,E,下 列 是 不 可 能 的 出 栈 序 歹 OA.A,B,C,D,E B.B,C,D,E,AC.E,A,B,C,D D.E,D,C,B,A1 6.在 一 个 具 有 n 个 单 元 的 顺 序 栈 中，假 定 以 地 址 低 端(即 0单 元)作 为 栈 底，以 top作 为 栈 顶 指 针，当 做 出 栈 处 理 时，to p变 化 为A.top 不 变 B.top=0 C.top-D.top+1 7.向 一 个 栈 顶 指 针 为 h s的 链 栈 中 插 入 一 个 s 结 点 时

15、，应 执 行 A.hs-next=s;B.s-next=hs;hs=s;C.s-next=hs-next;hs-next=s;D.s-next=hs;hs=hs-next;1 8.在 具 有 n 个 单 元 的 顺 序 存 储 的 循 环 队 列 中，假 定 front和 rear分 别 为 队 头 指 针 和 队 尾 指 针，则 判 断 队 满 的 条 件 为 OA.rear%n=front B.(front+l)%n=rearC.rear%n-1=front D.(rear+l)%n=front1 9.在 具 有 n 个 单 元 的 顺 序 存 储 的 循 环 队 列 中，不 支 定 fr

16、ont和 rear分 别 为 队 头 指 针 和 队 尾 指 针，则 判 断 队 空 的 条 件 为 0A.rear%n=front B.front+l=rearC.rear=front D.(rear+l)%n=front2 0.在 一 个 链 队 列 中，假 定 front和 rear分 别 为 队 首 和 队 尾 指 针，则 删 除 一 个 结 点 的 操 作 为。A.front=front-next B.rear=rear-nextC.rear=front-next D.front=rear-next二、填 空 题 1.线 性 表 是 一 种 典 型 的 结 构。2.在 一 个 长 度

17、 为 n 的 顺 序 表 的 第 i 个 元 素 之 前 插 入 一 个 元 素，需 要 后 移 个 元 素。3.顺 序 表 中 逻 辑 上 相 邻 的 元 素 的 物 理 位 置 o4.要 从 一 个 顺 序 表 删 除 一 个 元 素 时，被 删 除 元 素 之 后 的 所 有 元 素 均 需 一 个 位 置，移 动 过 程 是 从 向 依 次 移 动 每 一 个 元 素。5.在 线 性 表 的 顺 序 存 储 中，元 素 之 间 的 逻 辑 关 系 是 通 过 决 定 的；在 线 性 表 的 链 接 存 储 中，元 素 之 间 的 逻 辑 关 系 是 通 过 决 定 的。6.在 双 向

18、链 表 中，每 个 结 点 含 有 两 个 指 针 域，一 个 指 向 结 点，另 一 个 指 向 结 点。7.当 对 一 个 线 性 表 经 常 进 行 存 取 操 作，而 很 少 进 行 插 入 和 删 除 操 作 时，则 采 用 存 储 结 构 为 宜。相 反，当 经 常 进 行 的 是 插 入 和 删 除 操 作 时，则 采 用 存 储 结 构 为 宜。8.顺 序 表 中 逻 辑 上 相 邻 的 元 素，物 理 位 置 相 邻，单 链 表 中 逻 辑 上 相 邻 的 元 素，物 理 位 置 相 邻。9.线 性 表、栈 和 队 列 都 是 _结 构，可 以 在 线 性 表 的 位 置 插

19、 入 和 删 除 元 素；对 于 栈 只 能 在 位 置 插 入 和 删 除 元 素；对 于 队 列 只 能 在 位 置 插 入 元 素 和 在 位 置 删 除 元 素。10.根 据 线 性 表 的 链 式 存 储 结 构 中 每 个 结 点 所 含 指 针 的 个 数，链 表 可 分 为 和;而 根 据 指 针 的 联 接 方 式，链 表 又 可 分 为 和 O11.在 单 链 表 中 设 置 头 结 点 的 作 用 是 _O12.对 于 一 个 具 有 n 个 结 点 的 单 链 表，在 已 知 的 结 点 p 后 插 入 一 个 新 结 点 的 时 间 复 杂 度 为,在 给 定 值 为

20、 x 的 结 点 后 插 入 一 个 新 结 点 的 时 间 复 杂 度 为 o13.对 于 一 个 栈 作 进 栈 运 算 时，应 先 判 别 栈 是 否 为,作 退 栈 运 算 时，应 先 判 别 栈 是 否 为,当 栈 中 元 素 为 m 时，作 进 栈 运 算 时 发 生 上 溢，则 说 明 栈 的 可 用 最 大 容 量 为。为 了 增 加 内 存 空 间 的 利 用 率 和 减 少 发 生 上 溢 的 可 能 性，由 两 个 栈 共 享 一 片 连 续 的 内 存 空 间 时，应 将 两 栈 的 分 别 设 在 这 片 内 存 空 间 的 两 端，这 样 只 有 当 _时 才 产

21、生 上 溢。14.设 有 一 空 栈,现 有 输 入 序 列 1,2,3,4,5,经 过 push,push,pop,push,pop,push,push 后，输 出 序 列 是。15.无 论 对 于 顺 序 存 储 还 是 链 式 存 储 的 栈 和 队 列 来 说，进 行 插 入 或 删 除 运 算 的 时 间 复 杂 度 均 相 同 为 O三、简 答 题 1.描 述 以 下 三 个 概 念 的 区 别：头 指 针，头 结 点，表 头 结 点。2.线 性 表 的 两 种 存 储 结 构 各 有 哪 些 优 缺 点？3.对 于 线 性 表 的 两 种 存 储 结 构，如 果 有 n 个 线

22、性 表 同 时 并 存，而 且在 处 理 过 程 中 各 表 的 长 度 会 动 态 发 生 变 化，线 性 表 的 总 数 也 会 自 动 改 变，在 此 情 况 下，应 选 用 哪 一 种 存 储 结 构？为 什 么？4.对 于 线 性 表 的 两 种 存 储 结 构，若 线 性 表 的 总 数 基 本 稳 定，且 很 少 进 行 插 入 和 删 除 操 作，但 要 求 以 最 快 的 速 度 存 取 线 性 表 中 的 元 素，应 选 用 何 种 存 储 结 构？试 说 明 理 由。5.在 单 循 环 链 表 中 设 置 尾 指 针 比 设 置 头 指 针 好 吗？为 什 么？6.假 定

23、 有 四 个 元 素 A,B,C,D依 次 进 栈，进 栈 过 程 中 允 许 出 栈，试 写 出 所 有 可 能 的 出 栈 序 列。7.什 么 是 队 列 的 上 溢 现 象？一 般 有 几 种 解 决 方 法，试 简 述 之。8.下 述 算 法 的 功 能 是 什 么？LinkList*Demo(LinkList*L)L 是 无 头 结 点 的 单 链 表 LinkList*q,*p;if(L&L-next)q=L;L=L-next;p=L;while(p-next)p=p-next;p-next=q;q-next=NULL;)return(L);)四、算 法 设 计 题 1.设 计 在

24、 无 头 结 点 的 单 链 表 中 删 除 第 i 个 结 点 的 算 法。2.在 单 链 表 上 实 现 线 性 表 的 求 表 长 ListLength(L)运 算。3.设 计 将 带 表 头 的 链 表 逆 置 算 法。4.假 设 有 一 个 带 表 头 结 点 的 链 表，表 头 指 针 为 h e a d,每 个 结 点 含 三 个 域：data,next和 prior。其 中 data为 整 型 数 域，next和 prior均 为 指 针 域。现 在 所 有 结 点 已 经 由 next域 连 接 起 来，试 编 一 个 算 法，利 用 prior域(此 域 初 值 为 N U

25、 LL)把 所 有 结 点 按 照 其 值 从 小 到 大 的 顺 序 链 接 起 来。5.已 知 线 性 表 的 元 素 按 递 增 顺 序 排 列，并 以 带 头 结 点 的 单 链 表 作 存储 结 构。试 编 写 一 个 删 除 表 中 所 有 值 大 于 min且 小 于 m ax的 元 素(若 表 中 存 在 这 样 的 元 素)的 算 法。6.已 知 线 性 表 的 元 素 是 无 序 的，且 以 带 头 结 点 的 单 链 表 作 为 存 储 结 构。设 计 一 个 删 除 表 中 所 有 值 小 于 max但 大 于 m in的 元 素 的 算 法。7.假 定 用 一 个 单

26、 循 环 链 表 来 表 示 队 列(也 称 为 循 环 队 列)，该 队 列 只 设 一 个 队 尾 指 针，不 设 队 首 指 针，试 编 写 下 列 各 种 运 算 的 算 法：(1)向 循 环 链 队 列 插 入 一 个 元 素 值 为 x 的 结 点；(2)从 循 环 链 队 列 中 删 除 一 个 结 点。8.设 顺 序 表 L 是 一 个 递 减 有 序 表，试 写 一 算 法，将 x 插 入 其 后 仍 保 持 L 的 有 序 性。习 题 2参 考 答 案 一、单 项 选 择 题 1.A 2,A 3.D 4.C 5.D 6.A 7.B 8.B 9.C10.A 11.D 12.B

27、 13.C 14.B 15.C 16.C 17.B18.D 19.C20.A二、填 空 题 1.线 性 2.n-i+13.相 邻 4.前 移，前，后 5.物 理 存 储 位 置，链 域 的 指 针 值 6.前 趋，后 继 7.顺 序，链 接 8.一 定，不 一 定 9.线 性，任 何，栈 顶，队 尾，队 头 10.单 链 表，双 链 表，非 循 环 链 表，循 环 链 表 1 1.使 空 表 和 非 空 表 统 一；算 法 处 理 一 致 12.0(1),O(n)13.栈 满，栈 空，m,栈 底，两 个 栈 的 栈 顶 在 栈 空 间 的 某 一 位 置 相 遇 14.2、315.0(1)三、

28、简 答 题 1.头 指 针 是 指 向 链 表 中 第 一 个 结 点（即 表 头 结 点）的 指 针；在 表 头 结 点 之 前 附 设 的 结 点 称 为 头 结 点；表 头 结 点 为 链 表 中 存 储 线 性 表 中 第 一 个 数 据 元 素 的 结 点。若 链 表 中 附 设 头 结 点，则 不 管 线 性 表 是 否 为 空 表，头 指 针 均 不 为 空，否 则 表 示 空 表 的 链 表 的 头 指 针 为 空。2.线 性 表 具 有 两 种 存 储 结 构 即 顺 序 存 储 结 构 和 链 接 存 储 结 构。线 性 表 的 顺 序 存 储 结 构 可 以 直 接 存

29、取 数 据 元 素，方 便 灵 活、效 率 高，但 插 入、删 除 操 作 时 将 会 引 起 元 素 的 大 量 移 动，因 而 降 低 效 率：而 在 链 接 存 储 结 构 中 内 存 采 用 动 态 分 配，利 用 率 高，但 需 增 设 指 示 结 点 之 间 关 系 的 指 针 域，存 取 数 据 元 素 不 如 顺 序 存 储 方 便，但 结 点 的 插 入、删 除 操 作 较 简 单。3.应 选 用 链 接 存 储 结 构，因 为 链 式 存 储 结 构 是 用 一 组 任 意 的 存 储 单 元 依 次 存 储 线 性 表 中 的 各 元 素，这 里 存 储 单 元 可 以

30、是 连 续 的，也 可 以 是 不 连 续 的：这 种 存 储 结 构 对 于 元 素 的 删 除 或 插 入 运 算 是 不 需 要 移 动 元 素 的，只 需 修 改 指 针 即 可，所 以 很 容 易 实 现 表 的 容 量 的 扩 充。4.应 选 用 顺 序 存 储 结 构，因 为 每 个 数 据 元 素 的 存 储 位 置 和 线 性 表 的 起 始 位 置 相 差 一 个 和 数 据 元 素 在 线 性 表 中 的 序 号 成 正 比 的 常 数。因 此，只 要 确 定 了 其 起 始 位 置，线 性 表 中 的 任 一 个 数 据 元 素 都 可 随 机 存 取，因 此，线 性

31、表 的 顺 序 存 储 结 构 是 一 种 随 机 存 取 的 存 储 结 构，而 链 表 则 是 一 种 顺 序 存 取 的 存 储 结 构。5.设 尾 指 针 比 设 头 指 针 好。尾 指 针 是 指 向 终 端 结 点 的 指 针，用 它 来 表 示 单 循 环 链 表 可 以 使 得 查 找 链 表 的 开 始 结 点 和 终 端 结 点 都 很 方 便，设 一 带 头 结 点 的 单 循 环 链 表，其 尾 指 针 为 re a r,则 开 始 结 点 和 终 端 结 点 的 位 置 分 另 是 rear-next-next和 rear,查 找 时 间 都 是 0（1）。若 用 头

32、 指 针 来 表 示 该 链 表，则 查 找 终 端 结 点 的 时 间 为 0（n）。6.共 有 14种 可 能 的 出 栈 序 列，即 为：ABCD,ABDC,ACBD,ACDB,BACD,ADCB,BADC,BCAD,BCDA,BDCA,CBAD,CBDA,CDBA,DCBA7.在 队 列 的 顺 序 存 储 结 构 中，设 队 头 指 针 为 fro n t,队 尾 指 针 为 rear,队 列 的 容 量（即 存 储 的 空 间 大 小）为 maxnum。当 有 元 素 要 加 入 队 列（即 入 队）时，若 rear=maxnum,则 会 发 生 队 列 的 上 溢 现 象，此 时

33、就 不 能 将 该 元 素 加 入 队 列。对 于 队 列，还 有 一 种 飞 段 溢 出“现 象，队 列 中 尚 余 有 足 够 的 空 间，但 元 素 却 不 能 入 队，一 般 是 由 于 队 列 的 存 储 结 构 或 操 作 方 式 的 选 择 不 当 所 致，可 以 用 循 环 队 列 解 决。一 般 地，要 解 决 队 列 的 上 溢 现 象 可 有 以 下 几 种 方 法：(1)可 建 立 一 个 足 够 大 的 存 储 空 间 以 避 免 溢 出，但 这 样 做 往 往 会 造 成 空 间 使 用 率 低，浪 费 存 储 空 间。(2)要 避 免 出 现 F 段 溢 出”现

34、象 可 用 以 下 方 法 解 决：第 一 种：采 用 移 动 元 素 的 方 法。每 当 有 一 个 新 元 素 入 队，就 将 队 列 中 已 有 的 元 素 向 队 头 移 动 一 个 位 置，假 定 空 余 空 间 足 够。第 二 种：每 当 删 去 一 个 队 头 元 素，则 可 依 次 移 动 队 列 中 的 元 素 总 是 使 fron t指 针 指 向 队 列 中 的 第 一 个 位 置。第 三 种：采 用 循 环 队 列 方 式。将 队 头、队 尾 看 作 是 一 个 首 尾 相 接 的 循 环 队 列，即 用 循 环 数 组 实 现，此 时 队 首 仍 在 队 尾 之 前，

35、作 插 入 和 删 除 运 算 时 仍 遵 循“先 进 先 出”的 原 则。8.该 算 法 的 功 能 是：将 开 始 结 点 摘 下 链 接 到 终 端 结 点 之 后 成 为 新 的 终 端 结 点，而 原 来 的 第 二 个 结 点 成 为 新 的 开 始 结 点，返 回 新 链 表 的 头 指 针。四、算 法 设 计 题 1.算 法 思 想 为：(1)应 判 断 删 除 位 置 的 合 法 性，当 in-1时，不 允 许 进 行 删 除 操 作；(2)当 i=0时，删 除 第 一 个 结 点：(3)当 0 i n时，允 许 进 行 删 除 操 作，但 在 查 找 被 删 除 结 点 时

36、，须 用 指 针 记 住 该 结 点 的 前 趋 结 点。算 法 描 述 如 下：delete(LinkList*q,int i)在 无 头 结 点 的 单 链 表 中 删 除 第 i 个 结 点 LinkList*p,*s;int j;if(i0)printf(Cant delete);else if(i=0)s=q;q=q-next;free(s);else j=0;s=q;while(jnext;j+；)if(s=NULL)printf(Cantt delete);else p-next=s-next;free(s);2.由 于 在 单 链 表 中 只 给 出 一 个 头 指 针，所 以

37、 只 能 用 遍 历 的 方 法 来 数 单 链 表 中 的 结 点 个 数 了。算 法 描 述 如 下：int ListLength(LinkList*L)求 带 头 结 点 的 单 链 表 的 表 长 int len=O;ListList*p;P=L;while(p-next!=NULL)p=p-next;len+;return(len);3.设 单 循 环 链 表 的 头 指 针 为 h e a d,类 型 为 LinkList。逆 置 时 需 将 每 一 个 结 点 的 指 针 域 作 以 修 改，使 其 原 前 趋 结 点 成 为 后 继。如 要 更 改 q结 点 的 指 针 域 时

38、，设 s 指 向 其 原 前 趋 结 点，p 指 向 其 原 后 继 结 点，则 只 需 进 行 q-next=s;操 作 即 可，算 法 描 述 如 下：void invert(LinkList*head)逆 置 head指 针 所 指 向 的 单 循 环 链 表 linklist*p,*q,*s;q=head;p=head-next;while(p!=head)当 表 不 为 空 时，逐 个 结 点 逆 置 s=q;q=p;p=p-next;q-next=s;)p-next=q;)4.定 义 类 型 LinkList如 下：typedef struct node int data;stru

39、ct node*next,*prior;LinkList;此 题 可 采 用 插 入 排 序 的 方 法，设 p 指 向 待 插 入 的 结 点，用 q 搜 索 已 由 prior域 链 接 的 有 序 表 找 到 合 适 位 置 将 p 结 点 链 入。算 法 描 述 如 下：insert(LinkList*head)LinkList*p,*s,*q;p=head-next;p 指 向 待 插 入 的 结 点，初 始 时 指 向 第 一 个 结 点 while(p!=NULL)s=head;s 指 向 q 结 点 的 前 趋 结 点 q=head-prior;q指 向 由 prior域 构

40、成 的 链 表 中 待 比 较 的 结占 八、while(q!=NULL)&(p-dataq-data)查 找 插 入 结 点 p的 合 适 的 插 入 位 置 s=q;q=q-prior;)s-prior=p;p-prior=q;结 点 p 插 入 到 结 点 s 和 结 点 q 之 间 p=p-next;)5.算 法 描 述 如 下：delete(LinkList*head,int max,int min)linklist*p,*q;if(head!=NULL)q=head;p=head-next;while(p!=NULL)&(p-datanext;)while(p!=NULL)&(p-

41、datanext;q-next=p;)6.算 法 描 述 如 下：delete(LinkList*head,int max,int min)LinkList*p,*q;q=head;p=head-next;while(p!=NULL)if(p-datadata=max)q=p;p=p-next;else q-next=p-next;free(p);p=q-next;)7.本 题 是 对 一 个 循 环 链 队 列 做 插 入 和 删 除 运 算，假 设 不 需 要 保 留 被 删 结 点 的 值 和 不 需 要 回 收 结 点，算 法 描 述 如 下：(1)插 入(即 入 队)算 法：inse

42、rt(LinkList*rear,elemtype x)设 循 环 链 队 列 的 队 尾 指 针 为 rear,x为 待 插 入 的 元 素 LinkList*p;p=(LinkList*)malloc(sizeof(LinkList);if(rear=NULL)如 为 空 队，建 立 循 环 链 队 列 的 第 一 个 结 点 rear=p;rear-next=p;链 接 成 循 环 链 表)else 否 则 在 队 尾 插 入 p 结 点 p-next=rear-next;rear-next=p;rear=p;(2)删 除(即 出 队)算 法：delete(LinkList*rear)设

43、 循 环 链 队 列 的 队 尾 指 针 为 reari f(rear=NULL)空 队 printf(underflown);if(rear-next=rear)队 中 只 有 一 个 结 点 rear=NULL;elserear-next=rear-next-next;/rear-next 指 向 的 结 点 为 循 环 链 队 列 的 队 头 结 点)8.只 要 从 终 端 结 点 开 始 往 前 找 到 第 一 个 比 x 大(或 相 等)的 结 点 数 据,在 这 个 位 置 插 入 就 可 以 了。算 法 描 述 如 下：int lnsertDecreaseList(SqList*

44、L,elemtype x)int i;if(*L).len=maxlen)printf(uoverflow);return(O);)for(i=(*L).len;i0&(*L).elem i-1 x;i-)(*L).elem i=(*L).elem i-1;/比 较 并 移 动 元 素(*L).elem i=x;(*L).len+;return(1);习 题 3一、单 项 选 择 题 1.空 串 与 空 格 字 符 组 成 的 串 的 区 别 在 于（）oA.没 有 区 别 B.两 串 的 长 度 不 相 等 C.两 串 的 长 度 相 等 D.两 串 包 含 的 字 符 不 相 同 2.一

45、个 子 串 在 包 含 它 的 主 串 中 的 位 置 是 指（）oA.子 串 的 最 后 那 个 字 符 在 主 串 中 的 位 置 B.子 串 的 最 后 那 个 字 符 在 主 串 中 首 次 出 现 的 位 置C.子 串 的 第 一 个 字 符 在 主 串 中 的 位 置 D.子 串 的 第 一 个 字 符 在 主 串 中 首 次 出 现 的 位 置 3.下 面 的 说 法 中，只 有()是 正 确 的。A.字 符 串 的 长 度 是 指 串 中 包 含 的 字 母 的 个 数 B.字 符 串 的 长 度 是 指 串 中 包 含 的 不 同 字 符 的 个 数 C.若 T 包 含 在

46、S 中，则 T 一 定 是 S 的 一 个 子 串 D.一 个 字 符 串 不 能 说 是 其 自 身 的 一 个 子 串 4.两 个 字 符 串 相 等 的 条 件 是()oA.两 串 的 长 度 相 等 B.两 串 包 含 的 字 符 相 同 C.两 串 的 长 度 相 等，并 且 两 串 包 含 的 字 符 相 同 D.两 串 的 长 度 相 等，并 且 对 应 位 置 上 的 字 符 相 同 5.若 SUBSTR(S,i,k)表 示 求 S 中 从 第 i 个 字 符 开 始 的 连 续 k 个 字 符 组 成 的 子 串 的 操 作，则 对 于 S=Beijing&Nanjing”，

47、SUBSTR(S,4,5)=()。A.ijing”B.“jing&”C.”ingNa D.“ing&N”6.若 INDEX(S,T)标 求 T在 S 中 的 位 置 的 操 作，则 对 于$=组 训 访 9&Nanjing，T=jing，INDEX(S,T)=()。A.2 B.3 C.4D.57.若 REPLACE(S,S1,S 2)表 示 用 字 符 串 S2替 换 字 符 串 S 中 的 子 串 S1 的 操 作，则 对 于 S=Beijing&Nanjing，S1=Beijing”,S2=Shanghai，REPLACE(S,S1,S 2)=()。A.Nanjing&Shanghai”B

48、.“Nanjing&Nanjing”C.ShanghaiNanjing D.Shanghai&Nanjing”8.在 长 度 为 n 的 字 符 串 S 的 第 i 个 位 置 插 入 另 外 一 个 字 符 串，i 的 合 法 值 应 该 是()。A.i0 B.inC.1in D.1in+19.字 符 串 采 用 结 点 大 小 为 1的 链 表 作 为 其 存 储 结 构，是 指()oA.链 表 的 长 度 为 1B.链 表 中 只 存 放 1个 字 符 C.链 表 的 每 个 链 结 点 的 数 据 域 中 不 仅 只 存 放 了 一 个 字 符 D.链 表 的 每 个 链 结 点 的

49、数 据 域 中 只 存 放 了 一 个 字 符 二、填 空 题 1.计 算 机 软 件 系 统 中，有 两 种 处 理 字 符 串 长 度 的 方 法：一 种 是,第 二 种 是 _ O2.两 个 字 符 串 相 等 的 充 要 条 件 是 _和 3.设 字 符 串 S1=ABCDEF，S2=PQRS”，则 运 算 S=CONCAT(SUB(S1,2,LEN(S2),SUB(S1,LEN(S2),2)痔 勺 串 值 为 o4.串 是 指 o5.空 串 是 指,空 格 串 是 指 三、算 法 设 计 题 1.设 有 一 个 长 度 为 s 的 字 符 串，其 字 符 顺 序 存 放 在 一 个

50、一 维 数 组 的 第 1至 第 s 个 单 元 中（每 个 单 元 存 放 一 个 字 符）。现 要 求 从 此 串 的 第 m个 字 符 以 后 删 除 长 度 为 t 的 子 串，ms,t（s-m）,并 将 删 除 后 的 结 果 复 制 在 该 数 组 的 第 s 单 元 以 后 的 单 元 中，试 设 计 此 删 除 算 法。2.设 s 和 t 是 表 示 成 单 链 表 的 两 个 串，试 编 写 一 个 找 出 s 中 第 1个 不 在 t 中 出 现 的 字 符（假 定 每 个 结 点 只 存 放 1个 字 符）的 算 法。习 题 3参 考 答 案 一、单 项 选 择 题 1.