数据结构课后习题答案（修订版）

习题一答案

1． 填空题

（1） 数据元素的有限集合，k上关系的有限集合 （2） 顺序存储（连续），链式存储（不连续） （3） 有穷性，确定性，可行性，输入，输出 （4） 时间复杂度，空间复杂度

2．简述下列术语

（1） 数据——是信息的载体，它是描述客观事物的数、字符以及所有能输入到计算

机中被计算机程序识别、加工处理的信息的集合。

（2） 数据元素——是数据的基本单位 ，是对一个客观实体的数据描述。一个数据元

素可以由一个或若干个数据项组成。数据元素也被称为结点或记录。

（3） 数据对象——具有相同性质的数据元素的集合就是一个数据对象，它是数据的

一个子集。 （4） 数据结构——数据结构就是数据之间的相互关系（即数据的组织形式）及在这

些数据上定义的数据运算方法的集合。 （5） 存储结构——数据的存储结构是数据的逻辑结构在计算机内部的表示或实现，

又称为数据的物理结构，它包括数据元素的表示和关系的表示。

（6） 数据类型——是具有相同性质的计算机数据的集合及定义在这个数据集合上的

一组操作的总称。

3.举例说明一下数据结构和算法的关系。

通过公式：程序=数据结构+算法 我们可以比较直观地看出二者的关系，即数据结构（包个完整的程序括逻辑结构和存储结构）的设计和算法的编写是程序设计的两个关键步骤，一就是由一套合理的数据结构和建立在该结构上的算法构成的。具体的说：在进行程序设计之前我们首先要为待处理的数据设计一个合理的逻辑结构，进而为之设计一种适合的存储结构，因为光有逻辑结构是不够的，只有存储结构才是与计算机语言直接相关的！有了这一套前期准备，我们才能在这个基础上设计算法，用一种计算机语言去处理这些数据，最终达到程序设计的目的。当然，随着逻辑结构和存储结构的不同，我们设计的算法也会有所差别，这在以后的学习中会体会到。下面通过一个简单的例子说明这种关系。

假设我们要设计一个两个n阶方阵相乘的程序：已知两个n阶方阵A和B，我们要计算它们的乘积，得到一个新的n阶方阵C。那么在设计这个程序之前首先想到得就是设计一种逻辑结构表示方阵，这里我们用二维数组表示它们，因为二维数组最能直观地表示这种结构；有了逻辑结构了自然还要为之设计一种存储结构，这里我们选择顺序存储方法，因为C语言对这种存储结构给予了很好的支持，例如定义一个n阶实型的二维数组A只要用float A[n][n]; 这条语句就可以了，C语言在内存种为之分配了一个n*n长度的顺序存储空间（注意：C语言默认二维数组是按行优先存储的），是不是很方便？有了这些准备，我们就可以设计算法进行计算了，其算法如下：

void matrixmult ( float A[n][n], float B[n][n], float C[n][n] ) {

}

int i , j , k ; float x ;

for ( i=0; i

for ( j=0; j

x=0;

for ( k=0; k

x+=A[i][k]*B[k][j]; }

C[i][j]=x; } }

通过上面这个例子我们简单的阐述了数据结构与算法的关系，更深入的内涵还要读者在以后的学习中自己慢慢地体会。

4．设有数据逻辑结构为B=（K，R），K={k1，k2，……，k9} r={,,,,,,,,, ,} 画出这个逻辑结构的图示，并确定相对于r哪些结点是开始结点，哪些结点是终端结点？

通过以后的学习我们会知道这是一个有向图，图中共有9个结点，其中开始结点有2个，分别为K1和K2；终端结点有2个，分别为K6和K7。 逻辑结构图表示如下：

k1 k2 k4 k3 k5 k6 k8 k9 k7

7．何谓算法？试详述算法设计的目的和算法必须满足的条件。

算法是对特定问题求解步骤的一种描述，实际上是指令的有限序列，其中每一条指令表示一个或多个操作。我们知道，程序设计的第一步是为待处理的数据设计一种合理的数据结构（包括逻辑结构和物理结构），这一步固然重要，但这不是我们的目的，设计数据结构的最终目的是为了在这个基础上编写算法进而对其进行相关的操作（例如：遍历，查找，排序，插入，删除等），如果不去编写

相应的算法那么设计数据结构也就失去了它的意义，你所输入到计算机的数据永远都是―死数据‖，程序设计也就成了空谈！一句话：设计数据结构的目的是为了对它们进行处理，而数据处理正是通过相应的算法实现的！

总的来说，一个算法应具有以下5个重要特性：第一，有穷性：一个算法必须总是（对任何合法的输入值）在执行有穷步之后结束，且每一步都可在有穷时间内完成；第二，确定性：算法中每条指令必须有确切的含义，读者理解时不会产生二意性。并且，在任何条件下，算法只有唯一的一条执行路径，即对相同的输入只能得到相同的输出；第三，可行性：一个算法是能行的，即算法中描述的操作都是通过已经实现的基本运算执行有限次来实现的；第四，输入：一个算法有零个或多个的输入，这些输入取自于某个特定的对象的集合；第五，输出：一个算法有一个或多个的输出。这些输出是同输入有着某些特定关系的量。 8．编写一个算法，对三个两位数按由大到小的顺序进行排序，描述构造该算法的思维程。 算法如下：

void order(short a, short b, short c) {

short t;

if (a

printf(“%d %d %d\\n”, a, b, c);

}

算法对主函数传递过来的三个短整形变量（由于输入三个两位整数，所以定义短整形就足够了）两两进行比较，如果前面的数小于后面的数的话则进行交换，交换的中间变量用t来存放，交换的最后结果是三个变量由大到小排列，最后将结果打印输出。

习题二答案

1． 填空题

（1）顺序存储结构 顺序存储结构

链式存储结构

顺序存储结构 链式存储结构

（2）p->next=p->next->next;

（3）Head->next= =Head（Head为链表的头结点），Head= =NULL（Head为链表的第一个结点）

（4）Head->next=Head->next->next（Head为链表的头结点）；Head=Head->next（Head为链表的第一个结点），以上均假设链表存在至少两个结点。

（5）D（因为顺序表具有随即存取的优点）

2．动态与静态数据结构在计算机内存中的存储方式有何不同？各有何优缺点？

参考答案：

静态存储方式（顺序存储）——逻辑相邻，物理相邻。优点：便于数据的随即存取，结点存储利用率高（不需要存储指针）；缺点：存取数据时要移动大量的元素，由于事先不知道存储结点的最大个数，所以应该分配尽可能大的存储空间，从而可能会造成空间浪费！

动态存储方式（链式存储）——逻辑相邻，物理不一定相邻。优点：动态分配和释放存储单元，避免了空间浪费，插入删除结点不需要移动大量的其他结点，只需要修改有限的指针变量；缺点：不具备顺序存储结构随即存取的优点，查找结点需要从表头开始，一个结点的存储利用率较低，以为每个结点都要存储一个指向下个结点的指针变量。 3．描述以下三个概念的区别：头指针、头结点、 …… 此处隐藏：2374字，全部文档内容请下载后查看。喜欢就下载吧 ……