2025年没收到港大ds笔试及答案

2025年没收到港大ds笔试及答案

一、单项选择题（总共10题，每题2分）1.在数据结构中，下列哪一种结构是线性结构？A.树B.图C.队列D.图2.下列哪种排序算法的平均时间复杂度是O(nlogn)？A.冒泡排序B.选择排序C.快速排序D.插入排序3.在数据库中，关系模型中的主键是指？A.唯一标识元组的属性或属性组合B.非常重要的属性C.可以重复的属性D.长度较长的属性4.下列哪种数据压缩方法是无损压缩？A.Huffman编码B.LZW编码C.JPEG压缩D.MP3压缩5.在计算机网络中，TCP协议是一种？A.无连接的协议B.有连接的协议C.无状态的协议D.有状态的协议6.下列哪种算法是用于解决最短路径问题的？A.Dijkstra算法B.Floyd-Warshall算法C.Kruskal算法D.Prim算法7.在机器学习中，下列哪种模型是用于分类问题的？A.线性回归模型B.决策树模型C.神经网络模型D.支持向量机模型8.在数据挖掘中，关联规则挖掘的常见算法是？A.Apriori算法B.K-Means算法C.KNN算法D.SVM算法9.在操作系统内核中，下列哪种机制用于管理进程的调度？A.驱动程序B.中断C.进程调度算法D.内存管理10.在软件工程中，下列哪种方法学强调迭代和增量开发？A.瀑布模型B.V模型C.敏捷开发D.精益开发二、填空题（总共10题，每题2分）1.数据结构中的栈是一种______结构，遵循______原则。2.快速排序算法的平均时间复杂度是______。3.数据库中的事务具有ACID特性，其中A代表______。4.无损压缩方法能够______原始数据的压缩版本。5.TCP协议是一种面向______的协议。6.Dijkstra算法用于解决______问题。7.决策树模型在机器学习中常用于______问题。8.数据挖掘中的Apriori算法用于发现数据项之间的______规则。9.操作系统内核中的中断机制用于______外部事件。10.敏捷开发方法强调______和快速响应变化。三、判断题（总共10题，每题2分）1.栈和队列都是线性结构，但栈是先进先出，队列是后进先出。2.冒泡排序算法的时间复杂度在最好情况下是O(n)。3.数据库中的外键用于保证参照完整性。4.JPEG压缩是一种有损压缩方法。5.TCP协议是无连接的协议。6.Floyd-Warshall算法用于解决所有顶点对之间的最短路径问题。7.线性回归模型主要用于分类问题。8.K-Means算法是一种聚类算法。9.进程调度算法用于决定哪个进程在何时使用CPU。10.精益开发方法强调一次性完成所有开发任务。四、简答题（总共4题，每题5分）1.简述栈和队列的区别。2.解释数据库中的参照完整性的概念。3.描述TCP协议与UDP协议的主要区别。4.简述Apriori算法的基本原理。五、讨论题（总共4题，每题5分）1.讨论快速排序算法在不同数据分布下的性能表现。2.分析Dijkstra算法的优缺点及其适用场景。3.讨论机器学习中决策树模型的优缺点。4.讨论敏捷开发方法在软件开发中的应用及其优势。答案和解析一、单项选择题1.C2.C3.A4.B5.B6.A7.D8.A9.C10.C二、填空题1.线性，后进先出2.O(nlogn)3.原子性4.完全恢复原始数据5.连接6.单源最短路径7.分类8.关联9.处理10.迭代三、判断题1.正确2.正确3.正确4.正确5.错误6.正确7.错误8.正确9.正确10.错误四、简答题1.栈是一种后进先出（LIFO）的线性结构，而队列是一种先进先出（FIFO）的线性结构。栈的操作仅限于栈顶，而队列的操作可以在队头和队尾进行。2.参照完整性是指在数据库中，外键约束确保了关系之间的引用完整性，即一个表中的外键值必须在另一个表的主键中存在。这保证了数据的逻辑一致性。3.TCP协议是一种面向连接的、可靠的协议，通过三次握手建立连接，并确保数据的顺序和完整性。而UDP协议是一种无连接的、不可靠的协议，数据传输速度快但不对数据的顺序和完整性进行保证。4.Apriori算法是一种用于关联规则挖掘的算法，其基本原理是基于频繁项集的性质。算法通过生成候选项集，然后通过支持度进行剪枝，最终找到满足最小支持度的频繁项集，并生成关联规则。五、讨论题1.快速排序算法在不同数据分布下的性能表现差异较大。在最佳情况下，即数据分布均匀时，其时间复杂度为O(nlogn)。但在最坏情况下，即数据已经排序或接近排序时，其时间复杂度会退化到O(n^2)。因此，实际应用中常采用随机化快速排序来提高算法的鲁棒性。2.Dijkstra算法的优点是能够高效地找到单源最短路径，适用于稀疏图。但其缺点是只能处理非负权重的边，且在处理大规模图时可能会遇到性能问题。Dijkstra算法适用于需要找到最短路径的场景，如网络路由和交通导航。3.决策树模型的优点是易于理解和解释，能够处理混合类型的数据，且对缺失值不敏感。但其缺点是容易过拟合，对噪声数据敏感，且在处理高维数据时可能会出现性能问题。决策树模型适用于分类和回归问题，尤其是在