严蔚敏数据结构课后习题及答案解析.doc

1、 第 一 章 绪 论一 、 选 择 题 1.组 成 数 据 的 基 本 单 位 是 （ ） （ A） 数 据 项 （ B） 数 据 类 型 （ C） 数 据 元 素 （ D） 数 据 变 量 2.数 据 结 构 是 研 究 数 据 的 （ ） 以 及 它 们 之 间 的 相 互 关 系 。 （ A） 理 想 结 构 ， 物 理 结 构 （ B） 理 想 结 构 ， 抽 象 结 构 （ C） 物 理 结 构 ， 逻 辑 结 构 （ D） 抽 象 结 构 ， 逻 辑 结 构 3.在 数 据 结 构 中 ， 从 逻 辑 上 可 以 把 数 据 结 构 分 成 （ ） （ A） 动 态 结 构 和 静

2、 态 结 构 （ B） 紧 凑 结 构 和 非 紧 凑 结 构 （ C） 线 性 结 构 和 非 线 性 结 构 （ D） 内 部 结 构 和 外 部 结 构 4.数 据 结 构 是 一 门 研 究 非 数 值 计 算 的 程 序 设 计 问 题 中 计 算 机 的 （ ） 以 及 它 们 之 间 的（ ） 和 运 算 等 的 学 科 。 （ A） 数 据 元 素 （ B） 计 算 方 法 （ C） 逻 辑 存 储 （ D） 数 据 映 像 （ A） 结 构 （ B） 关 系 （ C） 运 算 （ D） 算 法 5.算 法 分 析 的 目 的 是 （ ） 。 （ A） 找 出 数 据 结 构

3、的 合 理 性 （ B） 研 究 算 法 中 的 输 入 和 输 出 的 关 系 （ C） 分 析 算 法 的 效 率 以 求 改 进 （ D） 分 析 算 法 的 易 懂 性 和 文 档 性 6.计 算 机 算 法 指 的 是 （ ） ,它 必 须 具 备 输 入 、 输 出 和 （ ） 等 5 个 特 性 。 （ A） 计 算 方 法 （ B） 排 序 方 法 （ C） 解 决 问 题 的 有 限 运 算 序 列 （ D） 调 度 方 法 （ A） 可 执 行 性 、 可 移 植 性 和 可 扩 充 性 （ B） 可 行 性 、 确 定 性 和 有 穷 性 （ C） 确 定 性 、 有 穷

4、 性 和 稳 定 性 （ D） 易 读 性 、 稳 定 性 和 安 全 性 二 、 判 断 题 1.数 据 的 机 内 表 示 称 为 数 据 的 存 储 结 构 。 （ ） 2.算 法 就 是 程 序 。 （ ） 3.数 据 元 素 是 数 据 的 最 小 单 位 。 （ ） 4.算 法 的 五 个 特 性 为 ： 有 穷 性 、 输 入 、 输 出 、 完 成 性 和 确 定 性 。 （ ） 5.算 法 的 时 间 复 杂 度 取 决 于 问 题 的 规 模 和 待 处 理 数 据 的 初 态 。 （ ） 三 、 填 空 题 1.数 据 逻 辑 结 构 包 括 _、 _、 _ 和 _四 种

5、 类 型 ,其 中 树 形 结 构和 图 形 结 构 合 称 为 _。 2.在 线 性 结 构 中 ,第 一 个 结 点 _前 驱 结 点 ,其 余 每 个 结 点 有 且 只 有 _个 前 驱 结 点 ； 最 后一 个 结 点 _后 续 结 点 ,其 余 每 个 结 点 有 且 只 有 _个 后 续 结 点 。 3.在 树 形 结 构 中 ,树 根 结 点 没 有 _结 点 ,其 余 每 个 结 点 有 且 只 有 _个 前 驱 结 点 ； 叶子 结 点 没 有 _结 点 ,其 余 每 个 结 点 的 后 续 结 点 可 以 _。 4.在 图 形 结 构 中 ,每 个 结 点 的 前 驱 结

