2019 408错题

1

设n是描述问题规模额非负整数，下列程序段的时间复杂度是
x=0；
while（n>(x+1)*(x+1)）
x=x+1;
O(n^1/2)

循环变量的初值不会影响复杂度的量级，所以循环终止条件可以等效于
x^2<=n,
即x<=n^1/2;
所以时间复杂度为 O(n^1/2)

2

对n个互不相同的符号进行哈夫曼树编码。若生成的哈夫曼树共有115个结点，则n的值是
其实这道题可以举例，如果n为2呢？就是有a和b两个符号，那么哈夫曼树共有3个节点。

3

在任意一棵非空平衡二叉树（AVL树）T1中，删除某节点v之后形成的平衡二叉树T2，再将v插入T2形成平衡二叉树T3.下列关于T1与T3的叙述中，正确的是

平衡二叉树，平衡因子小于等于1
若是丢失了叶节点导致平衡因子失衡，则树不同
若丢失的不是叶节点，那么树有可能变也有可能不变。

4

在带权有向图中，以顶点表示事件，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称AOE网。
AOE网和AOV网都是有向无环图，不同之处在于他们的边和顶点所代表的含义是不同的，AOE网中的边有权值，而AOV网中的边无权值，仅表示顶点之间的前后关系。

AOE网具有以下两个性质：
1：只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始。
2：只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。

在AOE网中，从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。

事件v的最早发生时间：它是指从源点到顶点v的最长路径长度。
事件v的最迟发生时间：它是指在不推迟整个工程完成的前提下，即保证它的后续事件v在其最迟发生时间v能够发生时，该事件最迟必须发生的时间。

5

现有长度为11且初始为空的散列表HT，散列函数是H（key）=key%7，采用线性探查（线性探测再散列）法解决冲突。将关键字序列87，40，30，6，11，22，98，20依次插入到HT后，HT查找失败的平均查找长度是 6

开放定址法，指可存放新表项的空闲地址既向它的同义词表项开放，又向它的非同义词表项开放

拉链法：显然，对于不同的关键字可能会通过散列函数映射到同一地址，为了避免非同义词发生冲突，可以把所有的同义词存储在一个线性链表中，这个线性链表由散列函数唯一地址标识。假设散列地址为i的同义词链表的头指针存放在散列表的第i个单元中，因而查找，插入和删除操作主要在同义词链中进行。拉链法适用于经常进行插入和删除的情况。

从散列表的查找过程可见：
1：虽然散列表在关键字与记录的存储位置之间建立了直接映像，但由于“冲突”的产生，使得散列表的查找过程仍然是一个给定值和关键字进行比较的过程。因此，仍需要以平均查找长度作为衡量散列表的查找效率的度量。
2：散列表的查找效率取决于三个因素：散列函数，处理冲突的方法和装填因子。
装填因子。散列表中的装填因子一般记为a，定义为一个表的装满程度，即
a=表中记录数n/散列表长度m

直观的看，a越大，表示装填的记录越“满”，发生冲突的可能性越大，反之发生冲突的可能性越小。

6

设主串T=“abaabaabcabaabc”，模式串S=“abaabc”，采用KMP算法进行模式比较，到匹配成功时为止，在匹配过程中单个字符间的比较次数为

KMP算法是暴力匹配的升级版
在暴力匹配中，每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀，这种频繁的重复比较相当于模式串在不断的进行自我比较，这就是其低效率的根源。因此，可以从分析模式本身的结构着手，如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀，那么就可以将模式向后滑动到与这些相等字符对齐的位置，主串i指针无需回溯，并从该位置开始继续比较。而模式向后滑动位数的计算仅与模式本身的结构有关，与主串无关。

前缀：指除去最后一个字符外，字符串的所有头部子串；
后缀：指除去第一个字符外，字符串的所有尾部字串；
部分匹配值：字符串的前缀和后缀的最长相等前后缀长度。
由部分匹配值可以得到PM（Partial Match），即部分匹配值。
abaabc，以它为例
编号 0 1 2 3 4 5
PM 0 0 1 1 2 0

某趟发生失配时，如果对应的部分匹配值为0，那么表示已匹配相等序列中没有相等的前后缀，此时的移动位数最大，直接将子串首字符后移到主串i位置进行下一趟比较；如果已匹配相等序列中存在最大相等前后缀（可理解为首尾重合），那么将子串向右滑动到和该相等前后缀对齐（这部分字符下一趟显然不需要比较），然后从主串i位置进行下一趟比较。

但这样还是有些麻烦，再将其改进得到next数组；

