数据结构
2016-01
已知表头元素为 c 的单链表在内存中的存储状态如下表所示。
现将 f 存放于 1014H 处并插入到单链表中，若 f 在逻辑上位于 a 和 e 之间，则 a、e、f 的“链接地址”依次是__。
答案
答案：D
当前显示 47 道题
单题查看 1
数据结构
2016-02
已知一个带有表头结点的双向循环链表 L，结点结构为 [ prev | data | next ]，其中，prev 和 next 分别是指向其直接前驱和直接后继结点的指针。现要删除指针 p 所指的结点，正确的语句序列是__。
答案
答案：D
数据结构
2016-03
设有下图所示的火车车轨，入口到出口之间有 n 条轨道，列车的行进方向均为从左至右，列车可驶入任意一条轨道。现有编号为 1~9 的 9 列列车，驶入的次序依次是 8, 4, 2, 5, 3, 9, 1, 6, 7。若期望驶出的次序依次为 1~9，则 n 至少是。
答案
答案：C
数据结构
2016-04
有一个 100 阶的三对角矩阵 M，其元素 mi,j（1≤ i≤100，1≤ j≤100）按行优先依次压缩存入下标从 0 开始的一维数组 N 中。元素 m30,30 在 N 中的下标是__。
答案
答案：B
数据结构
2016-05
若森林 F 有 15 条边、25 个结点，则 F 包含树的个数是__。
答案
答案：C
数据结构
2016-06
下列选项中，不是下图深度优先搜索序列的是__。
答案
答案：D
数据结构
2016-07
若将 n 个顶点 e 条弧的有向图采用邻接表存储，则拓扑排序算法的时间复杂度是__。
答案
答案：B
数据结构
2016-08
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是__。
答案
答案：B
数据结构
2016-09
在有 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
查找失败;本算法与折半查找算法相比，有可能具有更少比较次数的情形是__。
答案
答案：B
数据结构
2016-10
B+树不同于 B 树的特点之一是__。
答案
答案：A
数据结构
2016-11
对 10TB 的数据文件进行排序，应使用的方法是__。
答案
答案：D
组成原理
2016-12
将高级语言源程序转换为机器级目标代码文件的程序是__。
答案
答案：C
组成原理
2016-13
有如下 C 语言程序段
short si = -32767;
unsigned short usi = si;
执行上述两条语句后，usi 的值为__。
答案
答案：D
组成原理
2016-14
某计算机字长为 32 位，按字节编址，采用小端（Little Endian）方式存放数据。假定有一个 double 型变量，其机器数表示为 1122 3344 5566 7788H，存放在 0000 8040H 开始的连续存储单元中，则存储单元 0000 8046H 中存放的是__。
答案
答案：A
组成原理
2016-15
有如下 C 语言程序段：
for (k = 0; k < 1000; k++)
a[k] = a[k] + 32;若数组 a 及变量 k 均为 int 型，int 型数据占 4B，数据 Cache 采用直接映射方式，数据区大小为 1KB、块大小为 16B，该程序段执行前 Cache 为空，则该程序段执行过程中访问数组 a 的 Cache 缺失率约为__。
答案
答案：C
组成原理
2016-16
某存储器容量为 64KB，按字节编址，地址 4000H～5FFFH 位 ROM 区，其余为 RAM 区。若采用 8K×4 位的 SRAM 芯片进行设计，则需要该芯片的数量是__。
答案
答案：C
组成原理
2016-17
某指令格式如下所示。
其中 M 为寻址方式，I 为变址寄存器编号，D 为形式地址。若采用先变址后间址的寻址方式，则操作数的有效地址是__。
答案
答案：C
组成原理
2016-18
某计算机主存空间为 4GB，字长为 32 位，按字节编址，采用 32 位字长指令字格式。若指令按字边界对齐存放，则程序计数器（PC）和指令寄存器（IR）的位数至少分别是__。
答案
答案：B
组成原理
2016-19
在无转发机制的五段基本流水线（取指、译码/读寄存器、运算、访存、写回寄存器）中，下列指令序列存在数据冒险的指令对是__。
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
答案
答案：B
组成原理
2016-20
单周期处理器中所有指令的指令周期为一个时钟周期。下列关于单周期处理器的叙述中，错误的是__。
答案
答案：A
组成原理
2016-21
下列关于总线设计的叙述中，错误的是__。
答案
答案：A
组成原理
2016-22
异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。下列关于中断或异常情况的叙述中，错误的是__。
答案
答案：A
操作系统
2016-23
下列关于批处理系统的叙述中，正确的是_。
I. 批处理系统允许多个用户与计算机直接交互
II. 批处理系统分为单道批处理系统和多道批处理系统
III. 中断技术使得多道批处理系统和I/O设备可与CPU并行工作
答案
答案：A
操作系统
2016-24
某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms、3ms和4ms，且都按输入、计算和输出的顺序执行，则执行完3个作业需要的时间最少是_。
答案
答案：B
操作系统
2016-25
系统中有3个不同的临界资源R₁、R₂和R₃，被4个进程p₁、p₂、p₃及p₄共享。各进程对资源的需求为：p₁申请R₁和R₂，p₂申请R₂和R₃，p₃申请R₁和R₃，p₄申请R₂。若系统出现死锁，则处于死锁状态的进程数至少是_。
答案
答案：C
操作系统
2016-26
某系统采用改进型CLOCK置换算法，页表项中字段A为访问位，M为修改位。A = 0表示页最近没有被访问，A = 1表示页最近被访问过。M = 0表示页没有被修改过，M = 1表示页被修改过。按(A, M)所有可能的取值，将页分为四类：(0,0)，(1,0)，(0,1)和(1,1)，则该算法淘汰页的次序为_。
答案
答案：A
操作系统
2016-27
使用TSL（Test and Set Lock）指令实现进程互斥的伪代码如下所示。
do {
...
while (TSL(&lock));
critical_section;
lock = FALSE;
...
} while (TRUE);下列与该实现机制相关的叙述中，正确的是_。
答案
答案：B
操作系统
2016-28
某进程的段表内容如下所示。
当访问段号为 2、段内地址为 400 的逻辑地址时，进行地址转换的结果是__。
答案
答案：D
操作系统
2016-29
某进程访问页面的序列如下所示。
…,1,3,4,5,6,0,3,2,3,2,4,0,4,0,3,2,9,2,1,…
若工作集的窗口大小为6，则在t时刻的工作集为___。
答案
答案：A
操作系统
2016-30
进程P₁和P₂均包含并发执行的线程，部分伪代码描述如下所示。
下列选项中，需要互斥执行的操作是__。
答案
答案：C
操作系统
2016-31
下列关于SPOOLing技术的叙述中，错误的是___。
答案
答案：D
操作系统
2016-32
下列关于管程的叙述中，错误的是___。
答案
答案：A
计算机网络
2016-33
在OSI参考模型中，R1、Switch、Hub实现的最高功能层分别是___。
答案
答案：C
计算机网络
2016-34
若连接R2和R3链路的频率带宽为8kHz，信噪比为30dB，该链路实际数据传输速率约为理论最大数据传输速率的50%，则该链路的实际数据传输速率约是___。
答案
答案：C
计算机网络
2016-35
若主机H2向主机H4发送1个数据帧，主机H4向主机H2立即发送一个确认帧，则除H4外，从物理层上能够收到该确认帧的主机还有。
答案
答案：D
计算机网络
2016-36
若Hub再生比特流过程中，会产生1.535μs延时，信号传播速度为200m/μs，不考虑以太网帧的前导码，则H3与H4之间理论上可以相距的最远距离是。
答案
答案：B
计算机网络
2016-37
假设R1、R2、R3采用RIP协议交换路由信息，且均已收敛。若R3检测到网络201.1.2.0/25不可达，并向R2通告一次新的距离向量，则R2更新后，其到达该网络的距离是。
答案
答案：B
计算机网络
2016-38
假设连接R1、R2和R3之间的点对点链路使用201.1.3.x/30地址，当H3访问Web服务器S时，R2转发出去的封装HTTP请求报文的IP分组的源IP地址和目的IP地址分别是。
答案
答案：D
计算机网络
2016-39
若H1与H2的默认网关和子网掩码均分别配置为192.168.3.1和255.255.255.128，H3和H4的默认网关和子网掩码均分别配置为192.168.3.254和255.255.255.128，则下列现象中可能发生的是。
答案
答案：C
计算机网络
2016-40
假设所有域名服务器均采用迭代查询方式进行域名解析。当H4访问规范域名为www.abc.xyz.com的网站时，域名服务器201.1.1.1在完成该域名解析过程中，可能发出DNS查询的最少和最多次数分别是。
答案
答案：C
计算机网络
2016-41
假设题 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 释放该连接的最短时间是多少？
答案
（1）SYN=1，ACK=1，确认序号=101。
（2）接收窗口=12KB，拥塞窗口=9KB，发送窗口=9KB。
（3）下一个待发送数据段序号=20581，平均数据传输速率=20KB/s（或20.48kbps）。
（4）最短时间=300ms。
数据结构
2016-42
如果一棵非空 k（k≥2）叉树 T 中每个非叶结点都有 k 个孩子，则称 T 为正则 k 叉树。请回答下列问题并给出推导过程。
（1）若 T 有 m 个非叶结点，则 T 中的叶结点有多少个？
（2）若 T 的高度为 h（单结点的树 h = 1），则 T 的结点数最多为多少个？最少为多少个？
答案
(1) 叶结点数为 (k-1)m+1。
(2) 最多结点数为 ∑j=1hkj-1=(kh-1)/(k-1)；最少结点数为 1+(h-1)k。
数据结构
2016-43
已知由 n（n≥2）个正整数构成的集合 A=akmid 0≤ k<n\，将其划分为两个不相交的子集 A1 和 A2，元素个数分别是 n1 和 n2，A1 和 A2 中元素之和分别为 S1 和 S2。设计一个尽可能高效的划分算法，满足 |n1-n2| 最小且 |S1-S2| 最大。要求：
（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)，仅使用常数额外空间。
组成原理
2016-44
假定 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 进行了哪些操作？
答案
（1）每个字符传输10位；每秒最多送入2000个字符。
（2）完成1000个字符所需时间约为25,070,000个时钟周期；CPU用于该任务的时间约为90,000个时钟周期；在中断响应阶段CPU进行关中断、保护断点和程序状态、识别中断源的操作。
组成原理
2016-45
某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为 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）策略。
答案
（1）A=19位，B=19位，C=11位，D=13位，E=9位，F=9位，G=6位。TLB标记字段B中存放的是虚页号。
（2）Cache组号为3；H字段内容为0 0000 1000B。
（3）缺页处理的时间开销大。因为缺页处理需要访问磁盘，而Cache缺失只需访问主存。
（4）Cache-主存层次访问速度较快，直写策略可接受；主存-外存层次中磁盘访问速度极慢，回写策略可减少磁盘访问次数，提高性能。
操作系统
2016-46
某进程调度程序采用基于优先数（priority）的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime置0；进程处于就绪态时，cpuTime置0，waitTime定时加1。请回答下列问题。
（1）若调度程序只将nice的值作为进程的优先数，即priority = nice，则可能会出现饥饿现象，为什么？
（2）使用nice、cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用。
答案
【答案】
（1）由于nice为静态优先数，一旦设定不变。若就绪队列中总是存在优先数较小（即优先级更高）的进程，优先数较大的进程可能长期无法获得CPU，从而出现饥饿现象。
（2）动态优先数计算方法为：priority = nice + k₁ × cpuTime - k₂ × waitTime，其中k₁ > 0，k₂ > 0为可调参数。waitTime的作用是增加等待进程的优先级（减小优先数），使长时间等待的进程有机会被调度，避免饥饿。
操作系统
2016-47
某磁盘文件系统使用链接分配方式组织文件，簇大小为4KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。
（1）假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中dir、dir1是目录，file1、file2是用户文件。请给出所有目录文件的内容。
（2）若FAT的每个表项仅存放簇号，占2字节，则FAT的最大长度为多少字节？该文件系统支持的文件长度最大是多少？
（3）系统通过目录文件和FAT实现对文件的按名存取，说明file1的106、108两个簇号分别存放在FAT的哪个表项中。
（4）假设仅FAT和dir目录文件已读入内存，若需将文件dir/dir1/file的第5000个字节读入内存，则要访问哪几个簇？
答案
(1) 目录树和文件所占簇如下图所示：
dir目录文件包含目录项：dir1（簇号48）、file1（簇号100）；dir1目录文件包含目录项：file2（簇号200）。
(2) FAT的最大长度为128KB，该文件系统支持的文件长度最大为256MB。
(3) file1的簇号106存放在FAT的100号表项中，簇号108存放在FAT的106号表项中。
(4) 需要访问簇48和簇106。