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