数据构造课后习题答案.docx

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

1、数据构造课后习题答案第1章绪论一、基础知识题1.1简述下列概念数据，数据元素，数据类型，数据构造，逻辑构造，存储构造，算法。【解答】数据是信息的载体，是描绘客观事物的数、字符，以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。在不同的条件下，数据元素又可称为元素、结点、顶点、记录等。数据类型是对数据的取值范围、数据元素之间的构造以及允许施加操作的一种总体描绘。每一种计算机程序设计语言都定义有本人的数据类型。“数据构造这一术语有两种含义，一是作为一门课程的名称；二是作为一个科学的概念。作为科学概念，目前尚无公认定义，一般以为，讨论数据构造要包括三个方面，一是

2、数据的逻辑构造，二是数据的存储构造，三是对数据进行的操作运算。而数据类型是值的集合和操作的集合，能够看作是已实现了的数据构造，后者是前者的一种简化情况。数据的逻辑构造反映数据元素之间的逻辑关系即数据元素之间的关联方式或“邻接关系，数据的存储构造是数据构造在计算机中的表示，包括数据元素的表示及其关系的表示。数据的运算是对数据定义的一组操作，运算是定义在逻辑构造上的，和存储构造无关，而运算的实现则依靠于存储构造。数据构造在计算机中的表示称为物理构造，又称存储构造。是逻辑构造在存储器中的映像，包括数据元素的表示和关系的表示。逻辑构造与计算机无关。算法是对特定问题求解步骤的一种描绘，是指令的有限序列。

3、其中每一条指令表示一个或多个操作。一个算法应该具有下列特性：有穷性、确定性、可行性、输入和输出。1.2数据的逻辑构造分哪几种，为什么讲逻辑构造是数据组织的主要方面？【解答】数据的逻辑构造分为线性构造和非线性构造。可以以分为集合、线性构造、树形构造和图形即网状构造。逻辑构造是数据组织的某种“本质性的东西：1逻辑构造与数据元素本身的形式、内容无关。2逻辑构造与数据元素的相对位置无关。3逻辑构造与所含数据元素的个数无关。1.3试举一个数据构造的例子，叙述其逻辑结构、存储构造、运算三方面的内容。【解答】学生成绩表，逻辑构造是线性构造，可以顺序存储可以以链式存储，运算能够有插入、删除、查询，等等。1.4

4、简述算法的五个特性，对算法设计的要求。【解答】算法的五个特性是：有穷性、确定性、可行性、零至多个输入和一至多个输出。对算法设计的要求：正确性，易读性，强健性，和高的时空间效率运算速度快，存储空间小。1.5设n是正整数，求下列程序段中带记号的语句的执行次数。(1)i=1;k=0;(2)i=1;j=0;while(ij)j+;elsei+;(3)x=y=0;(4)x=91;y=100;for(i=0;iwhile(y0)for(j=0;j100)x+;x=x-10;y-;for(k=0;k4时，算法A2好于A1。1.7选择题：算法分析的目的是A、找出数据构造的合理性B、研究算法中的输入和输出的关系

5、C、分析算法的效率以求改良D、分析算法的易懂性和文档特点【解答】C二、算法设计题1.8已知输入x，y，z三个不相等的整数，设计一个“高效算法，使得这三个数按从小到大输出。“高效的含义是用最少的元素比拟次数、元素移动次数和输出次数。【算法1.8】voidBest()/按序输出三个整数的优化算法inta,b,c,t;scanf(“%d%d%d,&a,if(ab)t=a;a=b;b=t:/a和b已正序if(bc)t=c;c=b;/c已到位if(at)b=a;a=t;/a和b已正序elseb=t;printf(“%d,%d,%dn,a,b,c);/最佳2次比拟，无移动；最差3次比拟，7个赋值1.9在数

6、组An中查找值为k的元素，若找到则输出其位置i(1in)，否则输出0作为标志。设计算法求解此问题，并分析在最坏情况下的时间复杂度。【题目分析】从后向前查找，若找到与k值一样的元素则返回其位置，否则返回0。【算法1.9】intSearch(ElemTypeAn+1,ElemTypek)i=n;while(i=1)&(Ai!=k)i-;if(i=1)returni;elsereturn0;当查找不成功时，总的比拟次数为n+1次，所以最坏情况下时间复杂度为O(n)。在学过第9章“查找后，可优化以上算法:设“监视哨。算法如下：intSearch(ElemTypeAn+1,ElemTypek)i=n;A

7、0=k;while(Ai!=k)i-;returni;研究表明，当n=1000时，算法效率提高50%。第2章线性表一、基础知识题2.1试述头指针、头结点、元素结点、首元结点的区别，讲明头指针和头结点的作【解答】指向链表第一个结点或为头结点或为首元结点的指针称为头指针。“头指针具有标识一个链表的作用，所以经常用头指针代表链表的名字，如链表L既是指链表的名字是L，也是指链表的第一个结点的地址存储在指针变量L中，头指针为“NULL则表示指针变量L没指向任何链表。有时，我们在整个线性链表的第一个元素结点之前参加一个结点，称为头结点，它的数据域能够不存储任何信息当然，作为“副产品，头结点的数据域可以能做

8、监视哨或存放线性表的长度等附加信息，指针域中存放的是第一个数据结点的地址，空表时为空。“头结点的参加，使插入和删除等操作方便、统一。元素结点即是数据结点，至少包括元素本身信息和其后继元素的地址两个域。首元结点是指链表中第一个数据元素的结点；为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点。2.2分析顺序存储构造和链式存储构造的优缺点，讲明何时应该利用何种构造。【解答】从空间上来看，当线性表的长度变化较大，难以估计其规模时，选用动态的链表作为存储构造比拟适宜。由于链表除了需要设置数据域外，还要额外设置指针域，因而当线性表长度变化不大，易于事先确定规模时，为了节约存储空间，宜采用顺序存储构造。从时间上看，顺序表具有按元素序号随机访问的特点，在顺序表中按序号访问数据元素的时间复杂度为O(1)；而链表中按序号访问的时间复杂度为O(n)。所以假如经常按序号访问数据元素，使用顺序表优于链表。在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因而n较大时顺序表的插入和删除效率低。在链表中作插入、删除，固然也要找插入位