数据结构习题集.pdf

第 一 章 概 论.2第 二 章 线 性 表.8第 三 章 栈 和 队 列.16第 四 章 串.25第 五 章 数 组 和 广 义 表.31第 六 章 树.38第 七 章 图.49第 八 章 查 找.61第 九 章 排 序.72想 据 错 构 习 题 条 第 一 章 概 论 一、选 择 题 1.算 法 指 的 是 A.计 算 机 程 序 C.排 序 方 法 案 B.解 决 问 题 的 计 算 方 法 D.解 决 问 题 步 骤 的 有 限 序 列 2.平 均 时 间 复 杂 度 是 指 所 有 可 能 的 输 入 实 例 均 以 A.等 概 率 出 现 的 情 况 下，算 法 的 期 望 运 行 时 间 B.不 等 概 率 出 现 的 情 况 下，算 法 的 期 望 运 行 时 间 C.最 坏 情 况 下，算 法 的 期 望 运 行 时 间 D.最 好 情 况 下，算 法 的 期 望 运 行 时 间 3.通 过 建 立 结 点 的 关 键 字 与 存 储 地 址 之 间 的 映 像 关 系 所 实 现 的 存 储 方 法 是 A.顺 序 存 储 B.链 式 存 储 C.索 引 顺 序 存 储 D.散 列 存 储 方 法 4.数 据 的 运 算 是 数 据 结 构 不 可 分 割 的 一 个 方 面，根 据 运 算 集 合 及 运 算 的 性 质 不 同 A.可 以 形 成 不 同 的 数 据 结 构 C.逻 辑 结 构 将 发 生 变 化 5.数 据 的 基 本 单 位 是 A.数 据 对 象 C.数 据 项 6.线 性 结 构 是 一 种（）A 一 对 一 的 关 系 B.不 会 导 致 不 同 的 数 据 结 构 D.逻 辑 结 构、存 储 结 构 都 将 会 发 生 变 化 B.数 据 元 素 D.数 据 类 型 B 一 对 多 的 关 系 2C 多 对 一 的 关 系 D 多 对 多 的 关 系 7.链 式 存 储 结 构 存 储 元 素 的 存 储 单 元 的 地 址（）A 必 须 是 连 续 的 B 必 须 是 不 连 续 的 C 可 以 连 续 也 可 以 不 连 续 D 与 顺 序 存 储 结 构 相 同 8.评 价 一 个 算 法 优 劣 除 了 要 考 虑 正 确 性、A 时 间 效 益 和 空 间 效 率 C 时 间 效 益 9.设 计 算 法 时.，应 辟 免 使 算 法 的 时 间 复 杂 度 为（A 常 量 阶 C 二 次 阶 1 0.程 序 段 如 下 for（i=1；in；i+）for（j=1；ji；j+）y+；该 算 法 的 时 间 复 杂 度 为（）A 0（1）C 0（n1 2）*4 51.数 据 的 逻 辑 结 构 与 数 据 元 素 本 身 的 和 形 式 无 关。2.数 据 结 构 包 含 三 方 面 的 内 容，分 别 是、o3.数 据 元 素 是 数 据 的 基 本 单 位，数 据 项 是 数 据 的。4.算 法 的 时 间 复 杂 度 不 仅 与 问 题 的 规 模 n有 关，还 与 有 关。5.顺 序 存 储 结 构 中 逻 辑 上 相 邻 的 元 素 在 物 理 位 置 上。二、填 空 题 易 读 性 和 健 壮 性 外，还 应 考 虑（）B 空 间 效 率 D 软 硬 件 环 境）B 线 性 阶 D 指 数 阶 B 0(n)D 0(lgn)想 据 错 构 习 题 条 6.数 据 的 逻 辑 结 构 是 从 逻 辑 关 系 上 描 述 数 据，它 与 数 据 的 无 关，是 独 立 于 计 算 机 的。7.最 坏 情 况 下 算 法 的 时 间 复 杂 度 是 算 法 在 任 何 输 入 实 例 上 运 行 时 间 的.8.算 法 具 有 的 五 个 重 要 特 性 是 有 效 性、输 入 和 输 出。9.数 据 的 存 储 结 构 的 基 本 存 储 方 法 是 顺 序 存 贮、链 式 存 储、和.1 0.设 有 三 个 函 数 f,g,h分 别 是 f(n)=lOOrf+nlOOO g(n)=25nf+5000n2 h(n)=w，+5000nlgn请 判 断 下 列 关 系 式 成 立 的 是 O(1)f(n)=0(g(n)(2)g(n)=O(f(n)(3)h(n)=O()(4)h(n)=0(nlgn)三、阅 读 程 序 题 1.估 计 下 列 程 序 段 的 时 间 复 杂 度。temp=Ii=jj=temp2.分 析 下 列 程 序 段 的 间 复 杂 度。x=0；y=0；for（k=l；k=n；k+）x=x+l；for（i=l；i=n；i+）for（j=l；j=n；j+）y+；43.阅 读 程 序 题，估 计 时 间 复 杂 度 x=0；for(i=l,j=l；i+j=n；i+,j+)x+；4.阅 读 程 序 题，估 计 时 间 复 杂 度 x=l；for(i=l；i=n；i+)for(j=l；j=i；j+)for(k=l,k=j；k+)x+；习 题 答 案 一、选 择 题 1.D 2.A 3.D 4.A 5.B 6.A 7.C 8.A 9.D 10.C二、填 空 题 1.内 容 2.逻 辑 结 构、存 储 结 构 和 定 义 在 其 上 的 运 算。3.最 小 单 位。4.输 入 实 例 的 初 始 状 态。5.也 相 邻 6.存 储 7.上 界 8.确 定 性、有 穷 性 9.索 引 存 储、散 列 存 储 1 0.(1)(2)(3)成 立，(4)不 成 立。三、阅 读 程 序 题 1.【答 案】0(1)【分 析】算 法 的 执 行 时 间 是 一 个 常 数，不 会 随 着 问 题 规 模 的 增 大 而 变 化，不 论 语 句 多 少 算 法 的 时 间 复 杂 度 均 为 常 数 阶。2.【答 案】0(r)【分 析】一 般 情 况 下，对 步 进 循 环 语 句 只 需 考 虑 循 环 体 中 语 句 的 执 行 次 数，而 忽 略 循 环 控 制 语 句 等 成 分。因 此，算 法 中 y+;语 句 的 频 度 为 胡，所 以 该 序 段 的 时 间 复 杂 度 是 平 方 阶。0(乃想 据 错 构 习 题 条 3.【答 案】循 环 体 x+；语 句 的 执 行 频 度 n/2,算 法 的 时 间 复 杂 度 T(n)=O(f(n)=O(n)4.【答 案】循 环 体 x+；语 句 的 执 行 频 度 f f j=(i+l)/2=f(n)=iJ=i=i En(n+1)(2n+l)/6+n(n+l)/2/2算 法 的 时 间 复 杂 度 T(n)=O(b6想 据 错 构 习 题 条 第 二 章 线 性 表 一、选 择 题 1.单 链 表 表 示 线 性 表 的 优 点 是（）A.便 于 随 机 存 取 B.节 省 存 储 空 间 C.数 据 元 素 的 逻 辑 顺 序 和 物 理 顺 序 相 同 D.便 于 插 入 和 删 除 2.在 长 度 为 n的 顺 序 表 中 插 入 元 素 平 均 移 动 元 素 的 个 数 是（）A.n/2 B.（n+l）/2C.n D.（n-l）/23.线 性 表 采 用 顺 序 存 储 结 构，设 存 储 空 间 的 基 地 址 是 b,每 个 元 素 占 k个 存 储 单 元，第 i个 元 素 的 存 储 位 置 是（）A.b+iC.b+（iT）*k4.在 链 式 存 储 结 构 中 引 入 头 结 点 的 作 用 是（）A.对 空 表 和 非 空 表 可 按 同 一 模 式 处 理 C.便 于 随 机 访 问 5.顺 序 存 储 结 构 的 优 点 是（）A.便 于 插 入 C.便 于 随 机 访 问 6.在 链 式 存 储 结 构 中，删 除 工 作 指 针 P所 指 结 点,结 构（）A.单 循 环 链 表 或 双 循 环 链 表 C.单 链 循 环 链 表 B.b+i*kD.b+i-1B.便 于 插 入 D.便 于 删 除 B.便 于 删 除 D.存 储 密 度 低 要 求 时 间 复 杂 度 为 0（1）,选 择 哪 种 存 储 B.双 向 链 表 D.单 链 表 87.两 个 循 环 单 链 表，只 有 尾 指 针 指 向 表 末 结 点，表 长 分 别 为 n和 叫 将 两 个 表 依 此 链 接 为 个 表 的 时 间 复 杂 度 是（）A.0（1）B.0（n+m）C.0（n）D.0（m）8.已 知 带 头 结 点 的 循 环 单 链 表 的 头 指 针 为 head,当 head-next=head时，（）A.是 非 空 表 C.是 空 表 C.上 溢 出 错 D.表 中 有 一 个 表 结 点 9.在 长 度 为 n的 顺 序 表 中 删 除 第 i个 元 素，须 移 动 元 素 的 个 数 是（）A.i B.nC.n-i+1 D.n-i10.已 知 p指 向 单 链 表 中 的 某 个 结 点，执 行 语 句：q=p-next;p-data=q-data;p-next=q-next;free（q）;的 功 能 是（）A.删 除 p所 指 结 点 B.删 除 p所 指 结 点 的 后 继 结 点 C.删 除 p所 指 结 点 的 前 趋 结 点 D.p所 指 结 点 与 后 继 结 点 值 互 换 11.线 性 表 采 用 链 式 存 储 时,结 点 的 存 储 地 址（）A.必 须 是 不 连 续 的 B.连 续 与 否 均 可 C.必 须 是 连 续 的 C.和 头 结 点 的 存 储 地 址 连 续 12.在 长 度 为 n的 顺 序 表 的 第 i（lnext;B.p-next=p-next-next;数 据 错 相 动 敢 集 C.p-next=p;D.p=p-next-next;15.在 头 指 针 为 head且 表 长 大 于 1的 单 循 环 链 表 中，指 针 p指 向 表 中 某 个 结 点，若 p-next-next=hcad,则（）A.p指 向 头 结 点 B.p指 向 尾 结 点 C.*p的 直 接 后 继 是 头 结 点 D.*P的 直 接 后 继 是 尾 结 点 二、填 空 题 1.在 线 性 表 的 顺 序 存 储 结 构 上，逻 辑 上 相 邻 的 元 素 在 物 理 位 置 上。2.顺 序 表 是 一 种,存 取 速 度 快，但 不 便 于 进 行 和 操 作。3.在 n个 元 素 的 顺 序 表 中 进 行 插 入 操 作，需 平 均 移 动 个 结 点，。具 体 的 移 动 次 数 取 决 于 和 4.删 除 p所 指 结 点，在 双 向 链 表 中 的 时 间 复 杂 度 为,在 单 链 表 中 的 时 间 复 杂 度 为 5.在 单 循 环 链 表 中 设 置 尾 指 针，其 优 点 是 便 于 在 和 操 作，其 时 间 复 杂 度 均 为。口 6.在 如 图 所 示 的 傩 表 中，若 在 指 针 p所 指 的 结 点 之 后 插 入 数 据 域 值 为 a结 点，则 可 用 卜.列 两 个 语 句 实 现 该 操 作，它 们 依 次 是 和。7.在 循 环 链 表 中，可 根 据 某 一 结 点 的 地 址 遍 历 整 个 链 表，在 单 链 表 中，需 要 知 道,才 能 遍 历。8.结 点 数 据 本 身 所 占 的 存 储 量 和 整 个 结 点 结 构 所 占 的 存 储 量 之 比 称 为 存 储 密 度，顺 序 表 存 储 密 度 为,链 表 的 存 储 密 度 o9.在 线 性 表 中 频 繁 进 行 插 入 和 删 除，应 选 择 存 储 结 构，否 则 应 选 择。10.求 一 个 单 链 表 的 长 度 的 时 间 复 杂 度 为.10三、阅 读 程 序 题 1.阅 读 程 序 指 出 程 序 功 能 void trans(linklist*la,linklist*lb,int a,int n)int k;linknode*p;*la=(linknode*)malloc(sizeof(linknode);(*la)-next=NULL;*lb=(linknode*)malloc(sizeof(linknode);(*lb)-next=NULL;k=0;while(kdata=ak;if(k%2)p-next=(*la)-next;(*la)-next=p;else p-next=(*lb)-next;(*lb)-ncxt=p;k+;2.阅 读 程 序 指 出 程 序 功 能 void deInode(linknode*p)/p指 向 带 头 结 点 循 环 链 表 中 某 结 点 1 inknode*q;q=p-next;while(q-next!=p)q=q-next;q-data=p-data;数 据 错 相 动 敢 集 q-next=p-next;free(p);3.阅 读 程 序 指 出 程 序 功 能,并 指 出 循 环 体 执 行 次 数。void delseqlist(seqlist*S,int i,int k)int j,n=0;for(j=i+k;j 1en;j+)*S-dataj-k=(*S)-dataj;n+;(*S)-len=(*S)-len-n;4.下 述 算 法 的 功 能 是 什 么？Linklist demo(Linklist L)L是 无 头 结 点 的 单 链 表 Listnode*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;/demo四、算 法 设 计 题 1.设 有 个 带 头 结 点 的 单 链 表，试 设 计 统 计 链 表 中 值 为 k的 结 点 个 数 的 算 法。122.设 线 性 表 采 用 顺 序 存 储 结 构，将 表 分 拆 成 两 个 线 性 表，使 小 于 x的 元 素 作 为 一 个 表，使 其 它 元 素 作 为 另 一 个 表。3.数 序 列(元 素 数 大 于 2)以 单 链 表 存 储，试 遍 写 算 法，判 断 序 列 是 否 为 等 差 数 列。4.是 分 别 用 顺 序 表 和 单 链 表 作 为 存 储 结 构，实 现 将 线 性 表(aO,al,an-1)就 地 逆 置 的 操 作，所 谓“就 地”是 指 辅 助 空 间 应 为 0(1).5.设 顺 序 表 L是 一 个 递 增 有 序 表，试 写 一 算 法 将 x插 入 L中，并 使 L仍 是 一 个 有 序 表。6.设 单 链 表 L是 一 个 递 减 有 序 表，试 写 一 算 法 将 x插 入 L中，并 使 L仍 保 持 有 序 性。7.已 知 L1和 L2分 别 指 向 的 两 个 单 链 表 的 头 结 点，且 已 知 其 长 度 分 别 为 m和 n。试 写 一 算 法 将 这 两 个 单 链 表 连 接 在 一 起，并 分 析 你 的 算 法 的 时 间 复 杂 度。8.设 A和 B是 两 个 单 链 表，其 表 中 元 素 递 增 有 序。试 写 一 个 算 法 将 A和 B归 并 成 一 个 按 元 素 值 递 减 有 序 的 单 链 表，并 要 求 辅 助 空 间 为 0(1),请 分 析 算 法 的 时 间 复 杂 度。9.已 知 单 链 表 L是 一 个 递 增 有 序 表，试 写 一 高 效 算 法，删 除 表 中 值 大 于 min且 小 于 的 max结 点(若 表 中 有 这 样 的 结 点)，同 时 释 放 被 删 除 结 点 的 空 间，这 里 max和 nin是 两 个 给 定 的 参 数。请 分 析 你 的 算 法 的 时 间 复 杂 度。10.写 一 算 法 将 单 链 表 中 值 重 复 的 结 点 删 除，是 所 得 的 结 果 表 中 各 结 点 位 均 不 相 同。11.假 设 在 长 度 大 于 1的 单 循 环 链 表 中，既 无 头 结 点 也 无 头 指 针。s为 指 向 链 表 中 某 个 结 点 的 指 针，是 编 写 算 法 删 除 结 点*s的 直 接 前 趋 结 点。习 题 答 案 一、选 择 题 1.D 2.A 3.C 4.A 5.C 6.B 7.A 8.C 9.D 10.A 11.B 12.A 13.C14.B 15.D二、填 空 题 1.也 相 邻；2.随 机 存 取 结 构、插 入、删 除；3.n/2,表 长，插 入 位 置；4.0(1),0(n)；5.表 头，表 尾，0(1)；6.S-next=p-next;p-next=s；7.头 指 针；8.1,1；9.链 式，顺 序 存 储 结 构；10.0(n)；三、阅 读 程 序 题 1.【答 案】将 数 组 a 中 元 素 按 奇、偶 分 类，分 别 建 成 单 链 表 la和 1b。2.【答 案】删 除 循 环 链 表 中 p所 指 结 点 的 前 趋 结 点。3.【答 案】在 顺 序 表 上 删 除 从 第 i个 元 素 起 连 续 k个 元 素。想 据 错 构 习 题 条 4.【答 案】当 单 链 表 为 空 表 或 只 有 一 个 结 点 时，其 结 构 不 变，若 多 于 一 个 结 点 时，将 第 一 个 结 点 移 至 表 末 作 为 最 后 一 个 结 点，而 原 来 第 二 个 结 点 作 为 链 表 的 第 一 个 结 点。14想 据 错 构 习 题 条 第 三 章 栈 和 队 列 一、选 择 题 1.若 一 个 栈 的 输 入 序 列 是 1,2,3,，n,输 出 序 列 的 第 一 个 元 素 是 n,则 第 i个 输 出 的 元 素 是（）6.长 度 为 n的 链 队 列 用 单 循 环 链 表 表 示 设 置 头 指 针，入 队 的 时 间 复 杂 度 是（）A.n-i B.n-i+1C.i D.i-12.栈 具 有（）A.先 进 先 出 的 特 点 B.后 进 先 出 的 特 点 C.进 出 次 序 是 随 机 的 D.操 作 与 线 性 表 相 同 3.入 栈 序 列 为 a,b,c,d,不 可 能 得 到 的 出 栈 序（)A.abed B.debaC.edba D.adbc4.支 持 递 归 算 法 的 数 据 结 构 是（）A.队 列 B.线 性 表 D.栈 D.树 5.容 量 为 maxsize的 循 环 队 列 Q队 满 的 判 定 条 件 是（)A.Q.rear=(Q.front+l)%maxsize B.Q.front=Q.rearC.Q.front=(Q.rear+l)%maxsize D.Q.front=Q.rear+1A.0(1)C.0(n2)B.0(n)D.0(lgn)167.设 有 一 顺 序 栈 S,元 素 1,2,3,4,5,6一 次 入 栈，出 栈 序 列 为：2,3,4,6,5,1,则 栈 的 容 量 至 少 应 该 是（）A.2 B.3C.5 D.68.向 一 个 栈 顶 指 针 为 top的 链 栈 插 入 s所 指 结 点 的 操 作 是（）A.s-next=top;top=s;C.s-next=top-next;top=s;9.容 量 为 maxsize的 循 环 队 列 Q的 长 度 是（）A.（Q.rear-Q.front+maxsize）&maxzi seC.Q.rear-Q.front+maxsize10.由 两 个 栈 共 享 一 个 向 量 空 间 的 好 处 是（A.减 少 存 取 时 间，降 低 下 溢 发 生 的 机 率 C.减 少 存 取 时 间，降 低 上 溢 发 生 的 机 率 B.top=s-next;D.top-next=s;top=s;B.Q.rear-Q.frontD.Q.front-Q.rear）B.节 省 存 储 空 间，降 低 上 溢 发 生 的 机 率 D.节 省 存 储 空 间，降 低 下 溢 发 生 的 机 率 二、填 空 题 1.队 列 的 逻 辑 特 点 是,栈 的 逻 辑 特 点 是。2.栈 结 构 中，允 许 插 入 和 删 除 的 一 端 称 为，不 允 许 进 行 插 入 和 删 除 的 一 端 称 为。3.循 环 队 列 为 空 的 判 定 条 件 是 o4.设 长 度 为 n的 链 队 列 用 单 循 环 链 表 表 示，若 只 设 尾 指 针，则 入 队 操 作 的 时 间 复 杂 度 是，出 队 操 作 的 时 间 复 杂 度 是。若 只 设 头 指 针，则 入 队 操 作 的 时 间 复 杂 度 是，出 队 操 作 的 时 间 复 杂 度 是。5.栈 和 队 列 是 操 作 受 限 制 的 o6.子 程 序 嵌 套 调 用 和 递 归 调 用 依 靠 实 现。7.在 循 环 队 列 Q中，设 置 时 队 头 指 针 Q.front指 向 队 头 元 素 和 队 列 长 度 Q.len,则 入 队 操 作 的 语 句 序 列 是；o想 据 错 构 习 题 条 8.两 个 栈 共 享 一 个 向 量 空 间，这 样 做 可 节 省,避 免 o9.出 栈 操 作 的 时 间 复 杂 度 是,入 栈 操 作 的 时 间 复 杂 度 是。10.顺 序 栈 中，出 栈 操 作 的 语 句 序 列 是；。11.栈 顶 的 位 置 是 随 着 操 作 而 变 化 12.假 设 以 S和 X分 别 表 示 进 栈 和 退 栈 操 作，则 对 输 入 序 列 a,b,c,d,e进 行 系 列 栈 操 作 SSXSXSSXXX之 后，得 到 的 输 出 序 列 为 _。13.如 图 两 个 栈 共 享 一 个 向 量 空 间，topi和 top分 别 为 指 向 两 个 栈 顶 元 素 的 指 针，则“栈 满”的 判 定 条 件 是。三、阅 读 程 序 题 1.阅 读 程 序 指 出 程 序 功 能 void stackexpl(linklist la)(linknode p,q;Seqstack S;Initstack(&S);p=la-next;while(p)push(&S,p-data);p=p-next;p=la-next;while(!stackempty(S)p-data=pop(&S);18p=p-next;2.阅 读 程 序 指 出 程 序 功 能 void stackexp2(Seqstack*S)datatype x;Cirqueue Q;Initqueue(&Q);while(!Stackempty(S)x=pop(&S);Enqueue(&Q,x);)while(!Queueempty(S)x=Delqueue(&Q);push(&S,x);)3.阅 读 程 序 void exmple3(Seqstack*S,linklist*La,datatype x)linknode*p;datatype t;Seqstack SI;*La=NULL;Initstack(&Sl);while(!Stackempty(S)t=Pop(&S);if(tdata=t;p-next=la;la=p;)数 据 错 相 动 敢 集 while(!Stackempty(S1)Push(&S,Pop(&Sl);指 出 程 序 功 能;若 栈 S初 始 状 态 为：(3,18,23,9,2 0),右 端 为 栈 顶，x为 18,算 法 运 行 后，La和 S的 状 态。4.如 图 所 示，利 用 同 一 循 环 向 量 空 间 实 现 两 个 队 列，其 类 型 Queue2定 义 如 下：typedef struct DataType dataMaxSize;int front2,length2;Queue2;对 于 i=0或 1,front和 length分 别 为 第 i个 队 列 的 头 指 针 和 长 度 域。请 在 空 缺 处 填 入 合 适 的 内 容，实 现 第 i个 循 环 队 列 的 入 队 操 作。int EnQueue(Queue2*Q,int i,DataType x)若 第 i个 队 列 不 满，则 元 素 x入 队 列，并 返 回 1,否 则 返 回 0if(il)return 0;if(1)return 0;Q-data(2)=x;Q-length(3)+;return 1;)5.设 栈 S=(1,2,3,4,5,6,7),其 中 7为 栈 顶 元 素。请 写 出 调 用 algo(&s)后 栈 S的 状 态。void algo(Stack*S)int i=0;20Queue Q;Stack T;Ini tQueue(&Q);InitStack(&T);while QStackEmpty(S)(if(i=!i)!=O)Push(&T,Pop(&S);else EnQueue(&Q,Pop(&S);)while(!QueueEmpty(Q)Push(&S,DeQueue(&Q);while(!StackEmpty(T)Push(&S,Pop(&T)；四、算 法 设 计 题 1.利 用 栈 实 现 队 列 逆 置。2.两 个 栈 共 享 一 个 向 量 栈 底 设 在 两 端，已 知 个 栈 顶 指 针 和 另 一 栈 的 元 素 数。写 出 入 栈 操 作 算 法；写 出 出 栈 操 作 算 法。3.回 文 是 指 正 读 和 反 读 均 相 同 的 字 符 序 列，例 如“abba”和“abdba”均 是 回 文，但“good”不 是 回 文。试 写 一 个 算 法 判 定 给 定 的 字 符 向 量 是 否 为 回 文(提 示：将 一 半 字 符 入 栈)。4.利 用 栈 的 基 本 操 作，写 一 个 返 回 栈 S中 结 点 个 数 的 算 法 int stacksize(Seqstack S),并 说 明 S为 何 不 用 作 为 指 针 参 数？想 据 错 构 习 题 条 5.设 计 算 法 判 断 一 个 算 术 表 达 式 的 圆 括 号 是 否 正 确 配 对。(提 示：凡 遇(就 进 栈，遇)就 退 掉 栈 顶 的(，表 达 式 扫 描 完 毕，栈 应 为 空)6.一 个 双 向 栈 S是 在 同 一 响 量 空 间 里 实 现 的 两 个 栈，它 们 的 栈 底 分 别 设 在 向 量 空 间 的 两 端。试 为 此 双 向 栈 设 计 初 始 化 Initstack(S)、入 栈 push(S,x,i)和 出 栈 pop(i)算 法，其 中，i为。或 1用 于 指 示 栈 号。7.Ackerman函 数 的 定 义 如 下:n+1AKM(m,n)=当 m=0 时 AKM(m-l,1)当 mWO,n=0 时 AKM(m-l,AKM(m,n-1)当 mWO,n W O 时 请 写 出 递 归 算 法。8.用 第 二 种 方 法，既 少 用 一 个 元 素 空 间 的 方 法 来 区 别 循 环 队 列 的 空 和 满，试 为 其 设 计 置 队 空、判 断 队 空、判 断 队 满、出 队、入 队、取 队 头 元 素 等 六 个 基 本 操 作 的 算 法。9.假 设 以 带 头 结 点 的 循 环 链 表 表 示 队 列，并 且 只 是 一 个 指 针 指 向 队 尾 元 素 结 点，试 编 写 相 应 的 置 队 空、判 断 队 空、出 队 和 入 队 等 算 法。10.对 于 循 环 向 量 中 的 循 环 队 列，写 出 求 队 列 长 度 的 公 式。11.假 设 循 环 队 列 中 只 设 rear和 quelen来 分 别 指 示 队 尾 元 素 的 位 置 和 队 中 元 素 的 个 数，试 给 出 循 环 队 列 的 队 满 条 件，并 写 出 相 应 的 入 队 和 出 队 算 法，要 求 出 队 时 需 返 回 队 头 元 素。习 题 答 案 一、选 择 题 1.B 2.B 3.D 4.D二、填 空 题 1.先 进 先 出，先 进 后 出；4.0(1),0(1),0(n),0(1)；5.C 6.B 7.2.栈 顶，栈 底；5.线 性 表；7.Q.data(Q.frot+Q.len)%maxsize,0.len+：B 8.A 9.A 10.B3.Q.Front=Q.rear；6.栈；8.存 储 空 间，溢 出；9.O(1),0(1)；10.Y=S.dataS.top,S.top；11.入 栈 和 出 栈。2212.BCEDA 13.topl+l=top2或 topl=top2T三、阅 读 程 序 题 1.【答 案】利 用 工 作 栈 S将 链 表 逆 置。2.【答 案】利 用 队 列 Q将 栈 S逆 置。3.【答 案】(1)将 栈 S中 元 素 分 为 两 类，大 于 等 于 x的 元 素 构 成 链 表 La,小 于 x的 元 素 仍 保 留 在 栈 S之 中。(1)栈 S中 元 素 从 栈 顶 到 栈 底 依 次 为：3,9；链 表 la为：la-20 _：-23 _ 18.4.【答 案】(1)Q-front(i+l)%2=(Q-fronti+Q-lengthi)%MaxSize(2)(Q-fronti+Q-1engthi)%MaxSize(3)i5.【答 案】算 法 结 束 后 S中 值 为：(6,4,2,1,3,5,7).数 据 错 相 动 敢 集 24第 四 章 串 一、选 择 题 1.下 列 有 关 字 符 串 的 描 述，正 确 的 是（）A.字 符 串 是 0个 或 多 个 字 符 构 成 的 有 限 序 列；B.字 符 串 是 0个 或 多 个 字 母 不 同 的 有 限 序 列；C.字 符 串 中 最 少 要 有 一 个 子 符；D.字 符 串 中 不 能 有 空 格 字 符。2.字 符 串 S=string中，包 含 的 子 串 的 个 数 是（）A.20 B.21 C.22 D.233.目 标 串 为 丁=this is a string,模 式 串 P=string,进 行 模 式 匹 配，有 效 位 移 是（）（起 始 位 置 为 0）。A.9 B.10 C.11 D.124.已 知 串 S=string,T=this,执 行 运 算 strlen（strcopy（S,T）的 结 果 是（）A.4 B.6 C.10 D.25.目 标 串 为 丁=this is a string,模 式 串 P=string,进 行 模 式 匹 配,所 有 的 无 效 位 移 数 是（）A.6 B.10 C.16 D.116.下 列 命 题 正 确 的 是（）A.空 串 就 是 空 白 串；BC.空 串 是 长 度 为 0的 字 符 串 D.7.若 字 符 串 采 用 链 式 存 储，每 个 字 符 占 用 一 个 字 节,的 存 储 密 度 为（）.空 串 不 是 串；串 相 等 指 的 是 长 度 相 等 每 个 指 针 在 占 用 四 个 字 节，则 该 字 符 串数 据 错 相 动 敢 集 8.数 当 目 标 串 的 长 度 为 n,模 式 串 的 长 度 为 m时，朴 素 的 模 式 匹 配 算 法 最 坏 情 况 下 字 符 的 比 较 次（）A.n(n-m+l)*m D.m9.当 目,A.B.n*m C.模 式 串 的 长 度 为 m时，朴 素 的 模 式 匹 配 算 法 最 好 情 况 下 字 符 的 比 较 次 数（）n B.m C.n+m D n-m10.字 符 串 是 一 种 特 殊 的 线 性 表，它 与 一 般 线 性 表 的 区 别 是（）A.字 符 串 是 一 种 线 性 结 构;B.字 符 串 可 以 进 行 复 制 操 作;C.字 符 串 由 字 符 构 成 并 且 通 常 作 为 整 体 参 与 操 作;D.字 符 串 可 以 顺 序 存 储 也 可 以 链 式 存 储。11.下 所 述 中 正 确 的 是（）12.A.串 是 一 种 特 殊 的 线 性 表 C.串 中 元 素 只 能 是 字 母 B.D.若 目 标 串 的 长 度 为 n,模 式 串 的 长 度 为 n/3,串 的 长 度 必 须 大 于 零 空 申 就 是 空 白 串 则 执 行 模 式 匹 配 算 法 时，在 最 坏 情 况 下 的 时 间 复 杂 度 是（)13.A.O(n/3)B.O(n)C.O(n2)D.0(n3)设 有 两 个 串 T和 P,求 P在 T中 首 次 出 现 的 位 置 的 串 运 算 称 作（A.联 接 B.求 子 串 C.字 符 定 位 D.子 串 定 位)14.为 查 找 某 一 特 定 单 词 在 文 本 中 出 现 的 位 置，可 应 用 的 串 运 算 是)A.插 入 B.删 除 C.串 联 接 D.子 串 定 位 15.已 知 函 数 Sub（s,i,j）的 功 能 是 返 回 串 s中 从 第 i个 字 符 起 长 度 为 j的 子 串,函 数 Scopy（s,t）的 功 能 为 复 制 串 t到 s。若 字 符 串 S=SCIENCESTUDY，则 调 用 函 数 Scopy（P,Sub（S,1,7）后 得 到（）A.P=，/SCIENCE，/B.P=STUDY”C.SSCIENCE”D.S=STUDY二、填 空 题 1.空 串 的 长 度 为,空 格 串（空 白 串）的 长 度 为 262,子 串 的 定 位 运 算 又 称 为，通 常 把 主 串 又 称 为 子 串 又 称 为 3.成 功 匹 配 的 起 始 位 置 称 为，匹 配 失 败 的 起 始 位 置 称 为。4.设 目 标 串 为 T=abccdadeef,模 式 串 P=ade,则 第 _趟 匹 配 成 功。5.已 知 串 T=abccdadeef,P=abccyde,函 数 strcmp(T,P)的 运 算 结 果 是 6.串 朴 素 的 模 式 匹 配 算 法 在 顺 序 串 和 链 串 上 运 行，时 间 复 杂 度。7.已 知 串 T=abccdadeef,T中 包 含 以 b打 头 的 子 串 有 个。8.通 常 在 程 序 设 计 中，串 分 为 和。9.按 存 储 结 构 通 常 分 为 和。10.设 sl=G00D,s2=,s3=BYE!,则 si,s2,和 s3 连 接 后 的 结 果 是 O三.阅 读 程 序 题 1.指 出 程 序 功 能 int stringcmp(Hstring S,Hstring T)int i=0,tag=l;if(S.length!=T.length)tag=0;elsewhile(iS.length&tag)if(S.chi=T.chi)i+;else tag=0;return tag;)2.阅 读 程 序 int stringpatindex(Hstring S,Hstring T)int i,j,k；数 据 错 相 动 敢 集 for(i=0;iS.length;i+)for(j=i,k=O;k=T.length)return i;return-1;(1)指 出 程 序 功 能；(2)设 S中 存 储 M there are a string”,T中 存 储?r*函 数 的 返 回 值 是 什 么？3.阅 读 程 序 指 出 程 序 功 能 void restring(Hstring S)char*p,*q,c;p=S.ch;q=S.ch+S.length-1;while(pq)c=*p;*p=*q;*q=c;p+；q_；)4.下 列 算 法 的 功 能 是 比 较 两 个 链 串 的 大 小，其 返 回 值 为：comstr(si,s2)=sls228请 在 空 白 处 填 入 适 当 的 内 容。K20012int comstr(1 inkstring si,1 inkstring