2011 整卷 · 四〇八档案室

BOK 数据结构

数据结构

2011-01

选择题2 分

设n是描述问题规模的非负整数，下面程序片段的时间复杂度是。

x = 2;
while (x < n / 2)
    x = 2 * x;

A. O(log₂n)
B. O(n)
C. O(nlog₂n)
D. O(n²)

单题查看 1

BOK 数据结构

数据结构

2011-02

选择题2 分

元素a, b, c, d, e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是。

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

单题查看 2

BOK 数据结构

数据结构

2011-03

选择题2 分

已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是。

A. 0, 0
B. 0, n-1
C. n-1, 0
D. n-1, n-1

单题查看 3

BOK 数据结构

数据结构

2011-04

选择题2 分

若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是。

A. 257
B. 258
C. 384
D. 385

单题查看 4

BOK 数据结构

数据结构

2011-05

选择题2 分

若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是。

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

单题查看 5

BOK 数据结构

数据结构

2011-06

选择题2 分

已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是。

A. 115
B. 116
C. 1895
D. 1896

单题查看 6

BOK 数据结构

数据结构

2011-07

选择题2 分

对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是。

A. 95, 22, 91, 24, 94, 71
B. 92, 20, 91, 34, 88, 35
C. 21, 89, 77, 29, 36, 38
D. 12, 25, 71, 68, 33, 34

单题查看 7

BOK 数据结构

数据结构

2011-08

选择题2 分

下列关于图的叙述中，正确的是。
Ⅰ. 回路是简单路径
Ⅱ. 存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ. 若有向图中存在拓扑序列，则该图不存在回路

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

单题查看 8

BOK 数据结构

数据结构

2011-09

选择题2 分

为提高散列（Hash）表的查找效率，可以采取的正确措施是。

Ⅰ. 增大装填（载）因子

Ⅱ. 设计冲突（碰撞）少的散列函数

Ⅲ. 处理冲突（碰撞）时避免产生聚集（堆积）现象

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

单题查看 9

BOK 数据结构

数据结构

2011-10

选择题2 分

为实现快速排序算法，待排序序列宜采用的存储方式是__。

A. 顺序存储
B. 散列存储
C. 链式存储
D. 索引存储

单题查看 10

BOK 数据结构

数据结构

2011-11

选择题2 分

已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是__。

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

单题查看 11

BOK 组成原理

组成原理

2011-12

选择题2 分

下列选项中，描述浮点数操作速度指标的是__。

A. MIPS
B. CPI
C. IPC
D. MFLOPS

单题查看 12

BOK 组成原理

组成原理

2011-13

选择题2 分

float型数据通常用IEEE 754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FR1中，且x=-8.25，则FR1的内容是__。

A. C104 0000H
B. C242 0000H
C. C184 0000H
D. C1C2 0000H

单题查看 13

BOK 组成原理

组成原理

2011-14

选择题2 分

下列各类存储器中，不采用随机存取方式的是__。

A. EPROM
B. CDROM
C. DRAM
D. SRAM

单题查看 14

BOK 组成原理

组成原理

2011-15

选择题2 分

某计算机存储器按字节编址，主存地址空间大小为64MB，现用4MB×8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是__。

A. 22位
B. 23位
C. 25位
D. 26位

单题查看 15

BOK 组成原理

组成原理

2011-16

选择题2 分

偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是__。

A. 间接寻址
B. 基址寻址
C. 相对寻址
D. 变址寻址

单题查看 16

BOK 组成原理

组成原理

2011-17

选择题2 分

某机器有一个标志寄存器，其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt（无符号整数比较大于时转移）的转移条件是__。

A. $CF +OF=1$
B. $SF +ZF=1$
C. $CF+ZF =1$
D. $CF +SF=1$

单题查看 17

BOK 组成原理

组成原理

2011-18

选择题2 分

下列给出的指令系统特点中，有利于实现指令流水线的是__。
Ⅰ.指令格式规整且长度一致
Ⅱ.指令和数据按边界对齐存放
Ⅲ.只有Load/Store指令才能对操作数进行存储访问

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

单题查看 18

BOK 组成原理

组成原理

2011-19

选择题2 分

假定不采用Cache和指令预取技术，且机器处于“开中断”状态。在下列有关指令执行的叙述中，错误的是__。

A. 每个指令周期中CPU都至少访问内存一次
B. 每个指令周期一定大于等于一个CPU时钟周期
C. 空操作指令的指令周期中任何寄存器的内容都不会被改变
D. 当前程序在每条指令执行结束时都可能被外部中断打断

单题查看 19

BOK 组成原理

组成原理

2011-20

选择题2 分

在系统总线的数据线上，不可能传输的是__。

A. 指令
B. 操作数
C. 握手（应答）信号
D. 中断类型号

