2012年考研计算机统考408真题.doc

精品文档
2012年考研(kǎo yán)计算机统考408真题
一、 单项选择题
1. 求整数n(n>=0)阶乘的算法如下，其时间复杂度是 1 。
Int fact(int n){
If(n<=1) return 1;
Return n*fact(n-1);
A. O(log2n)
B. O(n)
C. O(nlog2n)
D. O(n2)
2. 操作符包括’+’、’-‘、’*’、’/’、’(‘和’)’。将中缀表达式a+b-a*((c+d/e-f)+g转换为等价的后缀表达式ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符，假设栈初始为空，那么转换过程中同时保存在栈中的操作符的最大个数是 2 。
A. 5
B. 7
C. 8
D. 11
3. 假设一棵二叉树的前序遍历序列为a,e,b,d,c，后序遍历序列为b,c,d,e,a，那么根结点的孩子结点 3 。
A. 只有e
B. 有e,b
C. 有e,c
D. 无法确定
4. 假设平衡二叉的高度为6，且所有非叶结点的平衡因子均为1，那么该平衡二叉树的结点总数为 4 。
A. 10
B. 20
C. 32
D. 33
5. 对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是 5 。
A. O(n)
B. O(e)
C. O(n+e)
D. O(n*e)
6. 假设用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，那么关于该图拓扑序列的结论是 6 。
A. 存在，且唯一
B. 存在，且不唯一
C. 存在，可能不唯一
D. 无法确定是否存在
7. 对如下有向图带权图，假设采用迪杰斯特位〔Dijkstra〕算法求从源点a到其他各顶点的最短路径，那么得到的第一条最短路径的目标顶点是b，第二条最短路径的目标顶点是c，后续得到的其余最短路径的目标顶点依次是 7 。

A. d,e,f
B. e,d,f
C. f,d,e
D. f,e,d
8. 以下(yǐxià)关于最小生成树的表达中，正确的选项是 8 。
I.最小生成树的代价唯一。
II.所有权值最小的边一定会出现在所有的最小生成树中。
III.使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同。
IV.使用普里姆算法和克鲁斯卡尔〔Kruskal〕算法得到的最小生成树总不同。
A. 仅I
B. 仅II
C. 仅I、III
D. 仅II、IV
9. 一颗3阶B-树，如以下图所示。删除关键字78得到一颗新B-树，其最右叶结点中的关键字是 3 。

A. 60
B. 60,62
C. 62,65
D. 65
10. 在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。以下排序方法中，每一趟排序结束都至少能够确定一个元素最终位置的方法是 10 。
I.简单项选择择排序
II.希尔排序
III.快速排序
IV.堆排序
V.二路归并排序
A. 仅I、III、IV
B. 仅I、III、V
C. 仅II、III、IV
D. 仅III、IV、V
11. 对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是 11 。
A. 排序(pái xù)的总趟数
B. 元素的移动次数
C. 使用辅助空间的数量
D. 元素之间的比拟次数
12. 假定基准程序A在某计算机上的运行时间为100秒，其中90秒为CPU时间，其余为I/O时间。假设CPU速度提高50%，I/O速度不变，那么运行基准程序A所超消耗的时间是 12 。
A. 55秒
B. 60秒
C. 65秒
D. 70秒
13. 假定编译器规定int和short型长度分别为32位和16位，执行以下C语言语句：
unsigned short x=65530;
unsigned int y=x;
得到y的机器数为 13 。
A. 0000 7FFAH
B. 0000 FFFAH
C. FFFF 7FFAH
D. FFFF FFFAH
14. float类型〔即IEEE754单精度浮点数格式〕能表示的最大正整数是 14 。
A. 2126-2103
B. 2127-2104
C. 2127-2103
D. 2128-2104
15. 某计算机存储器按字节编址，采用小端方式存放数据。假定编译器规定int型和short型长度分别为32位和16位，并且数据按边界对齐存储。某C语言程序段如下：
struct{
int a;
char b;
short c;
}record;
record.a=273;
假设record变量的首地址为0xC008，那么地址0xC008中内容及record.c的地址分别为 15 。
A. 0x00、0xC00D
B. 0x00、0xC00E
C. 0x11、0xC00D
D. 0x11、0xC00E
16. 以下关于内存(flash memory)的表达中，错误的选项是 16 。
A. 信息可读可写，并且读、写速度一样快
B. 存储元由MOS管组成，是一种半导体存储器
C. 掉电后信息不丧失，是一种易失性存储器
D. 采用随机访问方式，可替代计算机外部存储器
17. 假设(jiǎshè)某计算机按字编址，Cache有4个行，Cache和主存之间交换的块大小为1个字。假设Cache的内容初始为空，采用2路组相联映射方式和LRU替换策略。访问的主存地址依次为0,4,8,2,0,6,8,6,4,8时，命中Cache的次数是 17 。
A. 1
B. 2
C. 3
D. 4
18. 某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有33个微命令，构成5个互斥类，分别包含7、3、12、5和6个微命令， 那么操作控制字段至少有 18 。
A. 5位
B. 6位
C. 15位
D. 33位
19. 某同步总线的时钟频率为100MHz，宽度为32位，地址/数据线复用，每传输一个地址或数据占用一个时钟周期。假设该总线支持突发〔猝发〕传输方式，那么一次“主存写〞总线事务传输128位数据所需要的时间至少是 19 。
A. 20ns
B. 40ns
C. 50ns
D. 80ns
20. 以下关于USB总线特性的描述中，错误的选项是 20 。
A. 可实现外设的即插即用和热拔插
B. 可通过级联方式连接多台
C. 是一种通信总线，连接不同外设
D. 同时传输2位数据，数据传输率高
21. 以下选项中，在I/O总线的数据线上传输的信息包括 21 。
I.I/O接口中的命令字
II.I/O接口中的状态字
III.中断类型号
A. 仅I、II
B. 仅I、III
C. 仅II、III
D. 仅I、II、III
22. 响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括 22 。
I.关中断
II.保存通用存放器的内存
III.形成中断效劳程序入口地址并送PC
A. 仅I、II
B. 仅I、III
C. 仅II、III
D. I、II、III
23. 以下选项中，不可能在用户态发生的事件是 23 。
A. 系统(xìtǒng)调用
B. 外部中断
C. 进程切换
D. 缺页
24. 中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是 24 。
A. 程序计数器
B. 程序状态字存放器
C. 通用数据存放器
D. 通用地址存放器
25. 以下关于虚拟存储器的表达中，正确的选项是 24 。
A. 虚拟存储只能基于连续分配技术
B. 虚拟储存只能基于非连续分配技术
C. 虚拟存储容量只受外在容量的限制
D. 虚拟存储容量只受内存容量的限制
26. 操作系统的I/O子系统通常由四个层次组成，每一层明确定义了与 邻近层次的接口。其合理的层次组织排列顺序是 25 。
A. 用户级I/O软件、设备无关软件、设备驱动程序、中断处理程序
B. 用户级I/O软件、设备无关软件、中断处理程序、设备驱动程序
C. 用户级I/O软件、设备驱动程序、设备无关软件、中断处理程序
D. 用户级I/O软件、中断处理程序、设备无关软件、设备驱动程序
27. 假设5个进程P0、P1、P2、P3、P4共享三类资源R1、R2、R3，这些资源总数分别为18、6、22。T0时刻的资源分配情况如下表所示，此时存在的一个平安序列是 26 。

A. P0,P2,P4,P1,P3
B. P1,P0,P3,P4,P2
C. P2,P1,P0,P3,P4
D. P3,P4,P2,P1,P0
28. 假设一个用户进程通过read系统调用读取一个磁盘文件中数据，那么以下关于此过程的表达中，正确的 28 。
I.假设该文件的数据不在内存，那么该进程进入睡眠等待状态
II.请求read系统调用会导致CPU从用户态切换到核心态
III.read系统调用的参数应包含文件的名称
A. 仅I、II
B. 仅I、III
C. 仅II、III
D. I、II和III
29. 一个多道批处理系统(xìtǒng)中仅有P1和P2两个作业，P2比P1晚5ms到达，它们的计算和I/O操作顺序如下：
P1：计算60ms，I/O 80ms，计算20ms
P2：计算120ms，I/O 40ms，计算40ms
假设不考虑调度和切换时间，那么完成两个作业需要的时间最少是 29 。
A. 240ms
B. 260ms
C. 340ms
D. 360ms
30. 假设某单处理器多进程系统中有多个就绪态进程，那么以下关于处理机调度的表达中，错误的选项是 30 。
A. 在进程结束时能进行处理机调度
B. 创立新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
31. 以下关于进程和线程的表达中，正确的选项是 31 。
A. 不管系统是否支持线程，进程都是资源分配的根本单位
B. 线程是资源分配的根本单位，进程是调度的根本单位
C. 系统级线程和用户及缓和的切换都需要内核的支持
D. 同一进程中的各个线程拥有各自不同的地址空间
32. 以下选项中，不能改善磁盘设备I/O性能的是 32 。
A. 重排I/O请求次序
B. 在一个磁盘上设置多个分区
C. 预读和滞后写
D. 优化文件物理块的分布
33. 在TCP/IP体系结构中，直接为ICMP提供效劳的协议是 33 。
A. PPP
B. IP
C. UDP
D. TCP
34. 在物理层接口特性中，用于描述完成每种功能的事件发生顺序是 34 。
A. 机械特性
B. 功能特性
C. 过程特性
D. 电气特性
35. 以太网的MAC协议提供的是 35 。
A. 无连接不可靠效劳
B. 无连接可靠效劳
C. 有连接不可靠效劳
D. 有连接可靠效劳
36. 两台主机之间的数据链路层采用后退N帧协议〔GBN〕传输数据，数据传输速率为16kbps，单向传播时延为270ms，数据帧长度范围是128~512字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率到达最高，帧序号的比特数至少为 36 。
A. 5
B. 4
C. 3
D. 2
37. 以下(yǐxià)关于IP路由器功能的描述中，正确的选项是 37 。
I.运行路由协议，设置路由表
II.监测到拥塞时，合理丢弃IP分组
III.对收到的IP分组头进行过失校验，确保传输的IP分组不丧失
IV.根据收到的IP分组的目的IP地址，将其转发到适宜的输出路线上
A. 仅III、IV
B. 仅I、II、III
C. 仅I、II、IV
D. I、II、III、IV
38. ARP协议的功能是 38 。
A. 根据IP地址查询MAC地址
B. 根据MAC地址查询IP地址
C. 根据域名查询IP地址
D. 根据IP地址查询域名
39. 某主机的IP地址为180.80.77.55，子网掩码为255.255.252.0。假设该主机向其所在子网发送播送分组，那么目的地址可以是 39 。
A. 180.80.76.0
B. 180.80.76.255
C. 180.80.77.255
D. 180.80.79.255
40. 假设用户1与用户2之间发送和接收电子邮件的过程如以下图所示，那么目的地址可以是 40 。

A. SMTP、SMTP、SMTP
B. POP3、SMTP、POP3
C. POP3、SMTP、SMTP
D. SMTP、SMTP、POP3
二、 综合应用题
41. 设有6个有序表A、B、C、D、E，分别含有10、35、40、50、60和200个数据元素，各表中元素按升序排列。要求通过5次两两合并，将6个表最终合并成1个升序表，并在最坏情况下比拟的总次数到达最小。请答复以下问题。
(1) 给出完整的合并过程，并求出最坏情况下比拟的总次数。
(2) 根据你的合并过程，描述N〔N>=2〕个不等长升序表的合并策略，并说明理由。
42. 假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，那么可共享相同的后缀存储空间，例如，’loading’和’being’的存储映像如以下图所示。

设str1和str2分别指向两个单词所在单链表的头结点(jié diǎn)，链表结点结构为，请设计一个时间上尽可能高效的算法，找出由str1和str2所指向两个链表共同后缀的起始位置〔如图中字符i所在的结点位置p〕。要求：
1) 给出算法的根本设计思想。
2) 根据设计思想，采用C或C++或Java语言描述算法，关键之处给出注释。
3) 说明你所设计算法的时间复杂度。
43. 假定某计算机的CPU主频为80MHz，CPI为4，平均每条指令访存1.5次，主存与Cache之间交换的块大小为16B，Cache的命中率为99%。存储器总线宽度为32位。请答复以下问题。
1) 该计算机的MIPS数是多少？平均每秒Cache缺失的次数是多少？在不考虑DMA传送的情况下，主存带宽至少到多少才能满足CPU的访存要求？
2) 假定在Cache丧失的情况下访问主存时，存储0.0005%的缺页率，那么CPU平均每秒产生多少次缺页异常？假设页面大小为4KB，每次缺页都需要访问磁盘，访问磁盘时DMA传送采用周期挪用方式，磁盘I/O接口的数据缓冲存放器为32位，那么磁盘I/O接口平均每秒发出的DMA请求次数至少是多少？
3) CPU和DMA控制器同时要求使用存储器总线时，哪个优先级更高？为什么？
4) 为了提高性能，主存采用4体低位交叉存储模式，工作时每1/4个存储周期启动一个体。假设每个体的存储周期为50ns，那么该主存能提供的最大带宽是多少？
44. 某16位计算机中，带符号整数用补码表示，数据Cache和指令Cache别离。题44表给出了指令系统中局部指令格式，其中Rs和Rd表示存放器，mem表示存储单地址，(x)表示存放器x或存储单元x的内容。

