数据结构复习提纲
第一章: 综述
1.什么是算法（Algorithm），什么是程序（Programming），它们之间的区别与
联系是什么？
算法是用问题实例所需的数据和生成预期结果所需的一系列步骤来描述问题的解决方案，是解决问题的通用的、一步一步的指令列表。例如给定一个特定的输入，算法会产生期望的结果。
程序是一种被编码成某种编程语言的算法，它提供一种符号化的方式来表示过程和数据，用于算法的实现。为此，语言提供了控制流程和数据类型。
联系：对于解决一个问题来说，先有算法，后有程序。算法靠程序这个平台来解决具体的问题。对于相同的算法，可能有许多程序，这取决于程序员和编程语言。
区别：算法是解决问题的思想和方案，程序是表达算法的一种方式。即算法用其他方法例如流程图，语言描述都是有意义的，程序只是其中一种表达方式，是计算机理解的语言。但算法需要依靠程序这个平台才能很好的解决问题。
2.什么是抽象数据类型（Abstract Data Type），简述其作用。
抽象的数据类型，有时缩写为ADT，是对我们如何看待数据和操作的逻辑描述，而不考虑它们将如何被实现。这意味着我们只关心数据的表示，而不是它最终将如何构造。
作用：通过抽象数据类型，我们围绕数据创建封装，以实现信息隐藏。抽象的数据类型是用户与算法实现交互的窗口。用户与接口交互，使用由抽象数据类型指定的操作，隐藏更深层次用户不关心的细节。
3.什么是“信息隐藏”（information hiding）技术，python中如何实现信息隐藏？
信息隐藏技术是将算法实现的细节封装成抽象数据类型，使得更深层次用户不关心的实现细节在用户视图中被隐藏。
Python中利用数据结构实现信息隐藏。即通过类或函数等的封装来实现一个
抽象的数据类型。这使得程序员可以切换被封装的细节，而不改变数据用户与之交互的方式。用户在使用程序时只需调用抽象数据类型，专注于解决问题的过程。
4.学习算法的目的是什么？
1)学习不同的算法是如何设计的有助于我们解决下一个具有挑战性的问题。
通过考虑许多不同的算法，我们可以开始开发模式识别，这样下次出现
类似问题时，我们就能更好地解决它。
2)算法通常是完全不同的。尽管两种解决方案都起作用，一种算法可能比
另一种算法使用更少的资源。我们希望有一些方法来比较这两种解决方
案。学习分析算法技术，使我们能够根据自己分析出的算法的特点来比
较和对比解决方案。
3)通过学习算法，我们能够区分有解决方案的问题，没有解决方案的问题，
和那些存在解决方案但需要太多时间或其他资源才能合理解决的问题。
4)通常有很多方法可以解决问题。找到一个解决方案，然后再决定它是否
是一个好的解决方案，我们将会权衡，一遍又一遍地做，以确定和决定
最终的解决方案。
5.如何使用python实现函数的定义，并举一个例子说明。
一般来说，我们可以通过定义一个函数来隐藏任何计算的细节。一个函数定义需要一个名称、一组参数和一个主体。它也可以显式地返回一个值。例如，下面定义的简单函数返回传入的值的平方。
def square(n):
return n ** 2
6.python中如何实现类的定义和使用？
A.类的定义：
1)在Python中，我们通过提供一个名称和一组方法来定义一个新的类，这
些定义与函数定义类似。类为我们定义方法提供了框架。
例如：class Fraction:
2)所有类都应该提供的第一个方法是构造函数。构造函数定义了创建数据
对象的方式。在Python中，构造函数总是被称为init（在init之前和之
后有两个下划线）。
例如：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)如果每一个步骤都被认为是计算的基本单位，那么算法的时间复杂度可
以表示为解决问题所需的步骤数量。它展示了算法的执行时间是如何随
着问题的大小而变化的。时间复杂度的数量级通常用大O符号表示，并
写成O（f（n））。它提供了计算中实际步骤数量的有用近似值。函数f
（n）提供了原始T（n）的主要部分的简单表示。
2)有时算法的性能依赖于数据的精确值，而不仅仅是问题的大小。对于这
类算法，我们需要用最好的情况，最坏的情况，以及平均的情况来描述
他们的表现。对于完全相同的算法，不同的数据集可能具有不同的执行
时间。然而，在大多数情况下，算法在这两个极端之间（平均情况）之
间执行。
3.会计算类似于下面程序段的时间复杂度，并用big O形式表达。
解决问题所需的步骤数量是四个项的和。第一项是常数3，表示在片段开始时的三个赋值语句。第二项是，因为有三个语句由于嵌套迭代而执行n2次。第三项是2n，两个语句重复n次。最后，第四个项是常数1，表示最终赋值语句。所以 T(n)=3+3n2+2n+1=3n2+2n+4。通过观察这些项数，我们可以很容易地看到n2占主导地位，当n变大时，所有其他项以及主项的系数都可以忽略，因此这段代码是O（n2）。
第三章: 基本数据结构
1.什么是线性结构？简述基本抽象数据类型的特点：堆栈、队列、双端队列。
A.线性结构：
1)线性结构可以被认为是有两个端点的数据结构。有时，这些末端被
称为“左”和“右”，或者在某些情况下是“前”和“后”。你也可以称它们
为“顶部”和“底部”。端点的名字并不重要。
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)
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)
def remove_front(self):
return self.pop()
def size(self):
return len(self.items)
3.能够解读如下程序段的执行结果：
解读：
4.借助堆栈实现括号匹配算法
def match(open,close):
opens = ‘([{’
closes =’)]}’
return opens.index(open) == close.index(close) def par_checker(string):
s = Stack()
balance = True
i = 0
while balance == True and i < len(string):
symbol = string[i]
if symbol = ‘(’:
s.push(symbol)
else:
if s.is_empty == True:
banlance = Flase
else:
top = s.pop()
if not match(top,symbol):
banlance = False
i = i + 1
if banlance and is_empty():
return True
else:
return False
5.借助堆栈实现10进制向任意数制转换的思想，能够绘制堆栈变化图。
def tran(num,base):
a = ‘0123456789ABCDEF’
s = Stack()
while num > 0:
n = num % base
s.push(n)
num = num // base
new = ‘ ’
while not s.is_empty():
new = new + a[s.pop()]
return new
print(tran(59,16))
6.算术表达式的先序、中序、后序表达。中序到后序的转换的算法思想及堆栈
变化状态。
def trans(exp):
s = Stack()
pos = []
prec = { }
prec[‘*’] = 3
prec[‘/’] = 3
prec[‘+’] = 2
prec[‘-’] = 2
prec[‘)’] = 1
i = 0
fp = exp.split()
for i in fp:
if i not in [‘+’,’-’,’*’,’/’,’(’,’)’]:
pos.append(i)
elif i == ‘(’:
s.push(i)
elif i ==’)’:
t = s.pop()
while t != ‘(‘:
pos.append(t)
t = s.pop()
elif i in [‘+’,’-’,’*’,’/’]:
while not s.is_empty() and prec[s.peek()]>=prec(i):
pos.append(s.pop())
s.push(i)
while not s.is_empty():
pos.append(s.pop())
return " ".join(postfix_list)
7.采用后序表达式，借助一个堆栈实现算术表达式求解的算法。
def post_val(postfix_list):
s = Stack()
fp = postfix_list.split()
for i in fp:
if i in ‘0123456789’:
s.push(int(i))
else:
op2 = s.pop()
op1 = s.pop()
result = math(op1,op2,i)
s.push(result)
if not s.is_empty():
return s.pop()
def math(op1,op2,operator):
if operator == ‘+’:
return op1 + op2
if operator == ‘-’:
return op1 - op2
if operator == ‘*’:
return op1 * op2
if operator == ‘/’:
return op1 / op2
8.采用队列实现“热土豆”的思想和程序实现（约瑟夫环的实现）。
def hot_potato(n_list,num):
s = Queue()
for name in n_list:
s.enqueue(name)
while s.size()>1:
for i in range(num):
s.enqueue(s.dequeue())
s.enqueue()
return s.enqueue()
9.采用双端队列实现回文检测（Palindrome-Checker）的思想及算法实现。
def p_checker(a_list):
q = Deque()
equal = True
for i in a_list:
q.add_rear(i)
while q.size>1 and equal:
first = q.remove_front()
last = q.remove_rear()
if first == last:
equal = True
else:
equal = False
return equal
10.简述采用链表（Linked Lists）实现线性结构的特点。有序链表（Ordered List）
的特点及python实现。
链表特点：
1)存储空间可以不连续，由独立的存储单元结点组成。每个结点都有自己
独立的数据域和指针域。
2)各数据结点的存储顺序与数据元素之间的逻辑关系可以不一致。各结点
的存放位置是随机的。
3)各数据元素之间的逻辑关系是由各结点的指针指向形成的。
4)链表一定有一个头指针，这个指针没有数据域只有指针域，由它作为链
表的头指向其他结点。
5)链表不需要提前申请空间，在需要时添加结点即可。
有序链表：在链表中存放的元素在逻辑结构上存在一定的顺序。
当我们考虑有序列表的操作时，isEmpty和size方法可以与无序列表一样实现，无序列表的移除方法在有序列表中也可以很好地运
行。但有序列表的查找和添加则与无序列表不同。在数据项不在链
表中的情况下，我们可以利用有序的优势来尽快停止搜索。
class order_list():
def __init__(self):
self.head = None
def is_empty(self):
self.head == None
def search(self,item):
found = False
stop = False
current = self.head
while self.current !== None and not found and not stop:
if current.get_data()==item:
return found = True
else:
if current.get_data()>items:
stop = True
else:
current = current.get_data()
return found
def add_order(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.get_data()>item:
stop = True
else:
current = current.get_next()
previous = current
temp = Node(item)
if previous == None: #应该插在第一个位置
temp.set_next(self.head)
self.head = temp
else: #应该插在其他位置
temp.set_next(current) #先将要添加的结点的指针指向它的后继
previous.set_next(temp) #再将它的前端的指针指向它
11.编写函数实现链表（Linked Lists）中元素的插入（add）和删除（remove）。
无序链表及有序联表中元素插入和删除有何区别？
插入：
无序链表在插入元素时，统一插在元素的头指针指向的位置，即插入后的新元素将会在逻辑结构上成为第一个元素。所以时间复杂度为常数级别T(n)=3。
def add_unorder(self,item):
temp = Node(item)
temp.set_next(self.head)
self.head = temp
有序链表因为要保证元素逻辑结构上的有序性，所以在插入时要用指针遍历链表直至找到合适元素插入的位置.所以时间复杂度O(n)
def add_order(self,item):
current = self.head
previous = None
stop = False
while current != None and not stop:
if current.get_data()>item:
stop = True
else:
current = current.get_next()
previous = current
temp = Node(item)
if previous == None: #应该插在第一个位置
temp.set_next(self.head)
self.head = temp
else: #应该插在其他位置
temp.set_next(current) #先将要添加的结点的指针指向它的后继
previous.set_next(temp) #再将它的前端的指针指向它
删除：
无序链表表在删除元素时，需要遍历链表。如果要删除的元素恰好不存在于这个链表，那就需要遍历完整个链表。所以时间复杂度为O(n)
def remove_unorder(self,item):
found = False
current = self.head
previous = None
while True:
if current.get_data() == item:
if previous == None:
self.head = current.get_next()
current = self.head
found = True
else:
previous.set_next(current.get_next())
current = current.get_next()
found = True
else:
if current == None and found == False:
print(‘ %s is not be founded ‘ %item )
break
if current == None and found == True:
break
12.将下列中序表达式转变为先序。
?(A+B)*(C+D)*(E+F)
全括号表达式：(((A+B)*(C+D))*(E+F)) 结果：**+AB+CD+EF
?A+((B+C)*(D+E))
全括号表达式：(A+((B+C)*(D+E))) 结果：+A*+BC+DE
?A*B*C*D+E+F
全括号表达式：(((((A*B)*C)*D)+E)+F) 结果：++***ABCDEF
第四章: 递归问题
1.什么是递归？递归三要素是什么？
A.递归：递归是一种解决问题的方法，它将问题分解成更小的子问题，直
到这个子问题可以被很简单地解决。通常递归涉及到调用自身的函数，
它让我们可以用优雅的解决方案来解决那些可能很难编程的问题。
B.递归三要素：
1)递归算法必须有一个基本情况(base case)。
2)递归算法必须改变它的状态并向基本情况移动(分解问题为更小的子
问题)。
3)递归算法必须递归地调用自己。
2.将数字形字符转换为任意进制数的递归算法，并会绘制递归调用图揭示递归
过程。
def tran(n,base):
a = ‘0123456789ABCDEF’
if n return a[n] else: return str(tran(n//base,base)) + a[n%base] #可以不加str（） 3.汉诺塔问题的递归实现。能够绘指出三个盘子的汉诺塔移动过程图。 def move_tower(from_pole,to_pole,with_pole,height):#四个参数意义：from_pole 盘子现在在的柱子，to_pole盘子将要去的柱子，with_pole帮忙的柱子 if height > 1: move_tower(from_pole,with_pole,to_pole,height - 1)#将第一个柱子上的前n-1个盘子利用最后一个柱子移到中间的柱子上 move_disk(from_pole,to_pole)#将第一个柱子上剩下的最后一个盘子移到最后一个柱子上 move_tower(with_pole,to_pole,from_pole,height - 1)#将中间柱子上的n-1个盘子利用第一个柱子移到最后一个柱子上 def move_disk(from_pole,to_pole): print(‘%s to %s’ % from_pole,to_pole) 第五章：排序和检索 1.顺序查找的算法实现思想及时间复杂度分析。 def sequential_search(a_list,item): found = False i = 0 while found == False and i < len(a_list): if item == a_list[i] found = True else: i = i + 1 return found 时间复杂度：worst case:T(n)=2+n best case:T(n)=2+2=4 average case:O(n) 2.二分查找的算法实现思想及复杂度分析 def binary_search(a_list,item): found = False first = 0 last = len(a_list) - 1 while first<=last and found == False: mid = (first + last) / 2 if a_list[mid] == item: found = True else: if item>a_list[mid]: first = mid + 1 else: last = mid – 1 return found 时间复杂度：比较次数i与算法规模n的关系：1=n/(2^i)→i=log?n 故O(logn) 3.Hashing查找的算法实现思想。如何处理算法Hashing查找中的冲突问题。给 定一组数据，用开放寻址的冲突处理方法，能够实现哈希表的填充。 A.实现思想：将一组项目按照哈希函数计算出每项的哈希值（哈希表的槽）， 并将它们对应存放在哈希表的槽中，以实现查找的时间复杂度为O(1)。 B.冲突解决方法： 1)闭散列法及线性探测器：当应该被放置的槽不为空时，向后遍历，直 至寻找到一个空的槽。 2)再哈希：不再按顺序寻找下一个打开的槽，而是每次跳过事先规定的 槽数。 rehash(pos)=(pos+skip)%size_of_table 3)链表：允许哈希表中的一个槽有多个项目。这些项目组成链表。 4)二次探测：使用一个哈希函数来增加哈希值，而不是使用常数跳过。 第六章树和二叉树 1.二叉树的列表（list）结构存储实现。 def Binary_tree(r): return [r,[],[]] def insert_left(r,item): t = r.pop(1) if len(t)>1: r.insert(1,[item,t,[]]) else: r.insert(1,[item,[],[]]) def insert_right(r,item): t = r.pop(2) if len(t)>1: r.insert(2,[item,[],t]) else: r.insert(2,[item,[],[]]) def get_root_val(r): return r[0] def get_left_child(r): return r[1] def get_rigth_child(r): return r[2] def set_root_val(r,new): r[0] = new 2.二叉树的节点引用（Nodes and References）结构实现。 class Binary_tree(): def __init__(self,root): self.key = root self.left = None self.right = None def insert_left(self,item): if self.left == None: self.left = Binary_tree(item) else: t = Binary_tree(item) t.left = self.left self.left = t def insert_right(self,item): if self.right == None: self.right == Binary_tree(item) else: t = Binary_tree(item) t.right = self.right self.right = t def get_root_val(self): return self.key def set_root_val(self,new): self.key = new def get_left(self): return self.left def get_right(self): return self.right 3.解析树的实现，借助解析树实现算术表达式的求解。 from basic import Binary_tree from basic import Stack import operator def build_ptree(self,exp): fp = exp.split() s = Stack() e_tree = Binary_tree(‘’) s.push(e_tree) current = e_tree for i in fp: if i == ‘(’: current.insert_left(‘’) s.push(current) current = current.get_left() if i not in [‘+’,’-’ , ’*’ , ’/’ ,’)’]: current.set_root_val(int(i)) parent = s.pop() current = parent if i in[‘+’, ’-’, ‘*’, ‘/’]: current.set_root_val(i) curre nt.insert.right(‘’) s.push(current) current = current.get_right() if i == ‘)’: current = s.pop() else: raise ValueError return e_tree def evaluate(p_tree): oper = {‘+’: opertor.add, ’-’ : operator.sub, ’*’ : operator.mul, ‘/’ : operator.fr} left = p_tree.get_left() right = p_tree.get_right() if left and right: #若左右孩子都不为空 fn = oper[p_tree.get_root_val()] return fn(evaluate(left),evaluate(right)) else: return p_tree.get_root_val() 4.树、森林、二叉树的相互转化及遍历。 树与二叉树的相互转化： 树的遍历：前序（先根）：ABCEFGDH 后序（后根）:BEFGCHDA 树的遍历与对应的二叉树对应关系：树的前序遍历对应二叉树的前序遍历，树的后序遍历对应二叉树的中序遍历 练习：树的先根访问序列为GFKDAIEBCHJ 后根访问序列为DIAEKFCJHBG ，画出树 森林转化为二叉树： A C A B D F E G I J H D B C E F G H I J 5.什么是二叉堆？简述采用二叉堆实现优先队列的算法的思想。 二叉堆：二叉堆看起来很像一个完全二叉树，但它实质上只用一个简单的列表存储。二叉堆有两种常见的形式：min堆，其中最小的项总是在前面，即双亲的值总是小于或等于它的孩子的值；而max堆是最大的项总是在前面。 实现优先队列思想：将优先队列初始化为一个空的二叉堆，调用二叉堆中的插入方法实现优先队列的入队，调用二叉堆的删除最小值方法实现从、优先队列的出队操作。 6.二叉树先序、中序、后序的递归遍历算法。 先序： def preorder(tree): if tree: print(tree.get_root_val()) preorder(tree.get_left()) preorder(tree.get_right()) 中序： def inorder(tree): if tree: inorder(get_left()) print(tree.get_root_val()) inorder(get_right()) 后序： def posorder(tree): if tree: posorder(tree.get_left()) posorder(tree.get_right()) print(tree.get_root_val()) 7.二叉排序树的构建，如何构建一颗平衡二叉树。 二叉排序树的构建： a)二叉树的插入: 已知一个关键字值为Key的结点s，插入的方法： ①若二叉排序树是空树，则Key 成为二叉排序树的根； ②若二叉排序树非空，则将key与二叉树排序树的根进行比较: ?如果key的值等于根结点的值，则停止插入; ?如果key的值小于根结点的值，则将key插入左子树; ?如果key的值大于根结点的值，则将key插入右子树。 b)二叉排序树的生成方法： 将二叉排序树初始化为一棵空树，然后逐个读入元素，每读入一个元素，就建立一个新的结点插入到当前已生成的二叉排序树中，即调用上述二叉排 序树的插入算法将新结点插入。 c)二叉排序树的删除： 首先确定被删除的结点是否在二叉排序树中。 若不在，则不做任何操作； 否则，假设要删除的结点为p，结点p的双亲结点为f，并假设结点p 是结点f的左孩子（右孩子的情况类似）。 1）若p为叶结点，则可直接将其删除： f->lchild=NULL； 2）若p结点只有左子树，或只有右子树，则可将p的左子树或右子树 直接改为其双亲结点f的左子树。即：f->lchild=p->lchild（或 f->lchild=p->rchild） 3）若p既有左子树，又有右子树。则首先找到p结点在中序序列中的 直接后继节点（successor:The successor is guaranteed to have no more than one child）S 结点，S的右孩子成为S双亲的左孩子。将S替换到 删除节点P位置。 d)二叉排序树的查找： 根据二叉排序树的特点，首先将待查关键字k与根结点关键字t进行比 较，如果： （1）k= t：则返回根结点地址； （2）k （3）k>t：则进一步查右子树。 显然，这是一个递归过程。 平衡二叉排序树的构建： 在一个平衡二叉排序树上插入一个新结点S时，主要包括以下三步： （1）查找应插位置，同时记录离插入位置最近的可能失衡结点A（A的平衡因子不等于0）。 （2）插入新结点S，并修改从A到S路径上各结点的平衡因子。 （3）根据A、B的平衡因子，判断是否失衡以及失衡类型，并做相应处理。 失衡类型： LL：在根节点的左子树的左子树插入元素后导致失衡 RR：在根节点的右子树的右子树插入元素后导致失衡 LR：在根节点的左子树的右子树插入元素后导致失衡 RL：在根节点的右子树的左子树插入元素后导致失衡 判断类型：RL 调整：将E改为D的右子树；将失衡结点B改为D的左子树，将D原来的左子树改为B的右子树
相关主题
文本预览