单题查看 20

BOK 组成原理

组成原理

2011-21

选择题2 分

某计算机有五级中断L₄～L₀，中断屏蔽字为M₄M₃M₂M₁M₀，Mᵢ=1（0⩽i⩽4）表示对Lᵢ级中断进行屏蔽。若中断响应优先级从高到低的顺序是L₄→L₀→L₂→L₁→L₃，则L₁的中断处理程序中设置的中断屏蔽字是__。

A. 11110
B. 01101
C. 00011
D. 01010

单题查看 21

BOK 组成原理

组成原理

2011-22

选择题2 分

某计算机处理器主频为50MHz，采用定时查询方式控制设备A的I/O，查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是__。

A. 0.02%
B. 0.05%
C. 0.20%
D. 0.50%

单题查看 22

BOK 操作系统

操作系统

2011-23

选择题2 分

下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是__。

A. 先来先服务
B. 高响应比优先
C. 时间片轮转
D. 非抢占式短任务优先

单题查看 23

BOK 操作系统

操作系统

2011-24

选择题2 分

下列选项中，在用户态执行的是__。

A. 命令解释程序
B. 缺页处理程序
C. 进程调度程序
D. 时钟中断处理程序

单题查看 24

BOK 操作系统

操作系统

2011-25

选择题2 分

在支持多线程的系统中，进程P创建的若干线程不能共享的是__。

A. 进程P的代码段
B. 进程P中打开的文件
C. 进程P的全局变量
D. 进程P中某线程的栈指针

单题查看 25

BOK 操作系统

操作系统

2011-26

选择题2 分

用户程序发出磁盘I/O请求后，系统的正确处理流程是__。

A. 用户程序→系统调用处理程序→中断处理程序→设备驱动程序
B. 用户程序→系统调用处理程序→设备驱动程序→中断处理程序
C. 用户程序→设备驱动程序→系统调用处理程序→中断处理程序
D. 用户程序→设备驱动程序→中断处理程序→系统调用处理程序

单题查看 26

BOK 操作系统

操作系统

2011-27

选择题2 分

某时刻进程的资源使用情况如下表所示。此时的安全序列是__。

A. P1, P2, P3, P4
B. P1, P3, P2, P4
C. P1, P4, P3, P2
D. 不存在的

单题查看 27

BOK 操作系统

操作系统

2011-28

选择题2 分

在缺页处理过程中，操作系统执行的操作可能是__。
I. 修改页表 II. 磁盘I/O III. 分配页框

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

单题查看 28

BOK 操作系统

操作系统

2011-29

选择题2 分

当系统发生抖动（thrashing）时，可以采取的有效措施是__。
I. 撤销部分进程 II. 增加磁盘交换区的容量 III. 提高用户进程的优先级

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

单题查看 29

BOK 操作系统

操作系统

2011-30

选择题2 分

在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是__。

A. 编辑
B. 编译
C. 链接
D. 装载

单题查看 30

BOK 操作系统

操作系统

2011-31

选择题2 分

某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是__。

A. 1500μs、1000μs
B. 1550μs、1100μs
C. 1550μs、1550μs
D. 2000μs、2000μs

单题查看 31

BOK 操作系统

操作系统

2011-32

选择题2 分

有两个并发执行的进程 $P 1$ 和 $P 2$ ，共享初值为1的变量 x。 $P 1$ 对 x 加1， $P 2$ 对 x 减1。加1和减1操作的指令序列分别如下所示。

// 加1操作
load R1, x    // 取x到寄存器R1中
inc R1
store x, R1  // 将R1的内容存入x

// 减1操作
load R2, x
dec R2
store x, R2

两个操作完成后，x 的值__。

A. 可能为-1或3
B. 只能为1
C. 可能为0、1或2
D. 可能为-1、0、1或2

单题查看 32

BOK 计算机网络

计算机网络

2011-33

选择题2 分

TCP/IP参考模型的网络层提供的是__。

A. 无连接不可靠的数据报服务
B. 无连接可靠的数据报服务
C. 有连接不可靠的虚电路服务
D. 有连接可靠的虚电路服务

单题查看 33

BOK 计算机网络

计算机网络

2011-34

选择题2 分

若某通信链路的数据传输速率为2400bps，采用四相位调制，则该链路的波特率是__。

A. 600 波特
B. 1200 波特
C. 4800 波特
D. 9600 波特

单题查看 34

BOK 计算机网络

计算机网络

2011-35

选择题2 分

数据链路层采用选择重传协议（SR）传输数据，发送方已发送了0~3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是__。

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

单题查看 35

BOK 计算机网络

计算机网络

2011-36

选择题2 分

下列选项中，对正确接收到的数据帧进行确认的MAC协议是__。

A. CSMA
B. CDMA
C. CSMA/CD
D. CSMA/CA

