第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)/2 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） 通过参数表中的参数显式传递； （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)/6 1.4 试...
