数据结构 python复习提纲

1

数据结构复习提纲

第一章 : 综述

1. 什么是算法（Algorithm），什么是程序（Programming），它们之间的区别与联系是什么？

算法是用问题实例所需的数据和生成预期结果所需的一系列步骤来描述问题的解决方案，是解决问题的通用的、一步一步的指令列表。例如给定一个特定的输入，算法会产生期望的结果。

程序是一种被编码成某种编程语言的算法，它提供一种符号化的方式来表示过程和数据，用于算法的实现。为此，语言提供了控制流程和数据类型。

联系：对于解决一个问题来说，先有算法，后有程序。算法靠程序这个平台来解决具体的问题。对于相同的算法，可能有许多程序，这取决于程序员和编程语言。

区别：算法是解决问题的思想和方案，程序是表达算法的一种方式。即算法用其他方法例如流程图，语言描述都是有意义的，程序只是其中一种表达方式，是计算机理解的语言。但算法需要依靠程序这个平台才能很好的解决问题。

2. 什么是抽象数据类型（Abstract Data Type），简述其作用。

抽象的数据类型，有时缩写为ADT，是对我们如何看待数据和操作的逻辑描述，而不考虑它们将如何被实现。这意味着我们只关心数据的表示，而不是它最终将如何构造。

作用：通过抽象数据类型，我们围绕数据创建封装，以实现信息隐藏。抽象的数据类型是用户与算法实现交互的窗口。用户与接口交互，使用由抽象数据类型指定的操作，隐藏更深层次用户不关心的细节。

3. 什么是“信息隐藏”（information hiding）技术，python中如何实现信息隐藏？

信息隐藏技术是将算法实现的细节封装成抽象数据类型，使得更深层次用户不关心的实现细节在用户视图中被隐藏。

Python中利用数据结构实现信息隐藏。即通过类或函数等的封装来实现一个2

抽象的数据类型。这使得程序员可以切换被封装的细节，而不改变数据用户与之交互的方式。用户在使用程序时只需调用抽象数据类型，专注于解决问题的过程。

4. 学习算法的目的是什么？

1) 学习不同的算法是如何设计的有助于我们解决下一个具有挑战性的问题。通过考虑许多不同的算法，我们可以开始开发模式识别，这样下次出现类似问题时，我们就能更好地解决它。

2) 算法通常是完全不同的。尽管两种解决方案都起作用，一种算法可能比另一种算法使用更少的资源。我们希望有一些方法来比较这两种解决方案。学习分析算法技术，使我们能够根据自己分析出的算法的特点来比较和对比解决方案。

3) 通过学习算法，我们能够区分有解决方案的问题，没有解决方案的问题，和那些存在解决方案但需要太多时间或其他资源才能合理解决的问题。

4) 通常有很多方法可以解决问题。找到一个解决方案，然后再决定它是否是一个好的解决方案，我们将会权衡，一遍又一遍地做，以确定和决定最终的解决方案。

5. 如何使用python实现函数的定义，并举一个例子说明。

一般来说，我们可以通过定义一个函数来隐藏任何计算的细节。一个函数定义需要一个名称、一组参数和一个主体。它也可以显式地返回一个值。例如，下面定义的简单函数返回传入的值的平方。

def square(n):

return n ** 2

6. python中如何实现类的定义和使用？

A. 类的定义：

1) 在Python中，我们通过提供一个名称和一组方法来定义一个新的类，这些定义与函数定义类似。类为我们定义方法提供了框架。

例如： class Fraction:

2) 所有类都应该提供的第一个方法是构造函数。构造函数定义了创建数据对象的方式。在Python中，构造函数总是被称为init（在init之前和之3

后有两个下划线）。

例如： class Fraction:

def __init__(self,top,bottom):

self.num = top

self.den = bottom

3) 正式的参数列表一般会包含self（、形式参数）。self是一个特殊的参数，它将始终作为对对象本身的引用。它必须始终是第一个正式参数;但是，在调用时它永远不会被赋予实际的参数值。

B. 类的使用：

要创建类的实例，我们必须调用构造函数。具体为使用类名并传递必要参数的实际值（注意，我们从不直接调用init）

例如： 创建一个名为my_fraction的对象表示分数3/5

my_fraction = Fraction(3,5)

第二章 : 分析

1. 什么是算法分析，算法分析的目的？

A. 算法分析是基于每一种算法所使用的计算资源量来比较算法的。这里计算资源量分为两个方面来衡量。

1) 一方面是考虑算法需要的空间或内存的数量。问题解决方案所需的空间数量通常由问题实例本身决定。

