2016 年计算机学科专业基础综合全国联考卷

                     

贡献者： xzllxls

1. 一、单项选择题

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

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

　　 现将 f 存放于 1014H 处并插入到单链表中，若 f 在逻辑上位于 a 和 e 之间，则 a，e，f 的 “链接地址” 依次是
A。1010H，1014H，1004H $\qquad$ B。1010H，1004H，1014H
C。1014H，1010H，1004H $\qquad$ D。1014H，1004H，1010H

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

　　 其中，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 至少是

　　 A. 2 $\qquad$ B。3 $\qquad$ C。4 $\qquad$ D。5

　　 4。有一个 $100$ 阶的三对角矩阵 $M$，其元素 $m_{i,j}$($1$≤$i$≤$100$,$1$≤$j$≤$100$)按行优先次序压缩存入下标从 $0$ 开始的一维数组Ⅳ中。元素 $m_{30}$,$30$ 在 $N$ 中的下标是
A.86 $\qquad$ B。87 $\qquad$ C。88 $\qquad$ D。89

　　 5。若森林 F 有 15 条边、25 个结点，则 F 包含树的个数是
A。8 $\qquad$ B。9 $\qquad$ C。10 $\qquad$ D。11

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

　　 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。$O(n)$ $\qquad$ B。$O(n+e)$ $\qquad$ C。$O(n^2)$ $\qquad$ D。$O(n\times e)$

　　 8。使用迪杰斯特拉（Dijkstra）算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是
A。5，2，3，4，6 $\qquad$ B。5，2，3，6，4
C。5，2，4，3，6 $\qquad$ D。5，2，6，3，4

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

k=0;
while(k<n且A[k]<x)k=k+3；
if(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。当 x 不在数组中 $\qquad$ B。当 x 接近数组开头处
C。当 x 接近数组结尾处 $\qquad$ D。当 x 位于数组中间位置

　　 10。$B^+$ 树不同于 B 树的特点之一是
A。能支持顺序查找
B。结点中含有关键字
C。根结点至少有两个分支
D。所有叶结点都在同一层上

　　 11。对 10TB 的数据文件进行排序，应使用的方法是
A。希尔排序 $\qquad$ B。堆排序
C。快速排序 $\qquad$ D。归并排序

　　 12。将高级语言源程序转换为机器级目标代码文件的程序是
A。汇编程序 $\qquad$ B。链接程序
C。编译程序 $\qquad$ D。解释程序

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

short si=-32767;
unsigned short usi=si;

执行上述两条语句后，usi 的值为 A。-32767 $\qquad$ B。32767 $\qquad$ C。32768 $\qquad$ D。32769

　　 14。某计算机字长为 32 位，按字节编址，采用小端（Little Endian）方式存放数据。假定有一个 double 型变量，其机器数表示为 1122 3344 5566 7788H，存放在 0000 8040H 开始的连续存储单元中，则存储单元 0000 8046H 中存放的是
A。22H $\qquad$ B。33H $\qquad$ C。66H $\qquad$ D。77H

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

for(k=0；k<1000；k++)
  a[k]=a[k]+32；

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

　　 16。某存储器容量为 64 KB，按字节编址，地址 4000H～5FFFH 为 ROM 区，其余为 RAM 区。若采用 8 K×4 位的 SRAM 芯片进行设计，则需要该芯片的数量是
A。7 $\qquad$ B。8 $\qquad$ C。14 $\qquad$ D。16

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

　　 其中 M 为寻址方式，I 为变址寄存器编号，D 为形式地址。若采用先变址后间址的寻址方式，则操作数的有效地址是
A。I+D $\qquad$ B。(I)+D $\qquad$ C。((I)+D) $\qquad$ D。((I))+D

　　 18。某计算机主存空间为 4 GB，字长为 32 位，按字节编址，采用 32 位定长指令字格式。若指令按字边界对齐存放，则程序计数器(PC)和指令寄存器(IR)的位数至少分别是
A。30、30 $\qquad$ B。30、32 $\qquad$ C。32、30 $\qquad$ 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。I1 和 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/O 设备可与 CPU 并行工作
A。仅Ⅱ、Ⅲ B。仅Ⅱ C。仅Ⅰ、Ⅱ D。仅Ⅰ、Ⅲ

　　 24。某单 CPU 系统中有输入和输出设备各 1 台，现有 3 个并发执行的作业，每个作业的输入、计算和输出时间均分别为 2 ms、3 ms 和 4 ms，且都按输入、计算和输出的顺序执行，则执行完 3 个作业需要的时间最少是
A。15 ms $\qquad$ B。17 ms $\qquad$ C。22 ms $\qquad$ D。27 ms

　　 25。系统中有 3 个不同的临界资源 R1、R2 和 R3，被 4 个进程 p1、p2、p3 及 p4 共享。各进程对资源的需求为：p1 申请 R1 和 R2，p2 申请 R2 和 R3，p3 申请 R1 和 R3，p4 申请 R2。若系统出现死锁，则处于死锁状态的进程数至少是
A。1 $\qquad$ B。2 $\qquad$ C。3 $\qquad$ 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=FALSE;
  ……
} while(TRUE);

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

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

