科目组合

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

下列程序段的时间复杂度是（ ）。

给定有限符号集 S, in 和 out 均为 S 中所有元素的任意排列。 对千初始为空的栈 ST, 下列叙述中， 正确的是（ ）。
A、若in是 ST 的入栈序列， 则不能判断 out 是否为其可能的出栈序列
B、若 out 是 ST 的出栈序列， 则不能判断 in 是否为其可能的入栈序列
C、若in是 ST 的入栈序列， out 是对应in的出栈序列， 则in与 out 一定不同
D、若 in 是 ST 的入栈序列， out 是对应in的出栈序列， 则in与 out 可能互为倒序

若结点 p 与 q 在二叉树 T 的中序遍历序列中相邻， 且 p 在 q 之前， 则下列 p 与 q 的关系中，不可能的是（ ）。

若三叉树 T 中有 244 个结点（叶结点的高度为 1)， 则 T 的高度至少是( )。

对任意给定的含n (n > 2) 个字符的有限集 S, 用二叉树表示 S 的哈夫曼编码集和定长编码集， 分别得到二叉树 T1和 T2。 下列叙述中， 正确的是( )。

对于无向图G=(V,E)，下列选项中， 正确的是（  ）。

下图是一个有 10 个活动的 AOE 网， 时间余量最大的活动是( )。

在下图所示的 5 阶 B 树 T 中， 删除关键字 260 之后需要进行必要的调整， 得到新的 B 树 T1。 下列选项中， 不可能是 T1 根结点中关键字序列的是（  ）。

A、60，90，280

B、60，90，350

C、60，85，110，350

D、60，90，110，350

下列因素中， 影响散列（哈希）方法平均查找长度的是（ ）。
I. 装填因子
II. 散列函数
III. 冲突解决策略
A、仅 I、 II
B、仅 I、 III
C、仅 II、 III
D、I、 II、 III

使用二路归并排序对含 n 个元素的数组 M 进行排序时，二路归并操作的功能是（ ）。
A、将两个有序表合并为一个新的有序表
B、将M划分为两部分， 两部分的元素个数大致相等
C、将 M 划分为n个部分，每个部分中仅含有一个元素
D、将M划分为两部分，一部分元素的值均小千另一部分元素的值

对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是（  ）。
I． 大部分元素已有序
II. 待排序元素数量很少
III. 要求空间复杂度为 O(l)
IV. 要求排序算法是稳定的

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

某计算机主频为1GHz，程序P运行过程中，共执行了10000条指令，其中，80%的指令执行平均需1个时钟周期，20%的指令执行平均需10个时钟周期。程序P的平均CPI和CPU执行时间分别是（ ）。

A. 2.8，28μs

B. 28，28μs

C. 2.8，28ms

D. 28，28ms

32位补码所能表示的整数范围是（ ）。

-0.4375的IEEE754单精度浮点数表示为（ ）。

A. BEE0 0000H

B. BF60 0000H

C. BF70 0000H

D. C0E0 0000H

某计算机主存地址为24位，采用分页虚拟存储管理方式，虚拟地址空间大小为4GB，页大小为4KB，按字节编址。某进程的页表部分内容如下表所示。当CPU访问虚拟地址00082840H，虚-实地址转换的结果是（ ）。

A. 得到主存地址02 4840H

B. 得到主存地址18 0840H

C. 得到主存地址01 8840H

D. 检测到缺页异常

某计算机主存地址为32位，按字节编址，某Cache的数据区容量为32KB，主存块大小为64B，采用8路组相联映射方式，该Cache中比较器的个数和位数分别为（ ）。

A. 8，20

B. 8，23

C. 64，20

D. 64，23

某内存条包含8个8192×8192×8位的DRAM芯片，按字节编址，支持突发传送方式，对应存储器总线宽度为64位，每个DRAM芯片内有一个行缓冲区。下列关于该内存条的叙述中，不正确的是（ ）。

A. 内存条的容量为512MB

B. 采用多模块交叉编址方式

C. 芯片的地址引脚为26位

D. 芯片内行缓冲有8192×8位

下列选项中，属于指令集体系结构（ISA）规定的内容是（ ）。

Ⅰ. 指令字格式和指令类型