6、 点 数 和 后 续 结 点 数 可 以 _。 5.线 性 结 构 中 元 素 之 间 存 在 _关 系 ,树 形 结 构 中 元 素 之 间 存 在 _关 系 ,图 形 结 构 中元 素 之 间 存 在 _关 系 。6.算 法 的 五 个 重 要 特 性 是 _、 _、 _、 _、 _。 7.数 据 结 构 的 三 要 素 是 指 _、 _和 _。 8.链 式 存 储 结 构 与 顺 序 存 储 结 构 相 比 较 ,主 要 优 点 是 _。 9.设 有 一 批 数 据 元 素 ,为 了 最 快 的 存 储 某 元 素 ,数 据 结 构 宜 用 _结 构 ,为 了 方 便 插 入 一个 元

7、素 ,数 据 结 构 宜 用 _结 构 。 四 、 算 法 分 析 题 1.求 下 列 算 法 段 的 语 句 频 度 及 时 间 复 杂 度 参 考 答 案 ：一 、 选 择 题1. C 2.C 3. C 4. A、 B 5. C 6.C、 B二 、 判 断 题 :1、 2、 3、 4、 5、 三 、 填 空 题1、 线 性 、 树 形 、 图 形 、 集 合 ? ； 非 线 性 （ 网 状 ） 2、 没 有 ； 1； 没 有 ； 1 3、 前 驱 ； 1； 后 继 ；任 意 多 个 4、 任 意 多 个 5、 一 对 一 ； 一 对 多 ； 多 对 多 6、 有 穷 性 ； 确 定 性 ；

8、 可 行 性 ； 输 入 ； 输出 7、 数 据 元 素 ； 逻 辑 结 构 ； 存 储 结 构 8、 插 入 、 删 除 、 合 并 等 操 作 较 方 便 9、 顺 序 存 储 ；链 式 存 储 四 、 算 法 分 析 题for(i=1; inext=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;5.在 一 个 单 链 表 中 ， 若 删 除 p 所 指 结 点 的 后 续 结 点 ， 则 执 行 （ ） （ A） p-next=p-next-next; （ B）

9、 p=p-next; p-next=p-next-next;（ C） p-next=p-next; （ D） p =p-next-next;6.下 列 有 关 线 性 表 的 叙 述 中 ， 正 确 的 是 （ ） （ A） 线 性 表 中 的 元 素 之 间 隔 是 线 性 关 系 （ B） 线 性 表 中 至 少 有 一 个 元 素 （ C） 线 性 表 中 任 何 一 个 元 素 有 且 仅 有 一 个 直 接 前 趋 （ D） 线 性 表 中 任 何 一 个 元 素 有 且 仅 有 一 个 直 接 后 继 7.线 性 表 是 具 有 n 个 （ ） 的 有 限 序 列 （ n 0)（

10、A） 表 元 素 （ B） 字 符 （ C） 数 据 元 素 （ D） 数 据 项 二 、 判 断 题 1.线 性 表 的 链 接 存 储 ， 表 中 元 素 的 逻 辑 顺 序 与 物 理 顺 序 一 定 相 同 。 （ ） 2.如 果 没 有 提 供 指 针 类 型 的 语 言 ， 就 无 法 构 造 链 式 结 构 。 （ ） 3.线 性 结 构 的 特 点 是 只 有 一 个 结 点 没 有 前 驱 ， 只 有 一 个 结 点 没 有 后 继 ， 其 余 的 结 点 只 有 一 个 前 驱和 后 继 。 （ ） 4.语 句 p=p-next 完 成 了 指 针 赋 值 并 使 p 指

11、针 得 到 了 p 指 针 所 指 后 继 结 点 的 数 据 域 值 。 （ ） 5.要 想 删 除 p 指 针 的 后 继 结 点 ， 我 们 应 该 执 行 q=p-next ； p-next=q-next； free(q)。（ ） 三 、 填 空 题 1.已 知 P 为 单 链 表 中 的 非 首 尾 结 点 ， 在 P 结 点 后 插 入 S 结 点 的 语 句 为 ：_ 。2.顺 序 表 中 逻 辑 上 相 邻 的 元 素 物 理 位 置 ( )相 邻 ， 单 链 表 中 逻 辑 上 相 邻 的 元 素 物 理 位 置_相 邻 。 3.线 性 表 L （ a1， a2， .， an