公式：移动位数=已匹配的字符数-对应的部分匹配值
写成：Move=（j-1）-PM（j-1）
使用部分匹配值时，每当匹配失败，就去找它前一个元素的部分匹配值，这样使用起来有些不方便，所以将PM表右移一位，这样哪个元素匹配失败，直接看它自己的部分匹配值即可。
这样就得到了next数组
编号 0 1 2 3 4 5
PM 0 0 1 1 2 0
next -1 0 0 1 1 2
我们注意到：
1：第一个元素右移以后空缺的用-1来填充，因为若是第一个元素就匹配失败，则需要将子串右移一位，而不需要计算子串移动的位数。
2：最后一个元素在右移时溢出，因为原来的子串中，最后一个元素的部分匹配值是其下一个元素使用的，但显然已没有下一个元素，故可以舍去。
这样，上式就改写为
Move=（j-1）-next[j]
相当于将字串的比较指针j回退到
j=j-Move=next[j]+1。
为了计算简单方便，便将next数组整体+1。

next[j]的含义是：在子串的第j个字符与主串发生失配时，则跳到子串的next[j]位置重新与主串当前位置进行比较。

尽管普通模式匹配的时间复杂度是O(mn)，KMP算法的时间复杂度是O(m+n)，但在一般情况下，普通模式匹配的实际执行时间近似为O(m+n)，因此至今仍然被采用。KMP算法仅在主串与子串有很多“部分匹配”时才显得比普通算法快得多，其主要优点就是主串不回溯。

7

快速排序
快速排序的基本思想是基于分治法的：在待排序表L[1…n]中任取一个元素pivot作为枢轴，通过一趟排序将待排序表划分为独立的两部分L[1…k-1]和L[k+1…n]，使得L[1…k-1]中的所有元素小于pivot，L[k+1…n]中的所有元素大于等于pivot，则pivot放在了其最终位置L(k)上，这个过程称为一趟快速排序，然后分别递归地对两个子表重复上述过程，直到每部分内只有一个元素或空为止，即所有元素放在了其最终位置上。
正常情况下，快速排序第二趟有3个元素在最终位置上，除非第一趟确定的是最大值或者最小值。

8

设外存上有120个初始归并段，进行12路归并时，为实现最佳归并，需要补充的虚段个数是 2
“归并”的含义是将两个或两个以上的有序表组合成一个新的有序表。

Merge()的功能是将前后相邻的两个有序表归并为一个有序表。
Merge()操作中，辅助空间刚好为n个单元，所以算法的空间复杂度为O(n)
时间效率：每趟归并的时间复杂度为O(n)，共需要进行log2n上取整趟归并，所以算法的时间复杂度为O(nlog2n)。
稳定性：由于Merge（）操作不会改变相同关键字记录的相对次序，所以稳定。

9

考虑以下C语言代码：
unsigned short usi = 65535;
short si =usi;

有一点很重要，就是数值在计算机内部是以补码的形式存在。

10

某计算机采用大端方式，按字节编址。某指令中操作数的机器数为1234 FF00H，该操作数采用基址寻址方式，形式地址（用补码表示）为FF12H，基址寄存器内容为F000 0000H，则该操作数的LSB（最低有效字节）所在的地址是

基址寻址：基址寻址是指将CPU中基址寄存器（BR）的内容加上指令格式中的形式地址A而形成操作数的有效地址，即EA=（BR）+A。其中基址寄存器既可采用专用寄存器，又可采用通用寄存器。

基址寄存器是面向操作系统的，其内容由操作系统或管理程序确定，主要用于解决程序逻辑空间与存储器物理空间的无关性。在程序执行过程中，基址寄存器的内容不变（作为基地址），形式地址可变（作为偏移量）。采用通用寄存器作为基址寄存器时，可由用户决定哪个寄存器作为基址寄存器，但其内容范围仍由操作系统决定。
基址寻址的优点是可以扩大寻址范围（基址寄存器的位数大于形式地址A的位数）；用户不必考虑自己的程序存于主存的哪个空间区域，因此有利于多道程序设计，并可用于编制浮动程序。

1111 1111 0001 0010 补求原
0000 0000 1110 1101 + 1
0000 0000 1110 1110
再加上基址寄存器内容。
F000 0000H + 00EEH

11

某指令功能为R[r1]+M[R[r0]] —>R[r2],其两个源操作数分别采用寄存器，寄存器间接寻址方式。
寄存器寻址是指在指令字中直接给出操作数所在的寄存器编号，即EA=Ri，其操作数在由Ri所指的寄存器内。在这一过程中要用到通用寄存数组。
优点是指令执行阶段不访问主存，只访问寄存器，因寄存器数量较少，对应地址码长度较小，使得指令字短且因不用访存，所以执行速度快，支持向量/矩阵运算；缺点是寄存器价格昂贵，计算机中的寄存器个数有限。

