2017 408选择题错题

1

下列函数的时间复杂度是
int func(int n){
int i = 0,sum = 0;
while(sum < n)
sum += ++i;
return i;
}
sum += ++i;等于
sum = sum + ++i;
sum=0,i=0;sum=0+1=1；
sum=1+2=3;sum=3+3=6;sum=6+4=10;
sum=10+5=15;sum=15+6=21;
不是O（n），
当n为1时，执行1次；
当n为2时，sum执行两次；
当n为3时，sum执行两次；
当n为4时，sum执行三次；
当n为5时，sum执行三次；
当n为6时，sum执行三次；
当n为7时，sum执行四次；
8，4
9，4
经过以上分析可以知道：
进行到第k趟循环的时候
sum=0+1+2+3+4+5+。。。+k
=（1+k）*k/2
所以时间复杂度为O(n^1/2)
这种思路真的很巧妙，而且举例子的办法也失效了，需要记住

2

所谓邻接矩阵存储，是指用一个一维数组存储图中顶点的信息，用一个二维数组存储图中边的信息（即各顶点之间的邻接关系），存储顶点之间邻接关系的二维数组称为邻接矩阵。
邻接矩阵空间复杂度为O（n^2），不适合存储稀疏矩阵。

结点数为n的图G=（V，E）的邻接矩阵A是n*n的，将G的顶点编号为v1，v2，v3，v4。若vi，j是图的一条边，则A [ i ] [ j ]=1，否则=0；
图的邻接矩阵表示法具有如下特点：
1：无向图的邻接矩阵一定是一个对称矩阵（并且唯一）。因此，在实际存储邻接矩阵时只需存储上（或下）三角矩阵的元素。
2：对于无向图，邻接矩阵的第i行（或第i列）非零元素的个数正好是顶点i的度TD（vj）
3：对于有向图，邻接矩阵的第i行非零元素的个数正好是顶点i的出度，第i列非零元素的个数正好是顶点i的入度。
4：用邻接矩阵存储图，很容易确定图中任意两个顶点之间是否有边相连。但是，要确定图中有多少条边，则必须按行，按列对每个元素进行检测，所花费的时间代价很大。
5：稠密图适合使用邻接矩阵的存储表示

十字链表是有向图的一种链式存储结构。在十字链表中，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点。
弧结点
tailvex，headvex，hlink，tlink，info
尾域（tailvex）和头域（headvex）分别指示弧尾和弧头这两个顶点在图中的位置；
链域hlink指向弧头相同的下一条弧，链域tlink指向弧尾相同的下一条弧；
info域指向该弧的相关信息。
这样，弧头相同的弧就在同一个链表上；
弧尾相同的弧也在同一个链表上。

3折半查找判定树

折半查找判定树是折半查找过程中产生的树，它有几个特性
（1）折半查找判定树一定是平衡树
（2）当表中元素为偶数个时，那么折半产生的子表中，必然会出现两种情况：前子表比后子表多一个元素或者后子表比前子表多一个元素，并且所有子树都应该有这种结构。
（3）当表中元素个数为奇数个时，那么折半所产生的子表中，只会产生一种情况，即前后子表元素个数相同，且所有字数都应该有这种结构。

对于B选项，它有11个元素，对于结点1，左子树元素有1个，右子树元素有0个，那么所有的左子树元素都应该比右子树元素要多，但是看看结点7，左子树结点为0个，右子树结点为1个，明显不对。
对于D选项，看看节点5，左子树结点有4个，右子树结点有5个，很明显应该是一个左子树结点比右子树结点多的结构，但看看结点9，左右子树居然结点数一样，这就出问题了。

4

下列排序方法中，若将顺序存储更换为链式存储，则算法的时间复杂度会降低的是 插入排序，选择排序，起泡排序，希尔排序，堆排序。
希尔排序和堆排序不适合使用链表

顺序存储相较于链式存储好的地方在于可以随机访问链表元素。
堆排序需要构建二叉树，如果是顺序存储，则只需访问数组就可以；可若是链式存储，需要不断的找左孩子右孩子，速度就慢了。

希尔排序首先需要划分几个数据组，比如一共有四个元素，第1个和第3个是一组，这就需要不断地查找后续元素。

