# 2016年全国硕士研究生招生考试

# 计算机科学与技术学科联考计算机学科专业基础综合试题

# 一、单项选择题：1～40小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项符合试题要求。

1.已知表头元素为c的单链表在内存中的存储状态如下表所示

<table><tr><td>地址</td><td>元素</td><td>链接地址</td></tr><tr><td>1000H</td><td>a</td><td>1010H</td></tr><tr><td>1004H</td><td>b</td><td>100CH</td></tr><tr><td>1008H</td><td>C</td><td>1000H</td></tr><tr><td>100CH</td><td>d</td><td>NULL</td></tr><tr><td>1010H</td><td>e</td><td>1004H</td></tr><tr><td>1014H</td><td></td><td></td></tr></table>

现将f存放于1014H处并插入到单链表中，若f在逻辑上位于a和e之间，则a，e，f的“链接地址”依次是

A. 1010H, 1014H, 1004H B. 1010H, 1004H, 1014H  
C.  ${1014}\mathrm{H},{1010}\mathrm{H},{1004}\mathrm{H}$  D.  ${1014}\mathrm{H},{1004}\mathrm{H},{1010}\mathrm{H}$

2. 已知一个带有表头结点的双向循环链表L, 结点结构为

<table><tr><td>prev</td><td>data</td><td>next</td></tr></table>

其中，prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是

A. p->next->prev=p->prev; p->prev->next=p->prev; free(p);  
B. p->next->prev=p->next; p->prey->next=p->next; free(p);  
C. p->next->prev=p->next; p->prev->next=p->prev; free(p);  
D. p->next->prey=p->prey; p->prev->next=p->next; free(p);

3. 设有如下图所示的火车车轨，入口到出口之间有n条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为1～9的9列列车，驶入的次序依次是8，4，2，5，3，9，1，6，7。若期望驶出的次序依次为1～9，则n至少是

