数据结构(C版)王红梅胡明王涛编著习题答案.docx

本文格式为Word版，下载可任意编辑数据结构(C版)王红梅胡明王涛编著习题答案 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的根本单位，在计算机程序中通常作为一个整体举行考虑和处理 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是议论数据布局时涉及的最小数据单位 【解答】数据项，数据元素 【分析】数据布局指的是数据元素以及数据元素之间的关系 ⑶ 从规律关系上讲，数据布局主要分为（ ）、（ ）、（ ）和（ ） 【解答】集合，线性布局，树布局，图布局 ⑷ 数据的存储布局主要有（ ）和（ ）两种根本方法，不管哪种存储布局，都要存储两方面的内容：（ ）和（ ） 【解答】依次存储布局，链接存储布局，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ） 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。

【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般处境下，一个算法的时间繁杂度是（ ）的函数 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间繁杂度为一个常数，那么表示成数量级的形式为（ ），若为n*log25n，那么表示成数量级的形式为（ ） 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间繁杂度，需要将低次幂去掉，将最高次幂的系数去掉 2. 选择题 ⑴ 依次存储布局中数据元素之间的规律关系是由（ ）表示的，链接存储布局中的数据元素之间的规律关系是由（ ）表示的 A 线性布局 B 非线性布局 C 存储位置 D 指针 【解答】C，D 【分析】依次存储布局就是用一维数组存储数据布局中的数据元素，其规律关系由存储位置（即元素在数组中的下标）表示；链接存储布局中一个数据元素对应链表中的一个结点，元素之间的规律关系由结点中的指针表示 ⑵ 假设有如下遗产继承规矩：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承那么表示该遗产继承关系的最适合的数据布局理应是（ ） A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出规律布局图。

⑶ 算法指的是（ ） A 对特定问题求解步骤的一种描述，是指令的有限序列 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的概括实现；简朴地说，算法是解决问题的方法；数据处理是通过算法完成的所以，只有A是算法的切实定义 ⑷ 下面（ ）不是算法所务必具备的特性 A 有穷性 B 切当性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ） A 找出数据布局的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求提升 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据繁杂性和程序繁杂性 【解答】C，E 3. 判断题 ⑴ 算法的时间繁杂度都要通过算法中的根本语句的执行次数来确定 【解答】错时间繁杂度要通过算法中根本语句执行次数的数量级来确定 ⑵ 每种数据布局都具备三个根本操作：插入、删除和查找 【解答】错如数组就没有插入和删除操作此题留神是每种数据布局 ⑶ 所谓数据的规律布局指的是数据之间的规律关系。

【解答】错是数据之间的规律关系的整体 ⑷ 规律布局与数据元素本身的内容和形式无关 【解答】对因此规律布局是数据组织的主要方面 ⑸ 基于某种规律布局之上的根本操作，其实现是唯一的 【解答】错根本操作的实现是基于某种存储布局设计的，因而不是唯一的 4. 分析以下各程序段，并用大O记号表示其执行时间 【解答】⑴ 根本语句是k=k+10*i，共执行了n-2次，所以T(n)=O(n) ⑵ 根本语句是k=k+10*i，共执行了n次，所以T(n)=O(n) ⑶ 分析条件语句，每循环一次，i+j 整体加1，共循环n次，所以T(n)=O(n) ⑷ 设循环体共执行T(n)次，每循环一次，循环变量y加1，最终T(n)=y，即： (T(n)+1)2≤n，所以T(n)=O(n1/2) ⑸ x++是根本语句，所以 5．设有数据布局（D，R），其中D={1, 2, 3, 4, 5, 6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}试画出其规律布局图并指出属于何种布局 【解答】其规律布局图如图1-3所示，它是一种图布局。