Ⅱ. CPU的时钟周期

Ⅲ. 通用寄存器个数和位数

Ⅳ. 加法器的进位方式

A. 仅Ⅰ、Ⅱ

B. 仅Ⅰ、Ⅲ

C. 仅Ⅱ、Ⅳ

D. 仅Ⅰ、Ⅲ、Ⅳ

设计某指令系统时，假设采用16位定长指令字格式，操作码使用扩展编码方式，地址码为6位，包含零地址、一地址和二地址3种格式的指令。若二地址指令有12条，一地址指令有254条，则零地址指令的条数最多为（ ）。

A. 0

B. 2

C. 64

D. 128

将高级语言源程序转换为可执行目标文件的主要过程是（ ）。

A. 预处理→编译→汇编→链接

B. 预处理→汇编→编译→链接

C. 预处理→编译→链接→汇编

D. 预处理→汇编→链接→编译

下列关于中断I/O方式的叙述中，不正确的是（ ）。

A. 适用于键盘、针式打印机等字符型设备

B. 外设和主机之间的数据传送通过软件完成

C. 外设准备数据的时间应小于中断处理时间

D. 外设为某进程准备数据时CPU可运行其他进程

下列关于并行处理技术的叙述中，不正确的是（ ）。

A. 多核处理器属于MIMD结构

B. 向量处理器属于SIMD结构

C. 硬件多线程技术只可用于多核处理器

D. SMP中所有处理器共享单一物理地址空间

下列关于多道程序系统的叙述中，不正确的是（ ）。

A. 支持进程的并发执行

B. 不必支持虚拟存储管理

C. 需要实现对共享资源的管理

D. 进程数越多CPU利用率越高

下列选项中，需要在操作系统进行初始化过程中创建的是（ ）。

A. 中断向量表

B. 文件系统的根目录

C. 硬盘分区表

D. 文件系统的索引节点表

进程P0、P1、P2和P3进入就绪队列的时刻、优先级（值越小优先权越高）及CPU执行时间如下表所示。

若系统采用基于优先权的抢占式进程调度算法，则从0ms时刻开始调度，到4个进程都运行结束为止，发生进程调度的总次数为（ ）。

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

系统中有三个进程P0、P1、P2及三类资源A、B、C。若某时刻系统分配资源的情况如下表所示，则此时系统中存在的安全序列的个数为（ ）。

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

下列关于CPU模式的叙述中，正确的是（ ）。

A. CPU处于用户态时只能执行特权指令

B. CPU处于内核态时只能执行特权指令

C. CPU处于用户态时只能执行非特权指令

D. CPU处于内核态时只能执行非特权指令

下列事件或操作中，可能导致进程P由执行态变为阻塞态的是（ ）。

Ⅰ. 进程P读文件

Ⅱ. 进程P的时间片用完

Ⅲ. 进程P申请外设

Ⅳ. 进程P执行信号量的wait()操作

A. 仅Ⅰ、Ⅳ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅲ、Ⅳ

D. 仅Ⅰ、Ⅲ、Ⅳ

某进程访问的页b不在内存中，导致产生缺页异常，该缺页异常处理过程中不一定包含的操作是（ ）。

A. 淘汰内存中的页

B. 建立页号与页框号的对应关系

C. 将页b从外存读入内存

D. 修改页表中页b对应的存在位

下列选项中，不会影响系统缺页率的是（ ）。

A. 页面置换算法

B. 工作集的大小

C. 进程的数量

D. 页缓冲队列的长度

执行系统调用的过程涉及下列操作，其中由操作系统完成的是（ ）。

Ⅰ. 保存断点和程序状态字

Ⅱ. 保存通用寄存器的内容

Ⅲ. 执行系统调用服务程序

Ⅳ. 将CPU模式改为内核态

A. 仅Ⅰ、Ⅲ

B. 仅Ⅱ、Ⅲ

C. 仅Ⅱ、Ⅳ

D. 仅Ⅱ、Ⅲ、Ⅳ

下列关于驱动程序的叙述中，不正确的是（ ）。

A. 驱动程序与I/O控制方式无关

B. 初始化设备是由驱动程序控制完成的

