还剩7页未读，继续阅读
文本内容:
北语计算机统考试题和答案
一、选择题（本题型共15题，每题2分，共30分）
1.在数据结构中，以下关于数组和链表的描述，正确的是（）A.数组的插入和删除操作效率高，链表的随机访问效率高B.数组是顺序存储结构，链表是链式存储结构C.数组只能存储同类型数据，链表只能存储不同类型数据D.数组和链表都支持动态扩容
2.栈和队列的主要区别在于（）A.栈是先进先出，队列是先进后出B.栈是后进先出，队列是先进先出C.栈只支持插入操作，队列只支持删除操作D.栈的存储结构是顺序的，队列的存储结构是链式的
3.某二叉树的先序遍历序列为“ABDCE”，中序遍历序列为“BDAEC”，该二叉树的后序遍历序列是（）A.BDECA B.BEDCA C.BDEAC D.BEDAC
4.以下算法中，时间复杂度为On logn的是（）A.冒泡排序B.快速排序（平均情况）C.简单选择排序D.直接插入排序
5.计算机组成原理中，CPI（时钟周期数/指令）的影响因素不包括（）A.指令类型B.数据相关C.存储系统D.程序设计语言
6.关于Cache的作用，以下描述正确的是（）A.提高CPU与主存之间的数据传输速度B.扩大主存的物理容量第1页共9页C.降低主存的功耗D.实现主存的并行访问
7.在页式存储管理中，若逻辑地址为（页号，页内偏移）=（2，1023），页面大小为4KB，则该逻辑地址对应的物理地址（页框号，页内偏移）是（）A.（页框号2，页内偏移1023）B.（页框号1023，页内偏移2）C.（页框号4，页内偏移1023）D.（页框号1023，页内偏移4）
8.操作系统中，进程从“就绪”状态转换为“运行”状态的原因是（）A.进程被创建B.进程调度程序选择该进程执行C.进程等待某资源D.进程执行完毕
9.以下死锁预防策略中，通过破坏“不可剥夺条件”实现的是（）A.资源有序分配法B.一次性分配所有资源C.银行家算法D.剥夺式资源分配（如抢占打印机）
10.文件系统中，索引文件的主要优点是（）A.存储空间利用率高B.访问速度快（相比连续分配）C.支持文件动态扩展D.数据一致性好
11.TCP协议的三次握手过程中，客户端发送的第二个报文段的标志位是（）A.SYN B.ACK C.SYN+ACK D.FIN
12.某C类IP地址为
192.
168.
10.0/24，若子网掩码为
255.
255.
255.224，则划分出的子网中，网络地址为
192.
168.
10.32的子网可容纳的主机数是（）A.14台B.30台C.62台D.126台
13.以下路由协议中，属于距离矢量路由协议的是（）第2页共9页A.OSPF B.RIP C.BGP D.IS-IS
14.HTTP协议中，GET请求与POST请求的主要区别是（）A.GET请求在URL中携带参数，POST请求在请求体中携带参数B.GET请求是无状态的，POST请求是有状态的C.GET请求只能获取数据，POST请求只能提交数据D.GET请求支持HTTPS，POST请求不支持
15.以下加密算法中，属于对称加密的是（）A.RSA B.ECC C.DES D.EIGamal
二、填空题（本题型共15题，每题2分，共30分）
1.在单链表中，若要在节点p之后插入节点s，则需要修改的指针为p的______指针指向s，s的______指针指向p的原后继节点
2.栈的“下溢”是指______，“上溢”是指______
3.二叉树的性质在非空二叉树中，第i层上最多有______个节点（根节点为第1层）；高度为h的二叉树最少有______个节点
4.快速排序算法的最好情况下，时间复杂度为______，此时每次划分操作将序列分为长度相等的两部分
5.主存与Cache的地址映射方式中，______方式的地址转换速度快，但Cache空间利用率低；______方式的空间利用率高，但地址转换速度慢
6.CPU响应中断时，需要完成的操作包括关中断、保存______、识别______、执行______、恢复现场、开中断
7.虚拟内存的页面置换算法中，LRU算法的含义是______，Belady异常是指______算法可能出现的现象
8.文件的逻辑结构分为两种和，其中后者的记录长度不固定，适合处理变长记录数据第3页共9页
9.TCP的拥塞控制机制包括四个阶段慢开始、______、拥塞避免、______
10.IP地址分为5类，其中A类地址的默认子网掩码是______，主机位为______位
11.子网划分的关键是确定子网掩码，若要将B类地址
172.
16.
0.0划分为10个子网，每个子网至少1000台主机，则子网掩码应为______，每个子网的广播地址范围是______
12.数据链路层的差错控制方法主要有两种和，前者通过循环冗余校验（CRC）实现，后者通过确认与重传机制实现
13.物理层的主要功能是定义物理连接的______特性、______特性、功能特性和规程特性
14.操作系统中进程调度的方式分为______和______，前者在进程完成或阻塞后才调度其他进程，后者可在当前进程阻塞时立即调度新进程
15.计算机网络中，“三网融合”通常指的是______网、______网和计算机网的融合
三、判断题（本题型共10题，每题1分，共10分）
1.队列是先进后出的线性表（）
2.时间复杂度为O1的算法一定比时间复杂度为On的算法执行速度快（）
3.程序计数器（PC）属于控制器的组成部分，用于存放下一条要执行的指令地址（）
4.页式存储管理中，页面大小越大，页面数量越少，地址转换效率越高（）第4页共9页
5.进程调度的优先级调度算法中，静态优先级一旦确定就不可修改（）
6.死锁的四个必要条件是互斥、请求与保持、不可剥夺、循环等待（）
7.TCP协议是无连接的、不可靠的传输层协议（）
8.子网掩码
255.
255.
255.0对应的IP地址一定是C类地址（）
9.物理层协议规定了数据在物理媒体上的传输方式，如电压、线缆类型等（）
10.HTTP协议是基于UDP的应用层协议，默认端口号为80（）
四、简答题（本题型共10题，每题5分，共50分）
1.简述栈和队列的基本操作，并说明它们在括号匹配问题中的应用
2.解释时间复杂度和空间复杂度的概念，并举例说明如何计算一个循环算法的时间复杂度
3.说明Cache的基本原理，包括地址映射方式（至少列举2种简述其原理）和替换策略（至少列举1种简述其工作方式）
4.简述进程和线程的区别，并说明引入线程的主要目的
5.解释虚拟内存的工作原理，说明页面置换算法中LRU（最近最少使用）算法的工作过程
6.说明TCP协议三次握手的过程，并解释为什么需要三次握手而不是两次
7.简述IP地址的分类及各类地址的范围（以十进制表示），说明子网划分的作用
8.说明数据链路层的主要功能，并比较MAC地址和IP地址的区别
9.简述操作系统中死锁的定义、产生死锁的四个必要条件，以及预防死锁的三种常用方法第5页共9页
10.简述TCP/IP协议簇中传输层的主要协议（TCP和UDP）的特点及适用场景
五、综合应用题（本题型共10题，每题8分，共80分）
1.数据结构已知某二叉树的中序遍历序列为“D BE AF C”，后序遍历序列为“D EB FC A”，画出该二叉树，并写出其先序遍历序列及高度
2.数据结构用单链表实现一个简单的队列，要求写出队列的结构体定义（包括头节点、尾节点指针）、入队操作（enqueue）和出队操作（dequeue）的伪代码（假设节点数据为int类型）
3.计算机组成原理某计算机字长32位，主存容量512MB，按字编址（1字=4字节），采用直接映射Cache，Cache容量为32KB，块大小为16字节计算
（1）主存地址格式（页号+页内偏移位数）；
（2）Cache的行数；
（3）主存地址0x12345678（十六进制）对应的Cache行号（写出计算过程）
4.计算机组成原理某指令流水线由5个阶段组成，各阶段时间均为1个时钟周期，执行100条连续指令，无数据冲突和控制冲突，计算平均CPI和吞吐率（单位指令/时钟周期）
5.操作系统5个进程P0-P4的到达时间（AT）和运行时间（BT）如下表，采用非抢占式短作业优先（SJF）调度进程P0P1P2P3P4第6页共9页------------------AT01234BT36452计算各进程的完成时间（CT）、周转时间（TAT=CT-AT）、带权周转时间（WCT=TAT/BT），并求平均周转时间和平均带权周转时间
6.操作系统某分页系统页面大小4KB，页表如下页号物理块号------第7页共9页051102338逻辑地址0x3A5F（十六进制），转换为物理地址（写出计算过程，结果用十六进制表示）
7.计算机网络C类地址
202.
113.
78.0/24划分4个子网，每个子网45台主机，求子网掩码、每个子网的网络地址、广播地址及可用IP范围
8.计算机网络H1（IP
192.
168.
1.10/24）→R1（
192.
168.
1.1/24）→R2（
10.
0.
0.1/24）→R3（
10.
0.
0.2/24）→H2（
10.
0.
0.10/24），简述H1到H2的通信过程（含ARP请求、路由选择、数据帧封装）
9.综合单级中断系统，中断优先级键盘
（1）、打印机
（2）、硬盘
（3），中断处理流程关中断→保存现场→判断中断源→执行服务程序→恢复现场→开中断若打印机请求中断，写出中断处理步骤（包括判断中断源的方法和服务程序内容）
10.综合索引文件系统，磁盘块4KB，索引项4字节，inode包含10个直接索引、1个一级间接、1个二级间接、1个三级间接索引项计算
（1）文件最大长度（字节）；
（2）100KB文件需多少磁盘块（直接/间接块均计）答案汇总（按题型顺序排列）第8页共9页
一、选择题答案
1.B
2.B
3.A
4.B
5.D
6.A
7.A
8.B
9.D
10.C
11.B
12.A
13.B
14.A
15.C
二、填空题答案
1.后继（next），后继（next）
2.栈为空时执行出栈操作，栈满时执行入栈操作
3.2^i−1，h
4.On logn
5.直接映射，全相联映射
6.现场，中断源，中断服务程序
7.最近最少使用的页面被置换，FIFO（先进先出）
8.流式文件，记录式文件
9.拥塞避免，快重传
10.
255.
0.
0.0，
2411.
255.
255.
255.224，
172.
16.
0.127-
172.
16.
0.255（每个子网）
12.差错检测，差错恢复
13.机械，电气
14.非抢占式，抢占式
15.电信（电话），电视（CATV）
三、判断题答案
1.×
2.×
3.√
4.×
5.√
6.√
7.×
8.×
9.√
10.×第9页共9页。
个人认证
优秀文档
获得点赞 0
