第一章：数据结构包含：逻辑结构，数据的存储结构，对数据进行的操作。数据元素：相对独立的基本单位，即可简单也可复杂，简单的数据元素只有一个数据项，数据项是数据的不可分割的最小单位。数据对象：性质相同的数据元素的集合。数据结构：相互存在一种或者多种特定关系的数据元素的集合（集合，线性结构，树结构，图结构）。顺序存储结构：数据元素按照逻辑顺序依次存放在存储器的一段连续存储单元中。链式存储结构：存储在存储空间的任意位置上，包含一个数据域和至少一个指针域，要访问，必须从第一个元素开始查找。数据类型：一组值加一组操作。
第二章：线性表：有限多个性质相同的数据元素构成的一个序列，数据元素的个数就是长度。线性表的顺序存储结构：用一组地址连续的存储单元能随机存取的结构。链式存储结构：具有链式存储结构的线性表称为链表，是用一组地址任意的存储单元来存线性表中的数据元素。每个数据元素存储结构包括数据元素信息域和地址域，存放一个数据元素的存储结构称为结点，每个结点只定义一个指针域，存放的是当前结点的直接后记结点的地址（直接后继结点），线性表的最后一个结点指针域存放空（0，NULL）标志结束。不支持随机存取，访问必须从第一个结点开始，一次访问。双向链表：每个结点设置两个方向的指针（直接前驱和直接后继）。
第三章：栈：堆栈的简称，限定在表尾进行插入和删除的线性表。特点是后进先出。当栈定指针指向栈底时，为空栈。队列：限定只能在一端进行插入和在另一端进行删除的线性表，进行插入的是队尾，删除的是队头。特点是先进先出。队列的链式结构：用一个链表依次存放从队头到队尾的所有的数据元素。存放队头地址（队头指针）队尾地址（队尾指针），空链队列： 有头结点，空队列条件是头结点存放0，无头结点为队头指针指向空。队列的顺序存储结构：用一组地址连续的存储空间依次存放从队头到队尾的所有数据元素，再用队头指针和队尾指针记录队头和队尾的位置。队头指针指向队头元素前一个数组元素的位置，队尾始终指向队尾，当队尾和队头指向同一位置，空队列。入队和出队，队尾指针都会向数组元素下标的增加方向移动，当队尾指针超出数组上界面无法进行操作（假溢出），解决方法是使用具有顺存储存结构的循环队列：将存放队列元素的数组首尾连接，形成一个环形结构。
试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好?
答：① 顺序存储时,相邻数据元素的存放地址也相邻（逻辑与物理统一)；要求内存中可用存储单元的地址必须是连续的。
优点：存储密度大（＝1），存储空间利用率高。缺点：插入或删除元素时不方便。
②链式存储时，相邻数据元素可随意存放,但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小（〈1），存储空间利用率低. 顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作.
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
若线性表的长度变化较大,且其主要操作是插入、删除操作，则采用链表。
一棵度为2的有序树与一棵二叉树有何区别？
答：一棵度为二的有序树与一棵二叉树的区别在于：有序树的结点次序是相对于另一结点而言的,如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序。
而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的.
简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。
数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。数据对象是性质相同的数据元素的集合，是数据的一个子集。
数据结构是相互之间存在一种或多种特定关系的数据元素的集合。
存储结构是数据结构在计算机中的表示。
数据类型是一个值的集合和定义在这个值集上的一组操作的总称。
抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展.
试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。
解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口.
- 1 - 数据的存储结构和逻辑结构的关系
数据的存储结构和逻辑结构是数据处理中的两个重要概念，二者密切相关。存储结构是数据在计算机中的存储方式，即数据的物理存储形式，包括顺序存储结构、链式存储结构、索引存储结构等。逻辑结构是指数据元素之间的逻辑关系，包括线性结构、树形结构、图形结构等。
数据的存储结构和逻辑结构之间的关系是：数据的逻辑结构决定了它的存储结构。不同的逻辑结构需要不同的存储结构来存储数据，如线性结构可以采用顺序存储结构或链式存储结构，而树形结构则通常采用链式存储结构。反之，数据的存储结构也可影响它的逻辑结构。例如，采用链式存储结构时，可以很方便地实现链表的插入和删除操作，因此链表就是一种常见的线性结构。
在实际应用中，应根据问题的特点选择合适的存储结构和逻辑结构，以便实现高效的数据操作。例如，对于需要频繁进行插入和删除操作的数据，应采用链式存储结构和链表逻辑结构。对于需要经常进行查找操作的数据，应采用顺序存储结构和树形逻辑结构。因此，熟练掌握数据的存储结构和逻辑结构的关系，对于数据处理和算法设计都具有重要的意义。
第1章绪论
1 •简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象 数据类型。
答案：
数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。如数 学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等 通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。在有些情况下，数 据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的 一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。例如，学生基本信息表中的学 号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合 N={0,
± 1，土 2，…}，字母字符数据对象是集合 C={ ‘A',‘ B',…，‘ Z', ‘a',‘ $,•••,‘ z' }, 学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。换句话说，数据结构是带“结 构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑 结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为 物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总 称。具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2•试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案：
例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记 录对应一个数据元素， 学生记录按顺序号排列， 形成了学生基本信息记录的线性序列。 对于整个表来说，
