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

上传人:11****ws 文档编号:3738772 上传时间:2019-07-10 格式:DOC 页数:54 大小:122KB
下载 相关 举报
严蔚敏 数据结构课后习题及答案解析.doc_第1页
第1页 / 共54页
严蔚敏 数据结构课后习题及答案解析.doc_第2页
第2页 / 共54页
严蔚敏 数据结构课后习题及答案解析.doc_第3页
第3页 / 共54页
严蔚敏 数据结构课后习题及答案解析.doc_第4页
第4页 / 共54页
严蔚敏 数据结构课后习题及答案解析.doc_第5页
第5页 / 共54页
点击查看更多>>
资源描述

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;

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 实用文档资料库 > 策划方案

Copyright © 2018-2021 Wenke99.com All rights reserved

工信部备案号浙ICP备20026746号-2  

公安局备案号:浙公网安备33038302330469号

本站为C2C交文档易平台,即用户上传的文档直接卖给下载用户,本站只是网络服务中间平台,所有原创文档下载所得归上传人所有,若您发现上传作品侵犯了您的权利,请立刻联系网站客服并提供证据,平台将在3个工作日内予以改正。