6. 为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个根本操作，每个根本操作的接口需定义前置条件、输入、功能、输出和后置条件 【解答】整数的抽象数据类型定义如下： ADT integer Data 整数a：可以是正整数(1, 2, 3, … )、负整数(-1, -2, -3, …)和零 Operation Constructor 前置条件：整数a不存在 输入：一个整数b 功能：构造一个与输入值一致的整数 输出：无 后置条件：整数a具有输入的值 Set 前置条件：存在一个整数a 输入：一个整数b 功能：修改整数a的值，使之与输入的整数值一致 输出：无 后置条件：整数a的值发生变更 Add 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相加 输出：相加后的结果 后置条件：整数a的值发生变更 Sub 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相减 输出：相减的结果 后置条件：整数a的值发生变更 Multi 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相乘 输出：相乘的结果 后置条件：整数a的值发生变更 Div 前置条件：存在一个整数a 输入：一个整数b 功能：将整数a与输入的整数b相除 输出：若整数b为零，那么抛出除零奇怪，否那么输出相除的结果 后置条件：整数a的值发生变更 Mod 前置条件：存在一个整数a 输入：一个整数b 功能：求当前整数与输入整数的模，即正的余数 输出：若整数b为零，那么抛出除零奇怪，否那么输出取模的结果 后置条件：整数a的值发生变更 Equal 前置条件：存在一个整数a 输入：一个整数b 功能：判断整数a与输入的整数b是否相等 输出：若相等返回1，否那么返回0 后置条件：整数a的值不发生变更 endADT 7. 求多项式A(x)的算法可根据以下两个公式之一来设计： ⑴ A(x)=anxn+an-1xn-1+…+a1x+a0 ⑵ A(x)=(…(anx+an-1)x+…+a1)x)+a0 根据算法的时间繁杂度分析对比这两种算法的优劣。

【解答】其次种算法的时间性能要好些第一种算法需执行大量的乘法运算，而其次种算法举行了优化，裁减了不必要的乘法运算 8. 算法设计（要求：算法用伪代码和C++描述，并分析最坏处境下的时间繁杂度） ⑴ 对一个整型数组A[n]设计一个排序算法 【解答】下面是简朴选择排序算法的伪代码描述 下面是简朴选择排序算法的C++描述 分析算法，有两层嵌套的for循环，所以， ⑵ 找出整型数组A[n]中元素的最大值和次最大值 【解答】算法的伪代码描述如下： 算法的C++描述如下： 分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n) 学习自测及答案 1．依次存储布局的特点是（ ），链接存储布局的特点是（ ） 【解答】用元素在存储器中的相对位置来表示数据元素之间的规律关系，用指示元素存储地址的指针表示数据元素之间的规律关系 2. 算法在发生非法操作时可以作出处理的特性称为（ ） 【解答】刚强性 3. 常见的算法时间繁杂度用大Ｏ记号表示为：常数阶( )、对数阶( )、线性阶 ( )、平方阶( )和指数阶( )。

【解答】Ｏ(1)，Ｏ(log2n)，Ｏ(n)，Ｏ(n2)，Ｏ(2n) 4．将以下函数按它们在n 时的无穷大阶数，从小到大排列 n, n-n3+7n5, nlogn, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n 【解答】log2n, n1/2+log2n, n, nlog2n, n2+log2n, n3, n-n3+7n5, 2n/2, (3/2)n, n! 5．试描述数据布局和抽象数据类型的概念与程序设计语言中数据类型概念的识别 【解答】数据布局是指相互之间存在确定关系的数据元素的集合而抽象数据类型是指一个数据布局以及定义在该布局上的一组操作程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称抽象数据类型可以看成是对数据类型的一种抽象 6. 对以下用二元组表示的数据布局,试分别画出对应的规律布局图，并指出属于何种布局 ⑴ A=(D，R)， 其中D={a1, a2, a3, a4}，R={ } ⑵ B=(D，R)， 其中D={a, b, c, d, e, f}，R={,,,,} ⑶ C=( D，R)，其中D={a，b，c，d，e，f}，R={,,,,,} ⑷ D=(D，R)， 其中D={1, 2, 3, 4, 5, 6}， R={(1, 2)，(1, 4)，(2, 3)，(2, 4)，(3, 4)，(3, 5)，(3, 6)，(4, 6)} 【解答】⑴ 属于集合，其规律布局图如图1-4(a)所示；⑵ 属于线性布局，其规律布局图如图1-4(b)所示；⑶ 属于树布局，其规律布局图如图1-4(c)所示；⑷ 属于图布局，其规律布局图如图1-4(d)所示。

7. 求以下算法的时间繁杂度 count=0; x=1; while (x { x*=2; count++; } return count; 【解答】Ｏ(log2n) 第 2 章 线性表 课后习题讲解 1. 填空 ⑴ 在依次表中，等概率处境下，插入和删除一个元素平均需移动（ ）个元素，概括移动元素的个数与（ ）和（ ）有关 【解答】表长的一半，表长，该元素在表中的位置 ⑵ 依次表中第一个元素的存储地址是100，每个元素的长度为2，那么第5个元素的存储地址是（ ） 【解答。