北京大学2025年计算机科学与技术（软件工程）专业历年真题答案及解析

北京大学2025年计算机科学与技术（软件工程）专业历年真题答案及解析考试时间：______分钟总分：______分姓名：______一、选择题（本大题共5小题，每小题2分，共10分。在每小题列出的四个选项中，只有一项是符合题目要求的，请将所选项前的字母填在题后的括号内。）1.下列数据结构中，适合用来实现先进先出（FIFO）行为的是？A.栈（Stack）B.队列（Queue）C.链表（LinkedList）D.树（Tree）2.设计算法时，选择使用分治法（DivideandConquer）通常是为了解决哪一类问题？A.具有重复子问题的最优问题B.可以高效划分成独立子集的问题C.需要多次访问同一元素的问题D.输入规模非常小的问题3.在多进程环境下，临界区（CriticalSection）是指？A.一个完整的进程执行周期B.进程创建到销毁的全过程C.一个进程中需要原子性执行的小段代码D.操作系统内核管理的内存区域4.下列关于TCP和UDP协议的描述，正确的是？A.TCP提供面向连接的、可靠的、无序的数据传输服务B.UDP提供面向连接的、不可靠的、按序的数据传输服务C.TCP协议头部比UDP协议头部包含更多的控制信息D.在实时视频传输场景下，UDP通常比TCP更受欢迎5.在面向对象设计中，将一个类的公共接口与其具体实现细节分离，允许对实现细节进行自由修改，而不会影响使用该接口的客户端，这主要体现了设计的哪个原则？A.封装（Encapsulation）B.继承（Inheritance）C.多态（Polymorphism）D.抽象（Abstraction）二、填空题（本大题共5小题，每小题2分，共10分。请将答案填写在答题纸的相应位置。）6.在快速排序（QuickSort）算法中，为了提高平均性能和避免最坏情况（如已排序数组），常用的策略是随机选择一个元素作为__________，并使用__________方法进行划分。7.操作系统中，进程上下文切换（ContextSwitch）需要保存和恢复的是进程的__________、程序计数器以及各种__________寄存器的值。8.软件测试中，黑盒测试和白盒测试的主要区别在于测试人员是否需要了解程序的__________。9.在UML（统一建模语言）中，用于表示一个类及其内部结构（属性和操作）的图是__________。10.设计模式中，用于解耦服务请求者与服务提供者，使两者可以独立变化的模式是__________。三、简答题（本大题共3小题，每小题5分，共15分。请将答案填写在答题纸的相应位置。）11.请简述数据结构“二叉搜索树”（BinarySearchTree）的定义及其主要性质。12.什么是操作系统中的“死锁”（Deadlock）？请列举并解释死锁产生的四个必要条件。13.请简述面向对象编程（OOP）的四个基本特性（封装、继承、多态、抽象）及其核心含义。四、计算题（本大题共1小题，共10分。请将答案填写在答题纸的相应位置。）14.给定一个无向连通图G（顶点集V={v1,v2,v3,v4,v5}，边集E={<v1,v2>,<v1,v3>,<v2,v4>,<v3,v4>,<v4,v5>}），请使用深度优先搜索（DFS）算法找出从顶点v1出发对图G进行遍历的访问序列（访问顶点时输出该顶点的编号）。请描述算法执行的主要步骤，并写出最终的访问序列。五、编程题（本大题共1小题，共15分。请将答案填写在答题纸的相应位置。）15.请使用你熟悉的编程语言（如C/C++、Java或Python），实现一个函数或方法，该函数/方法接收一个字符串作为输入，并返回该字符串中所有唯一字符的列表（即只出现一次的字符），按在原字符串中出现的顺序排列。例如，输入字符串"hello"，输出应为['h','e']。请提供函数/方法的代码实现，并简要说明其主要思路。六、综合应用与设计题（本大题共1小题，共20分。请将答案填写在答题纸的相应位置。）16.假设你需要设计一个简单的在线图书推荐系统。请简要描述该系统的核心功能模块，并说明其中至少两个关键模块的设计思路。例如，可以包括用户模块、图书模块、推荐引擎模块等。对于你选择的两个模块，请分别说明它们需要处理的关键数据、需要实现的主要功能以及可能采用的技术或方法。试卷答案一、选择题1.B2.B3.C4.C5.D二、填空题6.基准（或枢轴、pivot），分治（或partition）7.寄存器，状态8.内部实现（或内部结构、代码细节）9.类图（ClassDiagram）10.中介者（Mediator）三、简答题11.解析思路：定义是：二叉搜索树（BST）是二叉树，对于树中的任意节点N，其左子树中所有节点的值均小于N的值，其右子树中所有节点的值均大于N的值。主要性质包括：左子树和右子树本身也必须是二叉搜索树；没有重复的节点值；可以通过中序遍历得到一个有序的节点值序列。12.解析思路：死锁是指两个或多个进程在执行过程中，因争夺资源而造成的一种相互等待的现象，若无外力作用，这些进程都将无法向前推进。产生死锁的四个必要条件是：互斥条件（资源不能被共享）、占有并等待条件（进程至少占有一个资源，并请求其他进程占有的资源）、非抢占条件（资源不能被强制剥夺）、循环等待条件（存在一个进程等待环，环中的每个进程都等待下一个进程占有的资源）。13.解析思路：封装是将数据（属性）和操作数据的方法（行为）捆绑在一起，并对外部隐藏对象的内部实现细节，只通过接口与外部交互。继承允许一个类（子类）继承另一个类（父类）的属性和方法，实现代码复用和扩展，形成类之间的层次关系。多态是指同一个接口（或方法名）可以有不同的实现方式（对应不同类的同名方法），允许使用父类类型的引用调用子类对象的方法，实现接口的统一调用和灵活替换。抽象是从具体事物中抽取共同的、本质的特征，形成概念或类，忽略非本质的细节，关注核心的特性和行为。四、计算题14.解析思路：深度优先搜索（DFS）通常使用递归或栈实现。从起始顶点v1开始访问，标记为已访问。然后选择一个与v1相邻且未访问的顶点（如v2）访问，标记为已访问。对v2进行同样的操作，选择一个未访问的邻接顶点（如v4）访问。继续此过程，深入探索，直到到达叶节点或所有邻接顶点都已访问。然后回溯到上一个节点（v4），探索v4的其他未访问邻接顶点（v3），访问v3。最后回溯到v2，再回溯到v1，探索v1的其他未访问邻接顶点（v3已被访问，只有v3剩下），访问v3。最后回溯到v1，此时所有顶点均已访问。根据此过程，得到访问序列为：v1,v2,v4,v3,v5。（注：DFS的具体路径可能因邻接点的选择顺序不同而略有差异，但访问序列包含所有顶点且满足DFS特性即可）。五、编程题15.解析思路：主要思路是使用一个数据结构（如哈希表或集合）记录每个字符在输入字符串中出现的次数。遍历输入字符串，统计每个字符的出现频率。然后再次遍历输入字符串，对于每个字符，如果其出现次数为1，则将其添加到结果列表中，并确保结果列表中的字符顺序与它们在原字符串中出现的顺序一致。可以使用哈希表记录顺序，或者直接在遍历时判断。六、综合应用与设计题16.解析思路：核心功能模块可能包括用户模块（管理用户信息、偏好设置）、图书模块（管理图书信息、分类）、推荐引擎模块（根据用户行为和图书信息生成推荐列表）、评分/评论模块（用户对图书进行评分和评论）、搜索模块（用户查找图书）等。选择模块：用户模块。关键数据包括用户ID、用户基本信息、浏览历史、收藏列表、评分记录等。主要功能包括用户注册登录、更新个人信息、查看和编辑偏好设置、管理收藏夹等。可能采用的技术或方法包括用户画像构建（基于历史行为、评分等）、协同过滤（基于用户相似性或物品相似性）、内容推荐（基于图书特征和用户兴趣）等。选择模块：推