数据结构
2019-01
设n是描述问题规模的非负整数，下列程序段的时间复杂度是__。
x = 0;
while (n >= (x + 1) * (x + 1))
x = x + 1;A. O(logn)
B. O(n^{1/2})
C. O(n)
D. O(n^2)
答案
答案：B
当前显示 47 道题
单题查看 1
数据结构
2019-02
若将一棵树T转化为对应的二叉树BT，则下列对BT的遍历中，其遍历序列与T的后根遍历序列相同的是__。
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 按层遍历
答案
答案：B
数据结构
2019-03
对n个互不相同的符号进行哈夫曼编码。若生成的哈夫曼树共有115个结点，则n的值是__。
A. 56
B. 57
C. 58
D. 60
答案
答案：C
数据结构
2019-04
在任意一棵非空平衡二叉树（AVL 树）T1 中，删除某结点 v 之后形成平衡二叉树 T2，再将 v 插入 T2 形成平衡二叉树 T3。下列关于 T1 与 T3 的叙述中，正确的是__。
I. 若 v 是 T1 的叶结点，则 T1 与 T3 可能不相同
II. 若 v 不是 T1 的叶结点，则 T1 与 T3 一定不相同
III. 若 v 不是 T1 的叶结点，则 T1 与 T3 一定相同
A. 仅I
B. 仅II
C. 仅I、II
D. 仅I、III
答案
答案：A
数据结构
2019-05
下图所示的AOE网表示一项包含8个活动的工程。活动d的最早开始时间和最迟开始时间分别是__。
A. 3和7
B. 12和12
C. 12和14
D. 15和15
答案
答案：C
数据结构
2019-06
用有向无环图描述表达式((x+y)*((x+y)/x))，需要的顶点个数至少是__。
A. 5
B. 6
C. 8
D. 9
答案
答案：A
数据结构
2019-07
选择一个排序算法时，除算法的时空效率，下列因素中，还需要考虑的是__。
I. 数据的规模
II. 数据的存储方式
III. 算法的稳定性
IV. 数据的初始状态
A. 仅III
B. 仅I、II
C. 仅II、III、IV
D. I、II、III、IV
答案
答案：D
数据结构
2019-08
现有长度为11且初始为空的散列表 HT，散列函数是 H(key) = key % 7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列 87,40,30,6,11,22,98,20 依次插入 HT 后，HT查找失败的平均查找长度是__。
A. 4
B. 5.25
C. 6
D. 6.29
答案
答案：C
数据结构
2019-09
设主串 T = "abaabaabcabaabc"，模式串 S = "abaabc"，采用 KMP 算法进行模式匹配，到匹配成功时为止，在匹配过程中进行的单个字符间的比较次数是__。
A. 9
B. 10
C. 12
D. 15
答案
答案：B
数据结构
2019-10
排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一“趟”。下列序列中，不可能是快速排序第二趟结果的是__。
A. 5, 2, 16, 12, 28, 60, 32, 72
B. 2, 16, 5, 28, 12, 60, 32, 72
C. 2, 12, 16, 5, 28, 32, 72, 60
D. 5, 2, 12, 28, 16, 32, 72, 60
答案
答案：D
数据结构
2019-11
设外存上有 120 个初始归并段，进行 12 路归并时，为实现最佳归并，需要补充的虚段个数是__。
A. 1
B. 2
C. 3
D. 4
答案
答案：B
组成原理
2019-12
下列关于冯·诺依曼结构计算机基本思想的叙述中，错误的是__。
A. 程序的功能都通过中央处理器执行指令实现
B. 指令和数据都用二进制数表示，形式上无差别
C. 指令按地址访问，数据都在指令中直接给出
D. 程序执行前，指令和数据需预先存放在存储器中
答案
答案：C
组成原理
2019-13
考虑以下 C 语言代码：
unsigned short usi = 65535;
short si = usi;
执行上述程序段后，si 的值是__。
A. -1
B. -32767
C. -32768
D. -65535
答案
答案：A
组成原理
2019-14
下列关于缺页处理的叙述中，错误的是__。
A. 缺页是在地址转换时 CPU检测到的一种异常
B. 缺页处理由操作系统提供的缺页处理程序来完成
C. 缺页处理程序根据页故障地址从外存读入所缺失的页
D. 缺页处理完成后回到发生缺页的指令的下一条指令执行
答案
答案：D
组成原理
2019-15
某计算机采用大端方式，按字节编址。某指令中操作数的机器数为 1234 FF00H，该操作数采用基址寻址方式，形式地址（用补码表示）为 FF12H，基址寄存器的内容为 F000 0000H，则该操作数的 LSB（最低有效字节）所在的地址是__。
A. F000 FF12H
B. F000 FF15H
C. EFFF FF12H
D. EFFF FF15H
答案
答案：D
组成原理
2019-16
下列有关处理器时钟脉冲信号的叙述中，错误的是__。
A. 时钟脉冲信号由机器脉冲源发出的脉冲信号经整形和分频后形成
B. 时钟脉冲信号的宽度称为时钟周期，时钟周期的倒数为机器主频
C. 时钟周期以相邻状态单元间组合逻辑电路的最大延迟为基准确定
D. 处理器总是在每来一个时钟脉冲信号时就开始执行一条新的指令
答案
答案：D
组成原理
2019-17
某指令功能为 R[r2]←R[r1] + M[R[r0]]，其两个源操作数分别采用寄存器、寄存器间接寻址方式。对于下列给定部件，该指令在取数及执行过程中需要用到的是__。
I. 通用寄存器组（GPRs） II. 算术逻辑单元（ALU）
III. 存储器（Memory） IV. 指令译码器（ID）
A. 仅I、II
B. 仅I、II、III
C. 仅II、III、IV
D. 仅I、III、IV
答案
答案：B
组成原理
2019-18
在采用“取指、译码/取数、执行、访存、写回”5段流水线的处理器中，执行如下指令序列，其中s0、s1、s2、s3和t2表示寄存器编号。
I1: add s2, s1, s0 //R[s2]←R[s1]+R[s0]
I2: load s3, 0(t2) //R[s3]←M[R[t2]+0]
I3: add s2, s2, s3 //R[s2]←R[s2]+R[s3]
I4: store s2, 0(t2) //M[R[t2]+0]←R[s2]
下列指令对中，不存在数据冒险的是__。
A. I1和I3
B. I2和I3
C. I2和I4
D. I3和I4
答案
答案：C
组成原理
2019-19
假定一台计算机采用3通道存储器总线，配套的内存条型号为DDR3-1333，即内存条所接插的存储器总线的工作频率为1333MHz，总线宽度为64位，则存储器总线的总带宽大约是__。
A. 10.66GB/s
B. 32GB/s
C. 64GB/s
D. 96GB/s
答案
答案：B
组成原理
2019-20
下列关于磁盘存储器的叙述中，错误的是__。
A. 磁盘的格式化容量比非格式化容量小
B. 扇区中包含数据、地址和校验等信息
C. 磁盘存储器的最小读写单位为一字节
D. 磁盘存储器由磁盘控制器、磁盘驱动器和盘片组成
答案
答案：C
组成原理
2019-21
某设备以中断方式与CPU进行数据交换，CPU主频为1GHz，设备接口中的数据缓冲寄存器为32位，设备的数据传输率为50kB/s。若每次中断开销（包括中断响应和中断处理）为1000个时钟周期，则CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多是__。
A. 1.25%
B. 2.5%
C. 5%
D. 12.5%
答案
答案：A
组成原理
2019-22
下列关于DMA方式的叙述中，正确的是__。
I. DMA传送前由设备驱动程序设置传送参数
II. 数据传送前由DMA控制器请求总线使用权
III. 数据传送由DMA控制器直接控制总线完成
IV. DMA传送结束后的处理由中断服务程序完成
A. 仅I、II
B. 仅I、III、IV
C. 仅II、III、IV
D. I、II、III、IV
答案
答案：D
操作系统
2019-23
下列关于线程的描述中，错误的是__。
A. 内核级线程的调度由操作系统完成
B. 操作系统为每个用户级线程建立一个线程控制块
C. 用户级线程间的切换比内核级线程间的切换效率高
D. 用户级线程可以在不支持内核级线程的操作系统上实现
答案
答案：B
操作系统
2019-24
下列选项中，可能会将进程唤醒的事件是__。
I. I/O结束 II. 某进程退出临界区 III. 当前进程的时间片用完
A. 仅I
B. 仅III
C. 仅I、II
D. I、II、III
答案
答案：C
操作系统
2019-25
下列关于系统调用的叙述中，正确的是__。
I. 在执行系统调用服务程序的过程中，CPU处于内核态
II. 操作系统通过提供系统调用避免用户程序直接访问外设
III. 不同的操作系统为应用程序提供了统一的系统调用接口
IV. 系统调用是操作系统内核为应用程序提供服务的接口
A. 仅 I、IV
B. 仅 II、III
C. 仅 I、II、IV
D. 仅 I、III、IV
答案
答案：C
操作系统
2019-26
下列选项中，可用于文件系统管理空闲磁盘块的数据结构是__。
I. 位图 II. 索引结点 III. 空闲磁盘块链 IV. 文件分配表（FAT）
A. 仅 I、II
B. 仅 I、III、IV
C. 仅 I、III
D. 仅 II、III、IV
答案
答案：B
操作系统
2019-27
系统采用二级反馈队列调度算法进行进程调度。就绪队列 Q1 采用时间片轮转调度算法，时间片为10ms；就绪队列 Q2 采用短进程优先调度算法；系统优先调度 Q1 队列中的进程，当 Q1 为空时系统才会调度 Q2 中的进程；新创建的进程首先进入 Q1；Q1 中的进程执行一个时间片后，若未结束，则转入 Q2。若当前 Q1、Q2 为空，系统依次创建进程 P1、P2 后即开始进程调度，P1、P2 需要的 CPU 时间分别为30ms 和 20ms，则进程 P1、P2 在系统中的平均等待时间为__。
A. 25ms
B. 20ms
C. 15ms
D. 10ms
答案
答案：C
操作系统
2019-28
在分段存储管理系统中，用共享段表描述所有被共享的段。若进程 P1 和 P2 共享段 S，下列叙述中，错误的是__。
A. 在物理内存中仅保存一份段 S 的内容
B. 段 S 在 P1 和 P2 中应该具有相同的段号
C. P1 和 P2 共享段 S 在共享段表中的段表项
D. P1 和 P2 都不再使用段 S 时才回收段 S 所占的内存空间
答案
答案：B
操作系统
2019-29
某系统采用 LRU 页置换算法和局部置换策略，若系统为进程 P 预分配了 4 个页框，进程 P 访问页号的序列为 0, 1, 2, 7, 0, 5, 3, 5, 0, 2, 7, 6，则进程访问上述页的过程中，产生页置换的总次数是__。
A. 3
B. 4
C. 5
D. 6
答案
答案：C
操作系统
2019-30
下列关于死锁的叙述中，正确的是__。
I. 可以通过剥夺进程资源解除死锁
II. 死锁的预防方法能确保系统不发生死锁
III. 银行家算法可以判断系统是否处于死锁状态
IV. 当系统出现死锁时，必然有两个或两个以上的进程处于阻塞态
A. 仅 II、III
B. 仅 I、II、IV
C. 仅 I、II、III
D. 仅 I、III、IV
答案
答案：B
操作系统
2019-31
某计算机主存按字节编址，采用二级分页存储管理，地址结构如下所示：
[页目录号（10 位） | 页号（10 位） | 页内偏移（12 位）]
虚拟地址 2050 1225H 对应的页目录号、页号分别是__。
A. 081H、101H
B. 081H、401H
C. 201H、101H
D. 201H、401H
答案
答案：A
操作系统
2019-32
在下列动态分区分配算法中，最容易产生内存碎片的是__。
A. 首次适应算法
B. 最坏适应算法
C. 最佳适应算法
D. 循环首次适应算法
答案
答案：C
计算机网络
2019-33
OSI参考模型的第5层（自下而上）完成的主要功能是__。
A. 差错控制
B. 路由选择
C. 会话管理
D. 数据表示转换
答案
答案：C
计算机网络
2019-34
100BaseT快速以太网使用的导向传输介质是__。
A. 双绞线
B. 单模光纤
C. 多模光纤
D. 同轴电缆
答案
答案：A
计算机网络
2019-35
对于滑动窗口协议，若分组序号采用3比特编号，发送窗口大小为5，则接收窗口最大是_。
A. 2
B. 3
C. 4
D. 5
答案
答案：B
计算机网络
2019-36
假设一个采用CSMA/CD协议的10Mb/s局域网，最小帧长是128B，则在一个冲突域内两个站点之间的单向传播延时最多是_。
A. 2.56μs
B. 5.12μs
C. 10.24μs
D. 20.48μs
答案
答案：B
计算机网络
2019-37
若将101.200.16.0/20划分为5个子网，则可能的最小子网的可分配IP地址数是_。
A. 126
B. 254
C. 510
D. 1022
答案
答案：B
计算机网络
2019-38
某客户通过一个 TCP 连接向服务器发送数据的部分过程如题 38 图所示。客户在 t0 时刻第一次收到确认序列号 ack_seq=100 的段，并发送序列号 seq=100 的段，但发生丢失。若 TCP 支持快速重传，则客户重新发送 seq=100 段的时刻是__。
A. t1
B. t2
C. t3
D. t4
答案
答案：C
计算机网络
2019-39
若主机甲主动发起一个与主机乙的TCP连接，甲、乙选择的初始序列号分别为2018和2046，则第三次握手TCP段的确认序列号是_。
A. 2018
B. 2019
C. 2046
D. 2047
答案
答案：D
计算机网络
2019-40
下列关于网络应用模型的叙述中，错误的是_。
A. 在P2P模型中，结点之间具有对等关系
B. 在客户/服务器（C/S）模型中，客户与客户之间可以直接通信
C. 在C/S模型中，主动发起通信的是客户，被动通信的是服务器
D. 在向多用户分发一个文件时，P2P模型通常比C/S模型所需的时间短
答案
答案：B
数据结构
2019-41
设线性表 L=(a1,a2,a3,…,an-2,an-1,an) 采用带头结点的单链表保存，链表中的结点定义如下：
typedef struct node {
int data;
struct node *next;
} NODE;请设计一个空间复杂度为 O(1) 且时间上尽可能高效的算法，重新排列 L 中的各结点，得到线性表 L'=(a1,an,a2,an-1,a3,an-2,…)。要求：
1）给出算法的基本设计思想。
2）根据设计思想，采用 C 或 C++ 语言描述算法，关键之处给出注释。
3）说明所设计算法的时间复杂度。
答案
（1）先用快、慢指针找到链表中点，再原地逆置后半段，最后将前半段和逆置后的后半段交替合并。
（2）一种实现如下：
void reorderList(node *h) {
node *p, *q, *r, *s;
p = q = h;
while(q->next != NULL) { // 找到中间结点
p = p->next;
q = q->next;
if(q->next != NULL) {
q = q->next;
}
}
q = p->next;
p->next = NULL;
while(q != NULL) { // 后半部分原地逆置
r = q->next;
q->next = p->next;
p->next = q;
q = r;
}
s = h->next;
q = p->next;
p->next = NULL;
while(q != NULL) { // 逐个插入结点
r = q->next;
q->next = s->next;
s->next = q;
s = q->next;
q = r;
}
}（3）时间复杂度为 O(n)，空间复杂度为 O(1)。函数名与参数按测试文档统一为 reorderList(node *h)。
数据结构
2019-42
请设计一个队列，要求满足：①初始时队列为空；②入队时，允许增加队列占用空间；③出队后，出队元素所占用的空间可重复使用，即整个队列所占用的空间只增不减；④入队操作和出队操作的时间复杂度始终保持为 O(1)。请回答下列问题：
(1) 该队列是应选择链式存储结构，还是应选择顺序存储结构？
(2) 画出队列的初始状态，并给出判断队空和队满的条件。
(3) 画出第一个元素入队后的队列状态。
(4) 给出入队操作和出队操作的基本过程。
答案
（1）选择链式存储结构，用单向循环链表保存队列，设置队头指针 front 和队尾指针 rear。
（2）初始时只建立一个空闲结点，front 和 rear 均指向该结点。
- 队空：
front == rear - 队满：
front == rear->next
（3）第一个元素入队后，将元素写入 rear 所指结点，再令 rear = rear->next。
（4）基本操作：
入队 EnQueue(e)：
if (front == rear->next) { // 队满
在 rear 后插入一个新的空闲结点;
}
rear->data = e;
rear = rear->next;
return;
出队 DeQueue(e)：
if (front == rear) { // 队空
return ERROR;
}
e = front->data;
front = front->next;
return OK;入队、出队的时间复杂度均为 O(1)。
组成原理
2019-43
有 n（n≥3）位哲学家围坐在一张圆桌边，每位哲学家交替地就餐和思考。在圆桌中心有 m（m≥1）个碗，每两位哲学家之间有一根筷子。每位哲学家必须取到一个碗和两侧的筷子后，才能就餐，进餐完毕，将碗和筷子放回原位，并继续思考。为使尽可能多的哲学家同时就餐，且防止出现死锁现象，请使用信号量的 P、V 操作 [wait()、signal()操作] 描述上述过程中的互斥与同步，并说明所用信号量及初值的含义。
答案
设互斥信号量 chopstick[i]（初值均为 1）表示第 i 根筷子，信号量 bowl 表示允许同时取碗进餐的哲学家数，其初值为 min(m,n-1)。
semaphore chopsticks [n];
for (int i=0; i<n;i++)
chopsticks [i]=1;
bowl=min (n-1,m) ;
Pi:
while (true) {
think;
P(bowl);
P(chopstick[i]);
P(chopstick[(i+1) % n]);
eat;
V(chopstick[i]);
V(chopstick[(i+1) % n]);
V(bowl);
}这样既尽可能多地允许哲学家同时就餐，又保证至少有一位哲学家能够取得两根筷子，避免死锁。
组成原理
2019-44
某计算机系统中的磁盘有 300 个柱面，每个柱面有 10 个磁道，每个磁道有 200 个扇区，扇区大小为 512B。文件系统的每个簇包含 2 个扇区。请回答下列问题：
(1) 磁盘的容量是多少？
(2) 假设磁头在 85 号柱面上，此时有 4 个磁盘访问请求，簇号分别为 100 260、60 005、101 660 和 110 560。若采用最短寻道时间优先（SSTF）调度算法，则系统访问簇的先后次序是什么？
(3) 第 100 530 簇在磁盘上的物理地址是什么？将簇号转换成磁盘物理地址的过程是由 I/O 系统的什么程序完成的？
答案
（1）磁盘容量为 300×10×200×512 B=3×105 KB。
（2）SSTF 访问顺序为：100260、101660、110560、60005。
（3）每柱面含 10×200/2=1000 个簇，因此第 100530 簇位于 100 号柱面；柱面内偏移为 530 个簇，即 1060 个扇区，对应 5 号磁头、60 号扇区。簇号到磁盘物理地址的转换由磁盘驱动程序完成。
操作系统
2019-45
已知 f(n) = n! = n×(n-1)×(n-2)×…×2×1，计算 f(n) 的 C 语言函数 f1 的源程序（阴影部分）及其在 32 位计算机 M 上的部分机器级代码如下：
其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令，计算机M按字节编址，int型数据占32位。请回答下列问题：
（1）计算 f(10) 需要调用函数 f1 多少次？执行哪条指令会递归调用 f1?
（2）上述代码中，哪条指令是条件转移指令？哪几条指令一定会使程序跳转执行？
（3）根据第 16 行的 call 指令，第 17 行指令的虚拟地址应是多少？已知第 16 行的 call 指令采用相对寻址方式，该指令中的偏移量应是多少（给出计算过程）？已知第 16 行的 call 指令的后 4 字节为偏移量，M 是采用大端方式还是采用小端方式?
（4）f(13) = 6227020800，但 f1(13) 的返回值为 1932053504，为什么两者不相等？要使 f1(13) 能返回正确的结果，应如何修改 f1 的源程序?
（5）第 19 行的 imul 指令（带符号整数乘）的功能是 R[eax]←R[eax]×R[ecx]，当乘法器输出的高、低 32 位乘积之间满足什么条件时，溢出标志 OF=1? 要使 CPU 在发生溢出时转异常处理，编译器应在 imul 指令后应加一条什么指令？
答案
（1）计算 f(10) 共调用 f1 10 次；第 16 行 call 指令递归调用 f1。
（2）第 12 行 jle 是条件转移指令；第 16 行 call、第 20 行 jmp 和第 30 行 ret 一定使程序跳转。
（3）第 17 行地址为 0040102AH。偏移量为
00401000H-0040102AH=FFFFFFD6H，机器码中的存放顺序为 D6 FF FF FF，因此 M 采用小端方式。
（4）int 型只能表示 [-231,231-1]，而 f(13)=6\,227\,020\,800>231-1，因此发生溢出。可将形参、局部变量和返回值改为 double（或足够宽的整数类型）。
（5）若 64 位乘积的高 32 位不是低 32 位的符号扩展，则 OF=1。编译器应在 imul 后加入溢出自陷指令，使 CPU 在 OF=1 时转入溢出异常处理程序。
操作系统
2019-46
对于题45，若计算机M的主存地址为32位，采用分页存储管理方式，页大小为4KB，则第1行的 push 指令和第30行的 ret 指令是否在同一页中（说明理由）？若指令Cache有64行，采用4路组相联映射方式，主存块大小为64B，则32位主存地址中，哪几位表示块内地址？哪几位表示Cache组号？哪几位表示标记（tag）信息？读取第16行的call指令时，只可能在指令Cache的哪一组中命中（说明理由）？
答案
第 1 行 push 的地址为 00401000H，第 30 行 ret 的地址为 0040104AH，两者的高 20 位页号相同，因此在同一页中。
指令 Cache 有 64 行、4 路组相联，共 16 组；主存块大小为 64 B。因此 32 位地址中：
- 第 0～5 位：块内地址；
- 第 6～9 位：Cache 组号；
- 第 10～31 位：标记。
第 16 行 call 地址为 00401025H，其组号字段为 0000，只可能在第 0 组命中。
计算机网络
2019-47
某网络拓扑如题47图所示，其中 R 为路由器，主机 H1～H4 的 IP 地址配置以及 R 的各接口 IP 地址配置如图中所示。现有若干以太网交换机（无 VLAN 功能）和路由器两类网络互连设备可供选择。
请回答下列问题：
（1）设备 1、设备 2和设备 3 分别应选择什么类型的网络设备？
（2）设备 1、设备 2和设备 3 中，哪几个设备的接口需要配置 IP 地址？为对应的接口配置正确的 IP 地址。
（3）为确保主机 H1～H4 能够访问 Internet，R 需要提供什么服务？
（4）若主机 H3 发送一个目的地址为 192.168.1.127 的 IP 数据报，网络中哪几个主机会接收该数据报？
答案
（1）设备 1 选择路由器；设备 2、设备 3 选择以太网交换机。
（2）只有设备 1 的接口需要配置 IP 地址：
- IF1：
192.168.1.254 - IF2：
192.168.1.1 - IF3：
192.168.1.65
（3）R 需要提供 NAT（网络地址转换）服务。
（4）192.168.1.127 是 LAN2 的广播地址，只有同一子网中的 H4 会接收该数据报。