《数据结构课后习题及解析第一章.docx》由会员分享，可在线阅读，更多相关《数据结构课后习题及解析第一章.docx（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构课后习题及解析第一章第一章习题一、问答题1 .什么是数据结构？2 .叙述四类基本数据结构的名称与含义。3 .叙述算法的定义与特性。4 .叙述算法的时间复杂度。5 .叙述数据类型的概念。6 .叙述线性结构与非线性结构的差别。7 .叙述面向对象程序设计语言的特点。8 .在面向对象程序设计中，类的作用是什么？9 .叙述参数传递的主要方式及特点。10 .叙述抽象数据类型的概念。二、判断题（在各题后填写“ V ”或者“某”）1 .线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来 存放。（）2 .算法就是程序。3 .在高级语言（如C或者PASCAL）中，指针类型是原子类型。（）三、计算下
2、列程序段中某二某+1的语句频度for (i=l;i=n;i+)for(j=l;j=i;j+)for (k=l;k=j;k+)某二某+1；四、试编写算法，求一元多项式Pn (某)二a+a某+a2某2+a3某3+an某n的值Pn集),并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能 小，规定算法中不能使用求幕函数。注意：本题中的输入ai(i=0, 1,n),某和n,输出为Pn集)o通常算法的输入和输出可采用下列两种方式之一：(1)通过参数表中的参数显式传递。(2)通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方 式实现输入和输出。实习题
3、设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减 法、乘法、除法，以及求有理数的份子、分母。第一章答案1. 3计算下列程序中某二某+1的语句频度for (i=l;i=n;i+)for(j=l;j=i;j+)for (k=l;k=j;k+)某二某+1 ；【解答】某二某+1的语句频度为：T (n) -1 + (1 +2) + (1+2+3)+(1 +2+n)-n (n+1) (n+2) /61. 4试编写算法，求pn (某)=aO+al某+a2某2+ +an某n的值pn(某0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算 法中不能使用求累函数。
4、注意：本题中的输入为ai(i=0, 1,-n),某和n, 输出为Pn(某0)。算法的输入和输出采用下列方法通过参数表中的 参数显式传递(2)通过全局变量隐式传递。讨论两种方法的优缺点，并 在算法中以你认为较好的一种实现输入输出。【解答】(1)通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实 参维持，函数通用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。(2)通过全局变量隐式传递优点：减少实参预形参的个数，从而减少内存空间以及传递数据时的 时间消耗缺点：函数通用性降低，移植性差算法如下：通过全局变量隐式传递参数PolyValue () inti,
5、 n;float 某，a, p;printf( nn=);canf ( %f , &n);printf ( n 某二);canf(，&某);for(i=0;in;i+)canf ( f”;/某执行次数:n 次某/p=a0;for (i=l;i=n;i+)p=p+ai某某;/某执行次数：n次某/某二某某某;printf ( %f ，p);)算法的时间复杂度：T (n) =0 (n)通过参数表中的参数显式传递floatPolyValue(floata, float 某，intn)floatp,;inti;P二某； =a0;for (i=1;i=n;i+)二+ai某p;/某执行次数:n次某/P=P某
6、某;return (p);)算法的时间复杂度：T (n) =0 (n)提示：第1章绪论习题一、问答题1 .什么是数据结构？2 .四类基本数据结构的名称与含义。3 .算法的定义与特性。4 .算法的时间复杂度。5 .数据类型的概念。6 .线性结构与非线性结构的差别。7 .面向对象程序设计语言的特点。8 .在面向对象程序设计中，类的作用是什么?9 .参数传递的主要方式及特点。10 .抽象数据类型的概念。二、判断题1 .线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来 存放。2 .算法就是程序。3 .在高级语言(如C、或者PASCAL)中，指针类型是原子类型o三、计算下列程序段中某二某+1的
7、语句频度for (i=l;i=n;i+)for(j=l;j=i;j+)for (k=l;k=j;k+)某二某+1；提示:i=1 时：仁(1+1)某 1/2= (1+12)/2i=2 时：1+2=(1+2)某 2/2=(2+22)/2i=3 时：1+2+3=(1+3)某 3/2= (3+32) /2 i=n 时：1+2+3+n=(1+n)某 n/2=(n+n2)/2f (n)=(1 +2+3+n)+ (12+22+32+n2) /2=(1 +n) n/2+n (n+1) (2n+1)/6/2 =n (n+1) (n+2)/6=n3/6+n2/2+n/3区分语句频度和算法复杂度：0 (f (n)
8、=0 (n3)四、试编写算法求一元多项式Pn (某)=a0+a1某+a2某2+a3某3+an某n 的值Pn (某0),并确定算法中的每一语句的执行次数和整个算法的时间复 杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幕函数。注意: 本题中的输入1(匚0,1二川)，某和n,输出为Pn(某0).通常算法的输入 和输出可采用下列两种方式之一：(1)通过参数表中的参数显式传递；(2)通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方 式实现输入和输出。提示:floatPolyValue(floata, float 某，intn) 核心语句：P=l；(某的零次幕)二0；i从。至lj n循环二+ai某 P；P=P某某；或者：P二某；(某的一次幕)=a0;i从1至lj n循环二+ai某 p;P=P某某；实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减 法、乘法、除法，以及求有理数的份子、分母。