南开大学数据结构与算法 习题与答案

第1章 概 论

1.数据、数据元素、数据结构、数据类型的含义分别是什么？

数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并由计算机程序处理的符号的总称。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体考虑。

数据结构：数据元素之间的关系+运算，是以数据为成员的结构，是带结构的数据元素的集合，数据元素之间存在着一种或多种特定的关系。

数据类型：数据类型是用来区分不同的数据；由于数据在存储时所需要的容量各不相同，不同的数据就必须要分配不同大小的内存空间来存储，所有就要将数据划分成不同的数据类型。数据类型包含取值范围和基本运算等概念。

2.什么是数据的逻辑结构？什么是数据的物理结构？数据的逻辑结构与物理结构的区别和联系是什么？

逻辑结构：数据的逻辑结构定义了数据结构中数据元素之间的相互逻辑关系。数据的逻辑结构包含下面两个方面的信息：

① 数据元素的信息；

② 各数据元素之间的关系。

物理结构：也叫储存结构，是指逻辑结构的存储表示，即数据的逻辑结构在计算机存储空间中的存放形式，包括结点的数据和结点间关系的存储表示。

数据的逻辑结构和存储结构是密不可分的，一个操作算法的设计取决于所选定的逻辑结构，而算法的实现依赖于所采与的存储结构。采用不同的存储结构，其数据处理的效率是不同的。因此，在进行数据处理时，针对不同问题，选择合理的逻辑结构和存储结构非常重要。

3.数据结构的主要操作包括哪些？

对于各种数据结构而言，他们在基本操作上是相似的，最常用的操作有： 创建：建立一个数据结构；

清除：清除一个数据结构；

插入：在数据结构中增加新的结点；

删除：把指定的结点从数据结构中删除；

访问：对数据结构中的结点进行访问；

更新：改变指定结点的值或改变指定的某些结点之间的关系；

查找：在数据结构中查找满足一定条件的结点；

排序：对数据结构中各个结点按指定数据项的值，以升序或降序重新排列。

4.什么是抽象数据类型？如何定义抽象数据类型？

抽象数据类型(Abstract Data Type 简称ADT)是指一个数学模型以及定义在此数学模型上的一组操作。ADT是与具体的物理存储无关的数据类型，因此，不论ADT的内部结构如何变化，只要其数据结构的特性不变，都不影响其外部使用。

对抽象数据类型的描述一般用(D,R,P)三元组表示，抽象数据类型的定义格式为： ADT

{

数据对象D：

数据关系R：

基本操作P：