考研计算机统考2009年真题

2009年研究入学考试计算机统考试题
一、选择题
1) 操作系统的缓冲区，从外部依次输入数据再依次输出
A 栈
B 队列
C 链表 D
2) 以下哪个是平衡二叉树
3) 完全二叉树第6层有8个叶子节点，完全二叉树最多有几个节点
4) 森林转变二叉树的时候，U在二叉树中是V的父节点的父节点，U和V可能是什么关系
A 兄弟节点
B U，V的双亲节点是兄弟节点
C 父节点 D
5) 栈和队列，ABCDEFG先进栈，出来再进队列，出队列的顺序为BDCFEAG，问栈至少需要多少空间
6) 给一组数，找一个算法最快排序好?
7) 给定一个小根堆，插入一个数13，调整后的小根堆什么样?
8) 一堆数，大小不一，第2次排序得到，问可能是哪中排序方法得到的?
直接选择二路归并堆排序直接插入排序
9) B树描述中哪一项是错误?
10) X+Y = Z，X和Zint型，Y为short型，X = 127， y= -9，X，Y和Z的二进制编码是多少?
11) RISC哪种说法是错误的?
D 指令少
12) 硬布线控制和微程序控制器对比，容不容易修改，速度快
13) 给个访问序列，用电梯调度算法找到调度序列?(操作系统)
14) K个进程，打印机3个，共享资源8个，每个进程需要三个资源，求进程最小死锁数目(4个)
15) 访问1000次主存有50次缺页，命中率是多少?95%
16) 给定主存容量，使用二路链接，问页号地址大小是多少?
17) 与等待时间和执行时间有关的调度算法
18) 64K内存，多少ROM和RAM，需要多少地址线和数据线
19) 引用位，
20) 单通道程序可以并行的是哪几个选项
程序和程序之间并行程序和通道之间并行程序和设备之间并行设备和设备之间并行
21) 程序员进行系统调用访问设备用哪个地址
A 逻辑地址
B 物理地址
C 主设备地址
D 从设备地址
22) CPU靠什么识别传输的数据还是地址
MAR和MDR
23) 文件的控制信息放到哪?
A FCB
24) OSI标准中，能表现端到端传输的是哪一层?(传输层)
25) TCP的滑动窗口，4次成功发送后窗口阀值为多少?
A 4
B 8
C 9
D 16
26) FTP是利用哪个原理
A TCP面向控制
B TCP面向数据
C UDP控制链接
D UDP数据链接
二综合题
41、(10分)
带权图(权值非负，表示边连接的两顶点间的距离)的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径，假设从初始顶点到目标顶点之间存在路径，现有一种解决该问题的方法：
(1)该最短路径初始时仅包含初始顶点，令当前顶点u为初始顶点;(2)选择离u最近且尚未在最短路径中的
一个顶点v，加入到最短路径中，修改当前顶点u=v;(3)重复步骤(2)，直到u是目标顶点时为止。

请问上述方法能否求得最短路径?若该方法可行，请证明之，否则请举例说明。

42、(15分)
已知一个带有表头结点的单链表，结点结构为：
，假设该链表只给出了头指针list，在不改变链表的前提下，请设计一个尽可能高效的算法，查找链表中倒数第K个位置上的结点(K为正整数)，若查找成功，算法输出该结点的data域的值，并返回1;否则，只返回0。

要求：
(1)描述算法的基本设计思想;(2)描述算法的详细实现步骤(使用C或C++或Java语言实现)，关键之处请给出简要注释。

43、(8分)
某计算机的CPU主频为500MHz，CPI为5(即执行每条指令平均需5个时钟周期)。

假定某外设的数据传输率为0.5MB/S,采用中断方式与主机进行数据传送，以32位为传输单位，对应的中断服务程序包含18条指令，中断服务的其他开销相当于2条指令的执行时间。

请回答下列问题，要求给出计算过程。

(1)在中断方式下，CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?
(2)当该外设的数据传输率达到5MB/S时，改用DMA方式传送数据，假定每次DMA传送块大小为5000B，且DMA预处理和后处理的总开销为500个时钟周期，则CPU用于该外设I/O的时间占整个CPU时间的百分比是多少?(假设DMA与CPU之间没有访问冲突)。

44.(13分)
加法指令的执行过程，取指周期的情况给了，按照取指周期写执行周期的步骤
45、(7分)
三个进程P1、P2、P3互斥使用一个包含N(N>0)个单元的缓冲区。

P1每次用produce ( )生成一个正整数，并用put ( ) 送入缓冲区某一空单元中;P2每次用getodd ( ) 从该缓冲区中取出一个奇数，并用countodd ( ) 统计奇数个数;P3每次用geteven ( ) 从该缓冲区中取出一个偶数，并用counteven()统计偶数个数。

请用信号量机制实现这三个进程的同步与互斥活动，并说明所定义信号量的含义，要求用伪代码描述。

46 (8分)
3个虚拟地址，页表其中几项(页框，页号，)访问内存10ns，访问快表2ns，
1)分情况计算访问时间
2)求虚拟地址对应的物理地址
3)LLU算法，最近最长时间没有访问，给定一个序列。

47 (9分)
给定路由表(目的IP，子网掩码，下一跳IP，接口)
1) 给R2 IP地址/24, 网分为两个子网，每个局域网至少120个
2) 画R2路由表
3) 路由聚合技术画R1路由表。