插入排序只需要顺次的使用下一个元素。
选择排序也不需要寻找两个距离很远的元素。
起泡排序只需比较两个相邻的元素。这三个都可以使用链表存储。

5

某计算机主存按字节编址，由4个64M*8位的DRAM芯片采用交叉编制方式构成，并与宽度为32位的存储器总线相连，主存每次最多读写32位数据。若double型变量x的主存地址为804 001AH，则读取x所需的主存周期是

交叉编制：
高位交叉，各个体并行工作
高位地址可表示体号，地位地址为体内地址。按这种方式，只要合理调动，使不同的请求源同时访问不同的体，便可实现并行工作。例如，当一个体正与CPU交换信息时，另一个体可同时与外部设备进行直接存储器访问，实现两个体并行工作。这种编制方式由于一个体内的地址是连续的，有利于存储器的扩充。
低位交叉 各个体轮流编址
由于程序连续存放在相邻体中，故又有交叉存储之称。低位地址用来表示体号，高位地址为体内地址。这种编制方式又称为模M编址。一般模块取2的方幂，使硬件电路比较简单。有的机器为了减少存储器冲突，采取质数个模块。
低位交叉编制又称为横向编制，连续的地址分布在相邻的存储体中，而同一存储体内的地址都是不连续的。存储器地址寄存器的低位部分经过译码选择不同的存储体，而高位部分则指向存储体内的存储字。如果采用分时启动的办法，可以在不改变每个存储体周期的前提下，提高整个主存的速度。

由4个DRAM芯片采用交叉编制方式构成主存地址最低二位表示该字节存储的芯片编号。double型变量占64位，8个字节。它的主存地址804 001A最低二位是10，说明它从编号位2的芯片开始存储（编号从零开始），一个存储周期可以对所有芯片各读取一个字节。
不是按边界对齐，所以读取8B的数据需要三个存储周期

6

变址寻址：变址寻址是指有效地址EA等于指令字中的形式地址A与变址寄存器IX的内容之和，即EA=(IX)+A，其中IX为变址寄存器，也可用通用寄存器作为变址寄存器。
变址寄存器是面向用户的，在程序执行过程中，变址寄存器的内容可由用户改变，形式地址A不变。
变址寄存器的优点是可扩大寻址范围（变址寄存器的位数大于形式地址A的位数）；在数组处理过程中，可设定A为数组的首地址，不断改变变址寄存器IX的内容，便可很容易形成数组中任意数据的地址，特别适合编制循环程序。偏移量（变址寄存器IX）的位数足以表示整个存储空间。
显然，变址寻址与基址寻址的有效地址形成过程极为相似。但从本质上来讲，两者有较大区别。基址寻址面向系统，主要用于为多道程序或数据分配存储空间，因此基址寄存器的内容通常由操作系统或管理程序确定，在程序的执行过程中其值不可变，而指令字A是可变的。
变址寻址立足于用户，主要用于处理数组问题，在变址寻址中，变址寄存器的内容由用户设定，在程序执行过程中其值可变，而指令字的A是不可变的。

7

某计算机按字节编址，指令字固定且只有两种指令格式，其中三地址指令29条，二地址指令107条，每个地址字段为6位，则指令字长至少应该是 24位
三地址指令有29条，所以它的操作码至少为5位。以5位进行计算，它剩余32-29=3种操作码给二地址。而二地址另外多了6位给操作吗，因此它的数量最大达3*64=192.所以指令字长最少为32位，因为计算机按字节编址，需要是8的倍数，所以指令字长至少应该是24位。

8

超标量流水线
每个时钟周期内可并发多条独立指令，即以并行操作方式将两条或多条指令编译并执行。为此需配置多个功能部件。
超标量计算机不能调账指令的执行顺序，因此通过编译优化技术，把可并行执行的指令搭配起来，挖掘更多的指令并行性。
超标量是指在CPU中有一条以上的流水线，并且每个时钟周期内可以完成一条以上的指令，其实质是以空间换时间，它不影响流水线功能段的处理时间。

9