单题查看 36

BOK 计算机网络

计算机网络

2011-37

选择题2 分

某网络拓扑如下图所示，路由器R1只有到达子网192.168.1.0/24的路由。为使R1可以将IP分组正确地路由到图中所有的子网，则在R1中需要增加的一条路由（目的网络，子网掩码，下一跳）是__。

A. 192.168.2.0 255.255.255.128 192.168.1.1

B. 192.168.2.0 255.255.255.0 192.168.1.1

C. 192.168.2.0 255.255.255.128 192.168.1.2

D. 192.168.2.0 255.255.255.0 192.168.1.2

单题查看 37

BOK 计算机网络

计算机网络

2011-38

选择题2 分

在子网192.168.4.0/30中能接收目的地址为192.168.4.3的IP分组的最大主机数是__。

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

单题查看 38

BOK 计算机网络

计算机网络

2011-39

选择题2 分

主机甲向主机乙发送一个（SYN = 1，seq = 11220）的 TCP 段，期望与主机乙建立 TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的 TCP 段可能是__。

A. (SYN = 0, ACK = 0, seq = 11221, ack = 11221)
B. (SYN = 1, ACK = 1, seq = 11220, ack = 11220)
C. (SYN = 1, ACK = 1, seq = 11221, ack = 11221)
D. (SYN = 0, ACK = 0, seq = 11220, ack = 11220)

单题查看 39

BOK 计算机网络

计算机网络

2011-40

选择题2 分

主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3个连续的TCP段，分别包含300B、400B和500B的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1段和第3段，则主机乙发送给主机甲的确认序号是___。

A. 300
B. 500
C. 1200
D. 1400

单题查看 40

BOK 数据结构

数据结构

2011-41

综合题8 分

已知有6个顶点（顶点编号为0~5）的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中：

[4, 6, ∞, ∞, ∞, 5, ∞, ∞, ∞, 4, 3, ∞, ∞, 3, 3]

要求：
（1）写出图G的邻接矩阵A。
（2）画出有向带权图G。
（3）求图G的关键路径，并计算该关键路径的长度。

单题查看 41

BOK 数据结构

数据结构

2011-42

综合题15 分

一个长度为L（L≥1）的升序序列S，处在第[L/2]个位置的数称为S的中位数。例如，若序列S1=(11,13,15,17,19)，则S1的中位数是15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2,4,6,8,20)，则S1和S2的中位数是11。现在有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C、C++或Java语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。

答案

（1）算法的基本设计思想

分别取当前两个子序列 A' 和 B' 的中位数 a 和 b。

若 a == b，则 a（或 b）即为所求中位数。
若 a < b，则中位数不可能出现在 A' 的前半部分（含 a）和 B' 的后半部分（含 b）中。因此舍弃 A' 的前半部分和 B' 的后半部分，且舍弃长度相等。
若 a > b，则舍弃 A' 的后半部分和 B' 的前半部分，且舍弃长度相等。

重复上述过程，直到两个子序列都只剩一个元素，较小者即为所求中位数。

（2）算法的 C++ 实现

int M_Search(int A[], int B[], int n) {
    // 分别本轮搜索中A、B的起始位置和结束位置
    int start1 = 0, end1 = n - 1, start2 = 0, end2 = n - 1;
    // 分别本轮搜索中A、B的中位数
    int m1, m2;
    // 直到一个数组被遍历完
    while (start1 != end1 || start2 != end2) {
        m1 = (start1 + end1) / 2;
        m2 = (start2 + end2) / 2;
        // 满足情况(1)
        if (A[m1] == B[m2])
            return A[m1];
        // 满足情况(2)
        if (A[m1] < B[m2]) {
            // 考虑奇偶为保证子数组元素个数相同
            if ((start1 + end1) % 2 == 0) {
                start1 = m1;
                end2 = m2;
            } else {
                start1 = m1 + 1;
                end2 = m2;
            }
        }
        // 满足情况(3)
        if (A[m1] > B[m2]) {
            // 考虑奇偶为保证子数组元素个数相同
            if ((start1 + end1) % 2 == 0) {
                end1 = m1;
                start2 = m2;
            } else {
                end1 = m1;
                start2 = m2 + 1;
            }
        }
    }
    // 返回较小的
    return A[start1] < B[start2] ? A[start1] : B[start2];
}

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

时间复杂度：每次迭代将搜索范围减半，因此时间复杂度为 O(log n)。
空间复杂度：只使用了常数个辅助变量，因此空间复杂度为 O(1)。

单题查看 42

BOK 组成原理

组成原理

2011-43

综合题11 分

假定在一个8位字长的计算机中运行如下C程序段：

unsigned int x=134;
unsigned int y=246;
int m=x;
int n=y;
unsigned int z1=x-y;
unsigned int z2=x+y;
int k1=m-n;
int k2=m+n;

