数据结构课后习题部分参考答案.doc

《数据结构课后习题部分参考答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构课后习题部分参考答案第一章一、选择题1．C2．C　3．A　4．D　5．B二、判断题1．╳2．╳3．╳4．╳　5．∨三、简答题1．常见逻辑结构：集合结构，数据元素之间的关系仅仅是属于同一个集合。线性结构，除第一个元素只有一个直接后继、最后一个元素只有一个直接前驱，其余元素有且只有唯一一个直接前驱、有且只有唯一一个直接后继，数据元素之间存在一对一的关系。树形结构，树中只有唯一一个根元素，除根元素之外，其余元素只有一个直接前驱，但可以有多个直接后继元素，数据元素之间存在一对多的关系。图形结构，元素之间关系任意，数据元素之间存在多对多的关系。常用的存储结构：顺序存储，把

2、逻辑上相邻的元素存储在物理位置相邻的存储单元中，由此得到的存储表示称为顺序存储结构。通常用数组实现。链式存储，对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附加的指针字段来表示，由此得到的存储表示称为链式存储结构。通常用指针来实现。除上述两种方法外，有时为了查找方便还采用索引存储方法和散列存储方法。索引存储：在存储结点信息的同时，还建立附加的索引表来标识结点的地址。散列存储：根据元素的关键码确定元素存储位置的存储方式。2．算法与程序的区别：程序不一定满足有穷性(如操作系统)；程序中的指令必须是机器可执行的，算法中的指令则无此限制；算法代表了对问题的解，程序

3、则是算法在计算机上的特定的实现(一个算法若用程序设计语言来描述，它才是一个程序);数据结构+算法=程序。3．例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据结构。每个记录就是一个结点，对于整个表来说，只有一个开始结点和一个终端结点，其他的结点则各有一个也只有一个直接前趋和直接后继。这几个关系就确定了这个表的逻辑结构——线形结构。那么我们怎样把这个表中的数据存储到里呢?用高级语言如何表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录（顺序存储）还是随机存放各结点数据再用指针进行链接（链式存储）呢?这就是存储结构

4、的问题，我们都是从高级语言的层次来讨论这个问题的。最后，我们有了这个表，肯定要用它，那么就是要对这张表中的记录进行查询，修改，删除等操作，对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。4．例如栈和队列，两个数据结构的逻辑结构和存储方式完全相同，只是对于运算（如插入、删除）的定义不同，两个结构具有显著不同的特性。5．语句频度（1）n-1（2）1（3）n(n+1)/2（4）n/2-1（5）1006．时间复杂度（1）O(log3n)（2）O(n2)（3）O(n2)7．算法思想：P(x，n)=(…((anx+an-1)x+an-2)x+…+a1)x+a0语句

5、：y=0;for(i=n;i>=0;i--)y=y*x+ai;函数：voidp(){floatx,y;intn,i,a;scanf("%f",&x);scanf("%d",&n);y=0;for(i=n;i>=0;i--){scanf("%d",&a);y=y*x+a;}printf("x=%4.2f,y=%6.4f",x,y);}第二章一、选择题1．A2．A　3．D　4．C　5．D6．B7．C　8．B　9．A　10．D11．B12．D二、判断题1．╳2．∨3．╳4．∨　5．╳　　6．∨　7．╳8．∨　9．∨　10．╳11．╳　12．╳三、算法设计题1．第一种方法（从后

6、往前比较）：因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后，插入该位置后面即可。　　在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，插入x的位置i+1也空出来了。　　算法如下：voidInsertIncreaseList1(seqlist*L,datatypex){inti;if(L->elemnum==maxsize)printf("overflow");//L->elemnum中存放当前顺序表中的元素个数for(i=L->elemnu

7、m-1;i>=0&&L->data[i]>x;i--)L->data[i+1]=L->data[i];//从后往前比较并移动元素L->data[i+1]=x;L->elemnum++;}第二种方法（从前往后比较）：voidInsertIncreaseList2(seqlist*L,datatypex){inti,j;if(L->elemnum==maxsize)printf("overflow");i=0;while((i<=L->elemnum-1)&&(L->data[i]