12、） 采 用 顺 序 存 储 ， 假 定 在 不 同 的 n 1 个 位 置 上 插 入 的 概 率 相同 ， 则 插 入 一 个 新 元 素 平 均 需 要 移 动 的 元 素 个 数 是 _ 4.在 非 空 双 向 循 环 链 表 中 ， 在 结 点 q 的 前 面 插 入 结 点 p 的 过 程 如 下 ： p-prior=q-prior;q-prior-next=p;p-next=q;_; 5.已 知 L 是 无 表 头 结 点 的 单 链 表 ， 是 从 下 列 提 供 的 答 案 中 选 择 合 适 的 语 句 序 列 ， 分 别 实 现 ： （ 1） 表 尾 插 入 s 结 点 的

13、 语 句 序 列 是 _(2) 表 尾 插 入 s 结 点 的 语 句 序 列 是 _1. p-next=s; 2. p=L; 3. L=s; 4. p-next=s-next; 5. s-next=p-next; 6. s-next=L; 7. s-next=null; 8. while(p-next!= Q)? p=p-next; 9. while(p-next!=null) p=p-next; 四 、 算 法 设 计 题 1.试 编 写 一 个 求 已 知 单 链 表 的 数 据 域 的 平 均 值 的 函 数 （ 数 据 域 数 据 类 型 为 整 型 ） 。 2.已 知 带 有 头

14、结 点 的 循 环 链 表 中 头 指 针 为 head,试 写 出 删 除 并 释 放 数 据 域 值 为 x 的 所 有 结 点的 c 函 数 。 3.某 百 货 公 司 仓 库 中 有 一 批 电 视 机 ， 按 其 价 格 从 低 到 高 的 次 序 构 成 一 个 循 环 链 表 ， 每 个 结 点 有 价格 、 数 量 和 链 指 针 三 个 域 。 现 出 库 （ 销 售 ） m 台 价 格 为 h 的 电 视 机 ， 试 编 写 算 法 修 改 原 链 表 。 4.某 百 货 公 司 仓 库 中 有 一 批 电 视 机 ， 按 其 价 格 从 低 到 高 的 次 序 构 成 一

15、 个 循 环 链 表 ， 每 个 结 点 有 价格 、 数 量 和 链 指 针 三 个 域 。 现 新 到 m 台 价 格 为 h 的 电 视 机 ， 试 编 写 算 法 修 改 原 链 表 。 5.线 性 表 中 的 元 素 值 按 递 增 有 序 排 列 ， 针 对 顺 序 表 和 循 环 链 表 两 种 不 同 的 存 储 方 式 ， 分 别 编 写 C函 数 删 除 线 性 表 中 值 介 于 a 与 b（ a b） 之 间 的 元 素 。 6.设 A=(a0,a1,a2,.,an-1),B=(b0,b1,b2,.,bm-1)是 两 个 给 定 的 线 性 表 ,它 们 的 结 点 个

16、 数分 别 是 n 和 m,且 结 点 值 均 是 整 数 。 若 n=m， 且 ai= bi （ 0 iB。 试 编 写 一 个 比 较 A 和 B 的 C 函 数 ， 该 函 数 返 回 -1 或 0 或 1， 分 别 表 示 AB。 7.试 编 写 算 法 ,删 除 双 向 循 环 链 表 中 第 k 个 结 点 。 8.线 性 表 由 前 后 两 部 分 性 质 不 同 的 元 素 组 成 (a0,a1,.,an-1,b0,b1,.,bm-1),m 和 n 为 两部 分 元 素 的 个 数 ,若 线 性 表 分 别 采 用 数 组 和 链 表 两 种 方 式 存 储 ,编 写 算 法

