数据结构第二版王红梅课后习题解析

5星(超过95%的资源)
所需积分/C币:50 2014-11-09 15:50:10 15.63MB PDF
198
收藏 收藏
举报

数据结构 C++ 第二版 清华大学 王红梅 最新课后习题 答案
第1章绪论 1.1本章导学 1.知识结构图 本章的知识结构如图1-1所示,其中第二层的椭圆代表本章的学习主线。 绪论 数据结构 算法 基本概念 逻辑结构 结关系 存储结构 基本概念 算法分析 1)数据 (1)逻辑结构(1)存储结构 (1)算法 C (1)问题规模 (2)数据元素 (2)数据结构|(②)常用存储 (2)算法特性 (2)基本语句 (3)数据结构的分类 方法 (3)评价算法 (3时间复杂度 (4)抽象数据类型 (4)描述算法 (4)大O记号 图1-1知识结构图 2.学习要点 对本章的学习要从两条主线出发,一条主线是数据结构,包括数据结构的相关概念 及含义,另一条主线是算法,包括算法的相关概念、描述方法以及时间复杂度的分析方 法 在学习数据结构时要抓住两个方面:逻辑结构和存储结构,并注意把握二者之间的 关系。在学习算法时,要以算法的概念和特性为基本点,并在以后的学习中注意提高算 法设计的能力。对于算法时间性能的分析,要将注意力集中在增长率上,即基本语句执 行次数的数量级,在设计算法时,养成分析算法时间性能的习惯,进而有效地改进算法 的效率。 1.2习题解析 1.填空 (1)()是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 (2)( )是数据的最小单位,( )是讨论数据结构时涉及的最小数据单位。 【解答】数据项,数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 (3)从逻辑关系上讲,数据结构主要分为( )、( )和( 【解答】集合,线性结构,树结构、图结构 (4)数据的存储结构主要有()和()两种基本方法,不论哪种存储结构, 都要存储两方面的内容:()和() 【解答】顺序存储结构,链接存储结构,数据元素,数据元素之间的关系 (5)算法具有五个特性,分别是()、()、()、()、()。 【解答】有零个或多个输入,有一个或多个输出,有穷性,确定性,可行性 (6)算法的描述方法通常有( )和( )四种, 其中,( )被称为算法语言。 【解答】自然语言,程序设计语言,流程图,伪代码,伪代码 (7)在一般情况下,一个算法的时间复杂度是()的函数。 【解答】问题规模 (8)设待处理问题的规模为n,若一个算法的时间复杂度为一个常数,则表示成数量级 的形式为(),若为2n*log25n+8n,则表示成数量级的形式为() 【解答】O(1),O( nlog ,n) 【分析】用大O记号表示算法的时间复杂度,需要将低次幂去掉,将最高次幂的系数去 掉 2.选择题 (1)顺序存储结构中数据元素之间的逻辑关系是由()表示的,链接存储结构中 的数据元素之间的逻辑关系是由()表示的。 A线性结构 B非线性结构 C存储位置 D指针 【解答】C,D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素,其逻辑关系由存储 位置(即元素在数组中的下标)表示;链接存储结构中一个数据元素对应链表中的一个 结点,元素之间的逻辑关系由结点中的指针表示。 (2)假设有如下遗产继承规则:丈夫和妻子可以相互继承遗产;子女可以继承父亲或母 亲的遗产;子女间不能相互继承遗产。则表示该遗产继承关系的最合适的数据结构应该 是( A树 B图 C线性表 D集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素,根据继承关系画出逻辑结构图如图1-2 所示。 丈大 子女1…-子女m 图1-2遗产继承逻辑结构图 (3)计算机所处理的数据一般具有某种内在联系,这是指() A数据和数据之间存在某种关系 B元素和元素之间存在某种关系 C元素内部具有某种结构 D数据项和数据项之间存在某种关系 【解答】B 【分析】数据结构是指相互之间存在一定关系的数据元素的集合,数据元素是讨论数据 结构时涉及的最小数据单位,元素内部各数据项一般不予考虑。 (4)对于数据结构的描述,下列说法中不正确的是( A相同的逻辑结构对应的存储结构也必相同 B数据结构由逻辑结构、存储结构和基本操作三方面组成 C对数据结构基本操作的实现与存储结构有关 D数据的存储结构是数据的逻辑结构的机内实现 【解答】A 【分析】相同的逻辑结构可以用不同的存储结构实现,一般来说,在不同的存储结构下 基本操作的实现是不同的,例如线性表可以顺序存储也可以链接存储,在顺序存储和链 接存储结构下插入操作的实现截然不同。 (5)可以用( )定义一个完整的数据结构。 A数据元素 B数据对象 C数据关系 D抽象数据类 型 【解答】D 【分析】抽象数据类型是一个数据结构以及定义在该结构上的一组操作的总称 (6)算法指的是()。 A对特定问题求解步骤的一种描述,是指令的有限序列。 B计算机程序 C解决问题的计算方法 D数据处理 【解答】A 【分析】计算机程序是对算法的具体实现;简单地说,算法是解决问题的方法:数据处 理是通过算法完成的。所以,只有A是算法的准确定义。 (7)下面()不是算法所必须具备的特性。 A有穷性 B确切性 C高效性 D可行性 【解答】C 【分析】高效性是好算法应具备的特性。 (8)算法分析的目的是(),算法分析的两个主要方面是()。 A找出数据结构的合理性B研究算法中输入和输出的关系 C分析算法的效率以求改进D分析算法的易读性和文档性 E空间性能和时间性能 F正确性和简明性 G可读性和文档性 H数据复杂性和程序复杂性 【解答】C,E 3.判断题 (1)算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。 【解答】错。时间复杂度要通过算法中基本语句执行次数的数量级来确定 (2)每种数据结构都具备三个基本操作:插入、删除和查找 【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构 (3)所谓数据的逻辑结构指的是数据之间的逻辑关系。 【解答】错。是数据之间的逻辑关系的整体。 (4)逻辑结构与数据元素本身的内容和形式无关。 【解答】对。因此逻辑结构是数据组织的主要方面。 (5)基于某种逻辑结构之上的基本操作,其实现是唯一的。 【解答】错。基本操作的实现是基于某种存储结构设计的,因而不是唯一的。 4.分析以下各程序段,并用大O记号表示其执行时间。 (1)i=1;k=0 (2)i=1;k=0 while k=k+10*i; k=k+10*i; i++; ++ 丁 while(i<=n) (3)i=1;j=0; (4)y=0; while (i+j<=n) while(y+1)*(y+1)<=n) if (1>jj++ else i++. doc. com (5)for(i=1;i<n;i++) for(=1;j<=i;j+) for (k=l; k<=j; k++) X+十 【解答】(1)基本语句是k-k+10*i,共执行了n2次,所以T(n)=O(m)。 (2)基本语句是k-k+10*1,共执行了n次,所以T(m)=O(m)。 (3)分析条件语句,每循环一次,i整体加1,共循环n次,所以T(n)=O(n)。 (4)设循环体共执行T(n)次,每循环一次,循环变量y加1,最终T(n)=y,即 (T(n)+1)2≤n,所以T(n)=O(n12)。 t (5)x++是基本语句,所以T(n)=∑∑Σ1=0(n2) 5.解答下列问题 (1)设有数据结构(D,R),其中D={1,2,3,4,5,6},R={(1,2),(2,3),(2,4),(3,4),(3, ),(3,6),(4,5),(4,6)}。试画出其逻辑结构图并指出属于何种结构。 【解答】其逻辑结构图如图1-3所示,它是一种图结构。 图1-3逻辑结构图 (2)为整数定义一个抽象数据类型,包含整数的常见运算,每个运算对应一个基本操 作,每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件。 【解答】整数的抽象数据类型定义如下: ADT integer Data 整数:可以是正整数(1,2,3,…)、负整数(-1,-2,-3,…)和零 Operation Constructor 前置条件:整数a不存在 输入:一个整数b 功能:构造一个与输入值相同的整数 输出:无 后置条件:整数a具有输入的值 S 前置条件:存在一个整数a 豆丁 输入:一个整数b 功能:修改整数a的值,使之与输入的整数值相同 输出:无 后置条件:整数a的值发生改变 Add 前置条件:存在一个整数a ocin. com 输入:一个整数b 功能:将整数a与输入的整数b相加 输出:相加后的结果 后置条件:整数a的值发生改变 Sub 前置条件:存在一个整数a 输入:一个整数b 功能:将整数a与输入的整数b相减 输出:相减的结果 后置条件:整数a的值发生改变 Multi 前置条件:存在一个整数a 输入:一个整数b 功能:将整数a与输入的整数b相乘 输出:相乘的结果 后置条件:整数a的值发生改变 前置条件:存在一个整数a 输入:一个整数b 功能:将整数a与输入的整数b相除 输出:若整数b为零,则抛出除零异常,否则输出相除的结果 后置条件:整数a的值发生改变 Mod 前置条件:存在一个整数a 输入:一个整数b 功能:求当前整数与输入整数的模,即正的余数 输出:若整数b为零,则抛出除零异常,否则输出取模的结果 后置条件:整数a的值发生改变 qua 前置条件:存在一个整数a 输入:一个整数b 功能:判断整数a与输入的整数b是否相等 输出:若相等返回1,否则返回0 后置条件:整数a的值不发生改变 daDT (3)求多项式A(x)的算法可根据下列两个公式之一来设计: ①A(x)=anx+anx21+…+apx+ao ②A(x)=(…(anx+an1)x+…+a1)x)+ao 根据算法的时间复杂度分析比较这两种算法的优劣 解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算,而第二种 算法进行了优化,减少了不必要的乘法运算。 (4)选择和评价数据结构的标准与方法是什么? 【解答】首先,对给定的实际问题可以建立不同的数据结构;其次,对于给定的数据结 构,可以选择不同的存储实现,即采用不同的存储结构:再次,在给定数据结构和存储 结构的条件下,对同一基本操作可以设计出不同算法。因此,数据的逻辑结构、存储结 构和操作(特别是基本操作)的实现这三者是密切相关的。一般地,在建立数据结构时 应该考虑以下三个方面: ①确定表示问题所需的数据及其特性; ②确定必须支持的基本操作,并度量每种操作所受的时、空资源限制,某些重要 的操作,例如査找、插入和删除的资源限制通常决定了数据结构的选择; ③选择(或设计)最接近这些开销的数据结构。 6.算法设计(要求:用伪代码和C艹+描述两种方法描述算法,并分析时间复杂度) (1)对一个整型数组A[m设计一个排序算法 【解答】下面是简单选择排序算法的伪代码描述。 1.对n个记录进行n1趟简单选择排序 1.1在无序区[,n-1中选取最小记录,设其下标为 index 12将最小记录与第i个记录交换; 下面是简单选择排序算法的C++描述。 简单选择排序算法 Selectsort void SelectSort(intr[ l, int n) for(i=0;i<n-1;i++)/对n个记录进行n-1趟简单选择排序 Index-1 for(j=i+1;j<n;j++)∥在无序区中选取最小记录 if(r[] <index]index=j if( index!=i)r[il←→r[ index};∥交换元素 n-2 分析算法,有两层嵌套的fo循环,所以,r(n)=Ex1=0(n2)。 (2)找出整型数组A[n]中元素的最大值和次最大值。 【解答】算法的伪代码描述如下: ,将前两个元素进行比较,较大者放到mx中,较小者放到mmx中 2.从第3个元素开始直到最后一个元素依次取元素A[,执行下列操作: 21如果A[imax,则Ai]为最大值,原来的最大值为次最大值 22否则,如果A[nmax,则最大值不变,Ai为次最大值 3.输出最大值max,次最大值nmax; 算法的C++描述如下: 最大值和次最大位法 Max NextMax void Max NextMax(int A[], int n, int max, int & nmax if([O]>=A[lD& max=A[O]; nmax=A[l]: else max=A[l]; nmax=A[O]: for (i=2; i<n;i++ if(A[i]>=max)& nmax=max; max=Ai se if (a[i]> nmax) nmax=Al]; cou<"最大值为:"<<max<<"n次最大值为:"<<nmax<<endl 分析算法,只有一层循环,共执行n-2次,所以,T(n)=O(n)。 第2章线性表 2.1本章导学 1.知识结构图 本章的知识结构如图2-1所示,其中第二层的椭圆代表本章的学习主线 线性表 d 逻辑结构 丁 基本概念 抽象 数据 类型 比较 定义 顺序存储结构 链接存储结构 其他存储方法 om (饿线性表定义(①)ADT定义 (2)逻辑特征(2)基本操作(①)顺序表类定义()单链表静态链表 (2)基本操作的实(2)循环链表(2)间接寻址 现及时间性能(3双链表 图21知识结构图 2.学习要点 本章虽然讨论的是线性表,但涉及的许多问题都具有一定的普遍性,因此,本章是本 课程的重点之一,也是其它后续章节的重要基础 对于本章的学习要从两条明线、一条暗线出发。两条明线是线性表的逻辑结构和存储 结构,一条暗线是算法(即基本操作的实现)。注意线性表的ADT定义、顺序表类定义 和单链表类定义三者之间的关系;注意在不同的存储结构下,相同操作的不同实现算法 注意对顺序表和链表从时间性能和空间性能等方面进行综合对比,在实际应用中能为线性 表选择或设计合适的存储结构。 8

...展开详情
试读 100P 数据结构第二版王红梅课后习题解析
立即下载 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
weixin_37662589 十分不错的书
2018-06-03
回复
失了个眠 跟课本一样 清晰好用
2017-03-06
回复
hbant 内容不错,谢谢分享。
2015-12-26
回复
askdgx 清晰。而且确实是第二版的。谢谢分享!
2015-03-30
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
数据结构第二版王红梅课后习题解析 50积分/C币 立即下载
1/100
数据结构第二版王红梅课后习题解析第1页
数据结构第二版王红梅课后习题解析第2页
数据结构第二版王红梅课后习题解析第3页
数据结构第二版王红梅课后习题解析第4页
数据结构第二版王红梅课后习题解析第5页
数据结构第二版王红梅课后习题解析第6页
数据结构第二版王红梅课后习题解析第7页
数据结构第二版王红梅课后习题解析第8页
数据结构第二版王红梅课后习题解析第9页
数据结构第二版王红梅课后习题解析第10页
数据结构第二版王红梅课后习题解析第11页
数据结构第二版王红梅课后习题解析第12页
数据结构第二版王红梅课后习题解析第13页
数据结构第二版王红梅课后习题解析第14页
数据结构第二版王红梅课后习题解析第15页
数据结构第二版王红梅课后习题解析第16页
数据结构第二版王红梅课后习题解析第17页
数据结构第二版王红梅课后习题解析第18页
数据结构第二版王红梅课后习题解析第19页
数据结构第二版王红梅课后习题解析第20页

试读结束, 可继续阅读

50积分/C币 立即下载