中国科学院大学 2020 年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机学科综合（非专业） 考生须知： 1. 本试卷满分为 150 分，全部考试时间总计 180 分钟。 2. 所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。 第一部分：数据结构（共 70 分） 一、单项选择题（每小题 2 分，共 20 分） 1以下对数据结构的研究对象描述最准确的是( )。 A. 比特B. 算法C. 数据 D. 数据以及数据之间的关系 2. 关于大 O 记号 O(.)，下列表达式正确的是( )。 A. B. C. D. 3. 用单链表形式的链式存储结构的线性表来存储元素时，以下描述中错误的是( ) 。 A. 添加元素时不需要移动其他元素B. 删除元素时不需要移动其他元素 科目名称：计算机学科综合（非专业）第 17 页共 14 页C. 逻辑上相邻的元素在物理位置上也相邻D. 无法随机访问元素 4. 使用线性表时，如果需要经常执行随机访问某个元素的操作，那么使用( ) 作为存储结构比较合适。 A. 单链表 B. 双链表 C. 顺序表 D. 循环链表 5. 栈的入栈和出栈操作分别在栈的( )位置进行。 A. 栈顶，栈顶B. 栈顶，栈底 C. 栈 底 ， 栈 顶D. 栈底，栈底 6. 以下关于字符串的 KMP 算法，说法不正确的是( )。 A. KMP 算法是串的模式匹配算法 B. KMP 算法的时间复杂度是 O(n*m)，其中 n,m 分别是主串和子串的长度 C. KMP 算法的关键点是计算 next 函数，该函数表明当子串与主串不匹配时， 子串应该重新和主串进行比较的字符的位置 D. KMP 算法中 next 函数的计算只取决于子串，与主串无关 7. 已知一棵二叉树有 n 个节点，它的叶节点个数的上下界分别是( )。A. n-1, 1 B. C. , 1 D. , 1 8. 关于有向图的拓扑排序，以下说法不正确的是( )。 A. 如果可以对有向图的全部节点做拓扑排序，那么这个图至少有一个节点的入度为 0 B. 如果可以对有向图的全部节点做拓扑排序，那么这个图至少有一个节点的入度为 1 C. 如果可以对有向图的全部节点做拓扑排序，那么这个图没有环 D. 存在一个有向无环图，它的拓扑排序唯一 9. 以下排序算法中，平均情况下时间复杂度为 的算法是( )。A. 冒泡排序 B. 快 速 排 序C. 堆排序 D. 归并排序 10. 哈希表的典型特点是( )。 A. 记录的物理存放顺序和到来顺序有关 B. 记录的逻辑存放顺序和到来顺序有关 C. 可以通过折半查找的方式查找记录 D. 记录的相对位置和记录的关键字有关 二、填空题（每空 1 分，共 20 分） 1. 1-3 这 3 个数字构成的全排序有 个。1-3 这 3 个数字以 1,2,3 的顺序入栈，通过 3 次入栈操作和 3 次出栈操作会得到一个 1-3 的出栈序列，这样的 出栈序列有 种。请列出 1-3 的全排序中不在出栈序列中的排列：。 2. 一棵有 n 个节点的树有 条边。如果一棵二叉树的非叶子节点都有 2 个儿子，那么称为满二叉树。如果一棵满二叉树有 k 个叶子节点，那么它一共有 个节点。 3. 一个 n 个节点的强连通的有向图，至少有 条边。 4. 在一个有序表中，折半查找的查找过程如下：当待查元素的上下界指针分别为 low 和 high 的时候，查找 mid=(low+high)/2这个元素。此时，在有序表1、2、3、4、5、6、7、8、9、10 中，查找元素 4 需要 次比较操作，查找元素 9 需要 次比较操作。现在将折半查找的查找过程修改为：当待查元素的上下界指针分别为 low 和 high 的时候，查找 mid=(2*low+high)/3 这个元素。此时，查找元素 9 需要 次比较操作。注：low，high 指针初始为 1 和 10。 5. 以下是使用递归方法生成 1-n 的全排列的算法，请填空。要求算法按照字典升序输出所有的排列。 include <stdio.h> int n; /要输出的是 1-n 的全排列，n<100 int a100;/记录当前排列 int search(int x)/枚举第 x 个位置的元素 if ( ) for (int i=1;i<=n;i+) printf("%d ",ai); printf("n"); return 0; for (int i=1;i<=n;i+) bool ok=true; for (int j=1; ;j+) if ( ) ok=false; break; if (ok) ; search( ); return 0; int main() scanf("%d",&n); search( ); return 0; 6以下是用单链表存储结构实现的查找并删除元素算法，请填空。 LIST *Delete(LIST *p, ElemType e) /指针 p 为头指针，要删除第一个存储数据值为 e 的节点，如无，则不删除任何节点；返回完成后的单链表头指针；假定单链表至少有一个元素。 Node* q, r; if ( ) return p->next ; q=p; r= ; while ( ) q = q->next; r = r->next; if ( ) return p; else q->next = ; return p; 附注：本题中所用的数据类型定义LIST 型： typedef int ElemType; typedef struct Node ElemType data; struct Node *next; Node; typedef struct Node LIST; 三、 问答题（含 4 小题，共 30 分） 1（本题 8 分）已知某二叉树的前序遍历节点访问顺序是 BGKIDACEJFH，中序遍历的节点访问顺序是 KIGDBEJCAHF。 （1） 请画出这棵二叉树； （2） 请写出其后序遍历的节点访问顺序。 2（本题 6 分）考虑以下已经建成的堆结构，当堆顶最小元素 1 出堆后，请写出剩余元素建成的堆。 3. （本题 8 分）给定 8 个叶节点的权重分别为 1、2、3、4、5、6、7、10，构造二叉赫夫曼树，并计算叶节点的带权路径长度之和。 4（本题 8 分）给定一个已经按从小到大排好序的数组 ，和一个数字 k，请设计一个运行时间尽量快的算法判断是否存在 i,j，使得 ， 且 。 第二部分：操作系统（共 40 分） 一、单项选择题（每小题 2 分，共 10 分） 1. 在操作系统中，临界区是指（ ）。A. 一个缓冲区 B. 一段共享数据区 C. 一段访问共享资源且互斥执行的代码D.一个互斥的资源 2. 下列选项中，会导致用户进程从用户态切换到内核态的操作是 ( )。 I. 整数除以零 II. sin() 函数调用 III. read 函数调用A. 仅 I、II B. 仅 I 、 III C. 仅 II 、 III D. I、II 和 III 3. 如果进程需要读取磁盘上的多个连续的数据块，以下哪一种数据传送方式的效率最高。( ) A. 程序直接轮询方式B. 中断控制方式 C. DMA 方式D. 管道方式 4. 下列对象哪个不属于文件系统的一部分: ( ) A.空闲块表 B.目录 C.索引节点 D.页表 5. 虚拟地址指的是（ ） A. 程序访问内存时使用的地址 B访问内存总线上的地址 C内存与磁盘进行数据交换使用的地址D寄存器的地址 二、填空题（每空 1 分，共 14 分） 1. 机械硬盘通过一定调度算法减少磁头移动量，提升硬盘访问性能，请列举三种常见的机械硬盘磁头移动调度算法 、 、 。 2. 多个进程总共对一个信号量共执行了 4 次 P 操作和 3 次 V 操作后，信号量的值为 1。则信号量的初值为 ，此时还能允许 个进程进入临界区。 3. 产生死锁的必要条件有： 、 、 和 。 4. 假设文件 F1 的 i-node 引用计数为 1，先建立文件 F1 的符号链接(软链接)文件 F2，再建立文件 F1 的硬链接文件 F3，然后删除文件 F1。此时，文件 F2 的 i-node 引用计数是 ，文件 F3 的 i-node 引用计数是 。 5. 进程间通信既可以进行数据传输，也可以进行事件通知，请列举三种常见的单机上进程间通信方式 、 、 。 三、简答题（含 3 小题，共 16 分） 1. （本题 4 分）wait、signal、broadcast 操作是定义在条件变量上的三个操作，请简述 wait、signal 和 broadcast 操作的定义。 2. （本题 6 分）有一虚拟内存系统，采用先进先出（FIFO）的页面替换算法。在内存中为每一作业进程开辟 3 页。某作业运行中使用的操作数所在的页号依次为： 4，3，2，1，4，3，5，4，3，2，1，5 （1） 该作业运行中总共出现多少次缺页？ （2） 如果采用 LRU 算法，每个作业进程在内存拥有 4 页，总共出现多少次缺页？最后一次访问后，缓存的页面有哪些？ 3. （本题 6 分）某多道程序设计系统中配有一台处理器 CPU 和两台输入输出设备 IO1，IO2，现有优先级由高到低的两个进程 P1、P2 同时存在，它们使用资源的先后顺序和占用时间分别是: 进程 P1:IO2(30ms)，CPU(10ms)，IO1(30ms)，CPU(10ms)，IO2(10ms)。进程 P2:IO1(20ms)，CPU(20ms)，IO2(40ms)。 假设进程调度采用“可抢占的最高优先级”调度算法，且忽略调度、进程切换等操作所需的时间。假设 IO 设备在服务一个请求时不可被打断，例如 IO2(30ms) 表示一个请求。请回答下列问题: 1) 进程 P1、P2 从开始到完成所用的时间分别是多少?请在下图上画出进程 P1、P2 工作过程，其中横坐标表示时间，纵坐标表示 CPU、IO1、IO2 设备。注:可以使用实线表示进程对某个资源的占用，并在该实线上注明当前是哪个进程在占用。例如表示 P1 进程对资源的占用。 2) 两个进程从开始到全部完成时 CPU 的利用率为多少? 第三部分：计算机网络（共 40 分） 一、单项选择题（每小题 2 分，共 20 分） 1. 在 OSI 七层结构模型中，处于数据链路层与传输层之间的是（ ）。A. 物理层 B. 网络层 C. 会 话 层 D. 表示层 2. 工作在网络层的传统互连设备是（ ）。A. 中继器 B. 应用网关 C. 网 桥 D. 路由器 3. 交换机能够识别（ ）。A. IP 地址 B. TCP 端口号 C. MAC 地址 D. IP 分组的版本号（IPv4、IPv6） 4. 以下关于端系统间通信方式的表述，错误的是（ ）。A. 客户/服务器方式及对等方式是两种基本的通信方式 B. 在客户/服务器通信方式中，服务器只能接受客户端的请求，给出响应 C. 采用浏览器访问 Web 服务器是一种典型的客户/服务器通信方式D. 在一对<用户主机、服务器>之间可以建立多个服务连接 5 某主机的 IP 地址为 180.80.77.55，子网掩码为 255.255.252.0。若该主机向其所在子网发送广播分组，则目的地址可以是（ ）。 A. 180.80.76.0 B. 180.80.76.255 C. 180.80.77.255 D. 180.80.79.255 6. 以下关于分组交换原理的表述，错误的是（ ）。 A. 分组交换需要把较长的数据划分为固定长度的较短数据包进行传送B. 分组交换可降低数据传送延时 C. 分组交换可提升链路使用效率 D. 各个数据包基于独立路由决策传送给目的节点 7. 将一个 IP 数据包从源节点传送到目的节点，以下表述错误的是（ ）。A. 数据包传送过程中可能需要经过多个路由器 B. 逐跳传送过程中，IP 地址保持不变 C. 逐跳传送过程中，IP 校验和保持不变 D. 逐跳传送过程中，MAC 地址会发生改变 8. 以下关于域名系统的表述，错误的是（ ）。 A. 用户主机的域名查询请求总会先发送给本地域名服务器B. 当前域名系统采用层次化的设计结构 C. 域名查询请求到达根域名服务器以后，根域名服务器总会给出解析结果（或者报告无法解析） D. 采用缓存技术可在一定程度上降低服务器的解析负载 9. 数据传输速率是描述数据传输系统性能的重要指标之一，数据传输速率在数值上等于每秒钟在链路上传输的（ ）。 A. 比特数 B. 字 符 数 C. 帧数 D. 分组数 10. 主机甲与主机乙之间建立一个 TCP 连接，主机甲向主机乙发送了 3 个连续的TCP 报文段，分别包含 300 字节、400 字节和 500 字节的有效载荷，第 3 个报文段的序号为 900。若主机乙仅正确接收到第 1 和第 3 个报文段，则主机乙发送给主机甲的确认序号是（ ）。 A. 300 B. 500 C. 1200 D. 1400 二、问答题（含两小题，共 20 分） 1. （本题 10 分）网络中路由器 A 的路由表如下表所示： 目的网络 距离 下一跳路由器 N1 4 B N2 1 C N3 1 F N4 5 G 现路由器 A 收到路由器 C 发来如下的路由信息： 目的网络 距离 N1 2 N2 2 N3 3 N4 3 N5 4 请给出路由器 A 更新后的路由表。 2. （本题 10 分）在如下图所示的以太网链路上有 7 台主机，假设 ARP 缓存的有效期为 15 分钟，初始阶段各主机的 ARP 缓存表为空。现假设第 2 分钟， H2 主动向 H5 发起了一次通信；第 7 分钟，H2 主动向 H6 发起了一次通信； 第 12 分钟，H3 主动向 H2 发起了一次通信，请采用如下表格方式给出第 15 分钟时，各主机中的 ARP 缓存表。（假设通信过程中各节点的 IP 地址和 MAC 地址均不会发生改变，通信过程本身没有任何延时）。 H1H2H3H4H5H6H7 ARP 缓存表 IP 地址 MAC 地址 剩余有效期