第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;
[提示]：
1/2 = = (1+12)/2
i=1时：1 = (1+1)×1/2
2/2 = = (2+22)/2
i=2时：1+2= (1+2)×2/2
3/2 = = (3+32)/2
i=3时：1+2+3= (1+3)×3/2
…
n/2 = = (n+n2)/2
i=n时：1+2+3+……+n= (1+n)×n/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+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算
法中不能使用求幂函数。注意：本题中的输入a i
(i=0,1,…,n), x和n，输出为P
n
(x
)通常算
法的输入和输出可采用下列两种方式之一：
法的输入和输出可采用下列两种方式之一：
（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试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0)，并确定算法中每一语句的执
行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n，输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。
点，并在算法中以你认为较好的一种实现输入输出。
【解答】
【解答】
）通过参数表中的参数显式传递
（1）通过参数表中的参数显式传递
优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通
用性强，移置性强。
用性强，移置性强。
缺点：形参须与实参对应，且返回值数量有限。
缺点：形参须与实参对应，且返回值数量有限。
（2）通过全局变量隐式传递
）通过全局变量隐式传递
优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗
缺点：函数通用性降低，移植性差
缺点：函数通用性降低，移植性差
算法如下：通过全局变量隐式传递参数
算法如下：通过全局变量隐式传递参数
PolyValue()
{ int i,n;
float x,a[],p;
printf(“\nn=”);
scanf(“%f”,&n);
printf(“\nx=”);
scanf(“%f”,&x);
for(i=0;i<n;i++)
scanf(“%f ”,&a[i]); /*执行次数：n次*/
p=a[0];
for(i=1;i<=n;i++)
{ p=p+a[i]*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[0];
for(i=1;i<=n;i++)
{s=s+a[i]*p;            /*执行次数:n 次*/
p=p*x;}
return(p);
}
算法的时间复杂度：T(n)=O(n)
第2章 线性表
习  题
2.1
描述以下三个概念的区别：头指针，头结点，首元素结点。描述以下三个概念的区别：头指针，头结点，首元素结点。  2.2 填空：填空：
（1） 在顺序表中插入或删除一个元素，需要平均移动在顺序表中插入或删除一个元素，需要平均移动＿＿一半＿＿＿＿一半＿＿元素，具体移动的元
素个数与素个数与＿＿插入或删除的位置＿＿＿＿插入或删除的位置＿＿有关。有关。
（2） 在顺序表中，逻辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。在单链表中，逻
辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。辑上相邻的元素，其物理位置＿＿＿＿＿＿相邻。
（3） 在带头结点的非空单链表中，头结点的存储位置由＿＿＿＿＿＿指示，首元素结点的存储位置由＿＿＿＿＿＿指示，除首元素结点外，其它任一元素结点的存储位置
由＿＿其直接前趋的next 域＿＿指示。
2.3 已知L 是无表头结点的单链表，且P 结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。要求从下列语句中选择合适的语句序列。
a. 在P 结点后插入S 结点的语句序列是：结点的语句序列是：＿（＿（4）
、（1）＿。 b. 在P 结点前插入S 结点的语句序列是：（7）、（11）、（8）、（4）、（1）。
c. 在表首插入S 结点的语句序列是：（5）、（12）。
d. 在表尾插入S 结点的语句序列是：（11）、（9）、（1）、（6）。
供选择的语句有：供选择的语句有：
（1）P->next=S;
（2）P->next= P->next->next;
（3）P->next= S->next;
（4）S->next= P->next;
（5）S->next= L;
（6）S->next= NULL;
（7）Q= P;
（8）while(P->next!=Q) P=P->next;
（9）while(P->next!=NULL) P=P->next;
（10）P= Q;
（11）P= L;
（12）L= S;
（13）L= P;
2.4 已知线性表L 递增有序。试写一算法，将X 插入到L 的适当位置上，以保持线性表L 的有序性。的有序性。
[提示]：void  insert(SeqList  *L;  ElemType  x)
< 方法1 >
（1）出应插入位置i ，（2）移位，（3）……
< 方法2 > 参P . 229
2.5 写一算法，从顺序表中删除自第i 个元素开始的k 个元素。个元素。
[提示]：注意检查i 和k 的合法性。的合法性。  （集体搬迁，
“新房”、“旧房”） < 方法1 > 以待移动元素下标m （“旧房号”）为中心，为中心，
计算计算应移入位置（应移入位置（
“新房号”）：  for ( m= i －1+k ;  m<= m<= L L －>last ;  m++)
L －>elem[ >elem[ m m －k  ] = L －>elem[ >elem[ m m  ];
< 方法2 > 同时以同时以待移动元素下标待移动元素下标m 和应移入位置j 为中心：为中心：
< 方法3 > 以应移入位置j 为中心，计算为中心，计算待移动元素下标待移动元素下标：

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。