　　 当访问段号为 2、段内地址为 400 的逻辑地址时，进行地址转换的结果是
A。段缺失异常 $\qquad$ B。得到内存地址 4400
C。越权异常 $\qquad$ D。越界异常

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

　　 若工作集的窗口大小为 6，则在￡时刻的工作集为
A。{6，0，3，2} $\qquad$ B。{2，3，0，4} c。{0，4，3，2，9} $\qquad$ D。{4，5，6，0，3，2}

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

//进程P1
  int x=0：
  Thread1( )
  { int a：
    a=1； x+=1；
  }
  Thread2( )
  { int a：
    a=2；x+=2；
  }

//进程P2
  int x=0：
  Thread3( )
  { int a；
    a=x； x+=3；
  }
  Thread4( )
  { int b；
    b=x；x+=4；
  }

下列选项中，需要互斥执行的操作是
A。a=1 与 a=2 $\qquad$ B。a=x 与 b=x
c。x+=1 与 x+=2 $\qquad$ 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 $\qquad$ B。2、2、2 $\qquad$ C。3、2、1 $\qquad$ D。3、2、2

　　 34。若连接 R2 和 R3 链路的频率带宽为 8 kHz，信噪比为 30 dB，该链路实际数据传输速率约为理论最大数据传输速率的 50％，则该链路的实际数据传输速率约是
A。8 kbps $\qquad$ B。20 kbps $\qquad$ C。40 kbps $\qquad$ D。80 kbps

　　 35。若主机 H2 向主机 H4 发送 1 个数据帧，主机 H4 向主机 H2 立即发送一个确认帧，则除 H4 外，从物理层上能够收到该确认帧的主机还有
A。仅 H2 $\qquad$ B。仅 H3 $\qquad$ C。仅 H1、H2 $\qquad$ D。仅 H2、H3

　　 36。若 Hub 再生比特流过程中，会产生 1.535μs 延时，信号传播速度为 200 m/μs，不考虑以太网帧的前导码，则 H3 与 H4 之间理论上可以相距的最远距离是
A。200 m $\qquad$ B。205 m $\qquad$ C。359 m $\qquad$ D。512 m

　　 37。假设 R1、R2、R3 采用 RIP 协议交换路由信息，且均已收敛。若 R3 检测到网络 201.1。2.0/25 不可达，并向 R2 通告一次新的距离向量，则 R2 更新后，其到达该网络的距离是
A。2 $\qquad$ B。3 $\qquad$ C。16 $\qquad$ 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 $\qquad$ B。192.168.3。251，201.1。3.9
C。201.1。3.8，130.18.10.1 $\qquad$ 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 $\qquad$ B。1，3 $\qquad$ C。0，4 $\qquad$ D。1，4

2. 二、综合应用题

　　 41～47 小题，共 70 分。

