广东大学课程计算机科学期末试卷

广东大学课程计算机科学期末试卷考试时长：120分钟满分：100分班级：__________姓名：__________学号：__________得分：__________广东大学课程计算机科学期末试卷考核对象：计算机科学专业本科二年级学生题型分值分布：-单选题（20分）-填空题（20分）-判断题（20分）-简答题（12分）-应用题（18分）总分：100分一、单选题（每题2分，共10题，总分20分）1.下列哪种数据结构是先进先出（FIFO）的？A.栈B.队列C.链表D.树2.在二叉搜索树中，任意节点的左子树中的所有节点值均小于该节点的值，右子树中的所有节点值均大于该节点的值，该性质称为？A.完全二叉树性质B.满二叉树性质C.二叉搜索树性质D.平衡二叉树性质3.以下哪种排序算法的平均时间复杂度为O(n²)？A.快速排序B.归并排序C.堆排序D.插入排序4.在TCP/IP协议簇中，负责数据传输层的协议是？A.HTTPB.FTPC.TCPD.SMTP5.以下哪个不是数据库ACID特性？A.原子性B.一致性C.隔离性D.可恢复性6.在面向对象编程中，封装的含义是？A.继承B.多态C.封装数据和行为D.抽象7.以下哪种算法适用于解决最短路径问题？A.Dijkstra算法B.Floyd-Warshall算法C.A算法D.以上都是8.在SQL中，用于删除表的语句是？A.DELETEB.DROPC.REMOVED.ERASE9.以下哪种设计模式属于创建型模式？A.单例模式B.策略模式C.观察者模式D.责任链模式10.在数据压缩中，Huffman编码属于哪种编码方式？A.无损压缩B.有损压缩C.预测编码D.游程编码二、填空题（每题2分，共10题，总分20分）1.在二叉树中，一个节点的子节点数量称为______。2.快速排序的平均时间复杂度为______。3.TCP协议的连接建立过程称为______。4.数据库的完整性约束包括实体完整性、______和参照完整性。5.在面向对象中，继承分为单继承和______。6.图的两种基本表示方法为邻接矩阵和______。7.SQL中用于查询数据的语句是______。8.设计模式中的“开闭原则”指的是软件实体应对扩展开放，对修改封闭。______是开闭原则的核心思想。9.在数据结构中，栈的两种基本操作是______和出栈。10.哈夫曼编码的核心思想是使用______的编码方式来表示数据。三、判断题（每题2分，共10题，总分20分）1.二叉搜索树的删除操作可能需要重新平衡树。（√）2.堆排序是一种稳定的排序算法。（×）3.TCP协议是无连接的。（×）4.数据库的并发控制主要依靠事务隔离级别实现。（√）5.面向对象编程中，抽象是指将共同特征封装成类。（√）6.图的广度优先搜索（BFS）只能用于无权图。（×）7.SQL中的JOIN操作可以连接多个表。（√）8.单例模式确保一个类只有一个实例，并提供全局访问点。（√）9.Huffman编码是一种无损压缩算法。（√）10.快速排序在最坏情况下的时间复杂度为O(n³)。（×）四、简答题（每题4分，共3题，总分12分）1.简述栈和队列的区别。2.解释TCP协议的三次握手过程。3.什么是数据库的参照完整性？五、应用题（每题9分，共2题，总分18分）1.给定一个无重复元素的数组，使用快速排序算法对以下数组进行排序：[8,3,1,7,0,10,2,5,6,4]。请写出关键步骤（包括分区过程和最终排序结果）。2.假设有一个数据库表`Students`，包含以下字段：`StudentID`（主键）、`Name`、`Major`、`Grade`。请编写SQL语句完成以下操作：a.查询所有计算机科学专业的学生及其成绩。b.删除`StudentID`为1001的学生记录。标准答案及解析一、单选题1.B2.C3.D4.C5.D6.C7.D8.B9.A10.A解析：1.队列是先进先出的数据结构。2.二叉搜索树的性质是节点值满足左小右大的关系。3.插入排序的平均时间复杂度为O(n²)。4.TCP协议属于传输层的协议。5.可恢复性不是ACID特性，ACID包括原子性、一致性、隔离性、持久性。6.封装是指将数据和操作绑定在一起。7.以上算法都可用于最短路径问题。8.DROP语句用于删除表。9.单例模式是创建型模式。10.Huffman编码是无损压缩算法。二、填空题1.度2.O(n²)3.三次握手4.用户定义完整性5.多继承6.邻接表7.SELECT8.可扩展性9.入栈10.负载最小的解析：1.节点的子节点数量称为度。2.快速排序的平均时间复杂度为O(n²)。3.TCP连接建立通过三次握手完成。4.数据库完整性约束包括实体完整性、用户定义完整性和参照完整性。5.继承分为单继承和多继承。6.图的表示方法有邻接矩阵和邻接表。7.SELECT语句用于查询数据。8.开闭原则的核心是可扩展性。9.栈的基本操作是入栈和出栈。10.Huffman编码使用负载最小的编码方式。三、判断题1.√2.×3.×4.√5.√6.×7.√8.√9.√10.×解析：1.二叉搜索树删除节点可能需要重新平衡（如AVL树）。2.堆排序不稳定。3.TCP是面向连接的协议。4.并发控制通过事务隔离级别实现。5.抽象是将共同特征封装成类。6.BFS可用于有权图，只需调整优先级队列。7.JOIN操作可连接多个表。8.单例模式确保全局唯一访问点。9.Huffman编码无损压缩。10.快速排序最坏情况为O(n²)。四、简答题1.栈和队列的区别：-栈是先进后出（LIFO）的数据结构，只能在一端（栈顶）进行插入和删除操作。-队列是先进先出（FIFO）的数据结构，两端分别称为队头和队尾，队头出队，队尾入队。2.TCP三次握手：-第一次：客户端发送SYN包（seq=x）给服务器，请求连接。-第二次：服务器回复SYN+ACK包（seq=y，ack=x+1）确认连接。-第三次：客户端发送ACK包（seq=x+1，ack=y+1）完成连接建立。3.参照完整性：-指数据库中外键约束的引用完整性，确保外键值必须在被引用的主表中存在。例如，订单表的外键必须引用客户表中的客户ID。五、应用题1.快速排序步骤：-原始数组：[8,3,1,7,0,10,2,5,6,4]-选择8为pivot，分区后：[3,1,7,0,2,5,6,4]和[10]-继续对[3,1,7,0,2,5,6,4]分区，选择3为pivot，分区后：[1,0,2,4]和[7,5,6]-递归排序，最终排序结果：[0,1,2,3,4,5,6,7,8,10]