第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;
[提示]：
  　c语言中structi=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试编写算法，求pn(x)=a0+a1x+a2x2+…….+anxn的值pn(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为ai(i=0,1,…n)、x和n,输出为Pn(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<= L－>last;  m++)
    L－>elem[ m－k ] = L－>elem[ m ];
< 方法2 > 同时以待移动元素下标m和应移入位置j为中心：
< 方法3 > 以应移入位置j为中心，计算待移动元素下标：
2.6已知线性表中的元素（整数）以值递增有序排列，并以单链表作存储结构。试写一高效算法，删除表中所有大于mink且小于maxk的元素（若表中存在这样的元素），分析你的算
法的时间复杂度（注意：mink和maxk是给定的两个参变量，它们的值为任意的整数）。
[提示]：注意检查mink和maxk的合法性：mink < maxk

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