2016 整卷 · 四〇八档案室

BOK 数据结构

数据结构

2016-01

选择题2 分

已知表头元素为 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

单题查看 1

BOK 数据结构

数据结构

2016-02

选择题2 分

已知一个带有表头结点的双向循环链表 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);

单题查看 2

BOK 数据结构

数据结构

2016-03

选择题2 分

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

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

单题查看 3

BOK 数据结构

数据结构

2016-04

选择题2 分

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

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

单题查看 4

BOK 数据结构

数据结构

2016-05

选择题2 分

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

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

单题查看 5

BOK 数据结构

数据结构

2016-06

选择题2 分

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

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$

单题查看 6

BOK 数据结构

数据结构

2016-07

选择题2 分

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

A. O(n)
B. O(n+e)
C. O(n^2)
D. O(ne)

单题查看 7

BOK 数据结构

数据结构

2016-08

选择题2 分

使用迪杰斯特拉（Dijkstra）算法求下图中从顶点 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

单题查看 8

BOK 数据结构

数据结构

2016-09

选择题2 分

在有 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 位于数组中间位置

单题查看 9

BOK 数据结构

数据结构

2016-10

选择题2 分

B+树不同于 B 树的特点之一是__。

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

单题查看 10

BOK 数据结构

数据结构

2016-11

选择题2 分

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

A. 希尔排序
B. 堆排序
C. 快速排序
D. 归并排序

单题查看 11

BOK 组成原理

组成原理

2016-12

选择题2 分

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

A. 汇编程序
B. 链接程序
C. 编译程序
D. 解释程序

单题查看 12

BOK 组成原理

组成原理

2016-13

选择题2 分

有如下 C 语言程序段
short si = -32767;
unsigned short usi = si;
执行上述两条语句后，usi 的值为__。

A. -32767
B. 32767
C. 32768
D. 32769

单题查看 13

BOK 组成原理

组成原理

2016-14

选择题2 分

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

A. 22H
B. 33H
C. 77H
D. 66H

单题查看 14

BOK 组成原理

组成原理

2016-15

选择题2 分

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

单题查看 15

BOK 组成原理

组成原理

2016-16

选择题2 分

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

A. 7
B. 8
C. 14
D. 16

单题查看 16

BOK 组成原理

组成原理

2016-17

选择题2 分

某指令格式如下所示。

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

A. I+D
B. (I)+D
C. ((I)+D)
D. ((I))+D

单题查看 17

BOK 组成原理

组成原理

2016-18

选择题2 分

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

A. 30、30
B. 30、32
C. 32、30
D. 32、32

单题查看 18

BOK 组成原理

组成原理

2016-19

选择题2 分

在无转发机制的五段基本流水线（取指、译码/读寄存器、运算、访存、写回寄存器）中，下列指令序列存在数据冒险的指令对是__。
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

单题查看 19

BOK 组成原理

组成原理

2016-20

选择题2 分

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

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

单题查看 20

BOK 组成原理

组成原理

2016-21

选择题2 分

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

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

单题查看 21

BOK 组成原理

组成原理

2016-22

选择题2 分

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

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

单题查看 22

BOK 操作系统

操作系统

2016-23

选择题2 分

下列关于批处理系统的叙述中，正确的是_。
I. 批处理系统允许多个用户与计算机直接交互
II. 批处理系统分为单道批处理系统和多道批处理系统
III. 中断技术使得多道批处理系统和I/O设备可与CPU并行工作

A. 仅 II、III
B. 仅 II
C. 仅 I、II
D. 仅 I、III

单题查看 23

BOK 操作系统

操作系统

2016-24

选择题2 分

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

A. 15ms
B. 17ms
C. 22ms
D. 27ms

单题查看 24

BOK 操作系统

操作系统

2016-25

选择题2 分

系统中有3个不同的临界资源R₁、R₂和R₃，被4个进程p₁、p₂、p₃及p₄共享。各进程对资源的需求为：p₁申请R₁和R₂，p₂申请R₂和R₃，p₃申请R₁和R₃，p₄申请R₂。若系统出现死锁，则处于死锁状态的进程数至少是_。

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

单题查看 25

BOK 操作系统

操作系统

2016-26

选择题2 分

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

单题查看 26

BOK 操作系统

操作系统

2016-27

选择题2 分

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

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

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

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

单题查看 27

BOK 操作系统

操作系统

2016-28

选择题2 分

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

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

A. 段缺失异常
B. 得到内存地址4400
C. 越权异常
D. 越界异常

单题查看 28

BOK 操作系统

操作系统

2016-29

选择题2 分

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

…,1,3,4,5,6,0,3,2,3,2,4,0,4,0,3,2,9,2,1,…
若工作集的窗口大小为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}

单题查看 29

BOK 操作系统

操作系统

2016-30

选择题2 分

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

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

A. a=1 与 a=2
B. a=x 与 b=x
C. x += 1 与 x += 2
D. x += 1 与 x += 3

单题查看 30

BOK 操作系统

操作系统

2016-31

选择题2 分

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

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

