《数据结构(C语言版)》习题指导与解答

《《数据结构(C语言版)》习题指导与解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、附录2习题指导与解答习题一解答1.【解答】数据是人们利川文字符号、数字符号以及其他规定的符号对客观现实世界的事物及其活动所做的抽彖描述。它是计算机程序加工的“原料”。表示一个爭物的一组数据称为一个数据元索，它是数据的基木单位，在计算机中通常作为一个整体來进行考虑和处理。一般情况下，一个数据元索山若干个数据项构成。数据对彖是性质相同的数据元素的集合，是数据的一个子集。例如：描述N个学生的冇关信息的N个数据元索构成了一个数据对象。2.【解答】数据结构是指相互之间存在一种或多种特定关系的数据元索的集合。貝体来说，数据结构包含三个方

2、面的内容，既数据的逻辑结构、数据的存储结构（或称物理结构）和对数据所施加的一组操作。3.【解答】数据的逻辑结构是数据元索Z间木身所周有的独立于计算机的一种结构，这种结构可以用数据元素Z间固冇的关系的集合来描述。数据的存储结构（或物理结构）是逻辑结构在计算机存储器中的具体存放方式的体现，是逻辑结构在计算机存储器中的映像。4.【解答】根据数据元索之间存在的关系的不同特性，数据结构通常可以分为如下4类基本结构：（1）线性结构。元素之间存在一个一对一的线线关系，即除了第一个元素和最后一个元素外，每个元素都有一个直接前驱和一个直接后继

3、，第一个元索有一个后继，最后一个元索有一个直接前驱。例如学生档案管理系统中学生记录Z间的关系即为线性关系；（2）树形结构。数拯元素Z间存在着一个对多个的关系。例如，老师T指导3个硕士研究生Gl,G2,G3；每个研究生Gi（i=l,2,3）乂分别指导3个本科生Sil,Si2,Si3；则数据元素之间的呈现树形结构。（3）图形结构或网状结构。数据元索之间存徃多个对多个的关系。如城市交通网络中城市Z间的交通道路的连接关系就是一个网状结构。（4）集合结构。数据元素Z间无任何关系。5.【解答】抽象数据类型通常是指由用户定义，用以表示实际

4、应用问题的数拥模型，一般由基本数据类型或其他已定义的抽象数据类型以及定义在该模型上的-组操作组成。在C或C++语言中，-般可用struc或直接用“类”來定义抽彖数据类型。6.【解答】算法（Algorithm）是对待定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法分析（Algorithmanalysis）的主要工作是从“时间”和“空间”两个方而来分析算法的效率。7.【解答】算法应具有如下5个重要特性：（1）输入性；（2）输出性；（3）有限性；（4）确定性；（5）可行性；算法设计应满足以下5个

5、基木要求：（1）正确性；（2）可读性；（3）健壮性；（4）高时间效率；（5）高空间效率。8.【解答】（1）当210的时候有210>103,而29<93,故当210时，有2n>n（2）0（n）o（3）因为当n趋向于无穷大时有lim（（2n+n3）/2n）=l,所以2n+n3的同阶数量级是0（2学第2大题略习题二解答1.填空⑴【解答】表长的一半，表长，该元素在表中的位置⑵【解答】144【分析】第5个元素的存储地址=第1个元素的存储地址+(7-1)x4=144⑶【解答】p->next=(p->next)->next⑷【解答】为了

6、运算方便⑸【解答】0(1),0(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为0(1)：而在给定值为x的结点后插入一个新结点船要先查找值为x的结点，所以时间复杂度为0(n)。(6)【解答】两个，直接后继，直接前驱，尾结点，头结点.(7)【解答】顺序2.选择题(1)【解答】A【分析】顺序存储的特点是''逻辑上相邻，物理上也相邻”，所以无需存储元素间的关系,故存储密度大。⑵【解答】D【分析】线性表的链接存储是川一组任意的存储单元存储线性表的数据元索，这组存储单元可以连续，也可以不连续，茯至可以冬散分布在内

7、存中任意位置。⑶【解答】C【分析】因为有prior指针⑷【解答】A【分析】因为单链表属于顺序存储结构⑸【解答】B⑹【解答】B(7)【解答】B(8)【解答】B(9)【解答】B(10)【解答】B【分析】Loc(a6)=Loc(al)+(6-l)5=90+10=1003.简答题(1)【解答】顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。优点：一•般情况下，存储密度大,存储空间利用率高。缺点：a.在做插入和删除操作时，需移动大量元索；b・由于难以估计，必须预先分配

8、佼大的空间，往往使存储空间不能得到充分利用；c.表的容量难以扩充。链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。缺点：存储密度小，存储空间利用率低。(2)【解答】带头结点的单链表和不带