寄存器间接寻址是指在寄存器Ri中给出的不是一个操作数，而是操作数所在主存单元的地址，即EA=（Ri）。
与一般间接寻址相比速度更快，但需访存一次。在这一过程中要用到存储器。

指令译码器应该在译码阶段执行。

12

数据冒险：当指令在流水线重叠执行时，后面的指令需要用到前面的指令的执行结果，而前面的指令尚未写回导致的数据冒险，也称数据相关性。

写后读相关。
取值IF 译码/取数ID 执行EX 访存MEM 写回WB

13

假定一台计算机采用三通道存储器总线，配套的内存条型号为DDR3-1333，即内存条所接插的存储器总线的工作频率为1333MHz，总线宽度为64位，则存储器总线的总带宽大约是：
381333MB/s 差不多就是32GB/S。

14

某设备以中断方式与CPU进行数据交换，CPU主频为1GH在z，设备接口中的数据缓冲寄存器为32位，设备的数据传输率位50kB/S。若每次中断开销（包括中断响应和中断处理）为1000个时钟周期，则CPU用于该设备输入/输出的时间占整个CPU时间的百分比最多是

50kB/4B = 12.5k
12.5k*1000/10^9 =1.25%

15

DMA
DMA方式是一种完全由硬件进行成组信息传送的控制方式，它具有程序中断方式的优点，，即在数据准备阶段，CPU与外设并行工作。DMA方式在外设和内存之间开辟一条“直接数据通道”，信息传送不再经过CPU，降低了CPU在传送数据时的开销，因此称为直接存储器存取方式。由于数据传送不经过CPU，也就不需要保护，恢复CPU现场等繁琐操作。
这种方式适用于磁盘机，磁带机等高速设备大批量数据的传送，它的硬件开销比较大。在DMA方式中，中断的作用仅限于故障和正常传送结束时的处理。

DMA方式特点
1：它使主存与CPU的固定联系脱钩，主存既可被CPU访问，又可被外设访问。
2：在数据块传送时，主存地址的确定，传送数据的计数等都由硬件电路直接实现。
3：主存中要开辟专用缓冲区，及时供给和接受外设的数据。
4：DMA传送速度快，CPU与外设并行工作，提高了系统效率。
5：DMA在传送开始前要通过程序进行预处理，结束后要通过中断方式进行后处理。

DMA控制器的组成：
在DMA方式中，对数据传送过程进行控制的硬件称为DMA控制器（DMA接口）。当I/O设备需要进行数据传送时，通过DMA控制器向CPU提出DMA传送请求，CPU响应之后让出系统总线，由DMA控制器接管总线进行数据传送。
主要功能1：接受外设发出的DMA请求，并向CPU发出总线请求。
2：CPU响应此总线请求，发出总线响应信号，接管总线控制权，进入DMA操作周期。
3：确定传送数据的主存地址单元，接管总线控制权，进入DMA操作周期。
4：确定数据在主存和外设间的传送方向，发出读写等控制信号，执行数据传送操作。
5：向CPU报告DMA操作的结束。

DMA的传送方式：

DMA方式与中断方式的区别：
1：中断方式是程序的切换，需要保护和恢复现场；而DMA方式除了预处理和后处理，其他时候不占用CPU的任何资源。
2：对中断请求的响应只能发生在每条指令执行完毕时（即指令的执行周期后）；而对DMA请求的响应可以发生在每个机器周期结束时（在取值周期，间指周期，执行周期后均可），只要CPU不占用总线就可被响应。
3：中断传送过程需要CPU的干预；而DMA传送过程不需要CPU的干预，因此数据传送率非常高，适合于高速外设的成组数据传送。
4：DMA请求的优先级高于中断请求；
5：中断方式拥有对异常事件的处理能力，而DMA方式仅局限于传送数据块的I/O操作。
6：从数据传送来看，中断方式靠程序传送，DMA靠硬件传送。

16

线程
应用程序没有进行线程管理的代码，只有一个到内核级线程的编程内部接口，内核为进程及其内部的每个线程维护上下文信息，调度也是在内核中由操作系统完成的。
在多线程模型中，用户级线程和内核级线程的连接方式分为多对一，一对一，一对多，操作系统为每个用户进程建立一个线程控制块，属于一对一模型。
用户级线程的切换可以在用户空间内完成，内核级线程的切换需要操作系统帮忙进行调度，故用户级线程的切换效率更高。
用户级线程的管理工作可以只在用户空间中进行，故可以在不支持内核级线程的操作系统上实现。
进程的目的时更好地使多道程序并发执行，提高资源利用率和系统吞吐量；而引入线程的目的是减少程序在并发执行时所付出的时空开销，提高操作系统的并发性能。
线程是一个基本的CPU执行单元，也是程序执行流的最小单元，由线程ID，程序计数器，寄存器集合和堆栈组成。线程是被系统独立调度和分派的基本单位，线程自己不拥有系统资源，只拥有一点在运行中必不可少资源，但它可与同属一个进程的其他线程共享所拥有的全部资源。
一个线程可以创建和撤销另一个线程，同一个进程的多个线程之间可以并发执行。
进程是拥有资源的基本单位，线程是独立调度的基本单位。

