数据结构试卷1

一、列表（List）1. 列表简介

列表是Python中最基本的数据结构之一，它是一个有序的可变序列，可以存储不同类型的数据。

# 创建列表 fruits = ['apple', 'banana', 'orange'] # 访问元素 print(fruits[0]) # 输出 apple print(fruits[-1]) # 输出 orange # 修改元素 fruits[1] = 'pear' print(fruits) # 输出 ['apple', 'pear', 'orange'] # 添加元素 fruits.append('grape') # 在末尾添加元素 fruits.insert(1, 'mango') # 在指定位置插入元素 print(fruits) # 输出 ['apple', 'mango', 'pear', 'orange', 'grape'] # 删除元素 fruits.remove('pear') # 删除第一个匹配项 popped_fruit = fruits.pop() # 删除并返回最后一个元素 del fruits[0] # 删除指定索引的元素 print(fruits) # 输出 ['mango'] # 解释： # - 列表支持索引访问和修改 # - 可以使用多种方法添加或删除元素2. 列表推导式

列表推导式是一种简洁的方式来创建列表。

# 创建平方数列表 squares = [x**2 for x in range(10)] print(squares) # 输出 [0, 1, 4, 9, 16, 25, 36, 49, 64, 81] # 过滤偶数的平方数 even_squares = [x**2 for x in range(10) if x % 2 == 0] print(even_squares) # 输出 [0, 4, 16, 36, 64] # 解释： # - 列表推导式提供了一种简洁的方式创建列表 # - 可以结合条件语句进行过滤二、元组（Tuple）1. 元组简介

元组与列表类似，但它是不可变的，即一旦创建就不能修改。

# 创建元组 coordinates = (10, 20) # 访问元素 print(coordinates[0]) # 输出 10 # 尝试修改元组会抛出 TypeError # coordinates[0] = 15 # 这行代码会报错 # 解释： # - 元组使用圆括号创建 # - 元组是不可变的，不能修改其内容2. 元组解包

元组解包是指将元组中的元素赋值给多个变量。

person_info = ('Alice', 25, 'Beijing') name, age, city = person_info print(name) # 输出 Alice print(age) # 输出 25 print(city) # 输出 Beijing # 部分解包 numbers = (1, 2, 3, 4, 5) first, *middle, last = numbers print(first) # 输出 1 print(middle) # 输出 [2, 3, 4] print(last) # 输出 5 # 解释： # - 元组解包提供了简洁的方式来分配元组中的值 # - 使用星号 `*` 可以捕获剩余元素三、字典（Dictionary）1. 字典简介

字典是Python中的一种无序键值对集合，键必须是不可变类型（如字符串、数字或元组），而值可以是任意类型。

# 创建字典 person = {'name': 'Alice', 'age': 25, 'city': 'Beijing'} # 访问元素 print(person['name']) # 输出 Alice # 修改元素 person['age'] = 26 print(person) # 输出 {'name': 'Alice', 'age': 26, 'city': 'Beijing'} # 添加元素 person['gender'] = 'Female' print(person) # 输出 {'name': 'Alice', 'age': 26, 'city': 'Beijing', 'gender': 'Female'} # 删除元素 del person['city'] print(person) # 输出 {'name': 'Alice', 'age': 26, 'gender': 'Female'} # 解释： # - 字典使用花括号创建，键值对用冒号分隔 # - 支持通过键访问、修改和删除元素2. 字典方法

字典提供了许多有用的方法来操作键值对。

# 获取所有键 keys = person.keys() print(keys) # 输出 dict_keys(['name', 'age', 'gender']) # 获取所有值 values = person.values() print(values) # 输出 dict_values(['Alice', 26, 'Female']) # 获取所有键值对 items = person.items() print(items) # 输出 dict_items([('name', 'Alice'), ('age', 26), ('gender', 'Female')]) # 检查键是否存在 if 'name' in person: print("存在 name 键") # 输出存在 name 键 # 获取键对应的值，如果键不存在返回默认值 print(person.get('city', 'Unknown')) # 输出 Unknown # 解释： # - 字典提供了丰富的内置方法来操作键值对 # - `get()` 方法允许指定默认值四、集合（Set）1. 集合简介

