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

数据结构（C语言版） 附录2 习题指导与解答 附录2 习题指导与解答 习题一解答 1． 数据是人们利用文字符号、数字符号以及其他规定的符号对客观现实世界的事物及其活动所做的抽象描述。它是计算机程序加工的“原料”。表示一个事物的一组数据称为一个数据元素，它是数据的基本单位，在计算机中通常作为一个整体来进行考虑和处理。一般情况下，一个数据元素由若干个数据项构成。数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：描述N个学生的有关信息的N个数据元素构成了一个数据对象。 2． 数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。具体来说，数据结构包含三个方面的内容，既数据的逻辑结构、数据的存储结构（或称物理结构）和对数据所施加的一组操作。 3．数据的逻辑结构是数据元素之间本身所固有的独立于计算机的一种结构，这种结构可以用数据元素之间固有的关系的集合来描述。数据的存储结构（或物理结构）是逻辑结构在计算机存储器中的具体存放方式的体现，是逻辑结构在计算机存储器中的映像。 4．根据数据元素之间存在的关系的不同特性，数据结构通常可以分为如下4类基本结构： （1）线性结构。元素之间存在一个一对一的线线关系，即除了第一个元素和最后一个元素外，每个元素都有一个直接前驱和一个直接后继，第一个元素有一个后继，最后一个元素有一个直接前驱。例如学生档案管理系统中学生记录之间的关系即为线性关系； （2）树形结构。数据元素之间存在着一个对多个的关系。例如，老师T指导3个硕士研究生G1，G2，G3；每个研究生Gi（i=1,2,3）又分别指导3个本科生Si1，Si2，Si3；则数据元素之间的呈现树形结构。 (3)图形结构或网状结构。数据元素之间存在多个对多个的关系。如城市交通网络中城市之间的交通道路的连接关系就是一个网状结构。 （4）集合结构。数据元素之间无任何关系。 5．抽象数据类型通常是指由用户定义，用以表示实际应用问题的数据模型，一般由基本数据类型或其他已定义的抽象数据类型以及定义在该模型上的一组操作组成。在C或C++语言中，一般可用struc或直接用“类”来定义抽象数据类型。 6．算法（Algorithm）是对待定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。算法分析（Algorithm analysis）的主要工作是从“时间”和“空间”两个方面来分析算法的效率。 7．算法应具有如下5个重要特性： （1）输入性；（2）输出性；（3）有限性；（4）确定性；（5）可行性； 算法设计应满足以下5个基本要求： （1）正确性；（2）可读性；（3）健壮性；（4）高时间效率；（5）高空间效率。 8．（1）当n=10的时候有210103，而2993，故当n≥10时，有2nn3。 （2）O(n)。 （3）因为当n趋向于无穷大时有lim((2n+n3)/ 2n)=1，2n+n3的同阶数量级是O(2n)。 第2大题略 习题二解答 1. 填空 ⑴表长的一半，表长，该元素在表中的位置 ⑵144 第5个元素的存储地址=第1个元素的存储地址＋(7－1)×4=144 ⑶p-next=(p-next)-next ⑷为了运算方便 ⑸Ο(1)，Ο(n) 在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。 (6) 两个, 直接后继 , 直接前驱 , 尾结点, 头结点. （7）顺序 2. 选择题 ⑴ A 顺序存储的特点是“逻辑上相邻，物理上也相邻”，所以无需存储元素间的关系，故存储密度大。 ⑵D 线性表的链接存储是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以连续，也可以不连续，甚至可以零散分布在内存中任意位置。 ⑶C 因为有prior指针 ⑷A 因为单链表属于顺序存储结构 ⑸B ⑹B （7）B （8）B （9）B （10）B Loc(a6)=Loc(a1)+(6-1)*5=90+10=100 3.简答题 (1) 顺序结构存储时，相邻数据元素的存放地址也相邻，即逻辑结构和存储结构是统一的，，要求内存中存储单元的地址必须是连续的。优点：一般情况下，存储密度大，存储空间利用率高。缺点：a.在做插入和删除操作时，需移动大量元素；b.由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；c.表的容量难以扩充。 链式结构存储时，相邻数据元素可随意存放，所占空间分为两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。优点：插入和删除元素时很方便，使用灵活。