2024年计算机真题专项突破

2024年计算机真题专项突破考试时间：______分钟总分：______分姓名：______一、简述数据结构中线性表、栈和队列的定义、基本操作，并比较它们的异同点。二、说明冒泡排序、选择排序和插入排序的基本思想，并分析它们的时间复杂度（最好、平均、最坏情况）。三、什么是操作系统？简述操作系统的基本功能和类型（至少列举两种）。四、解释进程与线程的区别与联系。简述进程状态转换的原因及过程。五、描述TCP协议的三次握手过程，说明每次握手阶段的主要目的。六、什么是IP地址？简述IPv4地址的分类方法。什么是子网划分？简述其基本原理和优点。七、解释HTTP协议的GET和POST请求方法的主要区别。说明HTTP请求和响应消息的基本结构。八、什么是数据库范式？简述第一范式（1NF）、第二范式（2NF）和第三范式（3NF）的定义及要求。九、什么是递归算法？简述递归算法的适用条件。给出一个可以使用递归方法解决的问题，并描述其递归解法。十、简述操作系统中内存管理的概念。说明分页存储管理和分段存储管理的区别。十一、设计一个算法，用于查找无序链表中倒数第k个结点。要求说明算法的基本思路，并用文字描述算法步骤（类似于伪代码）。十二、某网络中的主机A和B分别属于不同的子网，子网掩码分别为和28。请计算主机A和B的网络地址、广播地址和主机地址范围。试卷答案一、线性表：零个或多个元素组成的有限序列。基本操作：插入、删除、查找、遍历等。栈：只允许在一端（栈顶）进行插入和删除操作的线性表（LIFO）。基本操作：入栈、出栈、栈顶元素查看。队列：允许在一端（队尾）插入元素，在另一端（队头）删除元素的线性表（FIFO）。基本操作：入队、出队、队头元素查看。异同：都是线性结构；存储元素的方式可以是顺序存储或链式存储；操作限制不同（线性表操作位置灵活，栈只限栈顶，队列只限队头/队尾）。二、冒泡排序：重复遍历待排序序列，比较相邻元素，若逆序则交换，直到没有逆序。选择排序：每次从未排序部分找出最小（或最大）元素，存放到已排序部分的末尾。插入排序：将每个元素插入到已排序部分的正确位置。时间复杂度：*冒泡排序：最好O(n)，平均/最坏O(n^2)。*选择排序：最好/平均/最坏O(n^2)。*插入排序：最好O(n)，平均/最坏O(n^2)。三、操作系统：管理计算机硬件与软件资源、控制程序执行、提供用户接口的系统软件。基本功能：进程管理、内存管理、文件系统管理、设备管理、提供系统调用接口。类型：批处理系统、分时系统、实时系统、网络操作系统、分布式操作系统、嵌入式操作系统。四、区别：进程是资源分配的基本单位，线程是CPU调度的基本单位。进程拥有独立的地址空间，线程共享所属进程的地址空间。联系：线程是进程的一部分，一个进程可以包含多个线程。进程创建线程比创建进程开销小。区别在于资源拥有和调度单元不同。五、三次握手：1.客户端向服务器发送SYN包（SYN=1，seq=x），请求建立连接。2.服务器收到SYN包后，回复SYN-ACK包（SYN=1，ACK=1，ack=x+1，seq=y），表示同意连接。3.客户端收到SYN-ACK包后，发送ACK包（ACK=1，ack=y+1，seq=x+1），完成连接建立。目的：*第一阶段：客户端告知服务器建立连接的意愿。*第二阶段：服务器确认客户端的请求，并告知客户端自己的初始序列号。*第三阶段：客户端确认服务器的确认，连接建立成功，双方可以开始数据传输。六、IP地址：互联网地址，用于唯一标识一台网络设备。IPv4地址分类：A类（1-，网络部分占8位，主机部分占24位）、B类（128-，网络部分占16位，主机部分占16位）、C类（192-，网络部分占24位，主机部分占8位）。子网划分：将一个大的网络（如B类或C类网络）分割成若干个小的子网络（子网），以增加可用主机数量或满足部门划分等需求。原理：从主机位借用若干位作为子网位，形成子网号。优点：提高网络管理灵活性、改善网络性能、增强网络安全性。七、区别：GET请求参数在URL中，无状态，适用于获取数据；POST请求参数在请求体中，可状态，适用于提交数据。结构：HTTP消息由请求行/响应行、请求头/响应头、空行、请求体/响应体组成。八、数据库范式：关系数据库设计规范，用于减少数据冗余、避免插入/更新/删除异常。范式级别：*1NF：每个属性值域中的元素都是原子值（不可再分）。*2NF：满足1NF，且非主属性完全函数依赖于所有主键（针对有复合主键的情况）。*3NF：满足2NF，且非主属性之间不存在函数依赖（即非主属性只依赖于主键）。九、递归算法：函数调用自身来解决问题的算法。适用条件：问题本身或其子问题具有递归性质，存在基准情形（BaseCase）和递归步骤（RecursiveStep）。问题示例：阶乘计算。递归解法：`factorial(n)=n*factorial(n-1)`，基准情形：`factorial(0)=1`。十、内存管理：操作系统对内存资源进行分配、回收和保护的机制。分页存储管理：将物理内存和逻辑地址空间划分成固定大小的块（页Frame），将逻辑地址空间划分成同样大小的块（页Page），通过页表进行地址映射。分段存储管理：将逻辑地址空间按程序的逻辑结构划分成若干个段（Segment），每个段具有独立的意义（如代码段、数据段），物理内存按任意大小分配，通过段表进行地址映射。区别：划分单位不同（页vs段），地址空间划分方式不同（固定大小vs逻辑单位），映射方式不同（页表vs段表）。十一、算法思路：利用快慢指针法。设置两个指针slow和fast，初始都指向链表头结点。fast指针先走k步，然后slow和fast同时开始走，当fast走到链表末尾时，slow指向的结点即为所求。步骤：1.初始化指针slow和fast为头结点。2.fast向前走k步。若fast为空，则k大于链表长度，返回空（或头结点）。3.slow和fast同时开始向后移动，每步移动一个结点。4.当fast到达链表末尾（next为空）时，slow所在位置即为倒数第k个结点。返回slow。十二、网络地址：主机位全为