资源描述
精品文档
2012 年全国硕士研究生入学(rù xué)统一考试—计算机专业根底综合试题
2012 年全国硕士研究生入学统一考试
计算机科学与技术学科联考
计算机学科专业根底综合试题
〔科目代码 408〕
1
35 / 35
2012 年全国硕士(shuòshì)研究生入学统一考试—计算机专业根底综合试题
一、单项选择题：第 1～40 小题，每题 2 分，共 80 分。以下每题给出的四个选项中，只有一个选项最符合试题
要求。
1．求整数 n(n≥0)阶乘的算法如下，其时间复杂度是
int fact(int n)
{
if (n<=1)return 1;
return n*fact(n-1);
}
A. O(log2n)
B. O(n)
C. (nlog2n)
D. O(n2)
2．操作符包括‘+’、‘-’、‘*’、‘/’、‘(’和‘)’。将中缀表达式 a+b-a*((c d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+
时，用栈来存放暂时还不能确定运算次序的操作符，假设栈初始时为空，那么转换过程中同时保存在栈中的操作符的最
大个数是
A. 5
B. 7
C. 8
D. 11
3.假设一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，那么根结点的孩子结点
A. 只有 e
B. 有 e、b
C. 有 e、c
D. 无法确定
4．假设平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，那么该平衡二叉树的结点总数为
A. 10
B. 20
C. 32
D. 33
5．对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是
A. O(n)
B. O(e)
C. O(n+e)
D. O(n*e)
6．假设用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，那么关于该图拓扑序列的结论是
A. 存在，且唯一
C. 存在，可能不唯一
B. 存在，且不唯一
D. 无法确定是否存在
7．对如下有向带权图，假设采用迪杰斯特拉〔Dijkstra〕算法求源点 a 到其他各顶点的最短路径，那么得到的第一条最
短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余各最短路径的目标顶点依次是
2
2012 年全国(quán ɡuó)硕士研究生入学统一考试—计算机专业根底综合试题
A.d,e,f
B.e,d,f
C. f,d,e
D.f,e,d
8．以下关于最小生成树的说法中，正确的选项是
I. 最小生成树树的代价唯一
II. 权值最小的边一定会出现在所有的最小生成树中
III. 用普里姆〔Prim〕算法从不同顶点开始得到的最小生成树一定相同
IV. 普里姆算法和克鲁斯卡尔〔Kruskal〕算法得到的最小生成树总不相同
A. 仅 I
B. 仅 II
C. 仅 I、III
D. 仅 II、IV
9．设有一棵 3 阶 B 树，如以下图所示。删除关键字 78 得到一棵新 B 树，其最右叶结点所含的关键字是
A. 60
B. 60, 62
C. 62, 65
D. 65
10．在内部排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。以下排序方法中，每一趟排
序结束都至少能够确定一个元素最终位置的方法是
I. 简单项选择择排序
II. 希尔排序
III. 快速排序
IV 堆排序
V. 二路归并排序
A. 仅 I、III、IV
C. 仅 II、III、IV
B. 仅 I、III、V
D. 仅 III、IV、V
11．对一待排序序列分别进行折半插入排序和直接插入排序，两者之间可能的不同之处是
A. 排序的总趟数
C. 使用辅助空间的数量
B. 元素的移动次数
D. 元素之间的比拟次数
12．假定基准程序 A 在某计算机上的运行时间为 100 秒，其中 90 秒为 CPU 时间，其余为 I/O 时间。假设 CPU 速度
提高 50%，I/O 速度不变，那么运行基准程序 A 所消耗的时间是
A. 55 秒
B. 60 秒
C. 65 秒
D. 70 秒
13．假定编译器规定 int 和 short 类型长度占 32 位和 16 位，执行以下 C 语言语句
unsigned short x = 65530;
unsigned int y = x;
得到(dé dào) y 的机器数为
3
2012 年全国硕士研究生入学(rù xué)统一考试—计算机专业根底综合试题
A. 0000 7FFA
B. 0000 FFFA
C. FFFF 7FFA
D. FFFF FFFA
14．float 类型〔即 IEEE754 单精度浮点数格式〕能表示的最大正整数是
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 的地址分别为
A. 0x00、0xC00D
C. 0x11、0xC00D
B. 0x00、0xC00E
D. 0x11、0xC00E
16．以下关于闪存〔Flash Memory〕的表达中，错误的选项是
A. 信息可读可写，并且读、写速度一样快
B. 存储元由 MOS 管组成，是一种半导体存储器
C. 掉电后信息不丧失，是一种非易失性存储器
D. 采用随机访问方式，可替代计算机外部存储器
17．假设某计算机按字编址，Cache 有 4 个行，Cache 和主存之间交换的块为 1 个字。假设 Cache 的内容初始为空，
采用 2 路组相联映射方式和 LRU 替换算法。当访问的主存地址依次为 0,4,8,2,0,6,8,6,4,8 时，命中 Cache 的次数是
A. 1
B. 2
C. 3
D. 4
18．某计算机的控制器采用微程序控制方式，微指令中的操作控制字段采用字段直接编码法，共有 33 个微命令，
构成 5 个互斥类，分别包含 7、3、12、5 和 6 个微命令，那么操作控制字段至少有
A. 5 位
B. 6 位
C.15 位
D. 33 位
19．某同步总线的时钟频率为 100MHz，宽度为 32 位，地址/数据线复用，每传送一次地址或者数据占用一个时钟
周期。假设该总线支持突发〔猝发〕传输方式，那么一次“主存写〞总线事务传输 128 位数据所需要的时间至少是
A. 20ns
B. 40ns
C. 50ns
D. 80ns
20．以下(yǐxià)关于 USB 总线特性的描述中，错误的选项是
4
2012 年全国硕士(shuòshì)研究生入学统一考试—计算机专业根底综合试题
A. 可实现外设的即插即用和热拔插
B. 可通过级联方式连接多台外设
C. 是一种通信总线，连接不同外设
D. 同时可传输 2 位数据，数据传输率高
21．以下选项中，在 I/O 总线的数据线上传输的信息包括
I. I/O 接口中的命令字
II. I/O 接口中的状态字
III.中断类型号
A. 仅 I、II
B. 仅 I、III
C. 仅 II、III
D. I、II、III
22．响应外部中断的过程中，中断隐指令完成的操作，除保护断点外，还包括
I. 关中断
II.保存通用存放器的内容
III.形成中断效劳程序入口地址并送 PC
A. 仅 I、II
B. 仅 I、III
C. 仅 II、III
D. I、II、III
23．以下选项中，不可能在用户态发生的事件是
A. 系统调用
B. 外部中断
C. 进程切换
D. 缺页
24．中断处理和子程序调用都需要压栈以保护现场，中断处理一定会保存而子程序调用不需要保存其内容的是
A. 程序计数器
C. 通用数据存放器
25．以下关于虚拟存储器的表达中，正确的选项是
A. 虚拟存储只能基于连续分配技术
C. 虚拟存储容量只受外存容量的限制
B. 程序状态字存放器
D. 通用地址存放器
B. 虚拟存储只能基于非连续分配技术
D. 虚拟存储容量只受内存容量的限制
26．操作系的 I/O 子系统通常由四个层次组成，每一层明确定义了与邻近层次的接口，其合理的层次组织排列顺序
是
A. 用户级 I/O 软件、设备无关软件、设备驱动程序、中断处理程序
B. 用户级 I/O 软件、设备无关软件、中断处理程序、设备驱动程序
C. 用户级 I/O 软件、设备驱动程序、设备无关软件、中断处理程序
D. 用户级 I/O 软件、中断处理程序、设备无关软件、设备驱动程序
27．假设(jiǎshè) 5 个进程 P0、P1、P2、P3、P4 共享三类资源 R1、R2、R3，这些资源总数分别为 18、6、22。T0 时刻的
资源分配情况如下表所示，此时存在的一个平安序列是
5
2012 年全国硕士研究生入学统一(tǒngyī)考试—计算机专业根底综合试题
进程
P0
P1
P2
P3
P4
R1
3
4
4
2
3
已分配资源
R2
2
0
0
0
1
R3
3
3
5
4
4
R1
5
5
4
4
4
资源最大需求
R2
5
3
0
2
2
R3
10
6
11
5
4
A. P0, P2, P4, P1, P3
C. P2，P1，P0，P3，P4
B. P1, P0, P3, P4, P2
D. P3, P4, P2, P1, P0
28．假设一个用户进程通过 read 系统调用读取一个磁盘文件中的数据，那么以下关于此过程的表达中，正确的选项是
I. 假设该文件的数据不在内存，那么该进程进入睡眠等待状态
II. 请求 read 系统调用会导致 CPU 从用户态切换到核心态
III. read 系统调用的参数应包含文件的名称
A. 仅 I、II
B. 仅 I、III
C. 仅 II、III
D. I、II 和 III
29．一个多道批处理系统中仅有 P1 和 P2 两个作业，P2 比 P1 晚 5ms 到达，它的计算和 I/O 操作顺序如下：
P1：计算 60ms，I/O 80ms，计算 20ms
P2：计算 120ms，I/O 40ms，计算 40ms
假设不考虑调度和切换时间，那么完成两个作业需要的时间最少是
A. 240ms
B. 260ms
C. 340ms
D. 360ms
30．假设某单处理器多进程系统中有多个就绪态进程，那么以下关于处理机调度的表达中错误的选项是
A. 在进程结束时能进行处理机调度
B. 创立新进程后能进行处理机调度
C. 在进程处于临界区时不能进行处理机调度
D. 在系统调用完成并返回用户态时能进行处理机调度
31．以下关于进程和线程的表达中，正确的选项是
A. 不管系统是否支持线程，进程都是资源分配的根本单位
B. 线程是资源分配的根本单位，进程是调度的根本单位
C. 系统级线程和用户级线程的切换都需要内核的支持
D. 同一进程中的各个(gègè)线程拥有各自不同的地址空间
32．以下选项中，不能改善磁盘设备 I/O 性能的是
6
2012 年全国硕士(shuòshì)研究生入学统一考试—计算机专业根底综合试题
A. 重排 I/O 请求次序
C. 预读和滞后写
33．在 TCP/IP 体系结构中，直接为 ICMP 提供效劳协议的是
B. 在一个磁盘上设置多个分区
D. 优化文件物理的分布
A. PPP
B. IP
C. UDP
D. TCP
34．在物理层接口特性中，用于描述完成每种功能的事件发生顺序的是
A. 机械特性
B. 功能特性
C.过程特性
D.电气特性
35．以太网的 MAC 协议提供的是
A. 无连接的不可靠的效劳
C. 有连接的可靠的效劳
B. 无连接的可靠的效劳
D. 有连接的不可靠的效劳
36．两台主机之间的数据链路层采用后退 N 帧协议〔GBN〕传输数据数据传输速率为 16 kbps，单向传播时延为 270ms，
数据帧长度范围是 128~512 字节，接收方总是以与数据帧等长的帧进行确认。为使信道利用率到达最高，帧序列的
比特数至少为
A. 5
B. 4
C. 3
D. 2
37．以下关于 IP 路由器功能的描述中，正确的选项是
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 协议的功能是
A. 根据 IP 地址查询 MAC 地址
C. 根据域名查询 IP 地址
B. 根据 MAC 地址查询 IP 地址
D. 根据 IP 地址查询域名
39．某主机的 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
40．假设用户 1 与用户 2 之间发送和接收电子邮件的过程如以下图所示，那么图中①、②、③阶段分别使用的应用层协议
可以是
7
2012 年全国硕士(shuòshì)研究生入学统一考试—计算机专业根底综合试题
A. SMTP、SMTP、SMTP
C. POP3、SMTP、SMTP
B. POP3、SMTP、POP3
D. SMTP、SMTP、POP3
二、综合应用题：第 41～47 题，共 70 分。请将答案写在答题纸指定位置上。
41.〔10 分〕设有 6 个有序表 A、B、C、D、E、F，分别含有 10、35、40、50、60 和 200 个数据元素，各表中元素
按升序排列。要求通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比拟的总次数到达最小。
请问答以下问题。
〔1〕给出完整的合并过程，并求出最坏情况下比拟的总次数。
〔2〕根据你的合并过程，描述 n〔n≥2〕个不等长升序表的合并策略，并说明理由。
8
2012 年全国硕士研究生入学(rù xué)统一考试—计算机专业根底综合试题
42.〔13 分〕假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，那么可共享相同的后缀存储空间，
例如，“loading〞和“being〞的存储映像如以下图所示。
str1
l
o
a
d
str2
b
e
i
p
n
g ^
设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为
，请设计一个时间上尽
可能高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置〔如图中字符 i 所在结点的位置 p〕。要求：
〔1〕给出算法的根本设计思想。
〔2〕根据设计思想，采用 C 或 C++或 JAVA 语言描述算法，关键之处给出注释。
〔3〕说明你所设计算法的时间复杂度。
9
2012 年全国(quán ɡuó)硕士研究生入学统一考试—计算机专业根底综合试题
43.〔11 分〕假设某计算机的 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.〔12 分〕某 16 位计算机中，带符号整数用补码表示，数据 Cache 和指令 Cache 别离。题 44 表给出了指令系统
中局部指令格式，其中 Rs 和 Rd 表示存放器，mem 表示存储单元地址，〔x〕表示存放器 x 或存储单元 x 的内容。
题 44 表指令系统中局部指令格式
10名称
指令的汇编格式
指令功能
加法指令
ADD Rs，Rd
(Rs)+(Rd)->Rd
算术/逻辑左移
SHL Rd
2*(Rd)->Rd
算术右移
SHR Rd
(Rd)/2->Rd
取数指令
LOAD Rd，mem
(mem)->Rd
存数指令
STORE Rs，mem
Rs->(mem)
2012 年全国硕士研究生入学(rù xué)统一考试—计算机专业根底综合试题
该计算机采用 5 段流水方式执行指令，各流水段分别是取指〔IF〕、译码/读存放器〔ID〕、执行/计算有效地
址〔EX〕、访问存储器〔M〕和结果写回存放器〔WB〕，流水线采用“按序发射，按序完成〞方式，没有采用转发
技术处理数据相关，并且同一存放器的读和写操作不能在同一个时钟周期内进行。请答复以下问题。
〔1〕假设 int 型变量 x 的值为-513，存放在存放器 R1 中，那么执行“SHL R1〞后，R1 中的内容是多少？〔用十六进制表
示〕
〔2〕假设在某个时间段中，有连续的 4 条指令进入流水线，在其执行过程中没有发生任何阻塞，那么执行这 4 条指令
所需的时钟周期数为多少？
〔3〕假设高级语言程序中某赋值语句为 x=a+b，x、a 和 b 均为 int 型变量，它们的存储单元地址分别表示为[x]、[a]
和[b]。该语句对应的指令序列及其在指令流中的执行过程如题 44 图所示。
I1
I2
I3
I4
LOAD
LOAD
ADD
STORE
R1，[a]
R2，[b]
R1，R2
R2，[x]
题 44 图 指令序列及其执行过程示意图
那么这 4 条指令执行过程中 I3 的 ID 段和 I4 的 IF 段被阻塞的原因各是什么？
〔4〕假设高级语言程序中某赋值语句为 x=x*2+a，x 和 a 均为 unsigned int 类型变量，它们的存储单元地址分别表示
为[x]、[a]，那么执行这条语句至少需要多少个时钟周期？要求模仿题 44 图画出这条语句对应的指令序列及其在流水
线中的执行过程示意图。
11
2012 年全国硕士(shuòshì)研究生入学统一考试—计算机专业根底综合试题
45.(7 分)某请求分页系统的页面置换策略如下：
从 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〕这种方法是否适合于时间局部性好的程序？说明理由。
12
2012 年全国硕士研究生入学(rù xué)统一考试—计算机专业根底综合试题
46.〔8 分〕某文件系统空间的最大容量为 4TB〔1TB=240〕，以磁盘块为根本分配单位。磁盘块大小为 1KB。文件控
制块〔FCB〕包含一个 512B 的索引表区。请答复以下问题。
〔1〕假设索引表区仅采用直接索引结构，索引表区存放文件占用的磁盘块号，索引表项中块号最少占多少字节？
可支持的单个文件最大长度是多少字节？
〔2〕假设索引表区采用如下结构：第 0~7 字节采用<起始块号，块数>格式表示文件创立时预分配的连续存储
空间。其中起始块号占 6B，块数占 2B，剩余 504 字节采用直接索引结构，一个索引项占 6B，那么可支持的单个文件
最大长度是多少字节？为了使单个文件的长度到达最大，请指出起始块号和块数分别所占字节数的合理值并说明理
由。
47.〔9 分〕主机 H 通过快速以太网连接 Internet，IP 地址为 192.168.0.8，效劳器 S 的 IP 地址为 211.68.71.80。H 与
S 使用 TCP 通信时，在 H 上捕获的其中 5 个 IP 分组如 题 47-a 表所示。
题 47-a 表
答复以下问题。
〔1〕题 47-a 表中的 IP 分组中，哪几个是由 H 发送的？哪几个完成了 TCP 连接建立过程？哪几个在通过快速
以太网传输时进行了填充？
〔2〕根据(gēnjù)题 47-a 表中的 IP 分组，分析 S 已经收到的应用层数据字节数是多少？
〔3〕假设题 47-a 表中的某个 IP 分组在 S 发出时的前 40 字节如题 47-b 表所示，那么该 IP 分组到达 H 时经过了多
13编号
IP 分组的前 40 字节内容〔十六进制〕
1
45 00 00 30 01 9b 40 00 80 06 1d e8 c0 a8 00 08 d3 44 47 50
0b d9 13 88 84 6b 41 c5 00 00 00 00 70 02 43 80 5d b0 00 00
2
43 00 00 30 00 00 40 00 31 06 6e 83 d3 44 47 50 c0 a8 00 08
13 88 0b d9 e0 59 9f ef 84 6b 41 c6 70 12 16 d0 37 e1 00 00
3
45 00 00 28 01 9c 40 00 80 06 1d ef c0 a8 00 08 d3 44 47 50
0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 f0 43 80 2b 32 00 00
4
45 00 00 38 01 9d 40 00 80 06 1d de c0 a8 00 08 d3 44 47 50
0b d9 13 88 84 6b 41 c6 e0 59 9f f0 50 18 43 80 e6 55 00 00
5
45 00 00 28 68 11 40 00 31 06 06 7a d3 44 47 50 c0 a8 00 08
13 88 0b d9 e0 59 9f f0 84 6b 41 d6 50 10 16 d0 57 d2 00 00
2012 年全国硕士研究生入学统一(tǒngyī)考试—计算机专业根底综合试题
少个路由器？
题 47-b 表
来自 S 的分组
45 00 00 28 68 11 40 00 40 06 ec ad d3 44 47 50 ca 76 01 06
13 88 a1 08 e0 59 9f f0
84 6b 41 d6 50 10 16 d0 b7 d6 00 00
注：IP 分组头和 TCP 段头结构分别如题 47-a 图，题 47-b 图所示。
题 47-a 图 IP 分组头结构
题 47-b 图 TCP 段头结构
14
2012 年全国硕士研究生入学(rù xué)统一考试—计算机专业根底综合试题
计算机专业根底综合试题参考答案
一、单项选择题：每题 2 分，共 80 分。
1 - 5 BAABC
21-25 DBCBB
6-10 CCADA
26-30 ADABC
11-15 DDBDD
31-35 ABBCA
16-20 ACCCD
36-40 BCADD
二、综合应用题：41~47 小题，共 70 分。
41.【解析】
〔1〕对于长度分别为 m，n 的两个有序表的合并过程，最坏情况下需要一直比拟到两个表尾元素，比拟次数为
m+n-1 次。需要 5 次两两合并，故可设总比拟次数为 X-5，X 就是以 N 个叶子结点表示升序表，以升序表的表
长表示结点权重，构造的二叉树的带权路径长度。故只需设计方案使得 X 最小。这样受哈夫曼树和最正确归并树思想
的启发，设计哈夫曼树如下：
这样，最坏情况下比拟的总次数为：
N = (10 + 35) × 4 + (40 + 50 + 60) × 3 + 200 − 5 = 825
〔2〕N〔N≥2〕个不等长升序表的合并策略：
以 N 个叶子结点表示升序表，以升序表的表长表示结点权重，构造哈夫曼树。合并时，从深度最大的结点所代
表的升序表开始合并，依深度次序一直进行到根结点。
理由：N 个有序表合并需要进行 N-1 次两两合并，可设最坏情况下的比拟总次数为 X-N+1，X 就是以 N 个叶子
结点表示升序表，以升序表的表长表示结点权重，构造的二叉树的带权路径长度。根据哈夫曼树的特点，上述设计
的比拟次数是最小的。
42.【解析】
〔1〕算法思想：顺序遍历两个链表到尾结点时，并不能保证两个链表同时到达尾结点。这是因为两个链表的
长度不同。假设一个链表比另一个链表长 k 个结点，我们先在长链表上遍历 k 个结点，之后同步遍历两个链表。这
样我们就能够保证它们同时到达最后一个结点了。由于两个链表从第一个公共结点到链表的尾结点都是重合的。所
以它们肯定同时到达第一个公共结点。于是得到算法思路：
① 遍历两个链表求的它们的长度 L1，L2；
② 比拟(bǐnǐ) L1，L2，找出较长的链表，并求 L=|L1-L2|；
③ 先遍历长链表的 L 各结点；
15
2012 年全国(quán ɡuó)硕士研究生入学统一考试—计算机专业根底综合试题
④ 同步遍历两个链表，直至找到相同结点或链表结束。
〔2〕算法的 C 语言代码描述
LinkList Search_First_Common(LinkList L1,LinkList L2){
//本算法实现线性时间内找到两个单链表的第一个公共结点
int len1=Length(L1);,len2=Length(L2);
LinkList longList,shortlist;//分别指向较长和较短的链表
if(len1>len2){
longList=L1->next;
shortlist=L2->next;
L=len1-len2;//表长之差
}
else{
longList=L2->next;
shortlist=L1->next;
L=len2-len1;//表长之差
}
While(L--)
longList=longList->next;
while(longList!=NULL){
if(longList==shortList)//同步寻找共同结点
return longList;
else{
longList=longList->next;
shortlist=shortlist->next;
}
}//while
return NULL;
}
〔3〕算法的时间复杂度为 O(len1+len2)，空间复杂度为 O(1)。
43.【解析】
〔1〕MIPS=CPU 主频×10-6/CPI=80M/4=20；平均每条指令访存 1.5 次, Cache 的命中率为 99%，故每秒 Cache
缺失的次数=20M×1.5×1%=300000〔次〕；
〔 2〕在不使用 DMA 传送的情况下，所有主存的存取操作都需要经过 CPU，所以主存带宽至少应为
20M/s×1.5×4B=120MB/s。
由于页式虚拟存储方式的页表始终位于内存，那么产生缺页异常的只能是指令的访存。每秒产生缺页中断
20M/s×1.5×0.0005%=150 次。因此平均每秒发出的 DMA 请求次数至少是 150×4KB/4B=150K 次。
〔3〕优先响应 DMA 请求。DMA 通常连接高速 I/O 设备，假设不及时处理可能丧失数据。
〔4〕当 4 体低位交叉存储器稳定运行时，能提供的最大带宽为 4×4B/50ns=320MB/s。
44. 【解析】
〔1〕x 的机器码为[x]=1111 1101 1111B，即指令执行前〔R1〕=FDFFH，右移 1 位后位 1111 1110 1111 1111B，
即指令执行后〔R1〕=FEFFH。
〔2〕至少(zhìshǎo)需要 4+〔5-1〕=8 个时钟周期数。
〔3〕I3 的 ID 段被阻塞的原因：因为 I3 与 I1 和 I2 都存在数据相关，需等到 I1 和 I2 将结果写回存放器后，I3 才能
16
2012 年全国硕士研究生入学统一(tǒngyī)考试—计算机专业根底综合试题
读存放器内容，所以 I3 的 ID 段被阻塞。
I4 的 IF 段被阻塞的原因：因为 I4 的前一条指令 I3 在 ID 段被阻塞，所以 I4 的 IF 段被阻塞。
〔4〕因 2*x 操作有左移和加法两种实现方法，故 x=x*2+a 对应的指令序列为
I1 LOAD
R1，[x]
I2 LOAD R2，[a]
I3 SHL
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
