数据构造课后习题部分参考答案.docx

《数据构造课后习题部分参考答案.docx》由会员分享，可在线阅读，更多相关《数据构造课后习题部分参考答案.docx（12页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据构造课后习题部分参考答案数据构造课后习题部分参考答案第一章一、选择题1C2C3A4D5B二、判定题12345三、简答题1常见逻辑构造：集合构造，数据元素之间的关系仅仅是属于同一个集合。线性构造，除第一个元素只要一个直接后继、最后一个元素只要一个直接前驱，其余元素有且只要唯逐一个直接前驱、有且只要唯逐一个直接后继，数据元素之间存在一对一的关系。树形构造，树中只要唯逐一个根元素，除根元素之外，其余元素只要一个直接前驱，但能够有多个直接后继元素，数据元素之间存在一对多的关系。图形构造，元素之间关系任意，数据元素之间存在多对多的关系。常用的存储构造：顺序存储，把逻辑上相邻的元素存储在物理位置相邻的

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

3、，它才是一个程序);数据构造+算法=程序。3例如有一张学生成绩表，记录了一个班的学生各门课的成绩。按学生的姓名为一行记成的表。这个表就是一个数据构造。每个记录就是一个结点，对于整个表来讲，只要一个开场结点和一个终端结点，其他的结点则各有一个也只要一个直接前趋和直接后继。这几个关系就确定了这个表的逻辑构造线形构造。那么我们如何把这个表中的数据存储到里呢?用高级语言怎样表示各结点之间的关系呢?是用一片连续的内存单元来存放这些记录顺序存储还是随机存放各结点数据再用指针进行链接链式存储呢?这就是存储构造的问题，我们都是从高级语言的层次来讨论这个问题的。最后，我们有了这个表，肯定要用它，那么就是要对这张

4、表中的记录进行查询，修改，删除等操作，对这个表能够进行哪些操作以及怎样实现这些操作就是数据的运算问题了。4例如栈和队列，两个数据构造的逻辑构造和存储方式完全一样，只是对于运算如插入、删除的定义不同，两个构造具有显著不同的特性。5语句频度1n-1213n(n+1)/24n/2-151006时间复杂度1O(log3n)2O(n2)3O(n2)7算法思想：P(x，n)=(anx+an-1)x+an-2)x+a1)x+a0语句：y=0;for(i=n;i=0;i-)y=y*x+ai;函数：voidp()floatx,y;intn,i,a;scanf(%f,scanf(%d,y=0;for(i=n;i=

5、0;i-)scanf(%d,y=y*x+a;printf(x=%4.2f,y=%6.4f,x,y);第二章一、选择题1A2A3D4C5D6B7C8B9A10D11B12D二、判定题123456789101112三、算法设计题1第一种方法从后往前比拟：因已知顺序表L是递增有序表，所以只要从顺序表终端结点设为i位置元素开场向前寻找到第一个小于或等于x的元素位置i后，插入该位置后面即可。在寻找经过中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，插入x的位置i+1也空出来了。算法如下：voidInsertIncreaseList1(seqlist*

6、L,datatypex)inti;if(L-elemnum=maxsize)printf(overflow);/L-elemnum中存放当前顺序表中的元素个数for(i=L-elemnum-1;i=0&L-dataix;i-)L-datai+1=L-datai;/从后往前比拟并移动元素L-datai+1=x;L-elemnum+;第二种方法从前往后比拟：voidInsertIncreaseList2(seqlist*L,datatypex)inti,j;if(L-elemnum=maxsize)printf(overflow);i=0;while(ielemnum-1)&(L-dataiele

7、mnum-1;j=i;j-)L-dataj+1=L-dataj;/腾位置L-datai=x;/插入L-elemnum+;2思路同算法2-166同1类似，最好也做一下。1是顺序存储，6是链式存储。做完同1比拟一下7看算法2-17,尾插实现第三章一、选择题1C2B3D4B5B6C7B8D9C10C二、判定题12345三、简答题1循环队列的优点是：它能够克制顺序队列的假上溢现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的空或满通常有两种方法：1另设一个变量num记录当前队列中的元素个数,当num=0时队空，num=maxsize时队满。2少用一个存储单元(即少存一个元素),队空条件为fr

8、ont=rear，队满条件为(rear+1)%maxsize=front。2栈的特点是先进后出，队列的特点是先进先出。先进后出用栈；先进先出用队列。3一个直接调用本人或通过一系列调用间接调用本人的经过称为递归。递归程序构造明晰，可读性强，而且容易用数学归纳法来证实程序的正确性。递归程序运行效率低，不管是消耗的计算时间还是占用的存储空间都比非递归程序要多。41234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321十四种可能四、算法设计题1思想：将一半字符入栈)算法为：/下面为顺序栈的存储构造定义#defineSta

9、ckSize100/假定预分配的栈空间最多为100个元素typedefcharDataType;/假定栈元素的数据类型为字符typedefstructDataTypedataStackSize;inttop;SeqStack;intIsHuiwen(char*t)/判定t字符向量能否为回文，若是，返回1，否则返回0SeqStacks;inti,len;chartemp;InitStack(len=strlen(t);/求向量长度for(i=0;iifEmptyStack(&s)return1;/匹配，返回1elsereturn0;/不匹配，返回0第五章一、选择题1C2C3.B4B5B6C7B8D9A10D11D12C13B14D15B二、判定题1234567891011.12.1314151617181920三、简答题1一棵度为2的树与一棵二叉树的区别在于:度为2的树有两个分支，没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右不能交换。树与二叉树的区别：1二叉树的一个结点至多有两个子树，树形则不然。2树中的结点只要一个子树时，无须区分其是左子树还是右子树；而二叉树中的结点只要一个子树时，必需确定其是左子树还是右子树。212当前位置：文档视界数据构造课后习题部分参考答案数据构造课后习题部分参考答案