指令流水线数据通路
数据在功能部件之间传送的路径称为数据通路。路径上的部件称为数据通路部件，如ALU，通用寄存器，状态寄存器，异常和中断处理逻辑等。数据通路描述了信息从什么地方开始，中间经过哪个寄存器或多路开关，最后传送到哪个寄存器，这些都需要加以控制。
数据通路中专门进行数据运算的部件称为执行部件或者功能部件。数据通路由控制部件控制，控制部件根据每条指令功能的不同生成对数据通路的控制信号，并正确控制指令的执行流程。数据通路的功能是实现CPU内部的运算器与寄存器及寄存器之间的数据交换。

1：CPU内部单总线方式：将所有寄存器的输入端和输出端都连接到一条公共通路上，这种结构比较简单，但数据传输存在较多的冲突现象，性能较低。连接各部件的总线只有一条时，称为单总线结构
2：CPU内部三总线方式。将所有寄存器的输入端和输出端都连接到多条公共通路上，相比之下但单总线中一个时钟内只允许传一个数据，因而指令执行效率低，因此采用多总线方式，同时在多个总线上传输不同的数据，提高效率。
3：专用数据通路方式。根据指令执行过程中的数据和地址的流动方向安排连接线路，避免使用共享的总线，性能较高，但硬件量大。

10

多总线结构用速率高的总线连接高速设备，用速率低的总线连接低速设备。一般来说，CPU是计算机的核心，是计算机中速度最快的设备之一，所以靠近CPU的总线速度最快。
突发传送方式把多个数据单元作为一个独立传输处理，从而最大化设备的吞吐量。现实中一般用支持突发传送方式的总线提高存储器的读写效率。
各总线使用桥接器相连，后者起流量交换作用。
PCI-Express总线都采用串行数据包传输数据。

11

系统调用，是指用户在程序中调用操作系统所提供的一些子功能。系统调用可视为特殊的公共子程序，系统中的各种资源都由操作系统统一掌管，因此在用户程序中，凡是与资源有关的操作（如分配存储，进行I/O传输以及管理文件等），都必须通过系统调用方式向操作系统提出服务请求，并由操作系统代为完成。
设备管理：完成设备的请求或释放，以及设备启动等功能。
文件管理：完成文件的读，写，创建以及删除等功能。
进程控制：完成进程的创建，撤销，阻塞及唤醒等功能。
进程通信：完成进程之间的消息传递或信号传输等功能。
内存管理：完成内存的分配，回收以及获取作业占用内存区大小及始址等功能。
显然，系统调用相关功能涉及系统资源管理，进程管理之类的操作，需要特权指令。
从核心态向用户态由一条指令实现，这条指令也是特权指令，一般是中断返回指令。‘若进程的运行由用户态转到核心态，则会用到访管指令，该指令不是特权指令，在用户态使用。

12

绝大多数操作系统为改善磁盘访问时间，以簇为单位进行空间分配。

13

磁盘初始化：一个的磁盘只是一个含有磁性记录材料的空白盘。在磁盘能存储数据之前，它必须分为扇区以便磁盘控制器能进行读和写操作，这个过程称为低级格式化（物理分区）。低级格式化为磁盘的每个扇区采用特殊的数据结构。每个扇区的数据结构通常由头，数据区域和尾部组成。头部和尾部包含了一些磁盘控制器所使用的信息。
为了使用磁盘存储文件，操作系统还需将自己的数据结构记录在磁盘上：第一步将磁盘分为一个或多个煮面组成的分区（即我们熟悉的c盘，d盘等形式的分区）；第二步对物理分区进行逻辑格式化（创建文件系统），操作系统将初始的文件系统数据结构存储在磁盘上，这些数据结构包括空闲和已分配的空间及一个初始为空的目录。

14

IEEE802.11
对于有固定基础设施的无线局域网，IEEE制定了无线局域网的802.11系列协议标准。
802.11标准规定无线局域网的最小构件是基本服务集BBS，一个基本服务集包括一个基站和若干个移动站。所有的站在本BBS内都可以直接通信，但在和本BBS外的站通信时都必须通过本BBS的基站。
IEEE802.11数据帧有4种子类型，分别是IBSS，From AP，To AP，WDS

AP是Access Point，又称接入点。AP就是基本服务集中的基站，安装AP时，必须为该AP分配一个不超过32字节的服务集标识符和一个信道。一个基本服务集覆盖的地理位置称为一个基本服务区，无线局域网的基本服务区的直径一般不超过100M。
RA（receiver address）无线网络中，该数据帧的接收者
TA（transmitter address）无线网络中，该数据帧的发送者
DA（destine address）该帧的目的MAC地址
SA（source address）该帧的源MAC地址