每个线程都拥有一个唯一的标识符和一个线程控制块，线程控制块记录了线程执行的寄存器和栈等现场状态。

不同的线程可以执行相同的程序，即同一个服务程序被不同的用户调用时，操作系统把它们创建成不同的线程。

在单CPU的计算机系统内，各线程可交替的占用CPU；在多CPU的计算机系统中，各线程可同时占用不同的CPU，若各个CPU同时为一个进程内的各线程服务，则可缩短进程的处理时间。

17

传统的文件系统管理空闲磁盘的方法包括空闲表法，空闲链表法，成组链接法。
文件分配表FAT的表项与物理磁盘块一一对应，并且可以用一个特殊的数字-1表示文件的最后一块，用-2表示这个磁盘块是空闲的，因此FAT不仅记录了文件中各个块的先后链接关系，同时还标记了空闲的磁盘块，操作系统可以通过FAT对文件存储空间进行管理。
索引节点：索引节点是操作系统为了实现文件名和文件信息分开而设计的数据结构，存储了文件描述信息，索引节点属于文件目录管理部分的内容。

18

系统采用二级反馈队列调度算法进行进程调度。就绪队列Q1采用时间片轮转调度算法，时间片为10ms；就绪队列Q2采用短进程优先调度算法；系统优先调度Q1队列中的进程，当Q1为空时系统才会调度Q2中的进程；新创建的进程优先进入Q1；Q1中的进程执行一个时间片后，若未结束，则转入Q2.若当前Q1，Q2为空，系统依次创建进程P1，P2后即开始进程调度，P1，P2需要的CPU时间分别为30ms，20ms，则进程P1，P2在系统中的平均等待时间是。
P1进入Q1，10ms过去，P1转入Q2；剩余20ms
P2在10ms后进入Q1执行，10ms后进入Q2；剩余20ms
P1等待10ms，再等待10msP2完成。
P2等待10ms
平均的等待时间15ms

19

物理层：
物理层的任务就是为它的上一层提供一个物理连接，以及他们的机械，电气，功能，过程特性。
数据链路层：
数据链路层负责在两个相邻线路的节点上，无差错的传输以帧为单位的数据，每一帧包括一定量的数据和一些必要的控制信息。
建立逻辑链接，进行硬件地址寻址，差错校验
网络层：
进行逻辑地址寻址，实现不同网络间的路由选择。
传输层：
定义传输数据的协议端口号，以及流控和差错校验。
会话层，建立，管理，终止会话
表示层：
数据的表示，安全，压缩。
应用层：
确定进程间通信的性质以满足用户需要，提供网络与用户应用服务之间的接口服务。

21

假设一个采用CSMA/CD协议的100Mbps局域网，最小帧长是128B，则在一个冲突域内两个站点之间的单向传播延时最多是
5.12us。
为了确保发送站在发送数据的同时能检测到可能存在的冲突，需要在能发送完帧之前就能收到自己发送出去的数据，帧的传播时延至少要两倍于信号在总线中的传播时延。所以CSMA/CD总线网中的所有数据帧都必须要大于一个最小帧长，这个最小帧长=总线传播时延数据传输速率2。
已知最小帧长为128B，传输速率为12.5MB/S，
128/12.5=10.24us
10.24/2 =5.12us

22

若将101.200.16.0/20划分为5个子网，则可能的最小子网的可分配IP地址数是
11111111 11111111 11110000 00000000
101.200.00010000 00000000
其他子网尽可能大，只需考虑后面的12位即可
0000 00000000-01111 11111111第一位为0
1000 00000000-1011 11111111第一位为1，第二位为0
1100 00000000-1101 11111111，第一位为1，第二位为1，第三位为0
1110 00000000-1110 111111111，第一位为1，第二位为1，第三位为1，第四位为0
1111 00000000-1111 10000000 ，第一位为1，第二位为1，第三位为1，第四位为1，第五位为0 在第五个子网中，共有七位可变
除去全0和全1，共有254条IP地址。

23

100BaseT是一种速率100Mbps工作的局域网标准，它通常被称为快速以太网标准，并使用两队UTP（非屏蔽双绞线）铜质电缆。
Base表示基带传输
T表示传输介质为双绞线，F表示传输介质为光纤。