单题查看 31

BOK 操作系统

操作系统

2016-32

选择题2 分

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

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

单题查看 32

BOK 计算机网络

计算机网络

2016-33

选择题2 分

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

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

单题查看 33

BOK 计算机网络

计算机网络

2016-34

选择题2 分

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

A. 8kbps
B. 20kbps
C. 40kbps
D. 80kbps

单题查看 34

BOK 计算机网络

计算机网络

2016-35

选择题2 分

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

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

单题查看 35

BOK 计算机网络

计算机网络

2016-36

选择题2 分

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

A. 200m
B. 205m
C. 359m
D. 512m

单题查看 36

BOK 计算机网络

计算机网络

2016-37

选择题2 分

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

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

单题查看 37

BOK 计算机网络

计算机网络

2016-38

选择题2 分

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

单题查看 38

BOK 计算机网络

计算机网络

2016-39

选择题2 分

若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通信

单题查看 39

BOK 计算机网络

计算机网络

2016-40

选择题2 分

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

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

单题查看 40

BOK 计算机网络

计算机网络

2016-41

综合题9 分

假设题 33～41 图中的 H3 访问 Web 服务器 S 时，S 为新建的 TCP 连接分配了 20KB（K = 1024）的接收缓存，最大段长 MSS = 1KB，平均往返时间 RTT = 200ms。H3 建立连接时的初始序号为 100，且持续以 MSS 大小的段向 S 发送数据，拥塞窗口初始阈值为 32KB；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 释放该连接的最短时间是多少？

单题查看 41

BOK 数据结构

数据结构

2016-42

综合题8 分

如果一棵非空 k（k≥2）叉树 T 中每个非叶结点都有 k 个孩子，则称 T 为正则 k 叉树。请回答下列问题并给出推导过程。
（1）若 T 有 m 个非叶结点，则 T 中的叶结点有多少个？
（2）若 T 的高度为 h（单结点的树 h = 1），则 T 的结点数最多为多少个？最少为多少个？

单题查看 42

BOK 数据结构

数据结构

2016-43

综合题15 分

已知由 $n$ （ $n\geq2$ ）个正整数构成的集合 $A=akmid 0≤ 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）说明你所设计算法的平均时间复杂度和空间复杂度。

答案

（1）算法基本设计思想
要使两个子集元素个数差最小且和的差最大，应将最小的⌊n/2⌋个元素放入A₁，其余放入A₂。采用快速排序中的划分思想，基于枢轴进行划分，通过非递归方式逐步将数组划分为两部分，使得左半部分恰好包含最小的⌊n/2⌋个元素，右半部分包含剩余元素。最后分别计算两部分的和并返回其差值。

（2）算法描述（C语言）

int setPartition(int a[], int n) {
    int pivokey = 0, low = 0, low0 = 0, high = n - 1, high0 = n - 1, flag = 1, k = n / 2, i;
    int s1 = 0, s2 = 0;
    while(flag) {
        pivokey = a[low]; // 选择枢纽
        while(low < high) {
            while(low < high && a[high] >= pivokey) --high;
            if(low != high) a[low] = a[high]; // 替换较大的数
            while(low < high && a[low] <= pivokey) ++low;
            if(low != high) a[high] = a[low]; // 替换较小的数
        }
        a[low] = pivokey; // 完成交换枢纽
        if(low == k - 1) {
            flag = 0;
        } else {
            if(low < k - 1) {
                low0 = ++low;
                high = high0;
            } else {
                high0 = --high;
                low = low0;
            }
        }
    }
    for(i = 0; i < k; i++) s1 += a[i];
    for(i = k; i < n; i++) s2 += a[i];
    return s2 - s1;
}

（3）时间复杂度与空间复杂度

平均时间复杂度：O(n)，期望线性时间完成划分。
空间复杂度：O(1)，仅使用常数额外空间。

单题查看 43

BOK 组成原理

组成原理

2016-44

综合题9 分

假定 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 进行了哪些操作？

单题查看 44

BOK 组成原理

组成原理

2016-45

综合题14 分

某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为 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）策略。

单题查看 45

BOK 操作系统

操作系统

2016-46

综合题6 分

某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1。请回答下列问题。
（1）若调度程序只将nice的值作为进程的优先数，即priority = nice，则可能会出现饥饿现象，为什么？
（2）使用nice、cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用。

单题查看 46

BOK 操作系统

操作系统

2016-47

综合题9 分

某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。
（1）假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中dir、dir1是目录，file1、file2是用户文件。请给出所有目录文件的内容。
（2）若FAT的每个表项仅存放簇号，占2字节，则FAT的最大长度为多少字节？该文件系统支持的文件长度最大是多少？
（3）系统通过目录文件和FAT实现对文件的按名存取，说明file1的106、108两个簇号分别存放在FAT的哪个表项中。
（4）假设仅FAT和dir目录文件已读入内存，若需将文件dir/dir1/file的第5000个字节读入内存，则要访问哪几个簇？

单题查看 47

计算机学科专业基础2016 真题档案