C. 进程在执行驱动程序时可能进入阻塞态

D. 读/写设备的操作是由驱动程序控制完成的

在ISO/OSI参考模型中， 实现两个相邻结点间流量控制功能的是（ ）。

A. 物理层
B. 数据链路层
C. 网络层
D. 传输层

在一条带宽为200kHz的无噪声信道上，若采用4个幅值的ASK调制， 则该信道的最大数据传输速率是（ ）。
A. 200 kbps
B. 400 kbps
C. 800 kbps
D. 1600 kbps

若某主机的IP地址是183.80.72.48,子网掩码是255.255.192.0, 则该主机所在网络的网络地址是(  )。
A. 183.80.0.0 
B. 183.80.64.0 
C. 183.80.72.0
D. 183.80.192.0

下图所示网络中的主机H的子网掩码与默认网关分别是（  ）

A. 255.255.255.192, 192.168.1.1     B. 255.255.255.192, 192.168.1.62
C. 255.255.255.224, 192.168.1.1     D. 255.255.255.224, 192.168.1.62

在SDN网络体系结构中，SDN控制器向数据平面的SDN交换机下发流表时所使用的接口是（  ）
A. 东向接口
B. 南向接口
C. 西向接口 
D. 北向接口

假设主机甲和主机乙已建立一个TCP连接， 最大段长MSS = 1 KB, 甲 一直有数据向乙发送，当甲的拥塞窗口为16KB时， 计时器发生了超时， 则甲的拥塞窗口再次增长到16KB所需要的时间至少是（ ）。

A. 4 RTT      B. 5 RTT      C. 11 RTT      D. 16 RTT

假设客户C和服务器S已建立一个TCP连接， 通信往返时间RTT = 50 ms, 最长报文段寿命MSL= 800ms, 数据传输结束后，C主动请求断开连接。 若从C主动向S发出FIN段时刻算起， 则C和S进入CLOSED状态所需的时间至少分别是( )。

A. 850 ms, 50 ms
B. 1650 ms, 50 ms
C. 850 ms, 75 ms
D. 1650 ms, 75 ms

假设主机H通过HTTP/1.1请求浏览某Web服务器S上的Web页news408.html, news408.. html引用了同目录下的1幅图像， news408.html文件大小为1 MSS（最大段长）， 图像文件大小为3 MSS, H访问 S的往返时间RTT= IO ms,忽略HTTP响应报文的首部开销和TCP段传输时延。 若H已完成域名解析，则从H请求与S建立TCP连接时刻起， 到接收到全部 内容止，所需的时间至少 是（ ）。

A. 30ms     B. 40ms     C. 50ms     D. 60ms

已知非空二叉树T的结点值均为正整数，采用顺序存储方式保存，数据结构定义如下：

typedef struct {                    // MAX_SIZE为已定义常量
    Elemtype SqBiTNode[MAX_SIZE];   // 保存二叉树结点值的数组
    int ElemNum;                    // 实际占用的数组元素个数
}SqBiTree;

T中不存在的结点在数组SqBiTNode中用-1表示。例如，对于下图所示的两棵非空二叉树T1和T2：

请设计一个尽可能高效的算法，判定一棵采用这种方式存储的二叉树是否为二叉搜索树，若是，则返回true，否则，返回false，要求：

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

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

现有 n(n>100000) 个数保存在一维数组 M 中，需要查找 M 中最小的10个数，请回答下列问题。

⑴ 设计一个完成上述查找任务的算法，要求平均情况下的比较次数尽可能少，简单描述其算法思想，不需要程序实现。

⑵ 说明你所设计的算法平均情况下的时间复杂度和空间复杂度。

某CPU中部分数据通路如图所示，其中，GPRs为通用寄存器组；FR为标志寄存器，用于存放ALU产生的标志信息；带箭头虚线表示控制信号，如控制信号Read、Write分别表示主存读、主存写，MDRin表示内部总线上数据写入MDR，MDRout表示MDR的内容送内部总线。

(1) ALU的输入端A、B及输出端F的最高位分别为 A15 、 B15 及 F15 ，FR中的符号标志和溢出标志分别为SF和OF，则SF的逻辑表达式是什么？A加B、A减B时OF的逻辑表达式分别是什么？要求逻辑表达式的输入变量为A15 、 B15 及 F15 。

