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

int sum= 0;
for (int i=1;i<n；i*=2)
for(int j=0;j<i；j++)
 sum++;

给定有限符号集 S,in 和 out 均为 S 中所有元素的任意排列。对于初始为空的栈 ST，下列叙 述中,正确的是（ ）。

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

I. q 是 p 的双亲 

Ⅱ. q 是 p 的右孩子 

Ⅲ. q 是 p 的右兄弟 

Ⅳ. q 是 p 的双亲的双亲

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

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

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

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

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

下列因素中，影响散列（哈希）方法平均查找长度的是（ ）。 

I.装填因子

Ⅱ.散列函数

Ⅲ.冲突解决策略

使用二路归并排序对含 n 个元素的数组 M 进行排序时，二路归并操作的功能是（ ）。

对数据进行排序时，若采用直接插入排序而不采用快速排序，则可能的原因是（ ）。

I.大部分元素已有序 

Ⅱ.待排序元素数量很少 

Ⅲ.要求空间复杂度为 O（1） 

Ⅳ.要求排序算法是稳定的

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

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

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

某计算机主存地址为 24 位，采用分页虚拟存储管理方式，虚拟地址空间大小为 4GB，页 大小为 4KB，按字节编址。某进程的页表部分内容如下表所示。

下列选项中，支持文件长度可变、随机访问的磁盘存储空间分

下列与中断相关的操作中，由操作系统

I .保存被中断程

I I . 提供中断服务

I I I . 初始化

I V .保存中断屏蔽字

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

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

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

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

Ⅱ. CPU 的时钟周期 

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

Ⅳ.加法器的进位方式