下载文档原格式
第一章绪论1.数据：人们利用文字符号、数字符号及其他规定的符号对现实世界的事物及其活动的描述。
凡是能被计算机输入、存储、处理和输出的一切信息都叫数据。
2.数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
数据元素的组成：一个数据元素通常由一个或若干数据项组成。
数据项：指具有独立含义的最小标识单位。
3.数据对象：性质相同的数据元素的集合，是数据的一个子集。
4.数据结构：研究的是数据的逻辑结构和物理结构，以及它们之间的相互关系和所定义的算法在计算机上运行的学科。
5.算法：是对待定问题求解步骤的一种描述，是指令的有限序列。
算法应满足以下性质：1)输入性：具有零个或若干个输入量；2)输出性：至少产生一个输出；3)有穷性：每条指令的执行次数是有限的；4)确定性：每条指令的含义明确，无二义性；5)可行性：每条指令都应在有限的时间内完成。
6.评价算法优劣的主要指标：1)执行算法后，计算机运行所消耗的时间，即所需的机器时间；2)执行算法时，计算机所占存储量的大小，即所需的存储空间；3)所设计的算法是否易读、易懂，是否容易转换成其他可运行的程序语言。
7.会估算某一算法的总执行时间和时间复杂度。
8.熟悉习题P32:3(5)-(9)、4(2)(3)第二章线性表1.线性表(P7)：是性质相同的一组数据元素序列。
线性表的特性：1)数据元素在线性表中是连续的，表中数据元素的个数可以增加或减少，但调整后数据元素仍必须是连续的，即线性表是一种线性结构。
2)数据元素在线性表中的位置仅取决于自己在表中的序号，并由该元素数据项中的关键字(key)加以标识。
3)线性表中所有数据元素的同一数据项，其属性是相同的，数据类型也是一致的。
线性表的主要运算有：插入、删除、查找、存取、长度、排序、复制、合并。
线性表的顺序存储结构及特点(就是把表中相邻的数据元素存放在内存邻接的存储单元，这种存储方法叫做顺序分配，又称顺序映像。
第1章绪论1.1 什么是数据结构数据与数据之间的关系1.2 基本概念和术语1.基本定义(1).数据(Data) ：是客观事物的符号表示。
在计算机科学中指的是所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素(Data Element) ：是数据的基本单位，在程序中通常作为一个整体来进行考虑和处理。
(2)数据项(Data Item)：一个数据元素可由若干个数据项组成。
数据项是数据的不可分割的最小单位。
数据项是对客观事物某一方面特性的数据描述。
数据对象(Data Object)：是性质相同的数据元素的集合，是数据的一个子集。
2.举例如字符集合C={‘A’,‘B’,‘C’,…}--C表示字符对象；A ，B等表示数据元素；再如学生集合Students={“Zhangsan”, “Lisi”，…}Zhangsan(ID,name,age,grade,…)……--Students表示学生对象；“Zhangsan”、“Lisi”表示数据元素；Zhangsan的ID、name、age等表示数据项。
3.数据结构的形式定义数据结构的形式定义是一个二元组：Data-Structure=(D，S)其中：D是数据元素的有限集，S是D上关系的有限集4.逻辑结构与物理结构(1)数据元素之间的关系可以是元素之间代表某种含义的自然关系，也可以是为处理问题方便而人为定义的关系，这种自然或人为定义的“关系”称为数据元素之间的逻辑关系，相应的结构称为逻辑结构。
(2)数据结构在计算机中的表示（映像）称为数据的物理结构。
数据结构的存储方式1)顺序存储结构：用数据元素在存储器中的相对位置来表示数据元素之间的逻辑结构(关系)。
2)链式存储结构：在每一个数据元素中增加一个存放另一个元素地址的指针(pointer )，用该指针来表示数据元素之间的逻辑结构(关系)。
3)例：设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ，两种不同的存储结构。
《数据结构》吕云翔编著第1章绪论习题解答数据结构是计算机科学中的一个重要概念，它涉及到存储、组织和管理数据的方法和技术。
《数据结构》是吕云翔编著的一本经典教材，本文将就第1章绪论中的习题进行解答。
1. 为什么要学习数据结构？数据结构是计算机科学的基础，它为我们提供了存储和操作数据的方式。
学习数据结构能够帮助我们更好地理解和分析问题，设计高效的算法，并且能够为我们解决实际问题提供支持。
2. 什么是数据结构？数据结构指的是数据元素之间的关系，以及存储和访问这些数据的方法。
常见的数据结构包括数组、链表、栈、队列、树、图等。
每种数据结构都有各自的特点和适用场景。
3. 数据结构有哪些基本操作？数据结构的基本操作包括插入、删除和查找。
插入操作将一个新的元素插入到数据结构中，删除操作将一个元素从数据结构中移除，查找操作用于寻找特定元素的位置或者判断某个元素是否存在。
4. 什么是线性结构？线性结构是数据元素之间呈线性关系的数据结构。
常见的线性结构有数组和链表。
数组是一种连续存储数据元素的结构，链表是一种通过指针将数据元素链接起来的结构。
5. 什么是非线性结构？非线性结构是数据元素之间呈非线性关系的数据结构。
常见的非线性结构有树和图。
树是一种层次结构，图是由节点和边组成的结构，节点之间的关系可以是任意的。
6. 什么是抽象数据类型？抽象数据类型（ADT）是一种数学模型，它定义了一种数据类型的抽象行为和操作。
ADT将数据的逻辑结构和数据的物理存储分离，使得数据结构和数据操作可以独立地进行设计和实现。
7. 数据结构的选择原则是什么？选择适当的数据结构是解决问题的关键。
选择数据结构应该考虑到数据的特点、操作的效率和实际应用需求。
在选择数据结构时，需要综合考虑空间复杂度和时间复杂度的因素，并且合理权衡它们之间的关系。
8. 数据结构与算法之间有什么关系？数据结构和算法是紧密相关的。
数据结构提供了算法操作的底层基础，而算法则是对数据结构进行操作的具体步骤和方法。
大学课程《数据结构》课后习题答案第 1 章绪论课后习题讲解1. 填空⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
【解答】数据元素⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。
【解答】数据项，数据元素【分析】数据结构指的是数据元素以及数据元素之间的关系。
⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。
【解答】集合，线性结构，树结构，图结构⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。
【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。
【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。
【解答】自然语言，程序设计语言，流程图，伪代码，伪代码⑺在一般情况下，一个算法的时间复杂度是（）的函数。
【解答】问题规模⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。
【解答】Ο(1)，Ο(nlog2n)【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。
2. 选择题⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。
A 线性结构B 非线性结构C 存储位置D 指针【解答】C，D【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。
⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。
则表示该遗产继承关系的最合适的数据结构应该是（）。
