数据结构
2018-01
若栈S₁中保存整数，栈S₂中保存运算符，函数F()依次执行下述各步操作：
（1）从S₁中依次弹出两个操作数a和b；
（2）从S₂中弹出一个运算符op；
（3）执行相应的运算b op a；
（4）将运算结果压入S₁中。
假定S₁中的操作数依次是5,8,3,2（2在栈顶），S₂中的运算符依次是*, -, +（+在栈顶）。
调用3次F()后，S₁栈顶保存的值是__。
A. -15
B. 15
C. -20
D. 20
答案
答案：B
当前显示 47 道题
单题查看 1
数据结构
2018-02
现有队列Q与栈S，初始时Q中的元素依次是1,2,3,4,5,6（1在队头），S为空。若仅允许下列3种操作：①出队并输出出队元素；②出队并将出队元素入栈；③出栈并输出出栈元素，则不能得到的输出序列是__。
A. 1,2,5,6,4,3
B. 2,3,4,5,6,1
C. 3,4,5,6,1,2
D. 6,5,4,3,2,1
答案
答案：C
数据结构
2018-03
设有一个 12×12 的对称矩阵 M，将其上三角部分的元素 mi,j（1≤ i≤ j≤12）按行优先存入 C 语言的一维数组 N 中，元素 m6,6 在 N 中的下标是__。
A. 50
B. 51
C. 55
D. 66
答案
答案：A
数据结构
2018-04
设一棵非空完全二叉树T的所有叶结点均位于同一层，且每个非叶结点都有2个子结点。若T有k个叶结点，则T的结点总数是__。
A. 2k-1
B. 2k
C. k²
D. 2^k-1
答案
答案：A
数据结构
2018-05
已知字符集{a, b, c, d, e, f}，若各字符出现的次数分别为6, 3, 8, 2, 10, 4，则对应字符集中各字符的哈夫曼编码可能是__。
A. 00, 1011, 01, 1010, 11, 100
B. 00, 100, 110, 000, 0010, 01
C. 10, 1011, 11, 0011, 00, 010
D. 0011, 10, 11, 0010, 01, 000
答案
答案：A
数据结构
2018-06
已知二叉排序树如下图所示，元素之间应满足的大小关系是__。
A. x1<x2<x5
B. x1<x4<x5
C. x3<x5<x4
D. x4<x3<x5
答案
答案：C
数据结构
2018-07
下列选项中，不是如下有向图的拓扑序列的是__。
A. 1, 5, 2, 3, 6, 4
B. 5, 1, 2, 6, 3, 4
C. 5, 1, 2, 3, 6, 4
D. 5, 2, 1, 6, 3, 4
答案
答案：D
数据结构
2018-08
高度为5的3阶B树含有的关键字个数至少是__。
A. 15
B. 31
C. 62
D. 242
答案
答案：B
数据结构
2018-09
现有长度为7、初始为空的散列表HT，散列函数H(k) = k % 7，用线性探测再散列法解决冲突。将关键字22，43，15依次插入到HT后，查找成功的平均查找长度是__。
A. 1.5
B. 1.6
C. 2
D. 3
答案
答案：C
数据结构
2018-10
对初始数据序列(8,3,9,11,2,1,4,7,5,10,6)进行希尔排序。若第一趟排序结果为(1,3,7,5,2,6,4,9,11,10,8)，第二趟排序结果为(1,2,6,4,3,7,5,8,11,10,9)，则两趟排序采用的增量（间隔）依次是__。
A. 3，1
B. 3，2
C. 5，2
D. 5，3
答案
答案：D
数据结构
2018-11
在将数据序列(6,1,5,9,8,4,7)建成大根堆时，正确的序列变化过程是__。
A. 6, 1, 7, 9, 8, 4, 5 → 6, 9, 7, 1, 8, 4, 5 → 9, 6, 7, 1, 8, 4, 5 → 9, 8, 7, 1, 6, 4, 5
B. 6, 9, 5, 1, 8, 4, 7 → 6, 9, 7, 1, 8, 4, 5 → 9, 6, 7, 1, 8, 4, 5 → 9, 8, 7, 1, 6, 4, 5
C. 6, 9, 5, 1, 8, 4, 7 → 9, 6, 5, 1, 8, 4, 7 → 9, 6, 7, 1, 8, 4, 5 → 9, 8, 7, 1, 6, 4, 5
D. 6, 1, 7, 9, 8, 4, 5 → 7, 1, 6, 9, 8, 4, 5 → 7, 9, 6, 1, 8, 4, 5 → 9, 7, 6, 1, 8, 4, 5 → 9, 8, 6, 1, 7, 4, 5
答案
答案：A
组成原理
2018-12
冯·诺依曼结构计算机中数据采用二进制编码表示，其主要原因是__。
I. 二进制的运算规则简单
II. 制造两个稳态的物理器件较容易
III. 便于用逻辑门电路实现算术运算
A. 仅I、II
B. 仅I、III
C. 仅II、III
D. I、II和III
答案
答案：D
组成原理
2018-13
假定带符号整数采用补码表示，若int型变量x和y的机器数分别是FFFF FFDFH和0000 0041H，则x、y的值以及x-y的机器数分别是__。
A. x = -65, y = 41, x-y的机器数溢出
B. x = -33, y = 65, x-y的机器数为FFFF FF9DH
C. x = -33, y = 65, x-y的机器数为FFFF FF9EH
D. x = -65, y = 41, x-y的机器数为FFFF FF96H
答案
答案：C
组成原理
2018-14
IEEE 754单精度浮点格式表示的数中，最小的规格化正数是__。
A. 1.0×2-126
B. 1.0×2-127
C. 1.0×2-128
D. 1.0×2-149
答案
答案：A
组成原理
2018-15
某32位计算机按字节编址，采用小端（Little Endian）方式。若语句“int i = 0;”对应指令的机器代码为“C7 45 FC 00 00 00 00”，则语句“int i = -64;”对应指令的机器代码是__。
A. C7 45 FC C0 FF FF FF
B. C7 45 FC 0C FF FF FF
C. C7 45 FC FF FF FF C0
D. C7 45 FC FF FF FF 0C
答案
答案：A
组成原理
2018-16
整数x的机器数为1101 1000，分别对x进行逻辑右移1位和算术右移1位操作，得到的机器数分别是__。
A. 1110 1100, 1110 1100
B. 0110 1100, 1110 1100
C. 1110 1100, 0110 1100
D. 0110 1100, 0110 1100
答案
答案：B
组成原理
2018-17
假定DRAM芯片中存储阵列的行数为r、列数为c，对于一个2K×1位的DRAM芯片，为保证其地址引脚数最少，并尽量减少刷新开销，则r、c的取值分别是__。
A. 2048、1
B. 64、32
C. 32、64
D. 1、2048
答案
答案：C
组成原理
2018-18
按字节编址的计算机中，某double型数组A的首地址为2000H，使用变址寻址和循环结构访问数组A，保存数组下标的变址寄存器初值为0，每次循环取一个数组元素，其偏移地址为变址值乘以sizeof(double)，取完后变址寄存器内容自动加1。若某次循环所取元素的地址为2100H，则进入该次循环时变址寄存器的内容是__。
A. 25
B. 32
C. 64
D. 100
答案
答案：B
组成原理
2018-19
减法指令“sub R1, R2, R3”的功能为“(R1)－(R2)→R3”，该指令执行后将生成进位/借位标志CF和溢出标志OF。若(R1)=FFFF FFFFH，(R2)=FFFF FFF0H，则该减法指令执行后，CF与OF分别为__。
A. CF=0, OF=0
B. CF=1, OF=0
C. CF=0, OF=1
D. CF=1, OF=1
答案
答案：A
组成原理
2018-20
若某计算机最复杂指令的执行需要完成5个子功能，分别由功能部件A～E实现，各功能部件所需时间分别为80ps、50ps、50ps、70ps和50ps，采用流水线方式执行指令，流水线段寄存器延时为20ps，则CPU时钟周期至少为__。
A. 60ps
B. 70ps
C. 80ps
D. 100ps
答案
答案：D
组成原理
2018-21
下列选项中，可提高同步总线数据传输率的是__。
I. 增加总线宽度
II. 提高总线工作频率
III. 支持突发传输
IV. 采用地址/数据线复用
A. 仅I、II
B. 仅I、II、III
C. 仅III、IV
D. I、II、III和IV
答案
答案：B
组成原理
2018-22
下列关于外部I/O中断的叙述中，正确的是__。
A. 中断控制器按所接收中断请求的先后次序进行中断优先级排队
B. CPU响应中断时，通过执行中断隐指令完成通用寄存器的保护
C. CPU只有在处于中断允许状态时，才能响应外部设备的中断请求
D. 有中断请求时，CPU立即暂停当前指令执行，转去执行中断服务程序
答案
答案：C
操作系统
2018-23
下列关于多任务操作系统的叙述，正确的是__。
I. 具有并发和并行的特点
II. 需要实现对共享资源的保护
III. 需要运行在多CPU的硬件平台上
A. 仅I
B. 仅II
C. 仅I、II
D. I、II、III
答案
答案：C
操作系统
2018-24
某系统采用基于优先权的非抢占式进程调度策略，完成一次进程调度和进程切换的系统时间开销为1μs。在T时刻就绪队列中有3个进程P₁、P₂和P₃，其在就绪队列中的等待时间、需要的CPU时间和优先权如下表所示。
若优先权值大的进程优先获得 CPU，从 T 时刻起系统开始进程调度，系统的平均周转时间为__。
A. 54μs
B. 73μs
C. 74μs
D. 75μs
答案
答案：D
操作系统
2018-25
属于同一进程的两个线程thread1和thread2并发执行，共享初值为0的全局变量x。thread1和thread2实现对全局变量x加1的机器级代码描述如下。
在所有可能的指令执行序列中，使 x 的值为 2 的序列个数是__。
A. 1
B. 2
C. 3
D. 4
答案
答案：B
操作系统
2018-26
假设系统中有4个同类资源，进程P₁,P₂和P₃需要的资源数分别为4,3和1，P₁,P₂和P₃已申请到的资源数分别为2,1和0，则执行安全性检测算法的结果是
A. 不存在安全序列，系统处于不安全状态
B. 存在多个安全序列，系统处于安全状态
C. 存在唯一安全序列P₃,P₁,P₂，系统处于安全状态
D. 存在唯一安全序列P₃,P₂,P₁，系统处于安全状态
答案
答案：A
操作系统
2018-27
下列选项中，可能导致当前进程P阻塞的事件是
I. 进程P申请临界资源
II. 进程P从磁盘读数据
III. 系统将CPU分配给高优先权的进程
A. 仅I
B. 仅II
C. 仅I、II
D. I、II、III
答案
答案：C
操作系统
2018-28
若x是管程内的条件变量，则当进程执行x.wait()时所做的工作是
A. 实现对变量x的互斥访问
B. 唤醒一个在x上阻塞的进程
C. 根据x的值判断该进程是否进入阻塞状态
D. 阻塞该进程，并将之插入x的阻塞队列中
答案
答案：D
操作系统
2018-29
当定时器产生时钟中断后，由时钟中断服务程序更新的部分内容是
I. 内核中时钟变量的值
II. 当前进程占用CPU的时间
III. 当前进程在时间片内的剩余执行时间
A. 仅I、II
B. 仅II、III
C. 仅I、III
D. I、II、III
答案
答案：D
操作系统
2018-30
系统总是访问磁盘的某个磁道而不响应其他磁道的访问请求，这种现象称为磁臂黏着。下列磁盘调度算法中，不会导致磁臂黏着的是
A. 先来先服务（FCFS）
B. 最短寻道时间优先（SSTF）
C. 扫描算法（SCAN）
D. 循环扫描算法（CSCAN）
答案
答案：A
操作系统
2018-31
下列优化方法中，可以提高文件访问速度的是
I. 提前读
II. 为文件分配连续的簇
III. 延迟写
IV. 采用磁盘高速缓存
A. 仅I、II
B. 仅II、III
C. 仅I、III、IV
D. I、II、III、IV
答案
答案：D
操作系统
2018-32
下列同步机制中，可以实现让权等待的是
A. Peterson方法
B. swap指令
C. 信号量方法
D. TestAndSet指令
答案
答案：C
计算机网络
2018-33
下列TCP/IP应用层协议中，可以使用传输层无连接服务的是
A. HTTP
B. FTP
C. SMTP
D. DNS
答案
答案：B
计算机网络
2018-34
下列选项中，不属于物理层接口规范定义范畴的是
A. 接口形状
B. 引脚功能
C. 物理地址
D. 信号电平
答案
答案：C
计算机网络
2018-35
IEEE 802.11无线局域网的MAC协议CSMA/CA进行信道预约的方法是
A. 发送确认帧
B. 采用二进制指数退避
C. 使用多个MAC地址
D. 交换RTS与CTS帧
答案
答案：D
计算机网络
2018-36
主机甲采用停-等协议向主机乙发送数据，数据传输速率是3kbps，单向传播延时是200ms。忽略确认帧的传输延时。当信道利用率等于40%时，数据帧的长度为
A. 240比特
B. 400比特
C. 480比特
D. 800比特
答案
答案：D
计算机网络
2018-37
路由器R通过以太网交换机S1和S2连接两个网络，R的接口、主机H1和H2的IP地址与MAC地址如下图所示。若H1向H2发送1个IP分组P，则H1发出的封装P的以太网帧的目的MAC地址、H2收到的封装P的以太网帧的源MAC地址分别是
A. 00-1a-2b-3c-4d-62, 00-1a-2b-3c-4d-52
B. 00-1a-2b-3c-4d-62, 00-a1-b2-c3-d4-61
C. 00-1a-2b-3c-4d-51, 00-1a-2b-3c-4d-52
D. 00-1a-2b-3c-4d-51, 00-a1-b2-c3-d4-61
答案
答案：D
计算机网络
2018-38
某路由表中有转发接口相同的4条路由表项，其目的网络地址分别为35.230.32.0/21，35.230.40.0/21，35.230.48.0/21和35.230.56.0/21，将该4条路由聚合后的目的网络地址为
A. 35.230.0.0/19
B. 35.230.0.0/20
C. 35.230.32.0/19
D. 35.230.32.0/20
答案
答案：C
计算机网络
2018-39
UDP协议实现分用（demultiplexing）时所依据的头部字段是
A. 源端口号
B. 目的端口号
C. 长度
D. 校验和
答案
答案：B
计算机网络
2018-40
无须转换即可由SMTP协议直接传输的内容是
A. JPEG图像
B. MPEG视频
C. EXE文件
D. ASCII文本
答案
答案：D
数据结构
2018-41
给定一个含 n（n≥1）个整数的数组，请设计一个在时间上尽可能高效的算法，找出数组中未出现的最小正整数。例如，数组 {-5,3,2,3} 中未出现的最小正整数是 1；数组 {1,2,3} 中未出现的最小正整数是 4。
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。
答案
【答案】
（1）算法基本设计思想：采用空间换时间策略，使用标记数组B（大小为n）记录数组A中是否出现了1到n之间的正整数。遍历A，若元素值在1到n内，则标记B中对应位置；否则忽略。然后遍历B，找到第一个未标记的位置（值为0），返回该位置索引加1即为结果；若B全部标记，则结果为n+1。因为未出现的最小正整数必然在1到n+1之间。
（2）算法实现（C语言）：
int findMissingPositive(int A[], int n) {
int i, j, a;
int B[n];
// 手动初始化数组
for (j = 0; j < n; j++) {
B[j] = 0;
}
// 标记存在的正整数
for (i = 0; i < n; i++) {
if (A[i] > 0 && A[i] <= n) {
a = A[i];
B[a - 1] = 1;
}
}
// 寻找第一个未标记的位置
for (i = 0; i < n; i++) {
if (B[i] == 0) break;
}
return i + 1;
}关键注释：标记数组B用于记录1到n的出现情况，遍历A标记有效值，遍历B找首个未标记项，索引加1得结果。
（3）复杂度分析：
- 时间复杂度：O(n)，其中遍历A和B各一次，每次操作为O(1)。
- 空间复杂度：O(n)，额外使用标记数组B，大小为n。
数据结构
2018-42
拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市，题 42 图中无向边上的权值表示两个城市间备选光纤的铺设费用。
请回答下列问题。
（1）仅从铺设费用角度出发，给出所有可能的最经济的光纤铺设方案（用带权图表示），并计算相应方案的总费用。
（2）题 42 图可采用图的哪种存储结构？给出求解问题（1）所使用的算法名称。
（3）假设每个城市采用一个路由器按（1）中得到的最经济方案组网，主机 H1 直接连接在 TL 的路由器上，主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL = 5 的 IP 分组，则 H2 是否可以收到该 IP 分组？
答案
（1）题图如下。所有可能的最经济方案为最小生成树，共有两种方案，总费用均为16。
（2）存储结构可采用邻接矩阵或邻接表；求解算法为Prim算法或Kruskal算法。
（3）在方案1中，TL与BJ间距离过长，TTL=0时会丢弃数据报无法到达，H2不能收到分组；在方案2中，TL与BJ相邻，最短路径长度为1，H2可以收到分组。
组成原理
2018-43
假定计算机的主频为 500MHz，CPI 为 4。现有设备 A 和 B，其数据传输率分别为 2MB/s 和 40MB/s，对应 I/O 接口中各有一个 32 位数据缓冲寄存器。请回答下列问题，要求给出计算过程。
（1）若设备 A 采用定时查询 I/O 方式，每次输入/输出都至少执行 10 条指令。设备 A 最多间隔多长时间查询一次才能不丢失数据？CPU 用于设备 A 输入/输出的时间占 CPU 总时间的百分比至少是多少？
（2）在中断 I/O 方式下，若每次中断响应和中断处理的总时钟周期数至少为 400，则设备 B 能否采用中断 I/O 方式？为什么？
（3）若设备 B 采用 DMA 方式，每次 DMA 传送的数据块大小为 1000B，CPU 用于 DMA 预处理和后处理的总时钟周期数为 500，则 CPU 用于设备 B 输入/输出的时间占 CPU 总时间的百分比最多是多少？
答案
答案：
（1）设备 A 最多间隔 2 µs 查询一次；CPU 用于设备 A 输入/输出的时间占 CPU 总时间的百分比至少为 4%。
（2）设备 B 不能采用中断 I/O 方式，因为设备 B 准备数据的时间（0.1 µs）小于中断响应和处理时间（0.8 µs），数据可能丢失。
（3）CPU 用于设备 B 输入/输出的时间占 CPU 总时间的百分比最多为 4%。
组成原理
2018-44
某计算机采用页式虚拟存储管理方式，按字节编址。CPU 进行存储访问的过程如题 44 图所示。
根据题 44 图回答下列问题。
（1）主存物理地址占多少位？
（2）TLB 采用什么映射方式？TLB 是用 SRAM 还是用 DRAM 实现？
（3）Cache 采用什么映射方式？若 Cache 采用 LRU 替换算法和回写（Write Back）策略，则 Cache 每行中除数据（Data）、Tag 和有效位外，还应有哪些附加位？Cache 的总容量是多少？Cache 中有效位的作用是什么？
（4）若 CPU 给出的虚拟地址为 0008 C040H，则对应的物理地址是多少？是否在 Cache 中命中？说明理由。若 CPU 给出的虚拟地址为 0007 C260H，则该地址所在主存块映射到的 Cache 组号是多少？
答案
（1）主存物理地址占28位。
（2）TLB采用全相联映射方式；TLB用SRAM实现。
（3）Cache采用2路组相联映射方式；附加位有LRU位和修改位（脏位）；Cache总容量为4464位（558字节）；有效位的作用是指示Cache行中的数据是否有效。
（4）物理地址为0040040H；不命中，因为该地址对应的Cache组（组号2）中标志字段匹配但有效位为0；虚拟地址0007C260H所在主存块映射到的Cache组号为3。
操作系统
2018-45
请根据题 44 图给出的虚拟存储管理方式，回答下列问题。
（1）某虚拟地址对应的页目录号为6，在相应的页表中对应的页号为6，页内偏移量为8，该虚拟地址的十六进制表示是什么？
（2）寄存器PDBR用于保存当前进程的页目录起始地址，该地址是物理地址还是虚拟地址？进程切换时，PDBR的内容是否会变化？说明理由。同一进程的线程切换时，PDBR的内容是否会变化？说明理由。
（3）为了支持改进型CLOCK置换算法，需要在页表项中设置哪些字段？
答案
（1）该虚拟地址的十六进制表示为01806008H。
（2）PDBR保存的是页目录的物理基地址，因此是物理地址。进程切换时，PDBR的内容会变化，因为不同进程的地址空间和页目录不同。同一进程的线程切换时，PDBR的内容不会变化，因为线程共享进程的地址空间和页目录。
（3）需要设置访问位（使用位）和修改位（脏位）。
操作系统
2018-46
某文件系统采用索引节点存放文件的属性和地址信息，簇大小为 4KB。每个文件索引节点占 64B，有 11 个地址项，其中直接地址项 8 个，一级、二级和三级间接地址项各 1 个，每个地址项长度为 4B。请回答下列问题。
（1）该文件系统能支持的最大文件长度是多少？（给出计算表达式即可。）
（2）文件系统用 1M（1M=220）个簇存放文件索引节点，用 512M 个簇存放文件数据。若一个图像文件的大小为 5600B，则该文件系统最多能存放多少个图像文件？
（3）若文件F1的大小为6KB，文件F2的大小为40KB，则该文件系统获取F1和F2最后一个簇的簇号需要的时间是否相同？为什么？
答案
（1）最大文件长度为：
(8+1024+10242+10243)×4 KB
其中，一个 4 KB 索引块可保存 4 KB/4 B=1024 个索引项。
（2）最多能存放 64 M 个图像文件。
（3）不相同。
因为获取 F1（6KB）最后一个簇号只需访问索引节点的直接地址项；而获取 F2（40KB）最后一个簇号还需读取一级间接索引表，增加磁盘访问次数，故时间不同。
计算机网络
2018-47
（7分）某公司的网络如题47图所示。IP地址空间192.168.1.0/24被均分给销售部和技术部两个子网，并已分别为部分主机和路由器接口分配了IP地址，销售部子网的MTU = 1500B，技术部子网的MTU = 800B。
请回答下列问题。
（1）销售部子网的广播地址是什么？技术部子网的子网地址是什么？若每个主机仅分配一个IP地址，则技术部子网还可以连接多少台主机？
（2）假设主机192.168.1.1向主机192.168.1.208发送一个总长度为1500B的IP分组，IP分组的头部长度为20B，路由器在通过接口F1转发该IP分组时进行了分片。若分片时尽可能分为最大片，则一个最大IP分片封装数据的字节数是多少？至少需要分为几个分片？每个分片的片偏移量是多少？
答案
（1）
- 销售部子网的广播地址：192.168.1.127
- 技术部子网的子网地址：192.168.1.128
- 技术部子网还可以连接的主机数：45台
（2）
- 一个最大IP分片封装数据的字节数：776B
- 至少需要分为2个分片
- 每个分片的片偏移量：第一个为0，第二个为97