2025届西北工业大学航空航天计算专业计算机科学与技术试题

2025届西北工业大学航空航天计算专业计算机科学与技术试题汇总考试时间：______分钟总分：______分姓名：______一、简述数据结构中栈和队列的区别，并分别举例说明它们在计算机系统中的典型应用场景。二、假设使用快速排序算法对包含n个元素的数组进行排序。请描述快速排序的基本思想，并分析在最佳、平均和最坏情况下，快速排序所需比较次数的大致数量级（用大O表示法）。三、在计算机组成原理中，解释什么是“冯·诺依曼体系结构”，并说明其核心思想对现代计算机设计的影响。四、某计算机的内存地址空间为1MB，采用32位物理地址。若CPU的数据总线宽度为32位，地址总线宽度为32位，问该计算机的Cache容量和主存容量分别能达到多少（不考虑其他因素）？五、操作系统中引入“进程”概念的目的是什么？与“线程”相比，进程具有哪些主要特点？六、简述操作系统中实现进程同步的常用方法，并说明使用信号量机制解决死锁问题的基本原理。七、描述TCP协议如何保证数据传输的可靠性和顺序性。请分别说明TCP连接建立过程中的“三次握手”和“四次挥手”的步骤。八、什么是IP地址？解释IPv4地址与IPv6地址的主要区别，并说明引入IPv6的必要性。九、在关系数据库中，什么是“范式”？请简述第一范式（1NF）、第二范式（2NF）和第三范式（3NF）的主要要求，并说明为什么需要将数据库设计满足范式要求。十、假设你需要设计一个用于存储和管理飞行计划数据的数据库表。请说明该表至少应该包含哪些关键字段，并简要说明每个字段的意义和数据类型（例如，飞行编号、起飞时间、终点站、载客量等）。试卷答案一、栈是一种后进先出（LIFO）的数据结构，其操作只能在栈顶进行；队列是一种先进先出（FIFO）的数据结构，其操作在队头进行入队，在队尾进行出队。典型应用场景：栈用于函数调用栈、表达式求值、文本编辑器撤销操作等；队列用于任务调度、打印队列、消息队列等。二、快速排序的基本思想是分治法。选择一个基准元素，将数组划分为两部分，使得左部所有元素不大于基准，右部所有元素不小于基准，然后递归地对左右两部分进行快速排序。最佳情况（每次划分均分）：比较次数为O(nlogn)；平均情况：比较次数为O(nlogn)；最坏情况（每次划分只减少一个元素，如已排序数组）：比较次数为O(n^2)。三、冯·诺依曼体系结构是指计算机由运算器、控制器、存储器、输入设备和输出设备五部分组成，并采用存储程序方式，即将指令和数据存放在存储器中，按地址访问。其核心思想是程序存储和指令驱动，对现代计算机设计的影响在于奠定了计算机的基本结构框架，使得计算机能够自动执行存储的程序。四、Cache容量取决于具体实现，通常远小于主存容量，例如64KB、256MB等。主存容量为1MB，即2^20字节。若CPU地址总线宽度为32位，则可直接寻址2^32个地址单元，每个地址单元通常对应一个字节，因此物理主存容量理论上可达2^32字节，即4GB（注意：实际主存容量受硬件和地址映射方式限制，可能小于此理论值）。五、引入“进程”概念的目的是为了更好地管理计算机系统中的资源，并提高系统并发执行能力。进程是资源分配的基本单位（拥有独立地址空间、资源），是程序的一次执行过程。与线程相比，进程的主要特点包括：拥有独立的地址空间，进程间内存隔离；资源拥有者，可以创建、终止、睡眠进程；调度和执行的基本单位；进程间通信（IPC）机制相对复杂；开销较大（地址空间、资源管理）。六、操作系统中实现进程同步的常用方法包括：临界区、信号量机制、管程等。使用信号量机制解决死锁问题的基本原理是：通过引入信号量（一个整型变量）及P、V操作（P操作：申请资源，减1，若小于0进程阻塞；V操作：释放资源，加1，唤醒阻塞进程），来控制对共享资源的访问顺序，协调进程间的执行，从而避免死锁的发生。七、TCP协议通过序列号、确认应答（ACK）、超时重传、校验和、流量控制（滑动窗口）和拥塞控制等机制保证数据传输的可靠性和顺序性。可靠性体现在：发送方发送数据后等待确认，接收方收到数据后发送确认，若超时则重传；顺序性体现在：每个TCP报文段包含序列号，接收方按序列号有序重组数据。TCP连接建立的三次握手：①客户端发送SYN包，进入SYN_SENT状态；②服务器回复SYN-ACK包，进入SYN_RCVD状态；③客户端发送ACK包，进入ESTABLISHED状态，服务器进入ESTABLISHED状态，连接建立。TCP连接释放的四次挥手：①一方发送FIN包，进入FIN_WAIT_1状态；②另一方回复ACK包，进入CLOSE_WAIT状态；①方收到ACK后进入FIN_WAIT_2状态；②方发送FIN包，进入LAST_ACK状态；②方收到ACK后进入TIME_WAIT状态，等待计时器后关闭；①方收到ACK后进入TIME_WAIT状态，等待计时器后关闭。八、IP地址是分配给每个网络接口的唯一标识符，用于在网络层路由数据包。IPv4地址是32位二进制数，通常表示为4个8位字节（即点分十进制格式，如192.168.1.1），地址空间有限（约40亿地址）。IPv6地址是128位二进制数，通常表示为8个16位十六进制数（如2001:0db8:85a3:0000:0000:8a2e:0370:7334），地址空间极大（约3.4x10^38个地址）。引入IPv6的必要性主要是为了解决IPv4地址枯竭的问题，并提供了更丰富的功能（如更高效的路由、更好的安全性、更小的头部等）。九、范式是关系数据库中用于衡量数据依赖程度和消除冗余、避免插入/删除/更新异常的理论。第一范式（1NF）：要求关系中的每个属性都是原子值，即不可再分。第二范式（2NF）：要求关系满足1NF，且非主属性完全函数依赖于所有主键（适用于有复合主键的情况）。第三范式（3NF）：要求关系满足2NF，且非主属性之间不存在函数依赖（即非主属性只依赖于主键，不存在传递依赖）。需要将数据库设计满足范式要求，主要是为了确保数据的规范化，减少数据冗余，保证数据的一致性，提高数据integrity，简化数据维护。十、设计用于存储和管理飞行计划数据的数据库表，至少应包含以下关键字段：1.`flight_id`(飞行编号):字符串类型，唯一标识一次飞行，主键。2.`schedule_departure_time`(计划起飞时间):日期时间类型，记录计划的起飞时刻。3.`schedule_arrival_time`(计划到达时间):日期时间类型，记录计划的到达时刻。4.`departure_airport`(起飞机场):字符串类型，记录出发机场名称或代码。5.`arrival_airport`(到达机场):字符串类型，记录目的机场名称或代码。6.`aircraft_type`(飞机类型):字符串类型，记录执行该航班的飞机型号。7.`capacity`(载客量):整数类型，