《数据结构——C语言描述》习题及答案-耿国华

第 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++） for(j=1；j〈=i;j++)for(k=1;k〈=j；k++） x=x+1;［提示]： i=1 时： 1 = （1+1）×1/2 = (1+12）/2 i=2 时: 1+2 = （1+2)×2/2 = （2+22）/2 i=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区分语句频度和算法复杂度：O（f(n)） = O(n3)四、试编写算法求一元多项式 Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值 Pn（x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小,规定算法中不能使用求幂函数。注意：本题中的输入 ai(i=0,1，…，n）, x 和 n，输出为 Pn(x0）.通常算法的输入和输出可采纳下列两种方式之一：（1）通过参数表中的参数显式传递；（2）通过全局变量隐式传递。试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。[提示]：float PolyValue(float a［ ］, float x， int n) {……｝核心语句：p=1; (x 的零次幂)s=0;i 从 0 到 n 循环s=s+a[i］*p； p=p*x； 或：p=x; (x 的一次幂）s=a［0]；i 从 1 到 n 循环s=s+a［i]＊p； p=p*x; 实习题设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。第一章答案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)，...