2020年《数据结构与算法(徐凤生)》习题答案新版培训教材.doc

《数据结构与算法》习题答案目录第1章——————————————————2第2章——————————————————7第3章——————————————————13第4章——————————————————21第5章——————————————————26第6章——————————————————32第7章——————————————————42第8章——————————————————54第9章——————————————————60第10章——————————————————:数据、数据元素、数据对象、数据结构。解:数据是用于描述客观事物的数值、字符以及一切能够输入到计算机中并由计算机程序加以处理的符号的集合,是计算机操作的对象的总称。数据元素是数据的基本单位,它是数据中的一个“个体”。有时,一个数据元素可有若干数据项组成,。数据项是数据的不可分割的最小单位。数据对象是具有相同性质的数据元素的集合,是数据的一个子集。数据结构是指相互之间存在一种或多种关系的特性相同的数据元素的集合。?两者有何异同?抽象数据类型的主要特点是什么?使用抽象数据类型的主要好处是什么?解:数据类型是一个值的集合和定义在此集合上的一组操作的总称。例如,C语言中的整型变量,其值为某个区间上的整数(依赖于机器),定义在其上的操作为加、减、乘、除和取模等算术运算。抽象数据类型(AbstractDataType,简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。例如,“整数”是一个抽象数据类型,其数学特性和具体的计算机或语言无关。“抽象”的意义在于强调数据类型的数学特性。抽象数据类型和数据类型实质上是一个概念,只是抽象数据类型的范围更广,除了已有的数据类型外,抽象数据类型还包括用户在设计软件系统时自己定义的数据类型。ADT的定义取决于它的一组逻辑特性,与其在计算机内的表示和实现无关。因此,不论ADT的内部结构如何变化,只要其数学特性不变,都不影响其外部的使用。抽象数据类型的最重要的特点是抽象和信息隐蔽。抽象的本质是抽取反映问题本质的东西,忽略非本质的细节,从而使所设计的数据结构更具有一般性,能够解决一类问题。信息隐蔽就是对用户隐蔽数据存储和操作实现的细节,使用者仅需了解抽象操作,或界面服务,经过界面中的服务来访问这些数据。一个含抽象数据类型的软件模块一般应包含定义、表示和实现三部分。?各有什么特点?解:数据元素之间的关系在计算机中有四种不同的表示方法:(1)顺序存储方法。数据元素顺序存放,每个结点只含有一个元素。存储位置反映数据元素间的逻辑关系。存储密度大,但有些操作(如插入、删除)效率较差。(2)链式存储方法。每个结点除包含数据元素信息外还包含一组指针。指针反映数据元素间的逻辑关系。这种操作不要求存储空间连续,便于进行插入和删除等操作,但存储空间利用率较低。另外,由于逻辑上相邻的数据元素在存储空间上不一定相邻,因此不能对其进行随机存取。(3)索引存储方法。除数据元素存储在一地址连续的内存空间外,尚需建立一个索引表。索引表中的索引指示结点的存储位置,兼有动态和静态特性。(4)哈希(或散列)存储方法。经过哈希函数和解决冲突的方法,将关键字散列在连续的有限的地址空间内,并将哈希函数的值作为该数据元素的存储地址。其特点是存取速度快,只能按关键字随机存取,不能顺序存储,也不能折半存取。、五个要素。解:数据结构的三个层次是指抽象、实现和评价三个层次,五个要素是指逻辑结构、存储结构、基本运算、算法和不同数据结构的比较与算法分析五个方面。,说明其逻辑结构、存储结构及其运算三个方面的内容。并说明数据的逻辑结构、存储结构及其运算之间的关系。解:例如复数数据结构,其逻辑结构是复数的表示,而存储结构是指复数在计算机内的表示,运算是指对复数初始化、相加等操作。数据的逻辑结构反映数据元素之间的逻辑关系。数据的存储结构是数据结构在计算机中的表示,包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作,运算是定义在逻辑结构上的,和存储结构无关,而运算的实现则依赖于存储结构。,试给出下列各程序段中标号为@的语句的频度。(1)i=1;while(i<n)***@i=i+2;(2)i=1;k=0;while(i<=n-1){***@k+=10*i;i++;}(3)i=1;k=0;while(i<=n-1){i++;***@k+=10*i;}(4)i=1;j=0;while(i+j<=n){***@if(i>j)j++;elsei++;}(5)x=n;y=0;//n是不小于1的常数while(x>=(y+1)*(y+1)){@