《数据结构C++版王红梅版课后答案》由会员分享，可在线阅读，更多相关《数据结构C++版王红梅版课后答案（52页珍藏版）》请在金锄头文库上搜索。
1、第1章绪论课后习题讲解1 .填空（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。【解答】数据元素（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。结构数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系算法具有五个特性，分别是（）、（）、（）、（）、（）。【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性算法
2、的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。【解答】自然语言，程序设计语言，流程图，伪代码，伪代码在一般情况下，一个算法的时间复杂度是（）的函数。【解答】问题规模设待处理问题的规模为n,若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。【解答】0（1）,0（nlog2n）【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。2 .选择题顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。A线性结构B非线性结构C存储位置D指针【解
3、答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是）。A树B图C线性表D集合【解答】B【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。图2遗产继承逻辑结构图算法指的是()。A对特定问题求解步骤的一种描述，是指令的有限序列。B计算机程序C解决问题的计算方法D数据处理【解答】A【分
4、析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法;数据处理是通过算法完成的。所以，只有A是算法的准确定义。下面()不是算法所必须具备的特性。A有穷性B确切性C高效性D可行性【解答】C【分析】高效性是好算法应具备的特性。算法分析的目的是（），算法分析的两个主要方面是（）。A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易读性和文档性E空间性能和时间性能F正确性和简明性G可读性和文档性H数据复杂性和程序复杂性【解答】C，E3 .判断题算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。【解答】错。时间复杂度要通过算法中基本语句执行次数的数
5、量级来确定每种数据结构都具备三个基本操作：插入、删除和查找。【解答】错。如数组就没有插入和删除操作。此题注意是每种数据结构。所谓数据的逻辑结构指的是数据之间的逻辑关系。【解答】错。是数据之间的逻辑关系的整体。逻辑结构与数据元素本身的内容和形式无关。【解答】对。因此逻辑结构是数据组织的主要方面。基于某种逻辑结构之上的基本操作，其实现是唯一的。【解答】错。基本操作的实现是基于某种存储结构设计的，因而不是唯一的。4 .分析以下各程序段，并用大O记号表示其执行时间。Cl) i=l;MPwhile(k=k+10*i；i+；(3) i=l p j=0;while (i+j=n)if 饵 j+, else
6、i+;(5) for (i=l; i=n, i+)for (j=lJE,j+)for f kM; k+)X+； 1=1, do gk+li; if while (iF)(4) y=0,while (y+0* Cy+l)=n) y=y+i;【解答】基本语句是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)2n,所以T(n)=O(n1/2)。言东切萨jx+
7、小基本语句，所以.一5 .设有数据结构(D,R),其中D=1,2,3,4,5,6R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)试画出其逻辑结构图并指出属于何种结构。【解答】其逻辑结构图如图1-3所示，它是一种图结构U1-3逻辑给构图6 .为整数定义一个抽象数据类型，包含整数的常见运算，每个运算对应一个基本操作，每个基本操作的接口需定义前置条件、输入、功能、输出和后置条件【解答】整数的抽象数据类型定义如下：ADTintegerData整数a：可以是正整数(1,2,3,)、负整数(-1,-2,-3,)和零OperationConstructor前
8、置条件：整数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的值发生改
9、变Div前置条件：存在一个整数a输入：一个整数b功能：将整数a与输入的整数b相除输出：若整数b为零，则抛出除零异常，否则输出相除的结果后置条件：整数a的值发生改变Mod前置条件：存在一个整数a输入：一个整数b功能：求当前整数与输入整数的模，即正的余数输出：若整数b为零，则抛出除零异常，否则输出取模的结果后置条件：整数a的值发生改变Equal前置条件：存在一个整数a输入：一个整数b功能：判断整数a与输入的整数b是否相等输出：若相等返回1，否则返回0后置条件：整数a的值不发生改变endADT7 .求多项式A(x)的算法可根据下列两个公式之一来设计：A(x)=anxn+an-1xn-1+a1x+a0
10、A(x)=(anx+an-1)x+a1)x)+a0根据算法的时间复杂度分析比较这两种算法的优劣。【解答】第二种算法的时间性能要好些。第一种算法需执行大量的乘法运算，而第二种算法进行了优化，减少了不必要的乘法运算。8 .算法设计(要求：算法用伪代码和C+的述，并分析最坏情况下的时间复杂度)对一个整型数组An设计一个排序算法。【解答】下面是简单选择排序算法的伪代码描述。港对口个记录进行口1趟蔺单选择排序工y1.1在无序区i，门-1中选取最小记录，设其下标为也加1.2将最小记录与第1个记录交换微卜面是简单选择排序算法的C+的述。简单选择如E序算法elects口汽|voidSeiectSort(int
11、r,intn)farCi0;in-l;i+)第*个记录进行n-l趟简单选择排序(indeH;for(j=+l；卜口,J+)/由无序区中选取最小记录if(rj烟$则A”为最大值，原来的最大值为次最大值二2.2 否则，如果AQnmax,则最大值不变，为次最大,电3,输出最大值max,次最大值nna；算法的C+描述如下:最大值和次最大值算法而x|分析算法，只有一层循环，共执行n-2次，所以，T(n)=O(n)。学习自测及答案1 .顺序存储结构的特点是（），链接存储结构的特点是（）。【解答】用元素在存储器中的相对位置来表示数据元素之间的逻辑关系，用指示元素存储地址的指针表示数据元素之间的逻辑关系。2
12、.算法在发生非法操作时可以作出处理的特性称为（）解答】健壮性3 .常见的算法时间复杂度用大O记号表示为：常数阶()、对数阶()、线性阶()、平方阶()和指数阶()。【解答】O(1),O(log2n),O(n),O(n2),O(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试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的
13、区别。【解答】数据结构是指相互之间存在一定关系的数据元素的集合。而抽象数据类型是指一个数据结构以及定义在该结构上的一组操作。程序设计语言中的数据类型是一个值的集合和定义在这个值集上一组操作的总称。抽象数据类型可以看成是对数据类型的一种抽象。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)所示。图1-4第？题对应的逻辑结构图7.求下列算法的时间复杂度。count=0;x=1;while(xx*=2;count+;returncount;【解答】O(log2n)第2章线性表课后习题讲解