(2) 为什么要设置暂存器Y和Z？

(3) 若GPRs的输入端rs、rd分别为所读、写的通用寄存器的编号，则GPRs中最多有多少个通用寄存器？rs和rd来自图中的哪个寄存器？已知GPRs内部有一个地址译码器和一个多路选择器，rd应该连接地址译码器还是多路选择器？

(4) 取指令阶段（不考虑PC增量操作）的控制信号序列是什么？若从发出主存读命令到主存读出数据并传送到MDR共需5个时钟周期，则取指令阶段至少需要几个时钟周期？

(5) 图中控制信号由什么部件产生？图中哪些寄存器的输出信号会连到该部件的输入端？

假设某磁盘驱动器中有4个双面盘片，每个盘面有20000个磁道，每个磁道有500个扇区，每个扇区可记录512字节的数据，盘片转速为7200rpm（转/分），平均寻道时间为5ms，请回答下列问题。

(1) 每个扇区包含数据及地址信息，地址信息分为3个字段，这3个字段的名称格式什么？对于该磁盘，各字段至少占多少位？

(2) 一个扇区的平均访问时间约为多少？

(3) 若采用周期挪用DMA方式进行磁盘与主机之间的数据传送，磁盘控制器中的数据缓冲区大小为64位，则在一个扇区读写过程中，DMA控制器向CPU发送了多少次总线请求？若CPU检测到DMA控制器的总线请求信号时也需要访问主存，则DMA控制器是否可以获得总线使用权？为什么？

某文件系统的磁盘块大小为4KB，目录项由文件名和索引节点号构成，每个索引节点占256字节，其中包含直接地址项10个，一级、二级和三级间接地址项各1个，每个地址项占4字节。该文件系统中子目录stu的结构如题45(a)图所示，stu包含子目录course和文件doc，course子目录包含文件course1和course2。各文件的文件名、索引节点号、占用磁盘块的块号如题45(b)图所示。

请回答下列问题。

(1) 目录文件stu中每个目录项的内容是什么？

(2) 文件doc占用的磁盘块的块号 x 的值是多少？

(3) 若目录文件course的内容已在内存，则打开文件course1并将其读入内存，需要读几个磁盘块？说明理由。

(4) 若文件course2的大小增长到6MB，为了存取course2需要使用该文件索引节点的哪几级间接地址项？说明理由。

某进程的两个线程T1和T2并发执行A、B、C、D、E和F共6个操作，其中T1执行A、E和F，T2执行B、C和D。题46图表示上述6个操作的执行顺序所必须满足的约束：C在A和B完成后执行，D和E在C完成后执行，F在E完成后执行。请使用信号量的wait()、signal()操作描述T1和T2之间的同步关系，并说明所用信号量的作用及其初值。

某网络拓扑如题 47 图所示， R 为路由器， S 为以太网交换机， AP 是 802.11 接入点，路由器的 E0 接口和 DHCP 服务器的 IP 地址配置如图中所示； H1 与 H2 属千同一个广播域，但不属于同一个冲突域； H2 和 H3 属千同一个冲突域； H4 和 H5 已经接入网络，并通过 DHCP动态获取了 IP 地址。 现有路由器、 100BaseT 以太网交换机和 100BaseT 集线器(Hub)三类设备各若干台。

请回答下列问题。
1) 设备 1 和设备 2 应该分别选择哪类设备？
2) 若信号传播速度为 2x10^8 m/s, 以太网最小帧长为 64 B, 信号通过设备 2 时会产生额外的1.51 µs的时间延迟， 则 H2 与 H3 之间可以相距的最远距离是多少？
3) 在 H4 通过 DHCP 动态获取 IP 地址过程中， H4 首先发送了 DHCP 报文 M, M 是哪种DHCP 报文？路由器 E0 接口能否收到封装 M 的以太网帧？S 向DHCP 服务器转发的封装M的以太网帧的目的MAC地址是什么？
4) 若 H4 向 H5 发送一个 1P 分组 P, 则 H5 收到的封装 P 的 802.11 帧的地址1、 地址2 和地址3 分别是什么？