　　 41。(9 分)假设题 33～41 图中的 H3 访问 Web 服务器 S 时，S 为新建的 TCP 连接分配了 20 KB(K=1 024)的接收缓存，最大段长 MSS=1 KB，平均往返时间 RTT=200 ms。H3 建立连接时的初始序号为 100，且持续以 MSS 大小的段向 S 发送数据，拥塞窗口初始阈值为 32 KB；S 对收到的每个段进行确认，并通告新的接收窗口。假定 TCP 连接建立完成后，S 端的 TCP 接收缓存仅有数据存入而无数据取出。请回答下列问题。
(1)在 TCP 连接建立过程中，H3 收到的 S 发送过来的第二次握手 TCP 段的 SYN 和 ACK 标志位的值分别是多少？确认序号是多少？
(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 \geqslant 2)$ 个正整数构成的集合 $A=\{a_k|0\leqslant 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 主频为 50 MHz，CPI 为 4。设备 D 采用异步串行通信方式向主机传送 7 位 ASCII 字符，通信规程中有 1 位奇校验位和 1 位停止位，从 D 接收启动命令到字符送入 I/O 端口需要 0.5 ms。请回答下列问题，要求说明理由。
(1)每传送一个字符，在异步串行通信线上共需传输多少位？在设备 D 持续工作过程中，每秒钟最多可向 I/0 端口送入多少个字符？
(2)设备 D 采用中断方式进行输入/输出，示意图如下：

　　 请回答下列问题。
(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 分)某磁盘文件系统使用链接分配方式组织文件，簇大小为 4 KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表 FAT 中。
(1)假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中 dir、dir1 是目录，file1、file2 是用户文件。请给出所有目录文件的内容。

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

3. 参考答案

一、单项选择题

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

二、综合应用题

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

　　 42。【答案要点】
(1)根据定义，正则 $k$ 叉树中仅含有两类结点：叶结点（个数记为 $n_0$）和度为 $k$ 的分支结点（个数记为 $n_k$）。树 $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\leqslant j\leqslant h$)层结点数为 $k^{j-1}$，结点总数 $M_1$ 为：

含最少结点的正则 $k$ 叉树的树形为：第 $1$ 层只有根结点，第 $2$ 到第 $h-1$ 层仅含 $1$ 个分支结点和 $k-1$ 个叶结点，第 $h$ 层有 $k$ 个叶结点。即除根外第 $2$ 到第 $h$ 层中每层的结点数均为 $k$，故 $T$ 中所含结点总数 $M_2$ 为：
【评分说明】
①参考答案仅给出一种推导过程，若考生采用其他推导方法且正确，同样给分。
②若考生仅给出结果，但没有推导过程，则(1)、(2)的最高得分分别是 2 分和 3 分。若推导过程或答案不完全正确，酌情给分。

　　 43.【答案要点】
(1)算法的基本设计思想（4 分）
$\qquad$ 由题意知，将最小的 n/2 个元素放在 $A_1$ 中，其余的元素放在 $A_2$ 中，分组结果即可满足题目要求。仿照快速排序的思想，基于枢轴将 $n$ 个整数划分为两个子集。根据划分后枢轴所处的位置 $i$ 分别处理：
①若 $i= \lfloor n/2 \rfloor$，则分组完成，算法结束；
②若 $i< \lfloor n/2 \rfloor $，则枢轴及之前的所有元素均属于 $A_1$，继续对 $i$ 之后的元素进行划分；
③若 $i> \lfloor n/2 \rfloor$，则枢轴及之后的所有元素均属于 $A_2$，继续对 $i$ 之前的元素进行划分；
$\qquad$ 基于该设计思想实现的算法，毋须对全部元素进行全排序，其平均时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。 $\qquad$ (2)算法实现（9 分）

int setPartition(int a[ ], int n)
{ 
  int pivotkey，low=0，low0=0，high=n-l，high0=n-1，flag=1，k=n/2，i;
  int s1=0，s2=0;
  while(flag)
  { pivotkey=a[low]； //选择枢轴
    while(low<high) //基于枢轴对数据进行划分
    { while(low<high && a[high]>=pivotkey)
        --high;
      if(low!=high)
        a[low]=a[high];
      while(low<high && a[low]<=pivotkey)
        ++low;
      if(low!=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=++low;
        high=high0;
      }
      else
      { high0=--m high;
        low=low0；
      }
    }
  }
for(i=0; i<k; i++)
  s1+=a[i];
for(i=k; i<n; i++)
  s2+=a[i];
return s2-s1;
}

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

　　 ②若在算法的基本设计思想描述中因文字表达没有清晰反映出算法思路，但在算法实现中能够表达出算法思想且正确的，可参照①的标准给分。 ③若算法的基本设计思想描述或算法实现中部分正确，可参照①中各种情况的相应给分标准酌情给分。 ④参考答案中只给出了使用 C 语言的版本，使用 C++语言的答案视同使用 C 语言。
$\qquad$ (3)算法的平均时间复杂度和空间复杂度（2 分） 本参考答案给出的算法平均时间复杂度是 $O(n)$，空间复杂度是 $O(1)$。
$\qquad$【评分说明】若考生所估计的平均时间复杂度和空间复杂度与考生所实现的算法一致，可各给 1 分。