17、将 两 部 分 元 素 换 位 成(b0,b1,.,bm-1,a0,a1,.,an-1),分 析 两 种 存 储 方 式 下 算 法 的 时 间 和 空 间 复 杂 度 。 9.用 循 环 链 表 作 线 性 表 (a0,a1,.,an-1)和 （ b0,b1,.,bm-1） 的 存 储 结 构 ,头 指 针 分 别 为ah 和 bh， 设 计 C 函 数 ， 把 两 个 线 性 表 合 并 成 形 如 （ a0,b0,a1,b1,） 的 线 性 表 ， 要 求 不 开 辟新 的 动 态 空 间 ,利 用 原 来 循 环 链 表 的 结 点 完 成 合 并 操 作 ,结 构 仍 为 循 环 链

18、 表 ,头 指 针 为 head,并 分 析 算 法 的 时 间 复 杂 度 。 10.试 写 出 将 一 个 线 性 表 分 解 为 两 个 带 有 头 结 点 的 循 环 链 表 ， 并 将 两 个 循 环 链 表 的 长 度 放 在 各 自 的头 结 点 的 数 据 域 中 的 C 函 数 。 其 中 ,线 性 表 中 序 号 为 偶 数 的 元 素 分 解 到 第 一 个 循 环 链 表 中 ,序号 为 奇 数 的 元 素 分 解 到 第 二 个 循 环 链 表 中 。 11.试 写 出 把 线 性 链 表 改 为 循 环 链 表 的 C 函 数 。 12.己 知 非 空 线 性 链

19、表 中 x 结 点 的 直 接 前 驱 结 点 为 y,试 写 出 删 除 x 结 点 的 C 函 数 。 参 考 答 案 ： 一 、 选 择 题1. B 2.C 3. D 4. B 5. A 6.A 7、 C二 、 判 断 题 :参 考 答 案 ： 1、 2、 3、 4、 5、 三 、 填 空 题1、 s-next=p-next; p-next=s; 2、 一 定 ； 不 一 定 3、 n/2 4、 q-prior=p; 5、 (1)6) 3)(2) 2) 9） 1) 7)四 、 算 法 设 计 题1、#include “stdio.h“#include “malloc.h“typedef

20、struct nodeint data; struct node *link;NODE;int aver(NODE *head)int i=0,sum=0,ave; NODE *p; p=head;while(p!=NULL)p=p-link;+i;sum=sum+p-data;ave=sum/i;return (ave);2、#include “stdio.h“#include “malloc.h“typedef struct nodeint data; /* 假 设 数 据 域 为 整 型 */struct node *link;NODE;void del_link(NODE *head,

21、int x) /* 删 除 数 据 域 为 x 的 结 点 */NODE *p,*q,*s;p=head;q=head-link;while(q!=head)if(q-data=x)p-link=q-link;s=q;q=q-link;free(s); elsep=q;q=q-link;3、void del(NODE *head,float price,int num)NODE *p,*q,*s;p=head;q=head-next;while(q-pricenext;if(q-price=price)q-num=q-num-num;else printf(“无 此 产 品 “);if(q-n

22、um=0)p-next=q-next;free(q);4、#include “stdio.h“#include “malloc.h“typedef struct nodefloat price;int num;struct node *next;NODE;void ins(NODE *head,float price,int num)NODE *p,*q,*s;p=head;q=head-next;while(q-pricenext;if(q-price=price)q-num=q-num+num;elses=(NODE *)malloc(sizeof(NODE);s-price=price;

23、s-num=num;s-next=p-next;p-next=s;5、 顺 序 表 ： 算 法 思 想 ： 从 0 开 始 扫 描 线 性 表 ， 用 k 记 录 下 元 素 值 在 a 与 b 之 间 的 元 素 个 数 ， 对 于 不 满 足 该条 件 的 元 素 ， 前 移 k 个 位 置 ， 最 后 修 改 线 性 表 的 长 度 。 void del（ elemtype list， int *n， elemtype a， elemtype b） int i=0， k=0； while（ i=a /* 假 设 循 环 链 表 带 有 头 结 点 */while(q!=head while(q!=head free(r); if(p!=q)p-link=q;6、#define MAXSIZE 100int listAMAXSIZE,listBMAXSIZE;int n,m;int compare(int a,int b)int i=0;