讨论小课堂和习题解答

讨论小课堂 1

1.算法和程序的区别是什么呢？

【参考答案】：算法的含义与程序十分相似，但又有区别。一个程序不一定满足有穷性。例如，操作系统，只要整个系统不遭破坏，它将永远不会停止，即使没有作业需要处理，它仍处于动态等待中。因此，操作系统不是一个算法。另一方面，程序中的指令必须是机器可执行的，而算法中的指令则无此限制。算法代表了对问题的解，而程序则是算法在计算机上的特定的实现。一个算法若用程序设计语言来描述，则它就是一个程序。

算法与数据结构是相辅相承的。解决某一特定类型问题的算法可以选定不同的数据结构，而且选择恰当与否直接影响算法的效率。反之，一种数据结构的优劣由各种算法的执行来体现。

要设计一个好的算法通常要考虑以下的要求。

⑴正确。算法的执行结果应当满足预先规定的功能和性能要求。 ⑵可读。一个算法应当思路清晰、层次分明、简单明了、易读易懂。 ⑶健壮。当输入不合法数据时，应能作适当处理，不至引起严重后果。 ⑷高效。有效使用存储空间和有较高的时间效率。

2，你认为应该如何评估一个数据结构或算法的有效性。

【参考答案】：前提之一是算法的正确性；其二还必须考虑执行算法所耗费的时间和执行算法所耗费的空间（主要是只指辅助空间），以及算法是否易读、易编码和易于调试。

习题1

1. 抽象数据类型的定义由哪几部分组成？ 【参考答案】：数据对象、数据关系和基本操作三部分。 2. 按数据元素之间的逻辑关系不同，数据结构有哪几类？ 【参考答案】：线性结构、树型结构、图状结构和集合四类。 5.数据结构和数据类型两个概念之间有区别吗？

【参考答案】：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

6. 简述线性结构与非线性结构的不同点。 【参考答案】：线性结构反映结点间的逻辑关系是 一对一的，非线性结构反映结点间的逻辑关系是多对多的。 7. 有下列两段描述：

（1）void pro1( ) (2)void pro2( ) { {

n=2; y=0; While(n%2==0) x=5/y;

n=n+2; printf(―%d,%d\\n,x,y); printf(―%d\\n‖,n); }

}

这两段描述均不能满足算法的特征，试问它们违反了算法的那些特征？

【参考答案】：（1）是一个死循环，违反了算法的有穷性特征。（2）出现除零错误，违反了算法的可行性特征。

8. 分析并写出下面的各语句组所代表的算法的时间复杂度。 (1) for (i=0; i

for (j=0; j

A[i][j]=0;

【参考答案】：O（m*n）

(2) k=0;

for( i=1; i<=n; i++) { for (j=i ; j<=n; j++) k++; } 【参考答案】：O（n2）

(3) i=1;

while(i<=n)

i=i*3; 【参考答案】：3 T(n)≤n即：T(n) ≤log3n =O（log3n）所以：T(n)= O（log3n） (4) k=0;

for( i=1; i<=n; i++) { for (j=i ; j<=n; j++)

for (k=j ; k<=n; k++) x += delta;; } 【参考答案】：O（n3）

(5) for(i=0,j=n-1;i

{t=a[i]; a[i]= a[j]; a[i]=t;}

【参考答案】：基本语句共执行了n/2次，T(n)=O（n） (6) x=0;

for(i=1; i

x++;

【参考答案】：因为x++共执行了n-1+n-2+??＋1= n(n-1)/2，所以执行时间为O（n2）

讨论小课堂2

1. 在一个非递减有序线性表中，插入一个值为X的元素，使插入后的线性表仍为非递减有序。（注意：对比顺序存储结构和链式存储结构表示。） 【参考答案】

⑴方法一：顺序存储结构

void insert(ElemType x) { i=length-1;

while(i>=0&&elem[i]>x) {elem[i+1]=elem[i]; i--; }

elem[i+1]=x;length++; }

⑵方法二：链式存储结构 void insert(ElemType x) { NodeType *p,*q,*s;

p=L;q=q->next;

while(q!=NULL&&q->data<=x) {p=q;q=q->next;} s=new NodeType; s->data=x;

p->next=s; s->next=q; }

2.观察下面的算法，此算法完成如下功能：在非递减有序表中删除所有值为X的元素。问：如何改进此算法，使得算法效率提高？

void Deletaz(ElemType x) { int i=0,j;

while (i

{ for(j=I;j

}

}

【答案】

void delete(ElemType x)

{ int i=0,j,n;

while(i

while(elem[i]==x) {n++;i++;} for(j=i;j

3．试设计一个算法，将线性表中前 m 个元素和后 n 个元素进行互换，即将线性表 (a1, , ?, am, b1, b2, ?, bn ) 改变成

(b1, b2, ?, bn, a1, a2, ?, am )

要求采用顺序存储结构及链式存储结构分别完成，并比较采用这两种存储结构，其算法效率哪种存储结构更好？

【答案】试设计一个算法，顺序表中前 m 个元素和后 n 个元素进行互换，即将线性表 (a1, a2, ?, am, b1, b2, ?, bn ) 改变成 (b1, b2, ?, bn, a1, a2, ?, am ) 。

算法 1：进行三次“逆转顺序表”的操作。

算法 2：从 b1开始，从原地删除之后插入到 a1 之前直至 bn。

例如：具体实例：{ a, b, c, d, e, f, g ,1, 2，3，4，5}改变成{1, 2，3，4，5,a, b, c, d, e, f, g}

1 2 3 4 5 a b c d e f g 3 1 2 3 i j a b c d e f g 4 5