计算机理论考试题及答案

计算机理论考试题及答案一、单项选择题（每题2分，共20分）1.冯·诺依曼结构计算机的核心特征是（）。A.采用二进制表示数据B.程序和数据存储在同一存储器中C.具备运算器和控制器分离设计D.支持多任务并行处理2.某计算机的CPU主频为2GHz，执行某段程序时，CPI（每条指令的时钟周期数）为1.5，则该程序的MIPS（每秒百万条指令数）为（）。A.1000B.1333C.1500D.20003.以下关于操作系统进程状态的描述中，错误的是（）。A.运行态进程因时间片耗尽会转为就绪态B.阻塞态进程等待的事件完成后直接转为运行态C.就绪态进程获得CPU资源后转为运行态D.创建态进程完成初始化后转为就绪态4.若某二叉树的前序遍历序列为ABDECF，中序遍历序列为DBEAFC，则后序遍历序列为（）。A.DEBFCAB.DEBCFAC.EDBFCAD.DEFBCA5.以下关于TCP协议的描述中，正确的是（）。A.TCP提供无连接的不可靠传输服务B.TCP的滑动窗口机制用于流量控制C.TCP报文段的校验和字段仅校验数据部分D.TCP的端口号范围是0~10236.关系数据库中，若一个关系模式R满足：所有非主属性完全函数依赖于候选键，且不存在传递函数依赖，则R属于（）。A.第一范式（1NF）B.第二范式（2NF）C.第三范式（3NF）D.巴斯-科德范式（BCNF）7.虚拟内存管理中，页表项的“有效位”用于表示（）。A.该页是否在内存中B.该页最近是否被访问过C.该页是否被修改过D.该页的访问权限8.以下排序算法中，时间复杂度在最坏情况下为O(n²)的是（）。A.快速排序B.归并排序C.堆排序D.冒泡排序9.在OSI参考模型中，负责将上层数据封装成帧并进行差错检测的是（）。A.物理层B.数据链路层C.网络层D.传输层10.某32位计算机的虚拟地址空间为4GB，采用页式管理，页大小为4KB，则页表项的页号字段至少需要（）位。A.10B.12C.20D.30二、填空题（每空2分，共20分）1.计算机硬件的五大基本组成部分是运算器、控制器、存储器、输入设备和（）。2.指令周期通常分为取指周期、（）、执行周期和中断周期。3.操作系统中，进程的三种基本状态是运行态、就绪态和（）。4.数据结构中，队列的基本操作特性是（）。5.TCP/IP模型的传输层主要有TCP和（）两种协议。6.数据库系统中，实体-联系模型（E-R模型）的三个基本要素是实体、属性和（）。7.虚拟内存的理论基础是程序的（）原理，包括时间局部性和空间局部性。8.哈希表（散列表）中解决冲突的常用方法有开放定址法和（）。9.IPv4地址的32位二进制通常分为网络号和（）两部分。10.操作系统的磁盘调度算法中，（）算法通过减少磁头移动距离来优化I/O性能，类似于电梯运行方式。三、简答题（每题8分，共40分）1.简述计算机存储系统的层次结构及其设计依据。2.说明进程与线程的区别，并列举操作系统支持多线程的优势。3.解释TCP三次握手的过程，并说明其如何解决“已失效的连接请求报文段”问题。4.分析快速排序的基本思想，说明其平均时间复杂度和最坏时间复杂度的差异及原因。5.什么是数据库的事务？简述事务的ACID特性及其含义。四、综合题（每题10分，共20分）1.某计算机采用页式虚拟内存管理，页大小为4KB，虚拟地址32位，物理内存大小为256MB，页表项包含有效位、修改位、访问位和物理页号。假设某进程的页表如下（仅列出部分页表项）：虚拟页号有效位修改位访问位物理页号0101121010—2111531008（1）计算虚拟地址0x12345678的页号和页内偏移量。（2）若访问该虚拟地址时快表（TLB）缺失，描述地址转换的完整过程（包括页表访问和可能的缺页处理）。2.某公司网络拓扑如下：总部（IP段/24）通过路由器R1连接到互联网，分公司（IP段/24）通过路由器R2连接到同一互联网。总部内有主机A（0），分公司内有主机B（0）。假设主机A要向主机B发送一个HTTP请求（目的端口80），请分析：（1）数据从主机A到主机B的传输路径（按设备顺序列出）。（2）数据在传输过程中各层（物理层、数据链路层、网络层、传输层）的主要处理操作。答案一、单项选择题1.B（冯·诺依曼结构的核心是“存储程序”，即程序和数据统一存储在存储器中）2.B（MIPS=主频/(CPI×10⁶)=2×10⁹/(1.5×10⁶)≈1333）3.B（阻塞态进程事件完成后转为就绪态，需等待CPU调度）4.A（前序确定根A，中序划分左右子树，递归构建后序）5.B（TCP是面向连接的可靠传输，滑动窗口用于流量控制）6.C（3NF消除非主属性对候选键的传递依赖）7.A（有效位标记页是否在内存中）8.D（冒泡排序最坏情况为逆序，时间复杂度O(n²)）9.B（数据链路层负责帧封装和差错检测）10.C（页大小4KB=2¹²B，页号字段=32-12=20位）二、填空题1.输出设备2.译码（或指令分析）周期3.阻塞态（或等待态）4.先进先出（FIFO）5.UDP6.联系（或关系）7.局部性8.链地址法（或拉链法）9.主机号10.扫描（SCAN）三、简答题1.存储系统层次结构由高速缓存（Cache）、主存（内存）、外存（磁盘）组成。设计依据是程序的局部性原理（时间局部性：近期访问过的信息可能再次访问；空间局部性：近期访问的信息附近的信息可能被访问）。通过“速度由快到慢、容量由小到大、成本由高到低”的层次结构，平衡访问速度和存储成本，提升系统整体性能。2.进程与线程的区别：进程是资源分配的基本单位，线程是CPU调度的基本单位；进程拥有独立的地址空间，线程共享所属进程的资源；进程间切换开销大，线程间切换开销小。多线程优势：提高CPU利用率（并发执行）、减少程序响应时间、降低资源消耗（共享进程资源）。3.TCP三次握手过程：（1）客户端发送SYN=1，seq=x的连接请求；（2）服务器回复SYN=1，ACK=1，seq=y，ack=x+1的确认；（3）客户端发送ACK=1，seq=x+1，ack=y+1的最终确认。解决“已失效的连接请求”问题：若客户端早期发送的连接请求在网络中滞留，后续客户端已关闭该连接，当滞留的请求到达服务器时，服务器会发送确认（第二次握手），但客户端此时无对应连接，会忽略该确认，避免建立无效连接。4.快速排序基本思想：选择基准元素，将数组分为小于基准和大于基准的两部分，递归排序子数组。平均时间复杂度O(nlogn)：每次划分较均匀，递归深度为logn，每层处理n个元素；最坏时间复杂度O(n²)：当数组已有序或逆序时，每次划分极不均匀（如基准为最小/最大值），递归深度为n，每层处理n个元素。5.事务是数据库中逻辑上不可分割的操作序列，作为一个整体执行。ACID特性：原子性（Atomicity）：事务要么全部执行，要么全部回滚；一致性（Consistency）：事务执行前后数据库状态保持一致；隔离性（Isolation）：多个事务并发执行时互不干扰；持久性（Durability）：事务提交后结果永久保存。四、综合题1.（1）虚拟地址0x12345678为32位十六进制，转换为二进制后，页大小4KB=2¹²B，页内偏移占低12位。十六进制0x12345678的二进制为：00010010001101000101011001111000低12位（最后12位）是011001111000（即页内偏移量=0x678）；剩余高位为页号：00010010001101000101（共20位），即页号=0x12345（十进制为74565）。（2）地址转换过程：①TLB缺失，访问内存中的页表，根据页号0x12345查找页表项；②检查页表项的有效位：假设该页号对应页表项有效位为1（如虚拟页号0、2、3），则获取物理页号；③若有效位为0（如虚拟页号1），触发缺页中断：操作系统选择换出页（根据置换算法，如LRU，选择访问位为0的页，如虚拟页号3）；若换出页的修改位为1（如虚拟页号2），需将其写回磁盘；从磁盘读取目标页到内存，更新页表项的有效位、物理页号、修改位（初始为0）、访问位（置1）；重新执行访问指令，此时页表项有效，获取物理页号；④物理页号与页内偏移组合得到物理地址（物理页号×页大小+页内偏移）。2.（1）传输路径：主机A→总部交换机→R1→互联网→R2→分公司交换机→主机B。（2）各层处理操作：物理层：主机A将数据转换为电/光信号，通过双绞线/光纤传输；交换机、路由器转发比特流。数据链路层：主机A封装MAC帧（源MAC=A的MAC，目的MAC=R1的接口MAC）；R1接收帧，解封装后重新封装（源MAC=R1的出