　　 44.【答案要点】
$\qquad$ (1)每传送一个 ASCⅡ字符，需要传输的位数有 1 位起始位、7 位数据位（ASCⅡ字符占 7 位）、1 位奇校验位和 1 位停止位，故总位数为 1+7+1+1=10。(2 分)
I/O 端口每秒钟最多可接收 1000/0.5=2000 个字符。(1 分)
$\qquad$【评分说明】对于第一问，若考生回答总位数为 9，则给 1 分。
$\qquad$ (2)一个字符传送时间包括：设备 D 将字符送 I/0 端口的时间、中断响应时间和中断服务程序前 15 条指令的执行时间。时钟周期为 1/(50 MHz)=20 ns，设备 D 将字符送 I/0 端口的时间为 0.5 ms/20 ns=2.5×104 个时钟周期。一个字符的传送时间大约为 2.5×104+10+15×4=25070 个时钟周期。完成 1000 个字符传送所需时间大约为 1000×25070=25070000 个时钟周期。(3 分)
$\qquad$ CPU 用于该任务的时间大约为 1000×(10+20×4)=9×104 个时钟周期。(1 分)
$\qquad$ 在中断响应阶段，CPU 主要进行以下操作：关中断、保护断点和程序状态、识别中断源。(2 分)
$\qquad$【评分说明】①对于第一问，若答案是 25070020，则同样给分；若答案是 25000000 或 25000020，则给 2 分。如果没有给出分步计算步骤，但算式和结果正确，同样给分。 ②对于第三问，只要回答关中断和保护断点，就给 2 分，其他答案酌情给分。

　　 45。【答案要点】
$\qquad$ (1)页大小为 8 KB，页内偏移地址为 13 位，故 A=B=32-13=19；D=13；C=24-13=11；主存块大小为 64 B，故 G=6。2 路组相联，每组数据区容量有 64 B×2=128 B，共有 64 KB/128 B=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 分)
$\qquad$ (2)块号 4099=00 0001 0000 0000 0011B，因此，所映射的 Cache 组号为 0 0000 0011B=3，(1 分)对应的 H 字段内容为 0 0000 1000B。(1 分) $\qquad$ (3)Cache 缺失带来的开销小，而处理缺页的开销大。(1 分)因为缺页处理需要访问磁盘，而 Cache 缺失只要访问主存。(1 分)
$\qquad$【评分说明】对于(3)中第 2 问，若考生回答因为缺页需要软件实现而 Cache 缺失用硬件实现，则同样给分。 $\qquad$ (4)因为采用直写策略时需要同时写快速存储器和慢速存储器，而写磁盘比写主存慢得多，所以，在 Cache-主存层次，Cache 可以采用直写策略，而在主存-外存（磁盘）层次，修改页面内容时总是采用回写策略。(2 分)

　　 46。【答案要点】
$\qquad$ (1)由于采用了静态优先数，当就绪队列中总有优先数较小的进程时，优先数较大的进程一直没有机会运行，因而会出现饥饿现象。(2 分)
$\qquad$ (2)优先数 priority 的计算公式为： priority=nice+k1×cpuTime-k2×waitTime，其中 k1>0，k2>0，用来分别调整 cpuTime 和 waitTime 在 priority 中所占的比例。(3 分)waitTime 可使长时间等待的进程优先数减小，从而避免出现饥饿现象。(1 分)
$\qquad$【评分说明】①公式中包含 nice 给 1 分，利用 cpuTime 增大优先数给 1 分，利用 waitTime 减少优先数给 1 分；部分正确，酌情给分。 ②若考生给出包含 nice、cpuTime 和 waitTime 的其他合理的优先数计算方法，同样给分。

　　 47。【答案要点】
$\qquad$ (1)两个目录文件 dir 和 dir1 的内容如下表所示。(3 分)

　　 【评分说明】每个目录项的内容正确给 1 分，共 3 分。
$\qquad$ (2)FAT 的最大长度为 216×2 B=128 KB。(1 分)文件的最大长度是 216×4 KB=256 MB。(1 分)
【评分说明】若考生考虑到文件结束标志、坏块标志等，且答案正确，同样给分。
$\qquad$ (3) file1 的簇号 106 存放在 FAT 的 100 号表项中，(1 分)簇号 108 存放在 FAT 的 106 号表项中。(1 分)
$\qquad$ (4)需要访问目录文件 dir1 所在的 48 号簇，(1 分)及文件 file1 的 106 号簇。(1 分)