2) 另一方面是根据需要执行的时间来分析和比较算法。这个度量有时被称为算法的“执行时间”或“运行时”。 这意味着我们将跟踪程序所需的实际时间来计算其结果。

B. 目的：当两个程序解决了相同的问题但看起来不同的时候，我们希望通过算法分析得出哪一个程序更好，从而减少计算资源量，更有效的解决问题。

2. 什么是算法的时间复杂度？

1) 如果每一个步骤都被认为是计算的基本单位，那么算法的时间复杂度可以表示为解决问题所需的步骤数量。它展示了算法的执行时间是如何随4

着问题的大小而变化的。时间复杂度的数量级通常用大O符号表示，并写成O（f（n））。它提供了计算中实际步骤数量的有用近似值。函数f（n）提供了原始T（n）的主要部分的简单表示。

2) 有时算法的性能依赖于数据的精确值，而不仅仅是问题的大小。对于这类算法，我们需要用最好的情况，最坏的情况，以及平均的情况来描述他们的表现。对于完全相同的算法，不同的数据集可能具有不同的执行时间。然而，在大多数情况下，算法在这两个极端之间（平均情况）之间执行。

3. 会计算类似于下面程序段的时间复杂度，并用big O形式表达。

解决问题所需的步骤数量是四个项的和。第一项是常数3，表示在片段开始时的三个赋值语句。第二项是3n2 ，因为有三个语句由于嵌套迭代而执行n2次。第三项是2n，两个语句重复n次。最后，第四个项是常数1，表示最终赋值语句。所以 T(n)=3+3n2+2n+1=3n2+2n+4。通过观察这些项数，我们可以很容易地看到n2占主导地位，当n变大时，所有其他项以及主项的系数都可以忽略，因此这段代码是O（n2）。

第三章 : 基本数据结构

1. 什么是线性结构？简述基本抽象数据类型的特点：堆栈、队列、双端队列。

A. 线性结构：

1) 线性结构可以被认为是有两个端点的数据结构。有时，这些末端被称为“左”和“右”，或者在某些情况下是“前”和“后”。你也可以称它们5

为“顶部”和“底部”。端点的名字并不重要。

2) 将一个线性结构与另一个线性结构区别开来的是添加和删除项目的方式，特别是添加和删除发生的位置。例如，一个结构可能允许只在一端添加新项目。有些结构可能允许从两端删除项目。

3) 线性结构出现在许多算法中，可以用来解决各种各样的重要问题。

B. 基本抽象数据类型的特点：

1) 堆栈：添加新项目和删除现有项目总是在同一端进行。这一端通常被称为“顶部”。顶端的末端被称为“底部”。存储在离基座较近的堆栈中的项表示在堆栈中停留时间最长的项。最近添加的项是首先要删除的项。它的项目排序原则为LIFO，后进先出。它提供了基于集合中时间长度的排序。较新的物品靠近顶部，而较老的物品靠近底部。堆栈可以实现一组项目的反转（反序）。

2) 队列：在其中一端添加新项，这一端称为“尾”，而现有项的删除发生在另一端，这一端称为“头”。当一个元素进入队列时，它从尾开始，向头前进，直到被移除。队列中最近添加的项必须在集合的末尾处等待。队列中停留时间最长的项在队头。这种排序原则被称为FIFO，先进先出。

3) 双端队列：同样有两个端点，一个正面和一个背面。它的不同之处是添加和删除项的非限制性，即新项目可以在正面或背面添加。同样地，现有的项目可以从两端移除。在某种意义上，这种混合线性结构在单个数据结构中提供了栈和队列的所有功能。

2. 掌握使用Python的lists进行堆栈、队列和双端队列抽象数据类型的实现。

堆栈：

class Stack()

def __init__(self):

self.items = []

def is_empty(self):

return self.items == []

def push(self,item):

self.items.append(item) 6

def pop(self):

return self.items.pop()

def peek(self):

return self.items[len(self.items)-1]

def size(self):

return len(self.items)

队列：

class Queue():

def __init__(self):

self.items = []

def is_empty(self):

return self.items == []

def enqueue(self,item):

self.items.insert(0,item) #对比enqueue与dequeue应该是不同的两端

def dequeue(self):

return self.items.pop()

def size(self):

return len(self.items)

双端队列：

class Deque():

def __init__(self):

self.items = []

def is_empty(self):

return self.items == []

def add_rear(self,item):

self.items.insert(0,item)

def add_front(self,item):

self.items.append(item)

def remove_rear(self):

return self.pop(0)