数据结构
2011-01
设n是描述问题规模的非负整数，下面程序片段的时间复杂度是。
x = 2;
while (x < n / 2)
x = 2 * x;答案
答案：A
该年份真题解析暂未更新
当前显示 47 道题
单题查看 1
数据结构
2011-02
元素a, b, c, d, e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是。
答案
答案：B
该年份真题解析暂未更新
数据结构
2011-03
已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空，且要求第1个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是。
答案
答案：B
该年份真题解析暂未更新
数据结构
2011-04
若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是。
答案
答案：C
该年份真题解析暂未更新
数据结构
2011-05
若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是。
答案
答案：C
该年份真题解析暂未更新
数据结构
2011-06
已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点个数是。
答案
答案：D
该年份真题解析暂未更新
数据结构
2011-07
对于下列关键字序列，不可能构成某二叉排序树中一条查找路径的序列是。
答案
答案：A
该年份真题解析暂未更新
数据结构
2011-08
下列关于图的叙述中，正确的是。
Ⅰ. 回路是简单路径
Ⅱ. 存储稀疏图，用邻接矩阵比邻接表更省空间
Ⅲ. 若有向图中存在拓扑序列，则该图不存在回路
答案
答案：C
该年份真题解析暂未更新
数据结构
2011-09
为提高散列（Hash）表的查找效率，可以采取的正确措施是。
Ⅰ. 增大装填（载）因子
Ⅱ. 设计冲突（碰撞）少的散列函数
Ⅲ. 处理冲突（碰撞）时避免产生聚集（堆积）现象
答案
答案：D
该年份真题解析暂未更新
数据结构
2011-10
为实现快速排序算法，待排序序列宜采用的存储方式是__。
答案
答案：A
该年份真题解析暂未更新
数据结构
2011-11
已知序列25,13,10,12,9是大根堆，在序列尾部插入新元素18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是__。
答案
答案：B
该年份真题解析暂未更新
组成原理
2011-12
下列选项中，描述浮点数操作速度指标的是__。
答案
答案：D
该年份真题解析暂未更新
组成原理
2011-13
float型数据通常用IEEE 754单精度浮点数格式表示。若编译器将float型变量x分配到一个32位浮点寄存器FR1中，且x=-8.25，则FR1的内容是__。
答案
答案：A
该年份真题解析暂未更新
组成原理
2011-14
下列各类存储器中，不采用随机存取方式的是__。
答案
答案：B
该年份真题解析暂未更新
组成原理
2011-15
某计算机存储器按字节编址，主存地址空间大小为64MB，现用4MB×8位的RAM芯片组成32MB的主存储器，则存储器地址寄存器MAR的位数至少是__。
答案
答案：D
该年份真题解析暂未更新
组成原理
2011-16
偏移寻址通过将某个寄存器内容与一个形式地址相加而生成有效地址。下列寻址方式中，不属于偏移寻址方式的是__。
答案
答案：A
该年份真题解析暂未更新
组成原理
2011-17
某机器有一个标志寄存器，其中有进位/借位标志CF、零标志ZF、符号标志SF和溢出标志OF，条件转移指令bgt（无符号整数比较大于时转移）的转移条件是__。
答案
答案：C
该年份真题解析暂未更新
组成原理
2011-18
下列给出的指令系统特点中，有利于实现指令流水线的是__。
Ⅰ.指令格式规整且长度一致
Ⅱ.指令和数据按边界对齐存放
Ⅲ.只有Load/Store指令才能对操作数进行存储访问
答案
答案：D
该年份真题解析暂未更新
组成原理
2011-19
假定不采用Cache和指令预取技术，且机器处于“开中断”状态。在下列有关指令执行的叙述中，错误的是__。
答案
答案：C
该年份真题解析暂未更新
组成原理
2011-20
在系统总线的数据线上，不可能传输的是__。
答案
答案：C
该年份真题解析暂未更新
组成原理
2011-21
某计算机有五级中断L₄～L₀，中断屏蔽字为M₄M₃M₂M₁M₀，Mᵢ=1（0⩽i⩽4）表示对Lᵢ级中断进行屏蔽。若中断响应优先级从高到低的顺序是L₄→L₀→L₂→L₁→L₃，则L₁的中断处理程序中设置的中断屏蔽字是__。
答案
答案：D
该年份真题解析暂未更新
组成原理
2011-22
某计算机处理器主频为50MHz，采用定时查询方式控制设备A的I/O，查询程序运行一次所用的时钟周期数至少为500。在设备A工作期间，为保证数据不丢失，每秒需对其查询至少200次，则CPU用于设备A的I/O的时间占整个CPU时间的百分比至少是__。
答案
答案：C
该年份真题解析暂未更新
操作系统
2011-23
下列选项中，满足短任务优先且不会发生饥饿现象的调度算法是__。
答案
答案：B
该年份真题解析暂未更新
操作系统
2011-24
下列选项中，在用户态执行的是__。
答案
答案：A
该年份真题解析暂未更新
操作系统
2011-25
在支持多线程的系统中，进程P创建的若干线程不能共享的是__。
答案
答案：D
该年份真题解析暂未更新
操作系统
2011-26
用户程序发出磁盘I/O请求后，系统的正确处理流程是__。
答案
答案：B
该年份真题解析暂未更新
操作系统
2011-27
某时刻进程的资源使用情况如下表所示。此时的安全序列是__。
答案
答案：D
该年份真题解析暂未更新
操作系统
2011-28
在缺页处理过程中，操作系统执行的操作可能是__。
I. 修改页表 II. 磁盘I/O III. 分配页框
答案
答案：D
该年份真题解析暂未更新
操作系统
2011-29
当系统发生抖动（thrashing）时，可以采取的有效措施是__。
I. 撤销部分进程 II. 增加磁盘交换区的容量 III. 提高用户进程的优先级
答案
答案：A
该年份真题解析暂未更新
操作系统
2011-30
在虚拟内存管理中，地址变换机构将逻辑地址变换为物理地址，形成该逻辑地址的阶段是__。
答案
答案：C
该年份真题解析暂未更新
操作系统
2011-31
某文件占10个磁盘块，现要把该文件磁盘块逐个读入主存缓冲区，并送用户区进行分析，假设一个缓冲区与一个磁盘块大小相同，把一个磁盘块读入缓冲区的时间为100μs，将缓冲区的数据传送到用户区的时间是50μs，CPU对一块数据进行分析的时间为50μs。在单缓冲区和双缓冲区结构下，读入并分析完该文件的时间分别是__。
答案
答案：B
该年份真题解析暂未更新
操作系统
2011-32
有两个并发执行的进程 P1 和 P2，共享初值为1的变量 x。P1 对 x 加1，P2 对 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 的值__。
答案
答案：C
该年份真题解析暂未更新
计算机网络
2011-33
TCP/IP参考模型的网络层提供的是__。
答案
答案：A
该年份真题解析暂未更新
计算机网络
2011-34
若某通信链路的数据传输速率为2400bps，采用四相位调制，则该链路的波特率是__。
答案
答案：B
该年份真题解析暂未更新
计算机网络
2011-35
数据链路层采用选择重传协议（SR）传输数据，发送方已发送了0~3号数据帧，现已收到1号帧的确认，而0、2号帧依次超时，则此时需要重传的帧数是__。
答案
答案：B
该年份真题解析暂未更新
计算机网络
2011-36
下列选项中，对正确接收到的数据帧进行确认的MAC协议是__。
答案
答案：D
该年份真题解析暂未更新
计算机网络
2011-37
某网络拓扑如下图所示，路由器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
答案
答案：D
该年份真题解析暂未更新
计算机网络
2011-38
在子网192.168.4.0/30中能接收目的地址为192.168.4.3的IP分组的最大主机数是__。
答案
答案：C
该年份真题解析暂未更新
计算机网络
2011-39
主机甲向主机乙发送一个（SYN = 1，seq = 11220）的 TCP 段，期望与主机乙建立 TCP 连接，若主机乙接受该连接请求，则主机乙向主机甲发送的正确的 TCP 段可能是__。
答案
答案：C
该年份真题解析暂未更新
计算机网络
2011-40
主机甲与主机乙之间已建立一个TCP连接，主机甲向主机乙发送了3个连续的TCP段，分别包含300B、400B和500B的有效载荷，第3个段的序号为900。若主机乙仅正确接收到第1段和第3段，则主机乙发送给主机甲的确认序号是___。
答案
答案：B
该年份真题解析暂未更新
数据结构
2011-41
已知有6个顶点（顶点编号为0~5）的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中：
[4, 6, ∞, ∞, ∞, 5, ∞, ∞, ∞, 4, 3, ∞, ∞, 3, 3]
要求：
（1）写出图G的邻接矩阵A。
（2）画出有向带权图G。
（3）求图G的关键路径，并计算该关键路径的长度。
答案
答案
(1) 图G的邻接矩阵A：
A =
(2) 有向带权图G：
(3) 关键路径及长度：
关键路径为：0 → 1 → 2 → 3 → 5
关键路径长度为：4 + 5 + 4 + 3 = 16
该年份真题解析暂未更新
数据结构
2011-42
一个长度为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)。
该年份真题解析暂未更新
组成原理
2011-43
假定在一个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）计算机内部如何判断带符号整数加/减运算的结果是否发生溢出？上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出？
答案
（1）R1的内容为86H，R5的内容为90H，R6的内容为7CH。
（2）m的值为-122，k1的值为-112。
（3）能。因为无符号整数和带符号整数（补码表示）的加减运算均可通过补码加法实现，减法可转化为加补数，因此可用同一个加法器辅助电路实现。
（4）判断方法：若两个操作数符号相同但结果符号不同，则溢出；或次高位进位与最高位进位不同，则溢出。程序段中，带符号整数运算k2=m+n会发生溢出。
该年份真题解析暂未更新
组成原理
2011-44
某计算机存储器按字节编址，虚拟（逻辑）地址空间大小为 16MB，主存（物理）地址空间大小为 1MB，页面大小为 4KB；Cache 采用直接映射方式，共 8 行；主存与 Cache 之间交换的块大小为 32B。系统运行到某一时刻，页表的部分内容和 Cache 的部分内容分别如题 44-a 图、题 44-b 图所示，图中页框号及标记字段的内容为十六进制形式。
请回答下列问题。
（1）虚拟地址共有几位，哪几位表示虚页号？物理地址共有几位，哪几位表示页框号（物理页号）？
（2）使用物理地址访问 Cache 时，物理地址应划分成哪几个字段？要求说明每个字段的位数及在物理地址中的位置。
（3）虚拟地址 001C60H 所在的页面是否在主存中？若在主存中，则该虚拟地址对应的物理地址是什么？访问该地址时是否 Cache 命中？要求说明理由。
（4）假定为该机配置一个四路组相联的 TLB 共可存放 8 个页表项，若其当前内容（十六进制）如题 44-c 图所示，则此时虚拟地址 024BACH 所在的页面是否存在主存中？要求说明理由。
答案
（1）虚拟地址为24位，虚页号为高12位；物理地址为20位，页框号为高8位。
（2）物理地址划分为主存字块标记、Cache 行号和块内地址三个字段：主存字块标记占高 12 位（第 19～8 位），Cache 行号占 3 位（第 7～5 位），块内地址占低 5 位（第 4～0 位）。原“Cache字块标记（3位）”的说法不准确，这 3 位实际用于直接映射的 Cache 行索引。
（3）虚拟地址001C60H的虚页号为001H，对应页表项有效位为1，故页面在主存中；页框号为04H，页内偏移为C60H，物理地址为04C60H。访问该物理地址时，Cache索引为第3行，但行中标记（105H）与主存标记（04CH）不相等，故Cache不命中。
（4）虚拟地址024BACH的虚页号为024H，TLB组数为2，组号由虚页号最低1位决定（为0），TLB标记为高11位（012H）。TLB第0组中存在有效且标记匹配的项，故TLB命中，页面在主存中。
该年份真题解析暂未更新
操作系统
2011-45
某银行提供 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(empty); // 顾客离开等待座位，释放一个空座位
V(service); // 叫号（唤醒一位顾客）
为顾客服务;
}
}该年份真题解析暂未更新
操作系统
2011-46
某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。
（1）在连续、链式、索引三种文件的数据块组织方式中，哪种更合适？要求说明理由。为定位文件数据块，需要FCB中设计哪些相关描述字段？
（2）为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好？要求说明理由。
答案
【答案】
（1）连续分配方式更合适。理由：文件一次性写入且不可修改，连续分配能提供高效顺序访问，减少磁盘寻道时间，提升随机访问效率。FCB中需设计字段：起始块号和块数（或起始块号和结束块号）以定位数据块。
（2）集中存储FCB更好。理由：FCB集中存放（如目录区），文件数据集中存放，查找时仅需访问FCB对应块，减少磁头移动和磁盘I/O次数，加快文件检索。
该年份真题解析暂未更新
计算机网络
2011-47
某主机的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图所示。
答案
（1）Web服务器的IP地址为64.170.98.32；该主机的默认网关的MAC地址为00-21-27-21-51-ee。
（2）使用ARP协议确定目的MAC地址；封装ARP请求报文的以太网帧的目的MAC地址是FF-FF-FF-FF-FF-FF。
（3）需要6个RTT。
（4）路由器 R 转发该 IP 分组时需要：
- 将源 IP 地址从主机的私有地址改写为路由器的公有地址；
- 将生存时间 TTL 减 1；
- 因源 IP 地址和 TTL 均发生变化，重新计算 IP 首部校验和。
这里只问 IP 分组头，因此不把以太网帧的源/目的 MAC 地址或传输层校验和列入答案。
该年份真题解析暂未更新