(2025年)《计算机理论知识》复习题及答案

(2025年)《计算机理论知识》复习题及答案一、单项选择题（每题2分，共30分）1.图灵机的核心组成不包括以下哪一项？A.无限长的纸带B.读写头C.状态寄存器D.中央处理器（CPU）答案：D2.冯·诺依曼体系结构的核心特征是：A.程序和数据存储在不同介质中B.指令和数据以二进制形式统一存储C.采用并行计算模式D.硬件与软件完全解耦答案：B3.以下关于补码表示的描述中，错误的是：A.0的补码表示唯一B.负数的补码是其原码取反加1C.8位补码能表示的整数范围是-128到+127D.补码运算时符号位不参与计算答案：D4.对于完全二叉树，若有n个节点，则其深度为（log₂n取下整）+1的条件是：A.节点按层序从左到右填充B.所有叶子节点在同一层C.树中不存在度为1的节点D.根节点编号为0答案：A5.操作系统中，虚拟内存的页表主要用于：A.记录物理内存的空闲块B.实现虚拟地址到物理地址的映射C.管理进程的上下文切换D.优化文件I/O速度答案：B6.TCP协议中，流量控制的主要实现机制是：A.超时重传B.滑动窗口C.校验和D.拥塞避免算法答案：B7.关系数据库中，若一个关系模式满足“所有非主属性完全函数依赖于候选键”，则该模式至少属于：A.第一范式（1NF）B.第二范式（2NF）C.第三范式（3NF）D.BC范式（BCNF）答案：B8.以下关于编译过程的描述中，正确的是：A.词法分析将源程序转换为抽象语法树B.语法分析检查代码的逻辑错误C.语义分析处理变量类型匹配问题D.目标代码提供阶段输出汇编语言答案：C9.算法的时间复杂度分析中，O(n²)和O(nlogn)的本质区别在于：A.常数因子的大小B.问题规模n增大时的增长速率C.算法是否使用递归D.算法是否稳定答案：B10.在IPv4地址中，192.168.1.1属于：A.A类地址B.B类地址C.C类地址D.私有地址答案：D11.以下哪种数据结构适合实现“后进先出”（LIFO）的操作？A.队列B.栈C.二叉搜索树D.哈希表答案：B12.操作系统的进程状态中，“阻塞态”是指进程：A.正在CPU上执行B.等待某个事件（如I/O完成）C.已分配资源但未获得CPU时间片D.已结束运行答案：B13.数据库事务的ACID特性中，“隔离性”（Isolation）指的是：A.事务一旦提交，其结果不可撤销B.事务执行期间不被其他事务干扰C.事务中的操作要么全部完成，要么全部不完成D.事务处理的数据符合数据库约束答案：B14.以下关于哈希冲突的描述中，错误的是：A.开放寻址法通过探测其他位置存储冲突元素B.链地址法为每个哈希槽维护一个链表C.冲突无法避免，但可以通过优化哈希函数减少D.完美哈希函数可以完全消除冲突答案：D15.分布式系统中，CAP定理的三个特性不包括：A.一致性（Consistency）B.可用性（Availability）C.分区容错性（PartitionTolerance）D.可扩展性（Scalability）答案：D二、填空题（每题2分，共20分）1.计算机中，浮点数的表示通常由符号位、阶码和尾数三部分组成。答案：符号位；阶码；尾数2.二叉树的遍历方式中，若前序遍历序列为ABDCE，中序遍历序列为DBAEC，则后序遍历序列为DBECA（按顺序填写，用空格分隔）。答案：DBECA3.操作系统的进程调度算法中，时间片轮转算法通过固定时间片分配CPU，适用于分时系统；优先级调度算法则根据进程优先级决定执行顺序。答案：时间片轮转；优先级调度4.在TCP/IP模型中，传输层的两个主要协议是TCP（面向连接）和UDP（无连接）。答案：TCP；UDP5.关系数据库的完整性约束包括实体完整性（主键约束）、参照完整性（外键约束）和用户定义的完整性。答案：实体完整性；参照完整性6.算法的空间复杂度是指算法在执行过程中所需的额外存储空间与问题规模n的关系。答案：额外存储空间7.图的遍历方法中，深度优先搜索（DFS）通常使用栈或递归实现，广度优先搜索（BFS）使用队列实现。答案：深度优先搜索（DFS）；广度优先搜索（BFS）8.虚拟内存的置换算法中，最近最久未使用（LRU）算法选择最近长时间未访问的页面置换，先进先出（FIFO）算法选择最早进入内存的页面置换。答案：最近最久未使用（LRU）；先进先出（FIFO）9.编译过程中，中间代码提供阶段将语法分析的结果转换为与机器无关的中间表示（如四元式）。答案：中间代码提供10.区块链的核心技术包括哈希函数、共识机制（如PoW、PoS）和Merkle树结构。答案：哈希函数；共识机制三、简答题（每题6分，共36分）1.简述操作系统中进程与线程的区别。答案：进程是资源分配的基本单位，线程是CPU调度的基本单位；一个进程可包含多个线程，线程共享进程的资源（如内存、文件句柄），但拥有独立的栈和寄存器上下文；进程间切换开销大（需切换页表、缓存等），线程间切换仅需保存/恢复少量寄存器，开销更小；进程间通信（IPC）需通过管道、消息队列等机制，线程间可直接共享内存通信。2.解释TCP三次握手的过程及目的。答案：三次握手用于建立可靠连接：（1）客户端发送SYN=1，随机序号x（SYN报文）；（2）服务器回复SYN=1，ACK=1，确认号x+1，随机序号y（SYN-ACK报文）；（3）客户端发送ACK=1，确认号y+1（ACK报文）。目的是同步双方的初始序号（ISN），确认双方的发送和接收能力正常，避免历史连接的重复初始化。3.说明数据库中事务的原子性（Atomicity）和持久性（Durability）的含义及实现方式。答案：原子性指事务的所有操作要么全部成功，要么全部回滚，不可部分执行。实现依赖日志（如redo/undo日志），事务执行前记录操作，失败时通过日志回滚。持久性指事务提交后，数据修改永久保存，即使系统崩溃也不丢失。实现依赖磁盘持久化（如写日志到磁盘后再提交，或使用RAID冗余存储）。4.比较顺序查找与二分查找的适用场景及时间复杂度。答案：顺序查找适用于无序或小数据量的线性表，时间复杂度O(n)；二分查找要求数据有序（如升序），通过比较中间元素缩小查找范围，时间复杂度O(logn)。顺序查找对数据无要求但效率低，二分查找效率高但依赖有序性，适用于大数据量且需频繁查找的场景（如数据库索引）。5.简述计算机网络中CSMA/CD（载波侦听多路访问/冲突检测）的工作流程。答案：（1）节点发送数据前侦听信道，若空闲则发送；（2）发送过程中持续检测冲突，若检测到冲突则立即停止发送，并发送阻塞信号；（3）等待随机退避时间（如二进制指数退避算法）后，重新尝试发送。该机制用于以太网，解决共享介质下的多节点争用问题。6.解释编译原理中“词法分析”与“语法分析”的区别与联系。答案：词法分析将源程序字符流转换为词法单元（Token），如关键字、标识符、运算符，处理词法错误（如非法字符）；语法分析根据语法规则（如上下文无关文法）将Token序列转换为语法树（AST），检查语法错误（如括号不匹配）。词法分析是语法分析的基础，语法分析依赖词法分析提供的Token流，两者共同完成对源程序结构的初步验证。四、综合题（共14分）题目1（6分）：已知一棵二叉树的前序遍历序列为ABCDE，中序遍历序列为BADCE。（1）画出该二叉树的结构；（2）写出其后序遍历序列。答案：（1）二叉树结构：A/\BC/\DE（2）后序遍历序列：BDECA题目2（8分）：设计一个简单的文件系统目录结构，要求包含以下内容：-用户“user1”的主目录（/home/user1）；-主目录下有“文档”（docs）和“图片”（pics）子目录；-“文档”目录下有文件“report.txt”和子目录“2024”；-“图片”目录下有文件“photo.jpg”；-给出从根目录到“report.txt”的绝对路径，以及从“pics”目录到“report.txt”的相对路径。答案：目录结构示例：/└