集合是Python中的一种无序且不重复元素的容器类型。它基于哈希表实现，因此查找和插入操作的时间复杂度接近于O(1)。

# 创建集合 fruits = {'apple', 'banana', 'orange'} # 添加元素 fruits.add('grape') print(fruits) # 输出 {'apple', 'banana', 'orange', 'grape'} # 删除元素 fruits.remove('banana') # 如果元素不存在会抛出 KeyError fruits.discard('orange') # 即使元素不存在也不会报错 print(fruits) # 输出 {'apple', 'grape'} # 清空集合 fruits.clear() print(fruits) # 输出 set() # 解释： # - 集合使用花括号创建，元素之间用逗号分隔 # - 支持添加、删除和清空操作2. 集合运算

集合支持交集、并集、差集等运算。

set1 = {1, 2, 3} set2 = {3, 4, 5} # 并集 union_set = set1 | set2 # 或者使用 union_set = set1.union(set2) print(union_set) # 输出 {1, 2, 3, 4, 5} # 交集 intersection_set = set1 & set2 # 或者使用 intersection_set = set1.intersection(set2) print(intersection_set) # 输出 {3} # 差集 difference_set = set1 - set2 # 或者使用 difference_set = set1.difference(set2) print(difference_set) # 输出 {1, 2} # 对称差集 sym_diff_set = set1 ^ set2 # 或者使用 sym_diff_set = set1.symmetric_difference(set2) print(sym_diff_set) # 输出 {1, 2, 4, 5} # 解释： # - 集合支持多种集合运算 # - 运算符和方法都可以用于集合运算五、应用场景1. 数据处理

使用列表和字典处理和转换大量数据。

# 示例：计算平均分 grades = [85, 92, 78, 90, 88] average_grade = sum(grades) / len(grades) print(f"平均成绩: {average_grade}") # 示例：统计单词出现频率 from collections import Counter words = ['apple', 'banana', 'apple', 'orange', 'banana', 'apple'] word_counts = Counter(words) print(word_counts) # 输出 Counter({'apple': 3, 'banana': 2, 'orange': 1}) # 解释： # - 列表和字典广泛应用于数据处理任务 # - `Counter` 是一个方便的工具类，用于统计元素频率2. 用户输入处理

使用列表和集合存储用户输入的一系列数据，并进行去重处理。

user_inputs = [] unique_user_inputs = set() while True: user_input = input("请输入一个数字 (输入 'done' 结束): ") if user_input.lower() == 'done': break try: number = float(user_input) user_inputs.append(number) unique_user_inputs.add(number) except ValueError: print("无效输入，请输入一个有效的数字") print(f"您输入的数字: {user_inputs}") print(f"去除重复后的数字: {unique_user_inputs}") # 解释： # - 列表用于存储所有输入 # - 集合用于去除重复元素3. 图算法

使用字典和集合表示图结构，并实现图遍历算法。

def bfs(graph, start): visited = set() queue = [start] while queue: node = queue.pop(0) if node not in visited: visited.add(node) queue.extend(graph[node] - visited) return visited # 示例图 graph = { 'A': {'B', 'C'}, 'B': {'A', 'D', 'E'}, 'C': {'A', 'F'}, 'D': {'B'}, 'E': {'B', 'F'}, 'F': {'C', 'E'} } print(bfs(graph, 'A')) # 输出 {'A', 'B', 'C', 'D', 'E', 'F'} # 解释： # - 字典和集合非常适合表示图结构 # - BFS 算法用于广度优先搜索图六、总结

Python提供了多种内置数据结构，每种结构都有其特点和适用场景：