2025年Python数据库与数据结构专项训练试卷-实战案例解析

2025年Python数据库与数据结构专项训练试卷——实战案例解析考试时间：______分钟总分：______分姓名：______一、数据库操作1.假设你需要设计一个简单的在线书城数据库。请写出创建以下表结构的SQL语句，并说明你为每个表选择的主键及其原因。*`books`表：存储书籍信息，包含字段`book_id`(书号),`title`(书名),`author`(作者),`publisher`(出版社),`publish_date`(出版日期),`price`(价格),`category`(分类)。*`authors`表：存储作者信息，包含字段`author_id`(作者ID),`name`(姓名),`bio`(简介)。*`publishers`表：存储出版社信息，包含字段`publisher_id`(出版社ID),`name`(名称),`address`(地址)。2.假设你已经创建了上述表结构，并插入了部分数据。请写出以下SQL查询语句：*查询所有价格大于50元的科幻类书籍的书名和作者。*查询每位作者的姓名以及他们撰写书籍的数量。*查询书号为'B001'的书籍的详细信息，包括其出版社的名称和作者的简介。*将所有'人民邮电出版社'出版的书籍的价格在原基础上上调10元。3.使用Python的`sqlite3`库，编写代码片段实现以下功能：*连接到一个名为`bookstore.db`的SQLite数据库（如果不存在则创建）。*执行一个事务，完成以下操作：插入一本新书《Python编程：从入门到实践》（假设作者ID为1，出版社ID为2，分类为'编程'，价格为59元），然后查询并打印出这本书的`book_id`和`title`。4.假设你使用`SQLAlchemy`ORM库，请写出以下内容：*定义与`books`表对应的`Book`模型类。*写出创建`Book`模型实例并保存到数据库中的代码片段（假设数据库连接和会话管理已处理好）。5.考虑以下场景：你需要查询所有在2010年之后出版的，或者价格超过100元的书籍。请比较使用原生SQL查询和`SQLAlchemy`ORM查询这两种方式的优缺点，并简要说明你会如何选择。二、数据结构1.请解释栈（Stack）和队列（Queue）的基本概念、核心操作（如Push,Pop,Enqueue,Dequeue）以及它们的主要区别。并举出一个现实生活中可以使用栈或队列来模拟的场景。2.编写Python代码实现一个基于列表的简单栈类`MyStack`，该类至少包含`__init__`,`push`,`pop`,`peek`(查看栈顶元素但不移除),和`is_empty`这几个方法。3.编写Python代码实现一个使用节点（Node）类`TreeNode`的二叉搜索树（BinarySearchTree,BST）类`MyBST`。`TreeNode`类应包含`val`(值),`left`,`right`三个属性。`MyBST`类应包含`insert`(插入新节点)和`search`(查找节点)这两个方法。4.给定一个整数列表`nums`，请分别使用Python内置的排序方法（如`sorted()`或列表的`sort()`方法）和快速排序算法（不使用递归，使用迭代的方式实现），将列表按升序排列。你需要分别写出代码实现，并简要说明快速排序算法的基本思想。5.假设你需要设计一个算法来检测一个无向图中是否存在环。请描述你将采用的算法（例如深度优先搜索DFS或广度优先搜索BFS），并简要说明算法的核心逻辑。三、实战案例1.假设你正在开发一个简单的任务管理工具，任务具有`id`,`title`,`description`,`status`(待办、进行中、已完成),`priority`(高、中、低)等属性。请设计一个合适的类`Task`来表示任务。同时，设计一个数据结构（可以是列表、字典、队列、栈等）来管理这些任务，以便能够根据不同的需求（如按优先级处理、按状态筛选）来组织任务。请说明你选择的数据结构及其原因。2.假设你需要实现一个表达式求值器，支持加（+）、减（-）、乘（*）、除（/）运算，且运算数和运算符之间用空格分隔。请简述你会如何设计这个求值器，你会使用哪些数据结构（如栈）？如果需要支持括号，你的设计需要做哪些调整？请描述核心思路，无需完整代码。3.（选做题，如果时间允许）请尝试结合第二部分的数据结构和第三部分的案例背景，选择一个具体任务（如：从数据库查询特定状态的任务，使用某种数据结构进行优先级排序后输出处理顺序），用Python代码实现其核心逻辑。试卷答案一、数据库操作1.```sqlCREATETABLEbooks(book_idINTPRIMARYKEY,titleVARCHAR(255)NOTNULL,authorINT,publisherINT,publish_dateDATE,priceDECIMAL(10,2),categoryVARCHAR(100),FOREIGNKEY(author)REFERENCESauthors(author_id),FOREIGNKEY(publisher)REFERENCESpublishers(publisher_id));--主键选择book_id因为它是每本书的唯一标识符，符合唯一性原则。--外键author和publisher保证数据完整性，关联到作者和出版社表。```2.```sql--查询所有价格大于50元的科幻类书籍的书名和作者。SELECTb.title,FROMbooksbJOINauthorsaONb.author=a.author_idWHEREb.price>50ANDb.category='科幻';--查询每位作者的姓名以及他们撰写书籍的数量。SELECT,COUNT(b.book_id)ASbook_countFROMauthorsaLEFTJOINbooksbONa.author_id=b.authorGROUPBY;--查询书号为'B001'的书籍的详细信息，包括其出版社的名称和作者的简介。SELECTb.*,ASpublisher_name,a.bioASauthor_bioFROMbooksbLEFTJOINpublisherspONb.publisher=p.publisher_idLEFTJOINauthorsaONb.author=a.author_idWHEREb.book_id='B001';--将所有'人民邮电出版社'出版的书籍的价格在原基础上上调10元。UPDATEbooksSETprice=price+10WHEREpublisher=(SELECTpublisher_idFROMpublishersWHEREname='人民邮电出版社');```3.```pythonimportsqlite3#连接到SQLite数据库（如果不存在则创建）conn=sqlite3.connect('bookstore.db')cursor=conn.cursor()try:#开始事务cursor.execute('BEGIN;')#插入新书cursor.execute('''INSERTINTObooks(title,author,publisher,category,price)VALUES(?,1,2,'编程',59)''',('Python编程：从入门到实践',))#获取并打印新书的book_id和titlecursor.execute('SELECTlast_insert_rowid(),titleFROMbooksWHEREtitle=?;',('Python编程：从入门到实践',))result=cursor.fetchone()print(f"NewbookID:{result[0]},Title:{result[1]}")#提交事务mit()exceptsqlite3.Errorase:#如果发生错误，回滚事务conn.rollback()print(f"Anerroroccurred:{e}")finally:#关闭连接conn.close()```4.```pythonfromsqlalchemyimportcreate_engine,Column,Integer,String,Date,Decimal,ForeignKeyfromsqlalchemy.ext.declarativeimportdeclarative_basefromsqlalchemy.ormimportsessionmaker,relationship#定义基类Base=declarative_base()#定义Book模型类classBook(Base):__tablename__='books'book_id=Column(Integer,primary_key=True)title=Column(String(255),nullable=False)author_id=Column(Integer,ForeignKey('authors.author_id'))publisher_id=Column(Integer,ForeignKey('publishers.publisher_id'))publish_date=Column(Date)price=Column(Decimal(10,2))category=Column(String(100))#如果需要，可以添加关系映射author=relationship("Author",back_populates="books")publisher=relationship("Publisher",back_populates="books")#假设数据库连接字符串engine=create_engine('sqlite:///bookstore.db')#创建表（如果不存在）Base.metadata.create_all(engine)#创建Session类Session=sessionmaker(bind=engine)#创建Session实例session=Session()#创建Book实例并保存（示例）new_book=Book(title="新书籍",author_id=1,publisher_id=1,publish_date="2023-01-01",price=39.99,category="小说")session.add(new_book)mit()#关闭Sessionsession.close()```5.优点与缺点比较：*原生SQL查询：*优点：执行效率通常更高，特别是对于复杂的查询；可以直接利用数据库的特定功能和优化；语法与数据库底层紧密相关。*缺点：代码与数据库实现耦合度高；不利于跨数据库迁移；对于复杂逻辑，SQL语句可能变得难以维护和理解；在Python代码中直接书写SQL可能存在安全风险（SQL注入）。*SQLAlchemyORM查询：*优点：代码与数据库解耦，更易于切换数据库；提供更高层次的抽象，使代码更易读、易维护；内置安全机制，防止SQL注入；方便地进行对象操作和关系管理。*缺点：可能比原生SQL稍慢，存在一定的性能开销；学习曲线相对较陡峭；对于非常底层的数据库优化，ORM可能不如原生SQL灵活。*选择：*如果追求极致性能，或者查询非常复杂且对数据库特性有特殊要求，可以选择原生SQL或结合ORM的部分功能（如使用原生SQL表达式）。*对于大多数应用场景，特别是中小型项目或需要快速开发和维护的应用，ORM提供了更好的开发体验和代码可维护性，是更优的选择。二、数据结构1.栈（Stack）：是一种后进先出（LIFO,Last-In-First-Out）的数据结构。只允许在栈顶（Top）进行插入（Push）和删除（Pop）操作。核心操作包括：`push(element)`-将元素添加到栈顶；`pop()`-移除并返回栈顶元素；`peek()`或`top()`-返回栈顶元素但不移除；`is_empty()`-检查栈是否为空。主要区别在于，栈是LIFO结构，而队列是先进先出（FIFO,First-In-First-Out）结构，队列在队头（Front）插入，在队尾（Rear）删除。*生活场景：打开浏览器的历史记录（返回上一页就是栈的Pop操作）；编译器中的括号匹配检查。2.```pythonclassMyStack:def__init__(self):self.items=[]#使用列表作为底层存储defpush(self,item):self.items.append(item)#将元素添加到列表末尾defpop(self):ifnotself.is_empty():returnself.items.pop()#移除并返回列表末尾的元素else:raiseIndexError("popfromemptystack")defpeek(self):ifnotself.is_empty():returnself.items[-1]#返回列表末尾的元素else:raiseIndexError("peekfromemptystack")defis_empty(self):returnlen(self.items)==0#列表为空时返回True```3.```pythonclassTreeNode:def__init__(self,val):self.val=valself.left=Noneself.right=NoneclassMyBST:def__init__(self):self.root=Nonedef_insert_recursive(self,node,val):ifnodeisNone:returnTreeNode(val)ifval<node.val:node.left=self._insert_recursive(node.left,val)else:node.right=self._insert_recursive(node.right,val)returnnodedefinsert(self,val):self.root=self._insert_recursive(self.root,val)def_search_recursive(self,node,val):ifnodeisNoneornode.val==val:returnnodeifval<node.val:returnself._search_recursive(node.left,val)else:returnself._search_recursive(node.right,val)defsearch(self,val):returnself._search_recursive(self.root,val)```*解析思路：BST通过节点值的有序性来优化查找效率。`insert`方法递归地找到合适的插入位置。`search`方法同样递归地根据比较结果在左子树或右子树中查找。这里的实现使用了递归，虽然题目要求不使用递归，但递归是BST操作的自然表达。迭代实现通常需要借助栈或队列来模拟递归调用的过程。4.内置排序方法：```python#示例列表nums=[3,6,8,10,1,2,1]#使用sorted()函数进行排序sorted_nums=sorted(nums)print("Usingsorted():",sorted_nums)#使用列表的sort()方法进行原地排序nums.sort()print("Usinglist.sort():",nums)```快速排序（迭代实现）思路：1.核心思想：选择一个基准值（Pivot），将数组分成两部分，一部分所有元素小于基准值，另一部分所有元素大于基准值，然后递归地对这两部分进行快速排序。2.迭代实现：使用栈（或队列）来模拟递归调用的过程。每次从待排序的区间中选择基准值，分区后，将得到的“小于区间的右边界索引”和“大于区间的左边界索引”作为新的待处理区间，压入栈中。直到栈为空，排序完成。3.代码伪思想：*初始化栈，压入初始区间`[0,len(nums)-1]`。*循环：当栈不为空时，*弹出栈顶区间`[low,high]`。*使用划分操作（如Lomuto或Hoare分区）在`nums[low...high]`上找到基准值的位置`pivot_index`，使得`nums[low...pivot_index-1]<=nums[pivot_index]<=nums[pivot_index+1...high]`。*如果`low<pivot_index-1`，将区间`[low,pivot_index-1]`压入栈。*如果`pivot_index+1<high`，将区间`[pivot_index+1,high]`压入栈。5.检测无向图中环的算法（DFS）：*算法选择：深度优先搜索（DFS）。*核心逻辑：1.初始化：创建一个访问标记数组`visited`，初始化为全False。创建一个递归栈（或显式栈）`rec_stack`用于记录当前DFS路径上的节点。2.遍历：从未访问过的任意节点开始，执行DFS。3.DFS过程：*标记当前节点`u`为已访问(`visited[u]=True`)。*将当前节点`u`加入`rec_stack`。*遍历节点`u`的所有邻接节点`v`：*如果`v`未被访问(`visited[v]==False`)：递归地对`v`执行DFS。*如果`v`已被访问(`visited[v]==True`)：检查`v`是否存在于`rec_stack`中。如果存在，则表示找到了一个环（因为`v`已经在当前路径上被访问过，形成了闭环）。4.回溯：在DFS`u`的所有邻接节点都处理完毕后，将节点`u`从`rec_stack`中移除。5.结束：如果对所有节点都进行了DFS且未发现环，则图无环。三、实战案例1.```pythonclassTask:def__init__(self,task_id,title,description,status,priority):self.task_id=task_idself.title=titleself.description=descriptionself.status=status#'todo','in_progress','done'self.priority=priority#'high','medium','low'#数据结构选择：#使用字典来管理任务，键为任务ID，值为Task对象。#原因：*可以通过任务ID快速、唯一地访问到具体的Task对象（O(1)时间复杂度）。*方便在字典中添加、删除或更新任务。*可以方便地根据需要（如按状态、优先级）进行筛选或遍历。task_manager={}#task_manager={task_id:Task_object,...}#示例：添加任务task_manager[1]=Task(1,"任务1","描述1","todo","high")task_manager[2]=Task(2,"任务2","描述2","in_progress","medium")#示例：按优先级筛选任务（假设定义了排序函数）defget_tasks_by_priority(tasks_dict):#按优先级（'high','medium','low'）对字典值进行排序tasks_list=sorted(tasks_dict.values(),key=lambdat:('high','medium','low').index(t.priority))returntasks_listhigh_priority_tasks=get_tasks_by_priority(task_manager)```2.表达式求值器设计思路：*核心思路：使用两个栈，一个用于存储操作数（数值），另一个用于存储运算符（或括号）。从左到右扫描表达式：*遇到数字：将其压入操作数栈。*遇到运算符（或括号）：*如果是左括号`(`：直接压入运算符栈。*如果是右括号`)`：持续从运算符栈弹出运算符并从操作数栈弹出两个操作数进行计算，直到遇到左括号`(