计算机入学考试题目及答案

计算机入学考试题目及答案一、单项选择题（每题2分，共20分）1.以下数据结构中，属于非线性结构的是（）。A.队列B.二叉树C.栈D.线性表答案：B2.冒泡排序在最坏情况下（数组逆序）的时间复杂度为（）。A.O(n)B.O(n²)C.O(nlogn)D.O(1)答案：B3.操作系统中，进程从运行状态转换为阻塞状态的原因通常是（）。A.时间片用完B.被调度程序选中C.等待I/O操作完成D.进程创建完成答案：C4.在TCP/IP模型中，HTTP协议属于（）。A.网络接口层B.网络层C.传输层D.应用层答案：D5.关系数据库中，第二范式（2NF）要求消除（）。A.传递函数依赖B.部分函数依赖C.多值依赖D.完全函数依赖答案：B6.深度为5的满二叉树（根节点深度为1）的节点总数为（）。A.15B.31C.32D.63答案：B（满二叉树节点数为2⁵1=31）7.以下排序算法中，不稳定的是（）。A.冒泡排序B.归并排序C.快速排序D.插入排序答案：C8.虚拟内存的主要作用是（）。A.提高CPU访问内存的速度B.扩展物理内存的容量C.存储系统缓存D.加速文件读写答案：B9.以下不属于对称加密算法的是（）。A.AESB.DESC.RSAD.3DES答案：C（RSA是非对称加密）10.编译过程中，词法分析的主要任务是（）。A.检查语法错误B.将源程序转换为目标代码C.识别单词（如标识符、关键字）D.优化中间代码答案：C二、填空题（每题2分，共20分）1.计算多项式f(x)=a₀+a₁x+a₂x²+…+aₙxⁿ的秦九韶算法的时间复杂度为____。答案：O(n)2.对有序数组进行二分查找，最坏情况下的时间复杂度为____。答案：O(logn)3.TCP建立连接的过程称为____，需要经过____次握手。答案：三次握手；34.数据库实体联系（ER）模型的三个基本元素是____、____、____。答案：实体；属性；联系5.操作系统中，进程的三种基本状态是____、____、____。答案：就绪；运行；阻塞6.深度为5的完全二叉树（根节点深度为1）最少有____个节点。答案：16（完全二叉树最少节点数为2⁴=16）7.HTTP请求中，GET方法通常用于____，POST方法通常用于____。答案：获取资源；提交数据8.快速排序的平均时间复杂度为____，最坏时间复杂度为____。答案：O(nlogn)；O(n²)9.计算机内存地址的编址单位通常是____。答案：字节10.结构化程序设计的三种基本控制结构是____、____、____。答案：顺序；选择；循环三、简答题（每题10分，共40分）1.解释虚拟内存的定义、作用及实现方式。虚拟内存是操作系统为进程提供的一个逻辑地址空间，其容量不受物理内存限制。作用：解决物理内存不足的问题，允许进程使用比物理内存更大的地址空间；通过内存换页（或换段）实现进程间内存隔离，提高系统安全性。实现方式：分页机制：将虚拟内存划分为固定大小的页（Page），物理内存划分为页框（PageFrame），通过页表记录虚拟页与物理页框的映射关系。缺页中断：当进程访问的页不在物理内存时，触发缺页中断，将所需页从磁盘调入内存（若内存不足则置换出部分页）。交换空间：磁盘中预留的空间用于存储暂时不使用的页。2.比较归并排序与快速排序的异同点（从时间复杂度、空间复杂度、稳定性、适用场景角度）。时间复杂度：归并排序平均和最坏均为O(nlogn)；快速排序平均O(nlogn)，最坏O(n²)（如数组已有序时）。空间复杂度：归并排序需要O(n)的额外空间（合并时临时存储）；快速排序需要O(logn)的栈空间（递归调用）。稳定性：归并排序是稳定排序（相等元素的相对顺序不变）；快速排序不稳定（分区过程可能打乱顺序）。适用场景：归并排序适用于外排序（处理大文件）或对稳定性有要求的场景；快速排序适用于内存充足、平均情况性能好的场景（如通用排序）。3.说明关系数据库中1NF、2NF、3NF的定义，并举例说明。1NF（第一范式）：要求关系中的每个属性不可再分（原子性）。例如，若“学生”表包含“联系方式”字段（存储电话+邮箱），则违反1NF，需拆分为“电话”和“邮箱”两个字段。2NF（第二范式）：在1NF基础上，消除非主属性对候选键的部分函数依赖。例如，表（学号，课程号，姓名，成绩）中，候选键为（学号，课程号），姓名仅依赖于学号（部分依赖），需拆分为（学号，姓名）和（学号，课程号，成绩）。3NF（第三范式）：在2NF基础上，消除非主属性对候选键的传递函数依赖。例如，表（学号，系号，系主任）中，学号→系号，系号→系主任（传递依赖），需拆分为（学号，系号）和（系号，系主任）。4.描述TCP三次握手的过程，并说明每一步的作用。三次握手是TCP建立连接的过程，步骤如下：第一步（SYN）：客户端向服务端发送SYN包（同步序列号），标识自己的初始序列号x，并请求建立连接。作用：客户端通知服务端准备连接。第二步（SYN+ACK）：服务端收到SYN后，回复SYN+ACK包，包含自己的初始序列号y，以及对客户端序列号的确认（x+1）。作用：服务端确认客户端请求，并同步自己的序列号。第三步（ACK）：客户端收到SYN+ACK后，发送ACK包，确认服务端的序列号（y+1）。作用：客户端确认服务端已准备好，连接建立完成。三次握手的目的是防止历史连接的重复请求，确保双方通信能力正常，并同步初始序列号。四、编程题（共20分）题目：给定一个整数数组nums和一个整数目标值target，找出所有满足两数之和等于target的不重复二元组。要求：输出结果中每个二元组按升序排列（如[2,7]而非[7,2]）。整个结果数组按二元组的第一个元素升序排列。时间复杂度不超过O(nlogn)。示例：输入nums=[2,7,11,15,7,2]，target=9；输出[[2,7]]（因[2,7]重复出现但需去重）。Python实现代码：```pythondeftwo_sum_unique_pairs(nums,target):nums.sort()排序，时间复杂度O(nlogn)n=len(nums)result=[]left,right=0,n1双指针whileleft<right:current_sum=nums[left]+nums[right]ifcurrent_sum==target:result.append([nums[left],nums[right]])跳过左侧重复元素whileleft<rightandnums[left]==nums[left+1]:left+=1跳过右侧重复元素whileleft<rightandnums[right]==nums[right1]:right=1left+=1移动左指针right=1移动右指针elifcurrent_sum<target:left+=1和过小，左指针右移else:right=1和过大，右指针左移returnresult测试用例print(two_sum_unique_pairs([2,7,11,15,7,2],9))输出[[2,7]]print(two_sum_unique_pairs([3,2,4,2,3],6))输出[[2,4],[3,3]]```代码说明：1.首先对数组排序（O(nlogn)），