![](https://408.foreverlink.love/images/78897f8803541d832d597ec371729101.jpg)

A. 2 B. 3 C. 4 D. 5

4.有一个100阶的三对角矩阵M，其元素  $\mathbf{m}_{\mathrm{i},\mathrm{j}}(1\leq i\leq 100,1\leq j\leq 100)$  按行优先次序压缩存入下标从0开始的一维数组IV中。元素  $\mathbf{m}_{30,30}$  在N中的下标是

A.86 B.87 C.88 D.89

5.若森林F有15条边、25个结点，则F包含树的个数是

A. 8 B. 9 C. 10 D. 11

6. 下列选项中，不是下图深度优先搜索序列的是

![](https://408.foreverlink.love/images/05025c62029f10ed06ab79b0f09bddbd.jpg)

A.  $V_{1}, V_{5}, V_{4}, V_{3}, V_{2}$  B.  $V_{1}, V_{3}, V_{2}, V_{5}, V_{4}$  
C.  $V_{1}, V_{2}, V_{5}, V_{4}, V_{3}$  D.  $V_{1}, V_{2}, V_{3}, V_{4}, V_{5}$

7. 若将n个顶点e条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是

A.  $\mathrm{O}\left( \mathrm{n}\right)$

B.  $O(n + e)$

C.  $\mathrm{O}\left( {\mathrm{n}}^{2}\right)$

D.  $O(n \times e)$

8. 使用迪杰斯特拉(Dijkstra)算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是

![](https://408.foreverlink.love/images/92ea2daa059778c28bd440fd17f7180e.jpg)

A. 5, 2, 3, 4, 6  
B. 5, 2, 3, 6, 4  
C. 5, 2, 4, 3, 6  
D. 5, 2, 6, 3, 4

9. 在有n(n>1000)个元素的升序数组A中查找关键字x。查找算法的伪代码如下所示。

k=0;

while(k<n且A[k]>x)k=k+3;

if  $\mathrm{k <   n}$  且A[k]=x查找成功；

else if(k-1<n且A[k-1] == x) 查找成功;

else if(k-2<n且A[k-2] == x) 查找成功;

else查找失败；

本算法与折半查找算法相比，有可能具有更少比较次数的情形是

A. 当  $\mathrm{x}$  不在数组中

B. 当x接近数组开头处

C. 当x接近数组结尾处

D. 当x位于数组中间位置

10.  $\mathbf{B}^{+}$ 树不同于B树的特点之一是

A. 能支持顺序查找  
B. 结点中含有关键字  
C. 根结点至少有两个分支  
D. 所有叶结点都在同一层上

11. 对10 TB的数据文件进行排序，应使用的方法是

A. 希尔排序

B. 堆排序

C. 快速排序

D. 归并排序

12. 将高级语言源程序转换为机器级目标代码文件的程序是

A. 汇编

B. 链接程序

C. 编译程序

D. 解释程序

13.有如下C语言程序段：

short si=-32767;

unsigned short usi=si;

执行上述两条语句后，usi的值为

A. -32767

B. 32767

C. 32768

D. 32769

14. 某计算机字长为32位，按字节编址，采用小端(Little Endian)方式存放数据。假定有一个double型变量，其机器数表示为1122334455667788H，存放在00008040H开始的连续存储单元中，则存储单元00008046H中存放的是

A.  ${22}\mathrm{H}$

33H

D. 77H

15.有如下C语言程序段：

for(k=0;k<1000;k++)

a[k]=a[k]+32;

若数组a及变量k均为int型，int型数据占4B，数据Cache采用直接映射方式、数据区大小为1KB、块大小为16B，该程序段执行前Cache为空，则该程序段执行过程中访问数组a的Cache缺失率约为

A.  $1.25\%$

B.  $2.5\%$

C.  $12.5\%$

D.  $25\%$

16. 某存储器容量为64KB，按字节编址，地址  $4000\mathrm{H}\sim 5\mathrm{FFFH}$  为ROM区，其余为RAM区。若采用8K×4位的SRAM芯片进行设计，则需要该芯片的数量是

A. 7

B. 8

C. 14

D. 16

17. 某指令格式如下所示。

![](https://408.foreverlink.love/images/357fefb1882a28a070af427ace3c1477.jpg)

其中M为寻址方式，I为变址寄存器编号，D为形式地址。若采用先变址后间址的寻址方式，则操作数的有效地址是

A. I+D

B. (I) + D

C.  $(\mathrm{I}) + \mathrm{D}$

D.  $(\mathrm{I})^{+} + \mathrm{D}$

18. 某计算机主存空间为4GB，字长为32位，按字节编址，采用32位定长指令字格式。若指令按字边界对齐存放，则程序计数器(PC)和指令寄存器(IR)的位数至少分别是

A.30、30

B. 30、32

C. 32、30

D. 32、32

19. 在无转发机制的五段基本流水线(取指、译码/读寄存器、运算、访存、写回寄存器)中，下列指令序列存在数据冒险的指令对是

I1:add R1, R2, R3; (R2)+(R3)→R1

I2:add R5,R2,R4;R2)+(R4)→R5

I3:add R4,R5,R3;R5+(R3)→R4

I4:add R5,R2,R6;R2+(R6)→R5

A.II和I2 B.I2和I3 C.I2和I4 D.I3和I4

20. 单周期处理器中所有指令的指令周期为一个时钟周期。下列关于单周期处理器的叙述中，错误的是

A. 可以采用单总线结构数据通路  
B. 处理器时钟频率较低  
C. 在指令执行过程中控制信号不变  
D. 每条指令的CPI为1

21. 下列关于总线设计的叙述中，错误的是

A. 并行总线传输比串行总线传输速度快  
B. 采用信号线复用技术可减少信号线数量  
C. 采用突发传输方式可提高总线数据传输率  
D.采用分离事务通信方式可提高总线利用率

22. 异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。下列关于中断或异常情况的叙述中，错误的是

A. “访存时缺页”属于中断  
B. “整数除以0”属于异常  
C. “DMA传送结束”属于中断  
D. “存储保护错”属于异常

23.下列关于批处理系统的叙述中，正确的是

I. 批处理系统允许多个用户与计算机直接交互

II. 批处理系统分为单道批处理系统和多道批处理系统

III.中断技术使得多道批处理系统的I/O设备可与CPU并行工作

A. 仅Ⅱ、Ⅲ B. 仅Ⅱ C. 仅I、Ⅱ D. 仅I、Ⅲ

24. 某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为  $2 \mathrm{~ms}$  、  $3 \mathrm{~ms}$  和  $4 \mathrm{~ms}$ ，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是

A.  $15\mathrm{ms}$  B.  $17\mathrm{ms}$  C.  $22\mathrm{ms}$  D.  $27\mathrm{ms}$

25. 系统中有3个不同的临界资源R1、R2和R3，被4个进程p1、p2、p3及p4共享。各进程对资源的需求为：p1申请R1和R2，p2申请R2和R3，p3申请R1和R3，p4申请R2。若系统出现死锁，则处于死锁状态的进程数至少是

A. 1 B. 2 C. 3 D. 4

26. 某系统采用改进型CLOCK置换算法，页表项中字段A为访问位，M为修改位。A=0表示页最近没有被访问，A=1表示页最近被访问过。M=0表示页没有被修改过，M=1表示页被修改过。按(A，M)所有可能的取值，将页分为四类：(0，0）、(1，0）、(0，1)和(1，1)，则该算法淘汰页的次序为

A. (0, 0), (0, 1), (1, 0), (1, 1)  
B. (0, 0), (1, 0), (0, 1), (1, 1)  
C.  $(0, 0), (0, 1), (1, 1), (1, 0)$  
D. (0, 0), (1, 1), (0, 1), (1, 0)

27. 使用TSL(Test and Set Lock)指令实现进程互斥的伪代码如下所示。

do{ while(TSL(&lock)); critical section; lock  $\equiv$  FALSE;

} whileTRUE);

下列与该实现机制相关的叙述中，正确的是

A. 退出临界区的进程负责唤醒阻塞态进程  
B.等待进入临界区的进程不会主动放弃CPU  
C. 上述伪代码满足“让权等待”的同步准则  
D. while(TSL(&lock))语句应在关中断状态下执行

28. 某进程的段表内容如下所示。

<table><tr><td rowspan="4">段号012</td><td>段长</td><td>内存起始地址</td><td>权限</td><td>状态</td></tr><tr><td>100</td><td>6000</td><td>只读</td><td>在内存</td></tr><tr><td>200</td><td>-</td><td>读写</td><td>不在内存</td></tr><tr><td>300</td><td>4000</td><td>读写</td><td>在内存</td></tr></table>

当访问段号为2、段内地址为400的逻辑地址时，进行地址转换的结果是

A. 段缺失异常

B. 得到内存地址4400

C. 越权异常

D. 越界异常

29. 某进程访问页面的序列如下所示。

![](https://408.foreverlink.love/images/2caf119a3394a7c4efca8a6f76f7bbaa.jpg)

若工作集的窗口大小为6，则在£时刻的工作集为

A.  $\{6,0,3,2\}$

B.  $\{2, 3, 0, 4\}$

c.  $\{0,4,3,2,9\}$

D.  $\{4, 5, 6, 0, 3, 2\}$

30. 进程P1和P2均包含并发执行的线程，部分伪代码描述如下所示。

<table><tr><td>//进程P1
    int x=0;
    Thread1()
    {
        int a:
        a=1;     x+=1;
    }
    Thread2()
    {
        int a:
        a=2; x+=2;
    }</td><td>//进程P2
    int x=0;
    Thread3()
    {
        int a:
        a=x;     x+=3;
    }
    Thread4()
    {
        int b:
        b=x; x+=4;
    }</td></tr></table>

下列选项中，需要互斥执行的操作是

A.  $a = 1$  与  $a = 2$

B.  $\mathrm{a} = \mathrm{x}$  与  $\mathrm{b} = \mathrm{x}$

c.  $x+=1$  与  $x+=2$

D.  $x+=1$  与  $x+=3$

31. 下列关于SPOOLing技术的叙述中，错误的是

A. 需要外存的支持  
B. 需要多道程序设计技术的支持  
C. 可以让多个作业共享一台独占设备  
D. 由用户作业控制设备与输入/输出井之间的数据传送

32. 下列关于管程的叙述中，错误的是

A. 管程只能用于实现进程的互斥  
B. 管程是由编程语言支持的进程同步机制  
C. 任何时候只能有一个进程在管程中执行  
D. 管程中定义的变量只能被管程内的过程访问

题33～41均依据题33～41图回答。

33. 在OSI参考模型中，R1、Switch、Hub实现的最高功能层分别是

A. 2、2、1

B. 2、2、2

C. 3、2、1

D. 3、2、2

34.若连接R2和R3链路的频率带宽为8kHz，信噪比为30dB，该链路实际数据传输速率约为理论最大数据传输速率的50%，则该链路的实际数据传输速率约是

A. 8 kbps

B. 20 kbps

C. 40 kbps

D. 80 kbps

![](https://408.foreverlink.love/images/006334fa605c5dc3591806ffda024d5c.jpg)  
题33～41图

35. 若主机H2向主机H4发送1个数据帧，主机H4向主机H2立即发送一个确认帧，则除H4外，从物理层上能够收到该确认帧的主机还有

A. 仅H2 B. 仅H3 C. 仅H1、H2 D. 仅H2、H3

36. 若Hub再生比特流过程中，会产生  $1.535 \mu \mathrm{s}$  延时，信号传播速度为  $200 \mathrm{~m} / \mu \mathrm{s}$ ，不考虑以太网帧的前导码，则H3与H4之间理论上可以相距的最远距离是

A.  $200\mathrm{m}$  B.  $205\mathrm{m}$  C.  $359\mathrm{m}$  D.  $512\mathrm{m}$

37.假设R1、R2、R3采用RIP协议交换路由信息，且均已收敛。若R3检测到网络201.1.2.0/25不可达，并向R2通告一次新的距离向量，则R2更新后，其到达该网络的距离是

A. 2 B. 3 C. 16 D. 17

38.假设连接R1、R2和R3之间的点对点链路使用201.1.3.x/30地址，当H3访问Web服务器S时，R2转发出去的封装HTTP请求报文的IP分组的源IP地址和目的IP地址分别是

A. 192.168.3. 251, 130.18.10.1 B. 192.168.3. 251, 201.1. 3.9

C. 201.1.3.8, 130.18.10.1 D. 201.1.3.10, 130.18.10.1

39. 假设H1与H2的默认网关和子网掩码均分别配置为192.168.3. 1和255.255.255.128，H3与H4的默认网关和子网掩码均分别配置为192.168.3. 254和255.255.255.128，则下列现象中可能发生的是

A.H1不能与H2进行正常IP通信

B.H2与H4均不能访问Internet

C.H1不能与H3进行正常IP通信

D.H3不能与H4进行正常IP通信

40.假设所有域名服务器均采用迭代查询方式进行域名解析。当H4访问规范域名为

www. abc. xyz. com的网站时，域名服务器201.1.1.1在完成该域名解析过程中，可能发出DNS查询的最少和最多次数分别是

A. 0,3 B. 1,3 C. 0,4 D. 1,4

二、综合应用题：41～47小题，共70分。

41.(9分)假设题33～41图中的H3访问Web服务器S时，S为新建的TCP连接分配了20KB(K=1024)的接收缓存，最大段长MSS=1 KB，平均往返时间RTT=200 ms。H3建立连接时的初始序号为100，且持续以MSS大小的段向S发送数据，拥塞窗口初始阈值为32 KB；S对收到的每个段进行确认，并通告新的接收窗口。假定TCP连接建立完成后，S端的TCP接收缓存仅有数据存入而无数据取出。请回答下列问题。

(1)在TCP连接建立过程中，H3收到的S发送过来的第二次握手TCP段的SYN和ACK标志位的值分别是多少？确认序号是多少？
A. 0 B. 1 C. 2 D. 3

(2)H3收到的第8个确认段所通告的接收窗口是多少?此时H3的拥塞窗口变为多少?H3的发送窗口变为多少？

(3)当H3的发送窗口等于0时，下一个待发送的数据段序号是多少?H3从发送第1个数据段到发送窗口等于0时刻为止，平均数据传输速率是多少(忽略段的传输延时)?

(4)若H3与S之间通信已经结束，在t时刻H3请求断开该连接，则从t时刻起，S释放该连接的最短时间是多少？

42. (8分)如果一棵非空k(k≥2)叉树T中每个非叶结点都有k个孩子，则称T为正则后k树。请回答下列问题并给出推导过程。

(1)若T有m个非叶结点，则T中的叶结点有多少个？

(2)若T的高度为h（单结点的树h=1），则T的结点数最多为多少个？最少为多少个？

43. (15分)已知由  $n(n \geq 2)$  个正整数构成的集合  $A = \{a_{k}\} 0 \leq k < n$ , 将其划分为两个不相交的子集  $A_{1}$  和  $A_{2}$ , 元素个数分别是  $n_{1}$  和  $n_{2}$ ,  $A_{1}$  和  $A_{2}$  中元素之和分别为  $S_{1}$  和  $S_{2}$  。设计一个尽可能高效的划分算法, 满足  $|n_{1} - n_{2}|$  最小且  $|S_{1} - S_{2}|$  最大。要求:

(1)给出算法的基本设计思想。

(2)根据设计思想，采用C或C++语言描述算法，关键之处给出注释。

(3)说明你所设计算法的平均时间复杂度和空间复杂度。

44. (9分)假定CPU主频为50MHz，CPI为4。设备D采用异步串行通信方式向主机传送7位ASCII字符，通信规程中有1位奇校验位和1位停止位，从D接收启动命令到字符送入I/O端口需要  $0.5\mathrm{ms}$  。请回答下列问题，要求说明理由。

(1)每传送一个字符，在异步串行通信线上共需传输多少位？在设备D持续工作过程中，每秒钟最多可向I/O端口送入多少个字符？

(2)设备D采用中断方式进行输入/输出，示意图如下：

![](https://408.foreverlink.love/images/9b7185183a6dc70cc96597047dd789fb.jpg)

I/O端口每收到一个字符申请一次中断，中断响应需10个时钟周期，中断服务程序共有20条指令，其中第15条指令启动D工作。若CPU需从D读取1000个字符，则完成这一任务所需时间大约是多少个时钟周期?CPU用于完成这一任务的时间大约是多少个时钟周期?在中断响应阶段CPU进行了哪些操作？

45. (14分) 某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为32位，物理地址为24位，页大小为8KB；TLB采用全相联映射；Cache数据区大小为64KB，按2路组相联方式组织，主存块大小为64B。存储访问过程的示意图如下。

![](https://408.foreverlink.love/images/cedaabad1b7c5a2af6d7180a3ddafc78.jpg)

请回答下列问题。

(1)图中字段A～G的位数各是多少?TLB标记字段B中存放的是什么信息？

(2)将块号为4099的主存块装入到Cache中时，所映射的Cache组号是多少?对应的H字段内容是什么？

(3)Cache缺失处理的时间开销大还是缺页处理的时间开销大？为什么？

(4)为什么Cache可以采用直写(Write Through)策略，而修改页面内容时总是采用回写(Write Back)策略？

46. (6分)某进程调度程序采用基于优先数(priority)的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1。请回答下列问题。

(1)若调度程序只将nice的值作为进程的优先数，即priority=nice，则可能会出现饥饿现象，为什么？

(2)使用nice、cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用。

47. (9分)某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。

(1)假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中dir、dir1是目录，file1、file2是用户文件。请给出所有目录文件的内容。

<table><tr><td>文件名</td><td>簇号</td></tr><tr><td>dir</td><td>1</td></tr><tr><td>dir1</td><td>48</td></tr><tr><td>file1</td><td>100、106、108</td></tr><tr><td>file2</td><td>200、201、202</td></tr></table>

(2)若FAT的每个表项仅存放簇号，占2个字节，则FAT的最大长度为多少字节？该文件系统支持的文件长度最大是多少？
  
(3)系统通过目录文件和FAT实现对文件的按名存取，说明file1的106、108两个簇号分别存放在FAT的哪个表项中。  
(4)假设仅FAT和dir目录文件已读入内存，若需将文件dir/dir1/file1的第5000个字节读入内存，则要访问哪几个簇？

# 参考答案(2016年)

# 一、单项选择题

<table><tr><td>1. D</td><td>2. D</td><td>3. C</td><td>4. B</td><td>5. C</td></tr><tr><td>6. D</td><td>7. B</td><td>8. B</td><td>9. B</td><td>10. A</td></tr><tr><td>11. D</td><td>12. C</td><td>13. D</td><td>14. A</td><td>15. C</td></tr><tr><td>16. C</td><td>17. C</td><td>18. B</td><td>19. B</td><td>20. A</td></tr><tr><td>21. A</td><td>22. A</td><td>23. A</td><td>24. B</td><td>25. C</td></tr><tr><td>26. A</td><td>27. B</td><td>28. D</td><td>29. A</td><td>30. C</td></tr><tr><td>31. D</td><td>32. A</td><td>33. C</td><td>34. C</td><td>35. D</td></tr><tr><td>36. B</td><td>37. B</td><td>38. D</td><td>39. C</td><td>40. C</td></tr></table>

# 二、综合应用题

# 41.【答案要点】

(1)第二次握手TCP段的SYN=1，(1分)ACK=1；(1分)确认序号是101。(1分)  
(2)H3收到的第8个确认段所通告的接收窗口是12KB；（1分）此时H3的拥塞窗口变为9KB；(1分)H3的发送窗口变为9KB。（1分）
  
(3)当H3的发送窗口等于0时，下一个待发送段的序号是  $20\mathrm{K} + 101 = 20\times 1024 + 101 = 20581$ ；(1分)H3从发送第1个段到发送窗口等于0时刻为止，平均数据传输速率是  $20\mathrm{KB / (5\times 200ms)} = 20$  KB/s=20.48kbps。(1分)  
(4)从t时刻起，S释放该连接的最短时间是：  $1.5\times 200\mathrm{ms} = 300\mathrm{ms}$  。(1分)

# 42.【答案要点】

(1)根据定义，正则k叉树中仅含有两类结点：叶结点(个数记为n0)和度为k的分支结点(个数记为nk)。树T中的结点总数  $n = n_0 + n_k = n_0 + m$  。树中所含的边数  $e = n - 1$ ，这些边均为m个度为k的结点发出的，即  $e = m \times k$  。整理得：  $n_0 + m = m \times k + 1$ ，故  $n_0 = (k - 1) \times m + 1$  。(3分)  
(2)高度为h的正则k叉树T中，含最多结点的树形为：除第h层外，第1到第h-1层的结点都是度为k的分支结点，而第h层均为叶结点，即树是“满”树。此时第j(1≤j≤h)层结点数为k¹，结点总数M为：

$$
M _ {1} = \sum_ {j = 1} ^ {h} k ^ {j - 1} = \frac {k ^ {h} - 1}{k - 1} \tag {3分}
$$

含最少结点的正则k叉树的树形为：第1层只有根结点，第2到第h-1层仅含1个分支结点和k-1个叶结点，第h层有k个叶结点。即除根外第2到第h层中每层的结点数均为k，故T中所含结点总数M2为：

$$
\mathrm {M} _ {2} = 1 + (\mathrm {h} - 1) \times \mathrm {k} \quad (2 \text {分})
$$

# 【评分说明】

①参考答案仅给出一种推导过程，若考生采用其他推导方法且正确，同样给分。  
②若考生仅给出结果，但没有推导过程，则(1)、(2)的最高得分分别是2分和3分。若推导过程或答案不完全正确，酌情给分。

# 43.【答案要点】

(1)算法的基本设计思想(4分）

由题意知，将最小的  $\lfloor n / 2\rfloor$  个元素放在A中，其余的元素放在A中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将n个整数划分为两个子集。根据划分后枢轴所处的位置i分别处理：

①若  $i = \lfloor n / 2\rfloor$  ，则分组完成，算法结束；  
②若  $\mathrm{i} < \left\lfloor  {n/2}\right\rfloor$  ,则枢轴及之前的所有元素均属于  ${\mathrm{A}}_{1}$  ,继续对  $\mathrm{i}$  之后的元素进行划分；  
(3)若  $i > \lfloor n / 2\rfloor$  ，则枢轴及之后的所有元素均属于  $\mathbf{A}_2$  ，继续对i之前的元素进行划分；

基于该设计思想实现的算法，毋须对全部元素进行全排序，其平均时间复杂度是O(n)，空间复杂度是O(1)。

(2)算法实现(9分）

```javascript
intsetPartition(inta[ ],intn)   
{ intpivotkey，low  $= 0$  ，low  $0 = 0$  ，high=n-1，high0=n-1，flag  $= 1$  ，  $\mathrm{k} = \mathrm{n} / 2$  ，i; ints1  $= 0$  ，s2  $= 0$  while（flag） {pivotkey=a[low]； //选择枢轴 while(low<high) //基于枢轴对数据进行划分 {while(low<high&&a[high]  $\rightharpoonup$  pivotkey)-- high; if(low!  $\equiv$  high)a[low]=a[high]; while(low<high&&a[low]  $\rightharpoondown$  pivotkey) ++low: if(low！  $\equiv$  high)a[high]=a[low]; }//end of while(low<high) a[low]=pivotkey; if(low==k-1) //如果枢轴是第n/2小元素，划分成功 flag  $= 0$  ： else //否则继续划分 {if(low<k-1) { low0  $= + + 1$  low; high  $\equiv$  high0; } else {high0=-mhigh; low  $\equiv$  low0; } } } for(i=0；i<k；i++）s1+=a[i]; for(i=k；i<n；i++）s2+=a[i]; return s2-s1;
```

【(1)(2)的评分说明】

①本题目只需将最大的一半元素与最小的一半元素分组，不需要对所有元素进行全部排序。参考答案基于快速排序思想，采用非递归的方式实现。若考生设计的算法满足题目的功能要求且正确，则(1)、(2)根据所实现算法的平均时间复杂度给分，细则见下表。

<table><tr><td>时间复杂度</td><td>分数</td><td>说明</td></tr><tr><td>O(n)</td><td>13</td><td>采用类似快速排序思想,没有对元素进行全排序。</td></tr><tr><td>O(nlog2n)</td><td>11</td><td></td></tr><tr><td>\( \mathrm{O}\left( {\mathrm{n}}^{2}\right) \)</td><td>9</td><td></td></tr><tr><td>其他</td><td>7</td><td>时间复杂度高于 \( \mathrm{O}\left( {\mathrm{n}}^{2}\right) \) 的算法。</td></tr></table>

②若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，可参照①的标准给分。

③若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。

④参考答案中只给出了使用C语言的版本，使用C++语言的答案视同使用C语言。

(3)算法的平均时间复杂度和空间复杂度（2分）

本参考答案给出的算法平均时间复杂度是O(n)，空间复杂度是O(1)。

【评分说明】若考生所估计的平均时间复杂度和空间复杂度与考生所实现的算法一致，可各给1分。

# 44.【答案要点】

(1)每传送一个ASCII字符，需要传输的位数有1位起始位、7位数据位(ASCII字符占7位)、1位奇校验位和1位停止位，故总位数为  $1 + 7 + 1 + 1 = 10$  。(2分)

I/O端口每秒钟最多可接收1000/0.5=2000个字符。(1分)

【评分说明】对于第一问，若考生回答总位数为9，则给1分。

(2)一个字符传送时间包括：设备D将字符送I/0端口的时间、中断响应时间和中断服务程序前15条指令的执行时间。时钟周期为  $1 / (50\mathrm{MHz}) = 20$  ns，设备D将字符送I/0端口的时间为0.5 ms/20 ns=2.5×10^4个时钟周期。一个字符的传送时间大约为2.5×10^4+10+15×4=25070个时钟周期。完成1000个字符传送所需时间大约为1000×25070=25070000个时钟周期。(3分)

CPU用于该任务的时间大约为  $1000 \times (10 + 20 \times 4) = 9 \times 10^{4}$  个时钟周期。(1分)

在中断响应阶段, CPU主要进行以下操作: 关中断、保护断点和程序状态、识别中断源。(2分)

# 【评分说明】

①对于第一问，若答案是25070020，则同样给分；若答案是2500000或25000020，则给2分。如果没有给出分步计算步骤，但算式和结果正确，同样给分。  
②对于第三问，只要回答关中断和保护断点，就给2分，其他答案酌情给分。

# 45.【答案要点】

(1)页大小为8KB，页内偏移地址为13位，故A=B=32-13=19；D=13；C=24-13=11；主存块大小为64B，故G=6。2路组相联，每组数据区容量有64B×2=128B，共有64KB/128B=512组，故F=9；E=24-G-F=24-6-9=9。

因而A=19，B=19，C=11，D=13，E=9，F=9，G=6。（各1分，共7分）

TLB中标记字段B的内容是虚页号，表示该TLB项对应哪个虚页的页表项。(1分)

(2)块号4099=0000010000000000011B，因此，所映射的Cache组号为00000011B=3，（1分）对应的H字段内容为00001000B。(1分)  
(3) Cache 缺失带来的开销小，而处理缺页的开销大。(1分)因为缺页处理需要访问磁盘，而 Cache 缺失只要访问主存。(1分)

【评分说明】对于(3)中第2问，若考生回答因为缺页需要软件实现而Cache缺失用硬件实现，则同样给分。

(4)因为采用直写策略时需要同时写快速存储器和慢速存储器，而写磁盘比写主存慢得多，所以，在Cache-主存层次，Cache可以采用直写策略，而在主存-外存(磁盘)层次，修改页面内容时总是采用回写策略。(2分)

# 46.【答案要点】

(1)由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。(2分)

(2)优先数priority的计算公式为：

priority=nice+k1×cpuTime-k2×waitTime，其中k1>0，k2>0，用来分别调整cpuTime和waitTime在priority中所占的比例。(3分)waitTime可使长时间等待的进程优先数减小，从而避免出现饥饿现象。(1分)

# 【评分说明】

① 公式中包含nice给1分，利用cpuTime增大优先数给1分，利用waitTime减少优先数给1分；部分正确，酌情给分。  
②若考生给出包含nice、cpuTime和waitTime的其他合理的优先数计算方法，同样给分。

# 47.【答案要点】

(1)两个目录文件dir和dir1的内容如下表所示。(3分)

dir目录文件

文件名 簇号  

<table><tr><td>dir1</td><td>48</td></tr></table>

dir1目录文件

文件名 簇号  

<table><tr><td>file1</td><td>100</td></tr><tr><td>file2</td><td>200</td></tr></table>

【评分说明】每个目录项的内容正确给1分，共3分。

(2)FAT的最大长度为  $2^{16} \times 2$  B=128 KB。(1分)文件的最大长度是  $2^{16} \times 4$  KB=256 MB。(1分)

【评分说明】若考生考虑到文件结束标志、坏块标志等，且答案正确，同样给分。

(3)file1的簇号106存放在FAT的100号表项中，（1分）簇号108存放在FAT的106号表项中。（1分）

(4)需要访问目录文件dir1所在的48号簇，（1分）及文件file1的106号簇。（1分）