IBSS（independent basic service set）独立基本服务集

15

RIP，OSPF，BGP
自治系统（Autonomous System，AS），单一技术管理下的一组路由器，这些路由器使用一种AS内部的路由选择协议和共同的度量来确定分组在该AS内的路由，同时还使用一种AS之间的路由选择协议来确定分组在AS之间的路由。

内部网关协议（Interior Gateway Protocol，IGP）
内部网关协议即在一个自治系统内部使用的路由选择协议，它与互联网中其他自治系统选用什么路由选择协议无关。目前这类路由选择协议使用得最多，如RIP和OSPF。
外部网关协议（External Gateway Protocal，EGP）
若源站和目的站处在不同的自治系统中，当数据报传到一个自治系统得边界时，就需要使用一种协议将路由选择信息传递到另一个自治系统中。这样的协议就是外部网关协议。

路由信息协议（Routing Information Protocal，RIP）是内部网关协议（IGP）中最先得到广泛应用的协议。RIP是一种分布式得基于距离向量得路由选择协议，其最大优点就是简单。

RIP规定：
1：网络中的每个路由都要维护从它自身到其他每个目的网络的距离记录（因此这是一组距离，成为距离向量）
2：距离也称为跳数（Hop Count），规定从一个路由器到直接相连网络的距离（跳数）为1.而每经过一个路由器，距离（跳数）就加1.
3：RIP认为好的路由就是它通过的路由器的数目少，即优先选择跳数少的路径。
4：RIP允许一条路径上最多只能包含15个路由器（即最多允许15跳），因此距离等于16时，表示不可达。可见RIP只适用于小型互联网。距离向量路由可能会出现环路的情况，规定路径上的最高跳数的目的是为了防止数据报不断循环在环路上，减少网络拥塞的可能性。
5：RIP默认在任意两个使用RIP的路由器之间每30秒广播一次RIP路由更新信息，以便自动建立并维护路由表（动态维护）。
6：在RIP中不支持子网掩码的RIP广播，所以RIP中每个网络的子网掩码必须相同。
UDP封装RIP，IP封装OSPF，TCP封装BGP

16

FTP协议功能
1：提供不同种类主机系统（硬，软体系等都可以不同）之间的文件传输能力
2：以用户权限管理的方式提供用户对远程FTP服务器上的文件管理能力
3：以匿名FTP的方式提供共用文件共享的能力。
工作步骤：
1：打开熟知端口21（控制端口），使客户进程能够连接上。
2：等待客户进程法连接请求
3：启动从属进程来处理客户进程发来的请求。主进程与从属进程并发执行，从属进程对客户进程的请求处理完毕后即终止。
4：回到等待状态，继续接受其他客户进程的请求。

FTP在工作时使用两个并行的TCP连接：一个是控制连接（端口号21），一个是数据连接（端口号20）。
控制连接：
服务器监听21号端口，等待客户连接，建立在这个端口上的连接成为控制连接，控制连接用来传输控制信息（如连接请求，传送请求等），并且控制信息都以7位ASCII格式传送。FTP客户发出的传送请求，通过控制连接发送给服务器端的控制进程，但控制连接并不用来传送文件。在传输文件时还可以使用控制连接（如发送终止命令），因此控制连接在整个会话期间一直保持打开状态

数据连接。
服务器端的控制进程在接收到FTP客户发来的文件传输请求时，就创建“数据传送进程”和“数据连接”。数据连接用来连接客户端和服务器端的数据传送进程，数据传送进程实际完成文件的传送，在传输完毕后关闭“数据传送连接”并结束运行。

数据连接有两种传输模式：主动模式PORT和被动模式PASV。
PORT模式的工作原理：客户端连接到服务器的21号端口，登陆成功后要读取数据时，客户端随机开放一个端口，并发送给命令告知服务器，服务器收到PORT命令和端口号后，通过20号端口和客户端开放的端口连接，发送数据。
PASV模式的不同点是，客户端要读取数据时，发送PASV命令到服务器，服务器在本地随机开放一个端口，并告知客户端，客户端再连接到服务器开放的端口进行数据传输。