数据结构书本习题答案.docVIP

1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 ● 数据：指能够被计算机识别、存储和加工处理的信息载体。● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。● 逻辑结构：指数据元素之间的逻辑关系。● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。(1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 分析： 　　数学符号O的严格的数学定义： 若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）=O（f（n））表示存在正的常数C和n0，使得当n≥n0时都满足0≤T（n）≤C·f（n）。 　　通俗地说，就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。 　即： 　　　O(f(n))=n3 　　　O(g(n))=n3 　　　O(h(n))=n1.5 　　所以答案为： 答：●（1）成立。 　　　●（2）成立。 　　　●（3）成立。 　　　●（4）不成立。 1.5 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大? 分析：要使前者快于后者，即前者的时间消耗低于后者，即： 　　　　100n22n 　　求解上式，可得 答： n=15 1.6 设n为正整数，利用大O记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0; 　　while(in) 　　　{ k=k+10*i;i++; 　　　} 分析： 　　i=1; //1 　　k=0; //1 　 while(in) //n 　　　{ k=k+10*i; //n-1 　　　　i++; //n-1 　　　} 由以上列出的各语句的频度，可得该程序段的时间消耗： 　　　T(n)=1+1+n+(n-1)+(n-1)=3n 可表示为T(n)=O(n) (2) i=0; k=0; 　　do{ 　　　　k=k+10*i; i++; 　　　} 　　while(in); 分析： 　　i=0; //1 　　k=0; //1 　　do{ //n 　　　　k=k+10*i; //n 　　　　i++; //n 　　　} 　　while(in);//n 由以上列出的各语句的频度，可得该程序段的时间消耗： 　　T(n)=1+1+n+n+n+n=4n+2 可表示为T(n)=O(n) (3) i=1; j=0; 　　while(i+j=n) 　　　{ 　　　　if (ij) j++; 　　　　else i++; 　　　} 分析： 　　通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为： 　　　　T(n)=O(n) (4)x=n; // n1 　while (x=(y+1)*(y+1)) 　　y++; 分析： 　　由x=n且x的值在程序中不变，又while的循环条件(x=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。 　　由(y+1)*(y+1)n得：yn^0.5-1 　　所以，该程序段的执行时间为： 　　　向下取整(n^0.5-1) (5) x=91; y=100; while(y0) 　　　　if(x100) 　　　　　{x=x-10;y--;} 　　　　else x++; 分析： 　　x=91; //1 　　y=100; //1 　　while(y0) //1101 　　　　if(x100) //1100 　　　　　{　x=x-10; //100 　　　　　　y--; //100 　　　　　} 　　　　else 　　　　　x++; //1000 　　以上程序段右侧列出了执行