科目组合

数据结构 、计算机组成原理 、操作系统 、计算机网络

已知表头元素为c的单链表在内存中的存储状态如下表所示。现将f存放于1014H处并插入单链表，若f在逻辑上位于a和e之间，则a,e,f的”链表地址“依次是（ ）。

A、1010H，1014H，1004H
B、1010H，1004H，1014H
C、1014H，1010H，1004H
D、1014H，1004H，1010H

已知一个带有表头结点的双向循环链表L,结点结构为prev|data|next，prev和next分别是指向其直接前驱和直接后继结点的指针。现要删除指针p所指的结点，正确的语句序列是（ ）。

A. p->next->prev = p->prev; p->prev->next = p->prev; free(p);

B. p->next->prev = p->next; p->prev->next = p->next; free(p);

C. p->next->prev = p->next; p-> prev->next = p->prev; free(p);

D. p->next->prev = p->prev; p->prev->next = p->next; free(p);

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

A. 2

B. 3

C. 4

D. 5

有一个100阶的三对角矩阵 M ，其元素 mi,j(1≤i≤100,1≤j≤100) 按行优先依次压缩存入下标从0开始的一维数组 N 中。元素 m30,30 在数组 N 中的下标是（ ）。

A. 86

B. 87

C. 88

D. 89

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

A. 8

B. 9

C. 10

D. 11

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

A.V1，V5，V4，V3，V2

B.V1，V3，V2，V5，V4

C.V1，V2，V5，V4，V3

D.V1，V2，V3，V4，V5

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

A.O(n)

B.O(n+e)

C.O(n²)

D.O(n*e)

使用迪杰斯特拉（Djkstra）算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（ ）。

A. 5, 2, 3, 4, 6

B. 5, 2, 3, 6, 4

C. 5, 2, 4, 3, 6

D. 5, 2, 6, 3, 4

在有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不在数组中

B.当x接近数组开头处

C.当x接近数组结尾处

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

B+树不同于B树的特点之一是（）

A. 能支持顺序查找

B. 结点中含有关键字

C. 根结点至少有两个分支

D. 所有叶结点都在同一层上

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

A. 希尔排序

B. 堆排序

C. 快速排序

D. 归并排序

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

A. 汇编程序

B. 链接程序

C. 编译程序

D. 解释程序

有如下C语言程序段

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

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

A. -32767

B. 32767

C. 32768

D. 32769

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

A. 22H

B. 33H

C. 66H

D. 77H

有如下 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%

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

A. 7

B. 8

C. 14

D. 16

某指令格式如下所示。

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

A. I+D

B. (I)+D

C. ((I)+D)

D. ((I))+D

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

A. 30、30

B. 30、32

C. 32、30

D. 32、32

在无转发机制的五段基本流水线中，下列指令序列存在数据冒险的指令对是（ ）。

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

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

A. 可以采用单总线结构数据通路

B. 处理器时钟频率较低

C. 在指令执行过程中控制信号不变

D. 每条指令的CPI为1

下列关干单周期处理器的叙述中，错误的是（ ）。

A. 并行总线传输比串行总线传输速度快

B. 采用信号线复用技术可减少信号线数量

C. 采用突发传输方式可提高总线数据传输率

D. 采用分离事务通信方式可提高总线利用率

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

A. “访存时缺页”属于中断

B. “整数除以0”属于异常

C. “DMA传送结束”属于中断

D. “存储保护错”属于异常

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

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

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

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

A.仅Ⅱ、Ⅲ            B. 仅Ⅱ

C. 仅Ⅰ、Ⅱ           D. 仅Ⅰ、Ⅲ

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

A、15ms

B、17ms

C、22ms

D、27ms

系统中有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

某系统采用改进型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)

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

do {
    ...
    while (TSL(&lock));
    critical section;
    lock = FALSE;
    ...
} while (TRUE);

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

A. 退出临界区的进程负责唤醒阻塞态进程

B. 等待进入临界区的进程不会主动放弃CPU

C. 上述伪代码满足“让权等待”的同步准则

D. while (TSL(&lock)) 应在关中断状态下执行

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

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

A. 段缺失异常

B. 得到内存地址4400

C. 越权异常

D. 越界异常

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

若工作集的窗口大小为6，则在t时刻的工作集为（ ）。

A. {6, 0, 3, 2}

B. {2, 3, 0, 4}

C. {0, 4, 3, 2, 9}

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

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

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

A. a=1与a=2

B. a=x与b=x

C. x+=1与x+=2

D. x+=1与x+=3

下列关于SPOOLing技术的叙述中，错误的是（ ）。

A. 需要外存的支持

B. 需要多道程序设计技术的支持

C. 可以让多个作业共享一台独占设备

D. 由用户作业控制设备与输入/输出井之间的数据传送

下列关于管程的叙述中，错误的是（ ）。

A. 管程只能用于实现进程的互斥

B. 管程是由编程语言支持的进程同步机制

C. 任何时候只能有一个进程在管程中执行

D. 管程中定义的变量只能被管程内的过程访问

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

A. 2、2、1

B. 2、2、2

C. 3、2、1

D. 3、2、2

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

A. 8 kbps

B. 20 kbps

C. 40 kbps

D. 80 kbps

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

A. 仅H2

B. 仅H3

C. 仅H1、H2

D. 仅H2、H3

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

A. 200 m

B. 205 m

C. 359 m

D. 512 m

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

A. 2

B. 3

C. 16

D. 17

假设连接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

假设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通信

假设所有域名服务器均采用迭代查询方式进行域名解析。当H4访问规范域名为 www.abc.xyz.com 的网站时，域名服务器201.1.1.1在完成该域名解析过程中，可能发出DNS查询的最少和最多次数分别是（ ）。

A. 0，3

B. 1，3

C. 0，4

D. 1，4

假设题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释放该连接的最短时间是多少？

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

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

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

已知由 n(n≥2) 个正整数构成的集合 A={ak|0≤k<n} ，将其划分为两个不相交的子集 A1 和 A2 ，元素个数分别是 n1 和 n2 ， A1 和 A2 中元素之和分别为 S1 和 S2 。设计一个尽可能高效的划分算法，满足 |n1−n2| 最小且 |S1−S2| 最大。要求：

⑴ 给出算法的基本设计思想。

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

⑶ 说明你所设计算法的时间复杂度和空间复杂度。

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

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

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

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

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

请回答下列问题。

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

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

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

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

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

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

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

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

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

(2) 若FAT的每个表项仅存放簇号，占2个字节，则FAT的最大长度为多少字节？该文件系统支持的文件长度最大是多少？

(3) 系统通过目录文件和FAT实现对文件的按名存取，说明file1的106、108两个簇号分别存放在FAT的哪个表项中。

(4) 假设仅FAT和dir目录文件已读入内存，若需将文件dir/dir1/file1的第5000个字节读入内存，则要访问哪几个簇？