计算机科学与技术专业专接本入学考试试题及答案

计算机科学与技术专业专接本入学考试试题及答案一、单项选择题（每题2分，共30分）1.在C语言中，若定义inta=3,b=4;则表达式(a||b)&&(a^b)的值为A.0  B.1  C.3  D.4答案：B解析：a||b为真(1)，a^b为7(二进制011^100=111)，7非零即真，故1&&1得1。2.下列关于进程与线程的描述，错误的是A.线程切换开销小于进程切换B.同一进程的线程共享地址空间C.线程是CPU调度的基本单位D.进程间通信一定比线程间通信快答案：D解析：进程间通信需内核介入，线程共享内存即可通信，故D错误。3.对长度为n的顺序表执行删除第i个元素(1≤i≤n)，需移动元素次数为A.n-i  B.n-i+1  C.i  D.n答案：A解析：删除第i个元素后，i+1到n共n-i个元素前移一位。4.在IPv4中，子网掩码92可划分的主机数为A.62  B.126  C.30  D.14答案：A解析：192=11000000，主机位6位，2^6-2=62。5.下列排序算法中，平均时间复杂度为O(nlogn)且稳定的是A.快速排序  B.堆排序  C.归并排序  D.希尔排序答案：C解析：归并排序稳定，平均O(nlogn)。6.在关系数据库中，若属性集X→Y，Y→Z，则X→Z属于A.自反律  B.增广律  C.传递律  D.合并律答案：C解析：函数依赖的传递律。7.若一棵二叉树的后序遍历为DBEFCA，中序遍历为DBAECF，则先序遍历为A.ABCDEF  B.ABDCEF  C.ABDECF  D.ACBDFE答案：C解析：后序最后为根A，中序分左子树DB，右子树ECF；递归可得先序ABDECF。8.在OSI七层模型中，负责端到端可靠传输的是A.网络层  B.传输层  C.会话层  D.数据链路层答案：B解析：传输层提供端到端服务。9.若浮点数采用IEEE754单精度格式，指数域全1且尾数非0，则表示A.0  B.无穷大  C.NaN  D.规格化数答案：C解析：指数全1尾数非0为NaN。10.在Linux中，命令chmod4755file的作用是A.设置SUID位  B.设置SGID位  C.设置粘滞位  D.仅改权限为755答案：A解析：4为SUID，7为rwx，故设置SUID且权限755。11.下列关于TCP拥塞控制的描述，正确的是A.慢启动阈值初始为0  B.拥塞避免阶段cwnd线性增长C.快速重传后直接进入慢启动  D.超时发生时cwnd减半答案：B解析：拥塞避免阶段每RTTcwnd加1，线性增长。12.对n个顶点e条边的无向图，采用邻接矩阵存储时，空间复杂度为A.O(n+e)  B.O(n^2)  C.O(e)  D.O(n)答案：B解析：邻接矩阵n×n。13.在Python中，表达式[1,2]*3的值是A.[3,6]  B.[1,2,1,2,1,2]  C.报错  D.[1,2,3]答案：B解析：列表乘号为重复拼接。14.若Cache采用2路组相联映射，主存地址32位，块大小64B，Cache容量32KB，则组数为A.256  B.512  C.128  D.64答案：A解析：32KB/(64B×2)=256组。15.在公钥密码体系中，用于数字签名的是A.接收方公钥  B.接收方私钥  C.发送方公钥  D.发送方私钥答案：D解析：签名用发送方私钥，验证用发送方公钥。二、填空题（每空2分，共20分）16.若某算法时间复杂度为T(n)=4T(n/2)+O(n^2)，则根据主定理，T(n)=________。答案：Θ(n^2logn)解析：a=4,b=2,f(n)=n^2，满足主定理情形2。17.在IPv6中，地址长度为________位。答案：12818.若关系模式R(A,B,C)的函数依赖集F={A→B,B→C}，则R的候选码为________。答案：A解析：A的闭包为ABC。19.在操作系统中，页面置换算法Belady异常可能出现在________算法。答案：FIFO解析：FIFO可能出现Belady异常。20.若某磁盘块大小为4KB，磁盘地址指针占4B，则采用二级间接索引可支持的最大文件为________KB。答案：4KB/4B=1024，二级1024×1024×4KB=4GB，即4096×1024KB。21.在HTTP/1.1中，持久连接默认使用________机制判断消息边界。答案：Content-Length或分块传输编码(chunked)22.若某二叉树度为2的节点有10个，则叶子节点数为________。答案：11解析：n0=n2+1。23.在MySQL中，事务的隔离级别________可避免幻读。答案：可串行化(Serializable)24.若某无向图有20条边，则其生成树有________条边。答案：19解析：生成树边数=顶点数-1，顶点数=20+1=21，生成树20-1=19。25.在RSA算法中，若p=3,q=11，则欧拉函数φ(n)=________。答案：20解析：φ(n)=(p-1)(q-1)=2×10=20。三、判断题（每题1分，共10分，正确打“√”，错误打“×”）26.哈希表的装载因子越大，冲突概率越高。√27.在TCP三次握手中，SYN=1且ACK=1的报文一定由客户端发出。×28.关系数据库中，外码允许取空值。√29.快速排序的最坏时间复杂度为O(n^2)。√30.在Linux中，硬链接可以跨文件系统。×31.采用补码表示的整数，0的表示唯一。√32.在OSI模型中，路由器工作在网络层。√33.在Python中，元组是可变对象。×34.对任意二叉树，后序遍历的逆序即为拓扑排序序列。×35.在分页管理中，页内偏移量位数由页面大小决定。√四、简答题（每题8分，共40分）36.简述虚拟内存的工作原理，并说明页面置换算法LRU的实现思路。答案：虚拟内存通过将逻辑地址空间与物理内存分离，使程序可使用比实际内存更大的地址空间。操作系统为每个进程建立页表，记录逻辑页到物理帧的映射。访问时，MMU将逻辑地址拆分为页号和偏移，查页表若存在且有效位为1则直接访问；若缺页，则触发缺页异常，操作系统选择一页换出，调入所需页，更新页表后重新执行指令。LRU（LeastRecentlyUse）实现思路：维护一个按访问时间排序的链表，每次访问某页将其移至链表头；缺页时淘汰链表尾。实际可用双向链表+哈希表，哈希表存页号到链表节点指针，访问/插入均为O(1)。37.描述TCP流量控制与拥塞控制的区别，并给出各自的核心机制。答案：流量控制解决发送方与接收方速率匹配，防止接收方缓冲区溢出，核心机制为滑动窗口，接收方通过rwnd字段通告窗口大小，发送方发送数据不超过min(cwnd,rwnd)。拥塞控制解决网络容量限制，防止网络拥塞，核心机制包括慢启动、拥塞避免、快速重传、快速恢复。慢启动阶段cwnd指数增长至ssthresh；之后线性增长；收到3个重复ACK触发快速重传，ssthresh=cwnd/2，cwnd=ssthresh+3，进入快速恢复；超时则ssthresh=cwnd/2，cwnd=1，重新慢启动。38.给定关系模式R(学号，姓名，课程号，课程名，成绩，教师号，教师名)，函数依赖集F={学号→姓名，课程号→课程名，教师号→教师名，(学号，课程号)→成绩，(课程号)→教师号}，求R的候选码及最高范式，若不属于3NF，请分解。答案：候选码：(学号，课程号)。存在非主属性对码的部分依赖与传递依赖，如课程号→教师号→教师名，故仅1NF。分解：R1(课程号，课程名，教师号，教师名)候选码：课程号，存在传递依赖，再分：R11(课程号，课程名，教师号)，R12(教师号，教师名)R2(学号，课程号，成绩)R3(学号，姓名)最终：R11,R12,R2,R3均达3NF。39.说明HTTPS建立连接的全过程，并指出与HTTP的主要区别。答案：HTTPS在HTTP与TCP之间加入TLS/SSL层。过程：1.TCP三次握手；2.ClientHello：客户端发送支持的TLS版本、随机数、加密套件列表；3.ServerHello：服务端选加密套件、发送随机数、证书（含公钥）；4.客户端验证证书，生成预主密钥，用服务端公钥加密发送；5.双方根据随机数+预主密钥生成会话密钥；6.握手完成，后续数据用对称加密传输。与HTTP区别：HTTPS默认端口443，HTTP为80；HTTPS提供加密、完整性、身份认证，HTTP明文传输；HTTPS需数字证书，HTTP无需。40.解释死锁产生的四个必要条件，并给出银行家算法的基本思想。答案：四个必要条件：1.互斥：资源一次只能被一个进程占用；2.占有且等待：进程已占部分资源，又申请新资源而被阻塞；3.非抢占：已分配给进程的资源不能被强制剥夺；4.循环等待：存在进程-资源的循环等待链。银行家算法思想：系统在分配资源前，先模拟分配，检查是否仍存在安全序列（即所有进程都能顺利完成）。若存在则分配，否则拒绝申请，使系统始终处于安全状态，避免死锁。需维护Available、Max、Allocation、Need矩阵。五、算法与程序设计题（每题15分，共30分）41.给定一个长度为n的整数数组，找出其中出现次数超过⌊n/2⌋的元素（假设一定存在）。要求时间复杂度O(n)，空间复杂度O(1)。答案：采用摩尔投票法。初始化candidate=任意值，count=0；遍历数组：若count==0，则candidate=当前元素；若当前元素==candidate，count++，否则count--；最终candidate即为答案。C语言实现：intmajority(int*nums,intn){intc,cnt=0;for(inti=0;i<n;i++){if(cnt==0)c=nums[i];if(nums[i]==c)cnt++;elsecnt--;}returnc;}解析：每次不同元素相互抵消，剩余即为多数。42.实现一个函数，判断两棵二叉树是否互为镜像。函数原型boolisMirror(TreeNoderoot1,TreeNoderoot2)。答案：递归思路：1.若两树皆空，返回true；2.若一为空另一非空，返回false；3.若根值不等，返回false；4.递归判断左子树与右子树是否镜像，右子树与左子树是否镜像。C++实现：boolisMirror(TreeNodea,TreeNodeb){if(!a&&!b)returntrue;if(!a||!b)returnfalse;return(a->val==b->val)&&isMirror(a->left,b->right)&&isMirror(a->right,b->left);}时间复杂度O(n)，空间复杂度O(h)，h为树高。六、综合应用题（每题20分，共40分）43.某高校选课系统采用B/S架构，数据库MySQL，Web服务器Nginx+PHP-FPM，高峰期并发量约5000。近期出现“数据库连接耗尽”与“页面响应慢”问题。请从数据库、Web服务器、应用层给出完整优化方案，并说明如何验证效果。答案：数据库层：1.开启连接池，使用PDO长连接，限制最大连接数=CPU核数×2+磁盘数；2.对高频查询如“课程余量”建立联合索引(课程号,状态)，避免SELECT*；3.引入Redis缓存，将课程余量、课程详情缓存30s，写操作采用先写库再删缓存策略；4.分库分表：按学期哈希分表，减少单表数据量；5.开启慢查询日志，分析超过100ms的SQL，强制使用索引。Web服务器层：1.Nginx开启gzip压缩，静态资源缓存1天；2.调整php-fpmpm=static，子进程数=CPU核数×4，max_requests=10000防止内存泄漏；3.使用UnixSocket连接php-fpm，减少TCP开销；4.配置Nginx限流，限制单IP10r/s，防止恶意刷接口。应用层：1.采用异步消息队列(RabbitMQ)处理选课高峰，将选课请求先入队，后台消费者串行扣减库存，避免行锁冲突；2.前端按钮置灰+JS节流，减少重复提交；3.引入本地缓存(APCu)缓存配置信息，减少Redis穿透；4.使用预编译语句防止SQL注入，减少解析开销。验证：1.使用sysbench模拟5000并发，观察QPS、响应时间、错误率；2.通过Prometheus+Grafana监控连接数、CPU、IO；3.对比优化前后95分位响应时间，目标从3s降至500ms以内；4.进行48h压力测试，无连接耗尽报错。44.设计一个基于区块链的学历存证系统，要求防止学校私自篡改、支持第三方快速验证、保护学生隐私。请给出系统架构、关键数据结构、智能合约核心函数、隐私保护方案及攻击防御措施。答案：系统架构：1.联盟链(HyperledgerFabric)，由教育部、高校、用人单位组成组织；2.每个组织部署Peer节点，Orderer节点由教育部主导；3.前端DApp提供学生上传、企业验证界面；4.链下存储加密后的学历PDF，链上仅存哈希与索引。关键数据结构：区块头：前一区块哈希、Merkle根、时间戳、组织MSP签名；交易：学历哈希、学生学号密文、学校ID、学位类型、授予时间、状态(有效/撤销)。智能合约(链码)：1.issueDegree(ctx,studentIDHash,degreeHash,schoolMSP,encryptPubKey