中国科学院大学2015年招收攻读硕士学位研究生入学统一考试试题

科目名称：计算机学科综合(专业)
考生须知：
1．本试卷满分为150分，全部考试时间总计180分钟。
2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。
一、单项选择题：第1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项最符合试题要求。
1． 下列数据结构中，（ ）是非线性数据结构。
A．栈 B.队列 C.二叉树 D.堆
2．在非空双向循环链表中q所指的结点后插入一个由p所指的链结点的过程依次为：rlink(p)<-rlink(q); rlink(q)<-p; llink(p)<-q; ( )
A. rlink(q)<-p B. rlink(llink(p))<-p
C. llink(rlink(p))<-p D. rlink(rlink(p))<-p
3. 若一个栈以向量V[1…n]存储，初始栈顶指针top为n+1，则下面x入栈的正确操作是（ ）。
A．top=top+1; V[top]=x B. V[top]=x; top=top+1
C. top=top-1; V[top]=x D. V[top]=x; top=top-1
4. 若6行5列的数组以行序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是（ ）。
A. 1040 B. 1042 C. 1026 D. 以上答案都不对
5．A[N,N]是对称矩阵，将下三角（包括对角线）以行序存储到一维数组T[N(N+1)/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（ ）。
A. i(i-1)/2+j B. j(j-1)/2+i C. i(j-i)/2+1 D. j(i-1)/2+1
6. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）。
A．CABDEFG B. ABCDEFG C. DACEFBG D. ADCFEGB
7. 有n(n>0)个分支结点的满二叉树的深度是（ ）。
科目名称：计算机学科综合(专业) 第 2 页 共 8 页
A．n2 -1 B. log2(n+1)+1 C. log2(n+1) D. log2(n-1)
8. 无向图G=(V, E)， 其中V={a, b, c, d, e, f}, E={(a, b), (a, e), (a, c), (b, e), (c, f), (f, d), (e, d)}, 对该图进行深度优先遍历，得到的顶点序列正确的是（ ）。
A．a, b, e, c, d, f B. a, c, f, e, b, d
C. a, e, b, c, f, d D. a, e, d, f, c, b
9. 设哈希表长M=14，哈希函数H(KEY) = KEY mod 7。表中已有4个结点：ADDR(15) = 1, ADDR(38) = 3, ADDR(61) = 5; ADDR(84) = 0, 其余地址为空。如用二次探测再哈希法解决冲突，关键字为68的结点的地址是（ ）。
A. 8 B. 3 C. 5 D. 6
10. 对{05，46，13，55，94，17，42}进行基数排序，一趟排序的结果是（ ）：
A． 05，46，13，55，94，17，42 B. 05，13，17，42，46，55，94
C． 42，13，94，05，55，46，17 D. 05，13，46，55，17，42，94
11. 下列序列中，（ ）是执行第一趟快速排序后所得的序列。
A．[68，11，18，69][23，93，73] B. [68，11，69，23][18，93，73]
C．[93，73][68，11，69，23，18] D. [73，11，69，23，18][93，68]
12．生产者和消费者问题用于解决（ ）。
A. 多个并发进程共享一个数据对象的问题
B. 多个进程之间的同步和互斥问题
C. 多个进程共享资源的死锁与饥饿问题
D. 利用信号量实现多个进程并发的问题
13.下面的叙述中，正确的是（ ）。
A. 在一个进程中创建一个新线程比创建一个新进程所需的工作量多
B. 同一个进程中的线程间通信和不同进程中的线程间通信差不多
C. 同一进程中的线程间切换由于许多上下文相同而简化
D. 同一进程中的线程间通信需要调用内核
14．磁盘高速缓存设在（ ）中。
科目名称：计算机学科综合(专业) 第 3 页 共 8 页
A. 内存 B. 磁盘控制器 C. Cache D. 磁盘
15．位示图可用于（ ）。
A. 实现文件的保护和保密 B. 文件目录的查找
C. 磁盘空间的管理 D. 主存空间的共享
16．虚拟设备是通过（ ）技术实现的。
A. 并行 B. 通道 C. SPOOLING D. 虚拟存储
17．（ ）不是操作系统的功能。
A. CPU管理 B. 存储管理 C. 网络管理 D. 数据管理
18.下面叙述中，错误的是（ ）。
A. 操作系统既能进行多任务处理，又能进行多重处理
B. 多重处理是多任务处理的子集
C. 多任务是指同一时间内在同一系统中同时运行多个进程
D. 一个CPU的计算机上也可以进行多重处理
19. （ ）优先级是在创建进程时确定的，确定之后在整个进程运行期间不再改变。
A. 动态 B. 先来先服务 C. 短作业 D. 静态
20.在分时操作系统中，进程调度经常采用（ ）算法。
A. 时间片轮转 B. 最高优先级 C. 先来先服务 D. 随机
21.死锁产生的四个必要条件是：互斥、（ ）、环路等待和不剥夺。
A. 释放和阻塞 B. 请求和阻塞 C. 请求和保持 D. 请求和释放
22.公用电话交换网(PSTN)采用了（ ）交换方式。
A.分组 B.报文 C.信元 D.电路
23.在连续ARQ协议中，当滑动窗口序号位数为n，则发送窗口最大尺寸为( )。
科目名称：计算机学科综合(专业) 第 4 页 共 8 页
A.2n-1 B.2n-1 C.2n D.2n
24.以下哪个是快速以太网的介质访问控制方法（ ）
A.CSMA/CD B.令牌总线 C.令牌环 D.100VG-AnyLan
25.ARP协议的功能是（ ）
A.域名地址到IP地址的解析 B.IP地址到域名地址的解析
C.IP地址到物理地址的解析 D.物理地址到IP地址的解析
26.IPv6地址由（ ）位二进制数值组成。
A.16 B.64 C.32 D.128
27.决定局域网特性有三个主要技术，它们是 ( ) 。
A. 传输介质、差错检测方法和网络操作系统
B. 通信方式、同步方式和拓朴结构
C. 传输介质、拓扑结构和介质访问控制方法
D. 数据编码技术、介质访问控制方法和数据交换技术
28.无法隔离冲突域的网络互联设备是（ ）。 A.路由器 B.交换机 C.集线器 D.网桥
29.不是IP数据报操作特点的描述说法是（ ）
A. 每个分组自身携带有足够的信息，它的传送是被单独处理的
B．在整个传送过程中，不需建立虚电路
C．使所有分组按顺序到达目的端系统
D．网络节点要为每个分组做出路由选择
30.关于路由器说法正确的是（ ）。
A.路由器处理的信息量比交换机少，因而转发速度比交换机快
B.对于同一目标，路由器只提供延迟最小的最佳路由
C.通常的路由器可以支持多种网络层协议，并提供不同协议之间的分组转换
D.路由器不但能够根据逻辑地址进行转发，而且可以根据物理地址进行转发
31．两个二进制有符号数相加，00111111 + 11101111的十进制结果是（ ）。
A. 302 B. 47 C. 45 D. 46
32．根据存储内容来进行存取的存储器称为（ ）。
科目名称：计算机学科综合(专业) 第 5 页 共 8 页
A. 双端口存储器 B. 相联存储器 C. 交叉存储器 D. 串行存储器
33．在一个容量为128KB的SRAM存储器芯片上，按字长32位编址，其地址范围可从0000H到（ ）。
A. 3fffH B. 7fffH C. 7ffffH D. 3ffffH
34．连续两次启动同一存储器所需的最小时间间隔称为（ ）。
A. 存储周期 B. 存取时间 C. 存储时间 D. 访问周期
35．依赖硬件的数据传送方式是（ ）。
A．程序控制 B．程序中断 C．DMA D．无
36．在程序执行过程中，（ ）控制计算机的运行总是处于取指令、分析指令和执行指令的循环之中。
A．控制器 B．CPU C．指令存储器 D．指令译码器
37．需要周期刷新的存储器是（ ）。
A．SRAM B．DRAM C．ROM D．双稳态存储器
38．CPU的主频是10MHz，机器周期含3个时钟周期，则机器周期是（ ）ns。
A．100 B．300 C．33.3 D．30
39．命中率高且电路实现简单的Cache与内存映射方式是（ ）映射方式。
A．全相联 B．直接 C．组相联 D．哈希
40．只能检测错误而不能纠正错误的编码方法是（ ）。
A．卷积码 B．循环冗余码 C．海明码 D．奇偶校验
二、综合应用题：41~48小题，共70分。
41．（8分）设计并编程实现链式存储结构上交换二叉树中所有结点左右子树的算法。（注：用C/C++，Pascal等编程语言书写）
科目名称：计算机学科综合(专业) 第 6 页 共 8 页
42.（12分）假设有下面的有向图：
1） 请给出从顶点a出发得到深度优先遍历的顶点序列。（遍历过程中存在多种选择时，请以字母表顺序访问）
2） 请给出从顶点a出发得到广度优先遍历的顶点序列。（遍历过程中存在多种选择时，请以字母表顺序访问）
3） 该图的强连通子图有多少种？
43. （7分）假设一个磁盘驱动器有5000个柱面，从0 到4999。驱动器正在为柱面153的一个请求提供服务。按FIFO顺序，即将到来的请求队列是86，1470，913，1774，948，1509，1022，1750，130。从现在磁头位置开始，按照FCFS调度算法，要满足队列中即将到来的请求，磁头总的移动距离（按柱面数计）是多少？
44.（8分）现要对P1~P5五个进程进行调度，下表给出了这五个进程的到达时间、执行时间和优先级，其中，优先级数值越小表示优先级越高。
进程
到达时间 (ms)
执行时间 (ms)
优先级
P1
0
10
5
P2
1
1
1
P3
2
5
3
P4
3
1
2
P5
4
2
4
科目名称：计算机学科综合(专业) 第 7 页 共 8 页
请根据该表分别采用先来先服务（FCFS）调度算法、非抢占式短进程优先（nonpreemptive SPF）调度算法、抢占式优先权（preemptive priority）调度算法和时间片为2ms的时间片轮转（RR）调度算法对这五个进程进行调度，画出CPU执行进程的时间图。
45.（7分）要发送的数据为1101011011。采用CRC的生成多项式是P(x)=x4+x+1。试求应添加在数据后面的余数。数据在传输过程中最后一个1变成了0，问接收端能否发现？若数据在传输过程中最后两个1都变成了0，问接收端能否发现？
46.（8分）假定网络中的路由器A的路由表有如下的项目（这三列分别表示“目的网络”、“距离”和“下一跳路由器”）
N1 4 B
N2 2 C
N3 1 F
N4 5 G
现在A收到从C发来的路由信息（这两列分别表示“目的网络”和“距离”）：
N1 2
N2 1
N3 3
试求出路由器A更新后的路由表（详细说明每一个步骤）。
47.（8分）某磁盘存储器转速为100转/秒，共有2个记录盘面，每毫米10道，每道记录信息16384B，最小磁道直径为150mm，共有512道，求：
1）磁盘存储器的存储容量；
2）磁盘数据传输率；
3）平均等待时间。
48.（12分）一个直接映射的Cache有128个字块，主机内存包含16K个字块，
科目名称：计算机学科综合(专业) 第 8 页 共 8 页
每个块有16个字，访问Cache的时间是10ns，填充一个Cache字块的时间是200ns，Cache的初始状态为空。
1）如果按字寻址，请定义主存地址字段格式，给出各字段的位宽；
2）CPU从主存中依次读取位置16-210的字，循环读取10次，则访问Cache的命中率是多少？
3）10次循环中，CPU平均每次循环读取的时间是多少？