该计算机采用5段流水方式执行指令，各流水段分别是取指〔IF〕、译码/读存放器〔D〕、执行/计算有效地址〔EX〕、访问存储器〔M〕和结果写回存放器〔WB〕，流水线采用“按序发射，按序完成〞方式，没有采用转发技术处理数据相关，并且同一个存放器的读和写不能在同一个时钟周期内进行。请答复以下问题：
1) 假设int型变量x的值为-513，存放在存放器R1中，那么执行指令“SHL R1〞后，R1的内容是多少？〔用十六进制表示〕。
2) 假设某个时间段中，有连续的4条指令进入流水线，在其执行过程中没有发生任何阻塞，那么执行这4条指令所需的时钟周期数为多少？
3) 假设(jiǎshè)高级语言程序中某赋值语句为x=a+b,x,b和b均为int型变量，它们的存储单元地址分别表示为[x],[a]和[b]。该语句对应的指令序列及其在指令流水线中的执行过程如以下图所示。

那么这4条指令执行过程中，I3的ID段和I4的IF段被阻塞的原因各是什么？
4) 假设高级语言程序中某赋值语句为x=x*2+a,x和a均为unsigned int类型变量，它们的存储单元地址分别表示为[x],[a]，那么执行这条语句至少需要多少个时钟周期？要求模仿题44图画出这条语句对应的指令序列及其在流水线中的执行过程示意图。
45. 某请求分页系统的局部页面转换策略如下：
系统从0时刻开始扫描，每隔5个时间单位扫描下一轮驻留集〔扫描时间忽略不计〕，本轮没有被访问过的页框将被系统回收，并放入到空闲页框链尾，其中内容在下一次分配之前不被清空。当发生缺页时，如果该页曾被使用过且不在空闲页链表中，那么重新放回进程的驻留集中；否那么，从空闲页框链表善取出一个页框。
假设不考虑其他进程的影响和系统开销。初始时进程驻留集为空。目前系统空闲页框链表中页框号依次为32、15、21、41。进程P依次访问的<虚拟页号，访问时刻>是：<1,1>、<3,2>、<0,4>、<0,6>、<1,11>、<0,13>、<2,14>。请答复以下问题。
1) 访问<0,4>时，对应的页框号是什么？说明理由。
2) 访问<1,11>时，对应的页框号是什么？说明理由。
3) 访问<2,14>时，对应的页框号是什么？说明理由。
4) 该策略是否适合于时间局部性好的程序？说明理由。
46. 某文件系统空间的最大容量为4TB〔1TB=240B〕，以磁盘块为根本分配单位。磁盘块大小为1KB。文件控制块〔FCB〕包含一个512B的索引表区。请答复以下问题。
1) 假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？可支持的单个文件最大长度是多少字节？
2) 假设索引表区采用如下结构：第0~7字节采用<起始块号，块数>格式表示文件创立时预分配的连续存储空间，其中起始块号占6B，块数占2B；剩余504字节采用直接索引结构，一个索引项占6B，那么可支持的单个文件最大长度是多少字节？为了使单个文件的长度到达最大，请指出起始块号和块数分别所占字节数的合理值并说明理由。
47. 主机(zhǔjī)H通过快速以太网连接Internet，IP地址为192.168.0.8，效劳器S的IP地址为211.68.71.8。H与S使用TCP通信时，在H上捕获的其中5个IP分组如题47-a表所示。

答复以下问题。
1) 题47-a表中的IP分组中，哪几个是由H发送的？哪几个完成了TCP连接建立过程？哪几个在通过快速以太网传输时进行了填充？
2) 根据题47-a表中的IP分组，分析S已经收到的应用层数据字节数是什么？
3) 假设题47-a表中的某个IP分组在S发出时的前40字节如题47-b表所示，那么该IP分组到达H时经过了多少个路由器？

注：IP分组头和TCP段头结构分别如题47-a图，题47-b图所示。

与H与
11 / 11