若编译器编译时将8个8位寄存器R1~R8分别分配给变量x、y、m、n、z1、z2、k1和k2。
请回答下列问题。（提示：带符号整数用补码表示。）
（1）执行上述程序段后，寄存器R1、R5和R6的内容分别是什么（用十六进制表示）？
（2）执行上述程序段后，变量m和k1的值分别是多少（用十进制表示）？
（3）上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器辅助电路实现？简述理由。
（4）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出？上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？

单题查看 43

BOK 组成原理

组成原理

2011-44

综合题12 分

某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为 16MB，主存（物理）地址空间大小为 1MB，页面大小为 4KB；Cache 采用直接映射方式，共 8 行；主存与 Cache 之间交换的块大小为 32B。系统运行到某一时刻，页表的部分内容和 Cache 的部分内容分别如题 44-a 图、题 44-b 图所示，图中页框号及标记字段的内容为十六进制形式。

请回答下列问题。
（1）虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？
（2）使用物理地址访问 Cache 时，物理地址应划分成哪几个字段？要求说明每个字段的位数及在物理地址中的位置。
（3）虚拟地址 001C60H 所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否 Cache 命中？要求说明理由。
（4）假定为该机配置一个四路组相联的 TLB 共可存放 8 个页表项，若其当前内容（十六进制）如题 44-c 图所示，则此时虚拟地址 024BACH 所在的页面是否存在主存中？要求说明理由。

单题查看 44

BOK 操作系统

操作系统

2011-45

综合题8 分

某银行提供 1 个服务窗口和 10 个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：

cobegin
{
    process 顾客 i
    {
        从取号机获取一个号码；
        等待叫号；
        获取服务；
    }
    process 营业员
    {
        while (TRUE)
        {
            叫号；
            为客户服务；
        }
    }
}
coend

请添加必要的信号量和 P、V（或 wait()、signal()）操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。

答案

【答案】
(1) 信号量定义：

mutex = 1：互斥访问取号机（一次一位顾客取号）。
empty = 10：空座位数量（初始10，用于限制等待顾客数）。
full = 0：已占座位数量（初始0，表示等待服务的顾客数）。
service = 0：叫号同步信号（初始0，营业员叫号时唤醒顾客）。

(2) 顾客进程伪代码：

   process 顾客 i {
       P(empty);       // 等待空座位
       P(mutex);       // 互斥使用取号机
       从取号机获取号码;
       V(mutex);       // 释放取号机
       V(full);        // 通知营业员有新顾客
       P(service);     // 等待叫号
       获取服务;
   }

(3) 营业员进程伪代码：

   process 营业员 {
       while (True) {
           P(full);    // 等待顾客（已占座位）
           V(service); // 叫号（唤醒一位顾客）
           为顾客服务;
       }
   }

单题查看 45

BOK 操作系统

操作系统

2011-46

综合题7 分

某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。
（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需要FCB中设计哪些相关描述字段？
（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。

单题查看 46

BOK 计算机网络

计算机网络

2011-47

综合题9 分

某主机的MAC地址为00-15-C5-C1-5E-28，IP地址为10.2.128.100（私有地址）。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80B的十六进制及ASCII码内容。
（1）Web服务器的IP地址是什么？该主机的默认网关的MAC地址是什么？
（2）该主机在构造题47-b图的数据帧时，使用什么协议确定目的MAC地址？封装该协议请求报文的以太网帧的目的MAC地址是什么？
（3）假设HTTP/1.1协议以持续的非流水线方式工作，一次请求-响应时间为RTT，rfc.html页面引用了5个JPEG小图像，则从发出题47-b图中的Web请求开始到浏览器收到全部内容为止，需要多少个RTT？
（4）该帧所封装的IP分组经过路由器R转发时，需修改IP分组头中的哪些字段？
以太网数据帧结构和IP分组头结构分别如题47-c图、题47-d图所示。

单题查看 47

0	4	6	∞	∞	∞
∞	0	5	∞	∞	∞
∞	∞	0	4	3	∞
∞	∞	∞	0	∞	3
∞	∞	∞	∞	0	3
∞	∞	∞	∞	∞	0

0	4	6	∞	∞	∞
∞	0	5	∞	∞	∞
∞	∞	0	4	3	∞
∞	∞	∞	0	∞	3
∞	∞	∞	∞	0	3
∞	∞	∞	∞	∞	0

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

答案

（1）算法的基本设计思想

（2）算法的 C++ 实现

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

0	4	6	∞	∞	∞
∞	0	5	∞	∞	∞
∞	∞	0	4	3	∞
∞	∞	∞	0	∞	3
∞	∞	∞	∞	0	3
∞	∞	∞	∞	∞	0