本文学习自：Particle Swarm Optimization in MATLAB - Yarpiz Video Tutorial 与《精通MATLAB智能算法》
 
 
1. 简介：
 
Particle Swarm Optimization ，粒子群优化算法，常用来找到方程的最优解。
 
2. 算法概述：
 
每次搜寻都会根据自身经验（自身历史搜寻的最优地点）和种群交流（种群历史搜寻的最优地点）调整自身搜寻方向和速度。
 
3. 算法优势：
 
相较于传统算法计算速度非常快，全局搜索能力也很强；
PSO对于种群大小不十分敏感，所以初始种群往往设为500-1000，不同初值速度影响也不大；
粒子群算法适用于连续函数极值问题，对于非线性、多峰问题均有较强的全局搜索能力。
 
4. 算法基本原理
 
一个形象的例子：
 
A与B两个小粒子初始时在河的两侧，他们想要找到河最深处。如果A某时刻所在位置的深度比B的浅，A就会像B的方向走，反之亦然。 当A到达Global Minimum（全局最小值）时，B会一直向着A前进，直到在optimum solution（全剧最优解）处汇合。
 
 
4.1 概述
 
从上面的示例中我们得到两个准则，也可以说是每个粒子的必要特性：
 
Communication : 彼此互相通知
Learning : 不停地学习以达最优解
 
数量众多的粒子通过相互的交流与学习，全部粒子最终将汇聚到一点，即问题的解。粒子间相互交流与学习的过程用数学或计算机语言描述为迭代。
 
迭代的意义在于不断寻找更优的值，从理论上来说，如果我们掌握了一种可以不停寻找到更优解答的方法，通过不停的迭代，我们就能够找到最优的答案。
 
 
 
Learning the concept of better is the main problem that an optimizer should solve. Then an optimizer learns the concept of better, it is able to solve any kind of optimuzation.Because the solution of optimization problem is to find the best one . So if we know what is the better, we actually can discover the concept of best.
 
 
4.2 粒子的基本信息
 
 
 
回顾粒子群算法概述：
 每次搜寻都会根据自身经验（自身历史搜寻的最优地点）和种群交流（种群历史搜寻的最优地点）调整自身搜寻方向和速度。
 
 
我们首先聚焦与粒子本身，或许全部粒子研究起来很复杂，但单个粒子的属性是很简单的。
 
首先，每个粒子包含两个基本信息，Position（位置） & Velocity（速度）。
 在粒子群算法的每次迭代中，每个粒子的位置和速度都会更新。
 
我们用$\overrightarrow{X_i(t)}$记录位置
用$\overrightarrow{V_i(t)}$记录方向与速度
 
 
4.3 粒子的个体极值与全局极值
 
 
 
回顾粒子群算法概述：
 每次搜寻都会根据自身经验（自身历史搜寻的最优地点）和种群交流（种群历史搜寻的最优地点）调整自身搜寻方向和速度。
 
 
仅有上述位置与速度两个信息还不够，我们之前提到过，每一个粒子是会学习的。 每个粒子还拥有下面两个信息（每个信息都是一个向量）：
 
 
每一个粒子有它自己的记忆，会记住自己的best position , best experience，即个体极值 （personal best）, 标记为$\overrightarrow{P_i(t)}$
 
 
当前时刻全局的最优解，即全局极值（Common best experience among the members），标记为 $\overrightarrow{g_i(t)}$
 
总结：PSO初始化为一群随机粒子，然后通过迭代找到最优解。在每一次迭代过程中，粒子通过跟踪两个极值来更新自己，一个是粒子本身所找到的最优解，这个解称为个体极值$\overrightarrow{P_i(t)}$；另一个极值是整个种群目前找到的最优解，这个极值是全局极值 $\overrightarrow{g_i(t)}$ 。
 
 
 
4.4 找到新位置
 
根据平行四边形法则，已知个体极值与整体极值，有了新时刻的速度$\overrightarrow{V_i}(t+1)$ ,会得到新的位置$\overrightarrow{X_i}(t+1)$
 
 
状态转移方程：
 
$$\overrightarrow{v_{ij}}(t+1)=w\overrightarrow{v_{ij}}(t)+c_1{r}_1(p_{ij}(t)-\overrightarrow{x_{ij}}(t))+c_2{r}_2(g_j(t)-\overrightarrow{x_{ij}}(t))\text{\hspace{1em}(4-1)}$$
 
$$\overrightarrow{x_{ij}}(t+1)=\overrightarrow{x_{ij}}(t)+\overrightarrow{v_{ij}}(t+1)\text{\hspace{1em}(4-2)}$$
 
其中，$c_1,c_2$为学习因子，也称加速常数（acceleration constant）;
 
$r_1,r_2$，[0,1]范围内的均匀随机数。
 
式(1)右边由三部分组成：
 
第一部分为“惯性(inertia)”或“动量（MOMENTUM）”部分，反映了粒子的运动习惯，代表粒子有维持自己先前速度的趋势。
第二部分为“认知（cognition）”部分，反映了粒子对自身历史经验的记忆，代表粒子由向自身历史最佳位置逼近的趋势。
第三部分为“社会(social)”部分，反映了粒子间协同合作与知识共享的群体历史经验，代表粒子有向群体或领域历史最佳位置逼近的趋势。
 
5. 算法的运行参数
 
PSO算法一个最大的优点是不需要调节太多的参数，但是算法中少数几个参数却直接影响着算法的性能和收敛性。
 
基本粒子群算法有下述7个运行参数需要提前设定：
 
$r$：粒子群算法的种子数，对粒子群算法中种子数值可以随机生成也可以固定位一个初始的数值，要求能涵盖目标函数的范围内。
$m$：粒子群群体大小，即群体中所含个体的数量，一般取为20~40。在变两年比较多的时候可以取100以上较大的数。
$ma{x}_d$：一般为最大迭代次数以最小误差的要求满足的。粒子群算法的最大迭代次数，也是终止条件数。
$r_1,r_2$：两个在[0,1]之间变化的加速度权重系数随机产生。
$c_1,c_2$：加速常数，取随机2左右的值。
$w$：惯性权重产生的。
$v_k,x_k$：一个粒子的速度和位移数值，用粒子群算法迭代出每一组的数值。
 
6. 算法的基本流程
 
初始化粒子群，包括群体规模N，每个粒子的位置$x_i$和速度$v_i$。
计算吗每一个粒子的适应度值$Fit[i]$。
计算每个粒子，用它的适应度值$Fit[i]$和个体极值$p_{best}(i)$比较，如果$Fit[i]>p_{best}(i)$,则用$Fit[i]$替换掉$p_{best}(i)$。
计算每个粒子，用它的适应度值$Fit[i]$和全局极值$g_{best}(i)$比较，如果$Fit[i]>g_{best}(i)$,则用$Fit[i]$替换掉$g_{best}(i)$。
根据式（4-1）和式（4-2）更新粒子的位置$x_i$和速度$v_i$。
如果满足结束条件（误差足够好或到达最大循环次数）退出，否则返回步骤2.
 
7. 手动实现PSO
 
function[xm,fv] = PSO(fitness,N,c1,c2,w,M,D)
% c1,c2：学习因子
% w：惯性权重
% M：最大迭代次数
% D：搜索空间维数
% N：初始化群体个体数目


% 初始化种群的个体（可以在这里限定位置和速度的范围）
format long;
for i = 1:N
    for j=1:D
        x(i,j) = randn; % 随机初始化位置
        v(i,j) = randn; % 随即初始化速度
    end
end


% 先计算各个粒子的适应度，并初始化pi和pg
for i=1:N
    p(i) = fitness(x(i,:));
    y(i,:) = x(i,:);
end 
pg = x(N,:);  % pg为全局最优
for i=1:(N-1)
    if(fitness(x(i,:))<fitness(pg))
        pg = x(i,:);
    end
end


% 进入主要循环，按照公式依次迭代，直到满足精度要求
for t=1:M
    for i=1:N  % 更新速度、位移
        v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:));
        x(i,:)=x(i,:)+v(i,:);
        if fitness(x(i,:)) < p(i)
            p(i)=fitness(x(i,:));
            y(i,:)=x(i,:);
        end
        if p(i) < fitness(pg)
            pg=y(i,:);
        end
    end
    Pbest(t)=fitness(pg);
end


% 输出结果
disp('目标函数取最小值时的自变量：')
xm=pg';
disp('目标函数的最小值为：')
fv=fitness(pg);
 
例1:求解下列函数的最小值：
 
$$f(x)=\sum _{i=1}^{30}{x}_i^2+x_i-6$$
 
function F=fitness(x)
F = 0;
for i = 1:30
    F = F+x(i)^2+x(i)-6;
end
 
输入：
 
x = zeros(1,30);
[xm1,fv1] = PSO(@fitness,50,1.5,2.5,0.5,100,30)
 
 
 
后记：拜托 还有人问显示fitness未定义怎么办，找不到输出结果怎么办？？ 软件入门都没搞定就不要急于求成好吗？
 补入门知识：把手动实现PSO的代码保存为PSO.m，把function F=fitness(x)和后面4行代码保存为fitness.m。 然后再在命令行输入内容。
 
 
9. 自适应权重法
 
function[xm,fv] = PSO_adaptation(fitness,N,c1,c2,wmax,wmin,M,D)
% c1,c2：学习因子
% wmax：惯性权重最大值
% wmin：惯性权重最小值
% M：最大迭代次数
% D：搜索空间维数
% N：初始化群体个体数目


% 初始化种群的个体（可以在这里限定位置和速度的范围）
for i = 1:N
    for j=1:D
        x(i,j) = randn; % 随机初始化位置
        v(i,j) = randn; % 随即初始化速度
    end
end


%先计算各个粒子的适应度，并初始化个体最优解pi和整体最优解pg %
%初始化pi %
for i = 1:N
    p(i) = fitness(x(i,:)) ;
    y(i,:) = x(i,:) ;
end
%初始化pg %
pg = x(N,:) ;
%得到初始的全局最优pg %
for i = 1:(N-1)
    if fitness(x(i,:)) < fitness(pg)
        pg = x(i,:) ;
    end
end
 
%主循环函数，进行迭代，直到达到精度的要求 %
for t = 1:M
    for j = 1:N
        fv(j) = fitness(x(j,:)) ;
    end
    fvag = sum(fv)/N ;
    fmin = min(fv);
    for i = 1:N    %更新函数,其中v是速度向量，x为位置,i为迭代特征
        if fv(i) <= fvag
            w = wmin+(fv(i)-fmin)*(wmax-wmin)/(fvag-fmin) ;   %依据早熟收敛程度和适应度值进行调整
        else
            w = wmax ;
        end
        v(i,:) = w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:)) ;
        x(i,:) = x(i,:)+v(i,:) ;
        if fitness(x(i,:)) < p(i)
            p(i) = fitness(x(i,:)) ;
            y(i,:) = x(i,:) ;
        end
        if p(i) < fitness(pg)
            pg = y(i,:) ;
        end
    end
     Pbest(t) = fitness(pg) ;
end
 
%给出最后的计算结果 %
xm = pg' ;
fv = fitness(pg) ;
 
plot(Pbest)
xlabel('进化次数') ;
ylabel('适应度值') ;
 
例2：用自适应权重法求解函数
 
$$y=\frac{((sin(x_1^2+x_2^2){)}^2-cos(x_1^2+x_2^2)+1)}{((1+0.1\times (x_1^2+x_2^2){)}^2)-0.7}$$
 
其中，粒子数为50，学习因子均为2，惯性权重取值[0.6,0.8]，迭代步数为100.
 
建立目标函数：
 
function y = AdaptFunc(x)
    y = ((sin(x(1)^2+x(2)^2))^2-cos(x(1)^2+x(2)^2)+1)/((1+0.1*(x(1)^2+x(2)^2))^2)-0.7;
end
 
运行：
 
[xm,fv] = PSO_adaptation(@AdaptFunc,50,2,2,0.8,0.6,100,2)
 
 
10.线性递减权重法
 
 function [ xm,fv ] = PSO_lin(fitness,N,c1,c2,wmax,wmin,M,D)
format long ;
%给定初始化条件
% fitness：适应度函数
% N:       初始化种群数目
% c1:      个体最优化学习因子
% c2:      整体最优化学习因子
% wmax:    惯性权重最大值
% wmin:    惯性权重最小值
% M:       最大迭代次数      
% D:       搜索空间的维数
% xm:      最佳个体
% fv:      适应度值
 
%初始化种群个体%
for i = 1:N
    for j = 1:D
        x(i,j) = randn ;  %随机初始化位置
        v(i,j) = randn ;  %随机初始化速度
    end
end
 
%先计算各个粒子的适应度，并初始化个体最优解pi和整体最优解pg %
%初始化pi %
for i = 1:N
    p(i) = fitness(x(i,:)) ;
    y(i,:) = x(i,:) ;
end
%初始化pg %
pg = x(N,:) ;
%得到初始的全局最优pg %
for i = 1:(N-1)
    if fitness(x(i,:)) < fitness(pg)
        pg = x(i,:) ;
    end
end
 
%主循环函数，进行迭代，直到达到精度的要求 %
for t = 1:M
    for i = 1:N    %更新函数,其中v是速度向量，x为位置,i为迭代特征
        w = wmax-(t-1)*(wmax-wmin)/(M-1)
        v(i,:) = w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:)) ;
        x(i,:) = x(i,:)+v(i,:) ;
        if fitness(x(i,:)) < p(i)
            p(i) = fitness(x(i,:)) ;
            y(i,:) = x(i,:) ;
        end
        if p(i) < fitness(pg)
            pg = y(i,:) ;
        end
    end
    Pbest(t) = fitness(pg) ;
end
 
%给出最后的计算结果 %
xm = pg' ;
fv = fitness(pg) ;
 
11. 基于杂交（遗传算法）的算法
 
 function [ xm,fv ] = PSO_breed(fitness,N,c1,c2,w,bc,bs,M,D)
format long ;
%给定初始化条件
% fitness：适应度函数
% N:       初始化种群数目
% c1:      个体最优化学习因子
% c2:      整体最优化学习因子
% w:       惯性权重
% bc:      杂交概率
% bs:      杂交池的大小比率
% M:       最大迭代次数      
% D:       搜索空间的维数
% xm:      最佳个体
% fv:      适应度值
 
%初始化种群个体%
for i = 1:N
    for j = 1:D
        x(i,j) = randn ;  %随机初始化位置
        v(i,j) = randn ;  %随机初始化速度
    end
end
 
%先计算各个粒子的适应度，并初始化个体最优解pi和整体最优解pg %
%初始化pi %
for i = 1:N
    p(i) = fitness(x(i,:)) ;
    y(i,:) = x(i,:) ;
end
%初始化pg %
pg = x(N,:) ;
%得到初始的全局最优pg %
for i = 1:(N-1)
    if fitness(x(i,:)) < fitness(pg)
        pg = x(i,:) ;
    end
end
 
%主循环函数，进行迭代，直到达到精度的要求 %
for t = 1:M
    for i = 1:N    %更新函数,其中v是速度向量，x为位置,i为迭代特征
        v(i,:) = w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:)) ;
        x(i,:) = x(i,:)+v(i,:) ;
        if fitness(x(i,:)) < p(i)
            p(i) = fitness(x(i,:)) ;
            y(i,:) = x(i,:) ;
        end
        if p(i) < fitness(pg)
            pg = y(i,:) ;
        end
        r1 = rand() ;
        if r1 < bc
            numPool = round(bs*N) ;    %杂交池中随机选取numPool个种群%
            PoolX = x(1:numPool,:) ;   %杂交池中的初始杂交父辈位置%
            PoolVX = v(1:numPool,:) ;  %杂交池中的初始杂交父辈速度%
            for i = 1:numPool
                seed1 = floor(rand()*(numPool-1))+1 ;   %得到速度和位置的初始种子%
                seed2 = floor(rand()*(numPool-1))+1 ;
                pb = rand() ;
                childxl(i,:) = pb*PoolX(seed1,:)+(1-pb)*PoolX(seed2,:) ;   %子代的速度和位置计算
                childvl(i,:) = (pb*PoolVX(seed1,:)+pb*PoolVX(seed2,:))*norm(pb*PoolVX(seed1,:))/norm(pb*PoolVX(seed1,:)+pb*PoolVX(seed2,:)) ;
            end
            x(1:numPool,:) = childxl ;
            v(1:numPool,:) = childvl ;
        end
    end
end
 
%给出最后的计算结果 %
xm = pg' ;
fv = fitness(pg) ;
 
12. 基于自然选择
 
 function [xm,fv]=PSO_nature(fitness,N,c1,c2,w,M,D)
% fitness：待优化的目标函数;
% N：粒子数目;
% c1：学习因子1;
% c2：学习因子2;
% w：惯性权重;
% M：最大迭代次数;
% D：自变量的个数;
% xm：目标函数取最小值时的自变量值;
% fv：目标函数的最小值。
format long;
for i=1:N
    for j=1:D
        x(i,j)=randn;   %随机初始化位置
        v(i,j)=randn;   %随机初始化速度
    end
end
for i=1:N
    p(i)=fitness(x(i,:));
    y(i,:)=x(i,:);
end
pg=x(N,:);    %pg为全局最优
for i=1:(N-1)
    if fitness(x(i,:))
        pg=x(i,:);
    end
end
for t=1:M
    for i=1:N   %速度、位移更新
        v(i,:)=w*v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg-x(i,:));
        x(i,:)=x(i,:)+v(i,:);
        fx(i)=fitness(x(i,:));
        if fx(i)
            p(i)=fx(i);
            y(i,:)=x(i,:);
        end
        if p(i)
            pg=y(i,:);
        end
    end
    [sortf,sortx]=sort(fx);     %将所有的粒子按适应值排序
    exIndex=round((N-1)/2);
    x(sortx((N-exIndex+1):N))=x(sortx(1:exIndex));%将最好的一半粒子的位置替换掉最差的一半
    v(sortx((N-exIndex+1):N))=v(sortx(1:exIndex));%将最好的一半粒子的速度替换掉最差的一半
end
xm=pg';
fv=fitness(pg);
 
13.基于模拟退火
 
function [xm,fv]=PSO_lamda(fitness,N,c1,c2,lamda,M,D)
% fitness：待优化的目标函数;
% N：粒子数目;
% c1：学习因子1;
% c2：学习因子2;
% lamda:退火常数;
% M：最大迭代次数;
% D：自变量的个数;
% xm：目标函数取最小值时的自变量值;
% fv：目标函数的最小值。
format long;
for i=1:N
    for j=1:D
        x(i,j)=randn;   %随机初始化位置
        v(i,j)=randn;   %随机初始化速度
    end
end
for i=1:N
    p(i)=fitness(x(i,:));
    y(i,:)=x(i,:);
end
pg=x(N,:);    %pg为全局最优
for i=1:(N-1)
    if fitness(x(i,:))
        pg=x(i,:);
    end
end
T=-fitness(pg)/log(0.2);    %初始温度
for t=1:M
    groupFit=fitness(pg);
    for i=1:N           %当前温度下各个pi的适应值
        Tfit(i)=exp(-(p(i)-groupFit)/T);
    end
    SumTfit=sum(Tfit);
    Tfit=Tfit/SumTfit;
    pBet=rand();
    for i=1:N   %用轮盘赌策略确定全局最优的某个替代值
        ComFit(i)=sum(Tfit(1:i));
        if pBet<=ComFit(i)
            pg_plus=x(i,:);
            break;
        end
    end
    C=c1+c2;
   ksi=2/abs(2-C-sqrt(C^2-4*C));  %速度压缩因子
   for i=1:N
       v(i,:)=ksi*(v(i,:)+c1*rand*(y(i,:)-x(i,:))+c2*rand*(pg_plus-x(i,:)));
       x(i,:)=x(i,:)+v(i,:);
       if fitness(x(i,:))
           p(i)=fitness(x(i,:));
           y(i,:)=x(i,:);
       end
       if p(i)
           pg=y(i,:);
       end
   end
   T=T*lamda;
   Pbest(t) = fitness(pg) ;
end   
xm=pg';
fv=fitness(pg);
 
14. MATLAB粒子群工具箱
 
添加工具箱的具体步骤就不在这里说了，网上有很多。
 
例3:计算如下函数的最小值：
 
$$z=0.4\ast (x-2{)}^2+0.3\ast (y-4{)}^2-0.7,x\in [-40,40],y\in [-40,40]$$
 
 
定义待优化的MATLAB代码：
 
function z = pso_func(in)
n = size(in);
x = in(:,1);
y = in(:,2);
nx = n(1);
for i=1:nx
    temp = 0.4*(x(i)-2)^2+0.3*(y(i)-4)^2-0.7;
    z(i,:) = temp;
end
 
 
调用PSO算法的核心函数：pso_Trelea_vectorized
 
clear
clc
x_range = [-40,40];
y_range = [-40,40];
range = [x_range;y_range];
Max_V = 0.2*(range(:,2)-range(:,1));
n = 2;
pso_Trelea_vectorized('pso_func',n,Max_V,range)
 
 
执行即可得到答案。
 
在PSO算法函数pso_Trelea_vectorized173行中，PSO参数设置如下：
 
Pdef = [100 2000 24 2 2 0.9 0.4 1500 1e-25 250 NaN 0 1];
 
100：MATLAB命令窗口进行显示的间隔数
2000：最大迭代次数
24：初始化种子数，种子数越多，越有可能收敛到全局最优值，但算法收敛速度慢
2：算法的加速度参数，分别影响局部最优值和全局最优值，一般不需要修改
0.9和0.4为初始时刻和收敛时刻的加权值，一般不需要修改
1500：迭代次数超过此值时，加权值取其最小
1e-25：算法终止条件之一，当两次迭代中对应的种群最优值小于此阈值时，算法停止
250：算法终止条件之一，取NaN时表示为非约束下的优化问题（即没有附加约束方程）
0：制定采用何种PSO类型，0表示通常的PSO算法
1：说明是否指定种子，0表示随机产生种子，1表示用户自行产生种子

算法是问题求解过程的精确描述，他为解决特定类型的问题规定了一个运算过程，具有下列的特性：
 
1：有穷性。很容易理解这个特性，算法的目的是为了解决问题而设计的，只有执行有穷个步骤之后解决某个问题，并且每一步都要在有穷的时间内完成。
 
2;确定性。算法的每一个步骤必须是有确切定义的，不能有歧义。
 
3：可行性。很容易理解这个特性，算法中每个要进行的运算都能在相应的计算装置所理解和实现。并且可通过有穷次运算完成。
 
4：输入。一个算法有零个或者多个输入，他们是算法所需的初始量或被加工的对象的表示，这些输入取自特定的对象集合。
 
5：输出。一个算法有一个或多个输出，他们是与输出有特定关系的量。

算法设计分析题库一
 
 
 
  大家好，我叫亓官劼（qí guān jié ），在CSDN中记录学习的点滴历程，时光荏苒，未来可期，加油~博客地址为：亓官劼的博客
 
 
 
  
本文原创为亓官劼，请大家支持原创，部分平台一直在盗取博主的文章！！！
 
 
 
 
博主目前仅在CSDN中写博客，唯一博客更新的地址为：亓官劼的博客
 
 
 
 
 
选择题
 

 
下面（C）不是算法所必须具备的特性。
 (A)确切性 (B)有穷性 ©高效性 (D)可行性
 

 

 
算法与程序的区别是（B ）。
 
**A.**输出 **B.**有穷性 **C.**输入 **D.**确定性
 

 

 
解决问题的基本步骤是（D）。

有兴趣的话可以看看其他文章
 
这可能是最简单的C语言单链表入门详解
 计算机组成原理 Cache超仔细详解 期末一遍过
 LeetCode刷题专栏
 蓝桥杯、ACM的一些基础通用模板
 一、单项选择题
 1、下列说法中，错误的是（ B ）
 A.固件功能类似软件，形态类似硬件
 B.寄存器的数据位对微程序级用户透明
 C.软件与硬件具有逻辑功能的等效性
 D.计算机系统层次结构中，微程序属于硬件级
 2、完整的计算机系统通常包括（ A ）
 A.硬件系统与软件系统
 B.运算器、控制器、存储器
 C.主机、外部设备
 D.主机和应用软件
 3、CPU地址线数量与下列哪项指标密切相关（ B ）
 A.运算精确度
 B.内存容量
 C.存储数据位
 D.运算速度
 4、下列属于冯•诺依曼计算机的核心思想是（ C ）
 A.采用补码
 B.采用总线
 C.存储程序和程序控制
 D.存储器按地址访问
 5、计算机中表示地址时使用（ A ）
 A.无符号数
 B.反码
 C.补码
 D.原码
 6、当 -1 < x < 0时， [x]补=（ C ）
 A. x
 B.1-x
 C.2+x
 D.2-x
 7、假设寄存器为8位，用补码形式存储机器数，包括一位符号位，那么十进制数一25在寄存器中的十六进制形式表示为（ C ）
 A.99H
 B.67H
 C.E7H
 D.E6H
 8、如果某系统15*4=112成立，则系统采用的进制是（ C ）
 A.9
 B.8
 C.6
 D.7
 9、某十六进制浮点数A3D00000中最高8位是阶码（含1位阶符），尾数是最低24位（含1位数符），若阶码和尾数均采用补码，则该浮点数的十进制真值是（ A ）
 A.-0.375×2^(-93)
 B.-0.375×2^(-35)
 C. -0.625×2^(-93)
 D.0.625×2^(-35)
 10、存储器中地址号分别为1000#、1001#、1002#、1003的4个连续存储单元，分别保存的字节数据是1A、2B、3C、4D，如果数据字长为32位,存储器采用的是小端对齐模式，则这4个存储单元存储的数据值应被解析为（ A ）
 A.4D3C2B1A
 B.A1B2C3D4
 C.D4C3B2A1
 D.1A2B2C3D
 11、字长8位的某二进制补码整数为11011010，则该数的标准移码是（ B ）
 A.11011010
 B.01011010
 C.00111010
 D.10111010
 12、对于IEEE754格式的浮点数，下列描述正确的是（ D ）
 A.阶码和尾数都用补码表示
 B.阶码用移码表示，尾数用补码表示
 C.阶码和尾数都用原码表示
 D.阶码用移码表示，尾数用原码表示
 13、对字长为8位的二进制代码10001101，下列说法错误的是（ C ）
 A.如果代码为无符号数，则其十进制真值为+141
 B.如果代码为补码数，则其十进制真值为-115
 C.如果代码为标准移码数，则其十进制真值为+115
 D.如果代码为原码数，则其十进制真值为-13
 14、若浮点数的尾数是用5位补码来表示的，则下列尾数中规格化的尾数是（ B ）
 A.01011和11010
 B.10000和01001
 C.01100和11110
 D.11011和01011
 15、若浮点数的尾数是用5位补码来表示(其中符号位1位)，则下列尾数中规格化的尾数是（ B ）
 A.11011和01011
 B.10000和01001
 C.01011和11010
 D.01100和11110
 16、下列关于补码和移码关系的描述中，错误的是（ C ）
 A.同一个数的补码和移码，其数值部分相同，而符号相反
 B.相同位数的补码和移码具有相同的数据表示范围
 C.零的补码和移码相同
 D.一般用移码表示浮点数的阶码，而用补码表示定点数
 17、执行算术右移指令的操作过程是（ C ）
 A.进位标志移至符号位，各位顺次右移1位
 B.操作数的符号位填0，各位顺次右移1位
 C.操作数的符号位不变，各位顺次右移1位，符号位拷贝至最高数据位
 D.操作数的符号位填1，各位顺次右移1位
 18、原码除法是指（ D ）
 A.操作数用补码表示并进行除法，但商用原码表示
 B.操作数用绝对值表示，加上符号位后相除
 C.操作数用原码表示，然后相除
 D.操作数取绝对值相除，符号位单独处理
 19、对8位补码操作数A5H，进行二位算术右移后的十六进制结果为（ C ）H
 A.52
 B.D2
 C.E9
 D.69
 20、在定点二进制运算器中，减法运算一般通过（ D ）来实现
 A.补码运算的二进制减法器
 B.反码运算的二进制加法器
 C.原码运算的二进制减法器
 D.补码运算的二进制加法器
 21、浮点数加减运算过程一般包括对阶、尾数运算、规格化、舍入和判溢出等步骤。设浮点数的阶码和尾数均采用补码表示，且位数分别为5位和7位（均包含2位符号位）。若有两个数X = 2^7 ´ 29/32 ,Y= 2^5 ´ 5/8，则用浮点加法计算X+Y 的最终结果是（ C ）
 A.00111 1100010
 B.01000 0010001
 C.溢出
 D.00111 0100010
 22、 若浮点数用补码表示，则判断运算结果是否为规格化数的方法是（ B ）
 A.阶符与数符相同
 B.数符与尾数小数点后第一位数字相异
 C.阶符与数符相异
 D.数符与尾数小数点后第一位数字相同
 23、在定点运算器中，为判断运算结果是否发生错误，无论采用双符号位还是单符号位，均需要设置（ A ），它一般用异或门来实现
 A.溢出判断电路
 B.编码电路
 C.译码电路
 D.移位电路
 24、已知A=0.1011,B= -0.0101，则[A+B]补 为（ B ）
 A.1.1011
 B.0.0110
 C.1.0110
 D.0.1101
 25、下列说法错误的是（A ）
 A.补码乘法器中，被乘数和乘数的符号都不参加运算
 B.在小数除法中，为了避免溢出，要求被除数的绝对值小于除数的绝对值
 C.并行加法器中虽然不存在进位的串行传递，但高位的进位依然依赖于数据的低位
 D.运算器中通常都有一个状态标记寄存器，为计算机提供判断条件，以实现程序转移
 26、以下关于ALU的描述正确的是（A ）
 A.能完成算术与逻辑运算
 B.不能支持乘法运算
 C.只能完成逻辑运算
 D.只能完成算术运算
 27、在计算机中，对于正数，其三种机器数右移后符号位均不变，但若右移时最低数位丢1，可导致（ B ）
 A.无任何影响
 B.影响运算精度
 C.无正确答案
 D.运算结果出错
 28、CPU可直接访问的存储器是（A ）
 A.主存
 B.磁盘
 C.光盘
 D.磁带
 29、计算机字长32位，主存容量为128MB，按字编址，其寻址范围为（ D ）
 A.0 ~ 128M-1
 B.0 ~ 64M-1
 C.0 ~ 16M-1
 D.0 ~ 32M-1
 30、字位结构为256Kｘ4位SRAM存储芯片，其地址引脚与数据引脚之和为（ B ）
 A.24
 B.22
 C.18
 D.30
 31、某SRAM芯片，存储容量为64K×16位，该芯片的地址线和数据线数目分别为（D ）
 A.64，16
 B.16，64
 C.64 , 64
 D.16，16
 32、假定用若干块4K 4位的存储芯片组成一个8K8位的存储器，则地址0B1F所在芯片的最小地址是（ D ）
 A.0600H
 B.0700H
 C.0B00H
 D.0000H
 33、计算机系统中的存贮器系统是指（B ）
 A.RAM和ROM存贮器
 B.Cache、主存贮器和外存贮器
 C.Cache
 D.磁盘存储器
 34、动态存储器刷新以 （ D ） 为单位进行
 A.字节
 B.存储单元
 C.列
 D.行
 35、下列存储器类型中，速度最快的是（ B ）
 A.Flash Memory
 B.SRAM
 C.DRAM
 D.EPROM
 36、某计算机字长 32位，下列地址属性中属于按双字长边界对齐的是（ B ）
 A.存储器地址线低二位全部为0
 B.存储器地址线低三位全部为0
 C.存储器地址线最低为0
 D.存储器地址线低三位取值随意
 37、在32位的机器上存放0X12345678，假定该存储单元的最低字节地址为0X4000，则在小端存储模式下存在在0X4002单元的内容是（ B ）
 A.0X12
 B.0X34
 C.0X56
 D.0X78
 38、在虚存、内存之间进行地址变换时，功能部件 （ B ）将地址从虚拟（逻辑）地址空间映射到物理地址空间
 A.DMA
 B.MMU
 C.Cache
 D.TLB
 39、在程序执行过程中，Cache与主存的地址映象是由（ A ）
 A.硬件自动完成
 B.操作系统完成
 C.编译系统完成
 D.用户编写程序完成
 40、在 Cache的地址映射中， 若主存中的任意一块均可映射到Cache内任意一行的位置上， 则这种映射方法称为（ B ）
 A.直接映射
 B.全相联映射
 C.2-路组相联映射
 D.混合映射
 41、采用虚拟存储器的主要目的是（ A ）
 A.扩大主存储器的存储空间， 且能进行自动管理和调度
 B.提高主存储器的存取速度
 C.扩大外存储器的存储空间
 D.提高外存储器的存取速度
 42 、虚拟存储器中，程序执行过程中实现虚拟地址到物理地址映射部件（系统）是（ C ）
 A.应用程序完成
 B.编译器完成
 C.操作系统和MMU配合完成
 D.MMU完成
 43、 相联存储器是按( D )进行寻址访问的存储器
 A.地址
 B.队列
 C.堆栈
 D.内容
 44、以下哪种情况能更好地发挥Cache的作用（ C ）
 A.递归子程序
 B.程序的大小不超过内存容量
 C.程序具有较好的时间和空间局部性
 D.程序中存在较多的函数调用
 45、以下关于虚拟存储管理地址转换的叙述中错误的是（ B ）
 A.MMU在地址转换过程中要访问页表项
 B.一般来说，逻辑地址比物理地址的位数少
 C.地址转换是指把逻辑地址转换为物理地址
 D.地址转换过程中可能会发生“缺页”
 46、假定主存按字节编址，cache共有64行，采用4路组相联映射方式，主存块大小为32字节，所有编号都从0开始。问主存第3000号单元所在主存块对应的cache组号是（ A ）
 A.13
 B.29
 C.1
 D.5
 47、下列关于MMU的叙述中，错误的是（ C ）
 A.MMU是存储管理部件
 B.MMU参与虚拟地址到物理地址的转换
 C.MMU负责主存地址到Cache地址的映射
 D.MMU配合使用TLB 地址转换速度更快
 48、下列关于主存与cache地址映射方式的叙述中正确的是（ A ）
 A.在Cache容量相等条件下，组相联方式的命中率比直接映射方式有更高的命中率
 B.直接映射是一对一的映射关系，组相联映射是多对一的映射关系
 C.在Cache容量相等条件下，直接映射方式的命中率比组相联方式有更高的命中率
 D.全相联映射方式比较适用于大容量Cache
 49、下列关于CaChe的说法中，错误的是（ C ）
 A.CaChe行大小与主存块大小一致
 B.分离CaChe(也称哈佛结构)是指存放指令的CaChe与存放数据CaChe分开设置
 C.读操作也要考虑CaChe与主存的一致性问题
 D.CaChe对程序员透明
 50、下列关于CaChe的论述中，正确的是（ B ）
 A.CaChe的容量与主存的容量差距越大越能提升存储系统的等效访问速度
 B.采用直接映射时，CaChe无需使用替换算法
 C.加快CaChe本身速度，比提高CaChe命中率更能提升存储系统的等效访问速度
 D.采用最优替换算法，CaChe的命中率可达到100％
 51、某计算机系统中，CaChe容量为512 KB，主存容量为256 MB，则CaChe 一主存层次的等效容量为（ A ）
 A.256 MB
 B.256 MB - 512 KB
 C.512 KB
 D.256 MB+512 KB
 52、以下四种类型指令中，执行时间最长的是（ C ） (单选)
 A.RS型指令
 B.RR型指令
 C. SS型指令
 D.程序控制类指令
 53、程序控制类指令的功能是（ B ） （单选 ）
 A.进行主存与CPU之间的数据传送
 B.改变程序执行的顺序
 C.进行CPU和I/O设备之间的数据传送
 D.进行算术运算和逻辑运算
 54、下列属于指令系统中采用不同寻址方式的目的主要是（ B ）（单选）
 A.丰富指令功能并降低指令译码难度
 B.缩短指令长度，扩大寻址空间，提高编程灵活性
 C.为了实现软件的兼容和移植
 D.为程序设计者提供更多、更灵活、更强大的指令
 55、寄存器间接寻址方式中，操作数存放在（ C ）中 （单选）
 A.指令寄存器
 B.数据缓冲寄存器MDR
 C.主存
 D.通用寄存器
 56、指令采用跳跃寻址方式的主要作用是（ A ) (单选)
 A.实现程序的有条件、无条件转移
 B.实现程序浮动
 C.实现程序调用
 D.访问更大主存空间
 57、下列寻址方式中，有利于缩短指令地址码长度的是 （ C ） （单选）
 A.间接寻址
 B.直接寻址
 C.隐含寻址
 D.寄存器寻址
 58、假设某条指令的一个操作数采用寄存器间接寻址方式，假定指令中给出的寄存器编号为8，8号寄存器的内容为1200H，地址1200H中的内容为12FCH，地址12FCH中的内容为3888H，地址3888H中的内容为88F9H．则该操作数的有效地址为( A ) (单选)
 A.1200H
 B.88F9H
 C.12FCH
 D.3888H
 59、某计算机按字节编址，采用大端方式存储信息。其中，某指令的一个操作数的机器数为ABCD 00FFH，该操作数采用基址寻址方式，指令中形式地址（用补码表示）为FF00H，当前基址寄存器的内容为C000 0000H，则该操作数的LSB(即该操作数的最低位FFH)存放的地址是( C ) (单选)
 A.C000 FF00H
 B.C000 FF03H
 C.BFFF FF03H
 D.BFFF FF00H
 60 、假定指令地址码给出的是操作数所在的寄存器的编号，则该操作数采用的寻址方式是( D )(单选)
 A.寄存器间接寻址
 B.直接寻址
 C.间接寻址
 D.寄存器寻址
 61 、相对寻址方式中，操作数有效地址通过( A )与指令地址字段给出的偏移量相加得到 (单选)
 A.程序计数器的值
 B.基址寄存器的值
 C.变址寄存器的值
 D.段寄存器的值
 62、下列关于二地址指令的叙述中，正确的是( C ) (单选)
 A.地址码字段一定是操作数
 B.地址码字段一定是操作数的直接地址
 C.运算结果通常存放在其中一个地址码所指向的位置
 D.地址码字段一定是存放操作数的寄存器编号
 63、下列选项中不会直接成为影响指令长度的是( D )(单选)
 A.指令中地址码字段的长度
 B.指令中操作码字段的长度
 C.指令中地址码字段的个数
 D.通用寄存器的位数
 64、通常情况下，不包含在中央处理器(CPU)芯片中的部件是（ C ） （单选）
 A.ALU
 B.控制器
 C.DRAM
 D.寄存器
 65、一定不属于冯•诺依曼机体系结构必要组成部分的是（ B ）（单选）
 A.RAM
 B.Cache
 C.ROM
 D.CPU
 66、 冯•诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU依据（ D ）来区分它们(单选)
 A.指令和数据的地址形式不同
 B.指令和数据的寻址方式不同
 C.指令和数据的表示形式不同
 D.指令和数据的访问时间不同
 67、指令寄存器的位数取决于（ B ）。（单选）
 A.存储字长
 B.指令字长
 C.机器字长
 D.存储器的容量
 68、下列寄存器中，对汇编语言程序员不透明的是（ A ）（单选）
 A.条件状态寄存器
 B.存储器数据寄存器(MDR)
 C.存储器地址寄存器(MAR)
 D.程序计数器(PC)
 69、PC存放的是下一条指令的地址，故PC的位数与（ B ）的位数相同
 A.指令寄存器IR
 B.主存地址寄存器MAR
 C.程序状态字寄存器PSWR
 D.指令译码器ID
 70、在控制器的控制方式中，机器周期内的时钟周期个数可以不相同，这种控制方式属于（ C ）。（单选）
 A.同步控制
 B.联合控制
 C.异步控制
 D.分散控制
 71、下列不属于控制器功能的是（ B ） （单选）
 A.操作控制
 B.算术与逻辑运算
 C.指令的顺序控制
 D.异常控制
 72、当CPU内部cache发生缺失时，CPU如何处理（ A ) (单选)
 A.等待数据载入
 B.进程调度
 C.进行异常处理
 D.执行其他指令
 73、用以指定待执行指令所在主存地址的寄存器是（ D ）。（单选）
 A.数据缓冲寄存器
 B.存储器地址寄存器MAR
 C.指令寄存器IR
 D.程序计数器PC
 74、下列关于微程序和微指令的叙述中（ A ）是正确的。（单选）
 A.微程序控制器比硬连线控制器相对灵活
 B.同一条微指令可以发出互斥的微命令
 C.控制器产生的所有控制信号称为微指令
 D.微程序控制器的速度一般比硬布线控制快
 75某计算机采用微程序控制器的微指令格式采用编码方式组织，某互斥命令组由4个微命令组成，则微指令寄存器中相应字段的位数至少需( D )。 （单选）
 A.2
 B.4
 C.5
 D.3
 76、多周期CPU中，下列有关指令和微指令之间关系的描述中，正确的是（ A ）。（单选）
 A.一条指令的功能通过执行一个微程序来实现
 B.一条指令的功能通过执行一条微指令来实现
 C.通过指令的寻址方式实现指令与微程序的映射
 D.通过指令的形式地址字段实现指令与微程序的映射
 77、相对于微程序控制器，硬布线控制器的特点是（ C ）（单选）
 A.指令执行速度慢，指令功能的修改和扩展容易
 B.指令执行速度快，指令功能的修改和扩展容易
 C.指令执行速度快，指令功能的修改和扩展难
 D.指令执行速度慢，指令功能的修改和扩展难
 78、从信息流的传送效率来看，（ D ）工作效率最低。
 A.双总线系统
 B.多总线系统
 C.三总线系统
 D.单总线系统
 79、系统总线地址的功能是（ C ）。
 A.选择主存单元地址
 B.选择外存地址
 C.指定主存和I / O设备接口电路的地址
 D.选择进行信息传输的设备
 80、IEEE1394的高速特性适合于新型高速硬盘和多媒体数据传送，它的数据传输率最高可以达到（ C ）。
 A.200 Mb/秒
 B.100 Mb/秒
 C.400 Mb/秒
 D.300 Mb/秒
 81、异步控制常用于（ C ）作为其主要控制方式。
 A.微程序控制器中
 B.微型机的CPU中
 C.在单总线结构计算机中访问主存与外围设备时
 D.硬布线控制器中
 82、当采用（ A ）对设备进行编址情况下，不需要专门的I/O指令。
 A.统一编址法
 B.单独编址法
 C.两者都是
 D.两者都不是
 83、8086 CPU对I/O接口的编址采用了（ B ）。
 A.I/O端口和存储器统一编址
 B.I/O端口独立编址
 C.输入/输出端口分别编址
 D.I/O端口和寄存器统一编址
 84、中断向量地址是（ D ）。
 A.子程序入口地址
 B.中断服务例行程序入口地址
 C.中断返回地址
 D.中断服务例行程序入口地址的指示器
 85、为了便于实现多级中断，保存现场信息最有效的办法是采用（ A ）。
 A.堆栈
 B.通用寄存器
 C.外存
 D.存储器
 86、在单级中断系统中，CPU一旦响应中断，则立即关闭（ B ）标志，以防本次中断服务结束前同级的其他中断源产生另一次中断进行干扰。
 A.中断请求
 B.中断屏蔽
 C.中断保护
 D.中断允许
 87、通道对CPU的请求形式是（ C ）。
 A.跳转指令
 B.通道命令
 C.中断
 D.自陷
 
二填空题（每空2分，共20分）
 1、访问256KB的存储空间，需要的地址线数最少为( 18 ）根？ （只需要填阿拉伯数字）
 2、程序必须存放在哪里才能被CPU访问并执行（主存或CACHE ）请输入答案
 3、某计算机指令集中共有A、B、C、D四类指令，它们占指令系统的比例分别为40% 、20%、20%、20%, 各类指令的CPI分别为 2、3、4、5；该机器的主频为600MHZ，则该机的MIPS为( 187.5 )（保留到小数点后一位）
 4、存放一个24 * 24点阵汉字，至少需要多少字节的存储空间 （只需要填写十进数）（72）请输入答案
 5、设机器字长为16位，定点表示时，数据位15位，符号位1位，则定点原码表示时能表示的最小负数为 （填写十进制数，要带符号，且符号与数字间不能有空格）请输入答案（-2^15+1）将一个十进制数-129表示成补码时，至少应采用多少位二进制数（9）
 6、已知[X]补 = 1101001 , [Y]补 = 1101010, 则用变形补码计算2[X]补 +1/2 [Y]补的结果为 （直接填二进制数即可，数字间不留空格）
 请输入答案（1000111）
 7、计算机字长为8位，若 x = - 1101101，则 [x/4]补 的值为 （直接填写二进制数）请输入答案（11100100）
 8、移码表示法主要用于表示浮点数的（直接填汉字即可）（移码）
 9、某计算机主存容量为64K * 16,其中ROM区为4K，其余为RAM区，按字节编址。现要用2K * 8位的ROM芯片和4K * 8位的RAM来设计该存储器，则需要RAM芯片数是 （填写阿拉伯数字即可）（15）请输入答案
 10、设A=0x123456，计算机内存地址为由低到高。则采用小端方式下，最高地址存放的内容为（只填写2位阿拉伯数字）（12）
 请输入答案
 11、某计算机存储器按照字节编址，采用小端方式存储数据，假定编译器规定int和short型长度分别为32位和16位，并且数据按照边界对齐存储。 某C语言的程序段如下：
 struct
 {
 int a;
 char b;
 short c;
 } record;
 record.a = 273;
 若record变量的首地址为0xC008,则地址0xC008的内容是0X ( 11) （只填写2个阿拉伯数字）
 12、在请求分页存储管理方案中， 若某用户空间为16个页面， 页 长 1 K B，虚页号0、1、2、3、4对应的物理页号分别为1、5、3、7、2。则逻辑地址A2CH所对应的物理地址为(E2C )H （只需填数字和字母，不需要在最后带H，如有字母一定要大写，字母之间以及字母和数字间不留空格）请输入答案
 13、假定主存按字节编址，cache共有64行，采用直接映射方式，主存块大小为32字节，所有编号都从0开始。问主存第3000号单元所在主存块映射到的cache行号是( 29 )。（本题中的数字都是十进制数，答案也填十进制数）请输入答案
 14、计算机主存容量8MB，分为4096个主存块，Cache数据区容量为64KB，若Cache采用直接映射方式，则Cache的总行数为 ( 只需要填写阿拉伯数字 )（32）请输入答案
 15、某计算机为定长指令字结构，采用扩展操作码编码方式，指令长度为16位，每个地 址码占4位，若已设计三地址指令15条，二地址指令8条，一地址指令127条，则剩下的零地址指令最多有( 16 )条. (只需要填阿拉伯数字)请输入答案
 16、在变址寻址方式中，若变址寄存器的内容是4E3CH，指令中给出的偏移量为63H,则数据的有效地址为 （ 4E9F ）H (只需要填阿拉伯数字和大写字母,共需4位) 请输入答案
 17、某计算机采用双字节长指令,指令中形式地址字段8位 ，指令中的数据采用补码表示,且PC的值在取指阶段完成修改。 某采用相对寻址的指令的当前地址和转移后的目标地址分别为为2008和 2001（均为10进制数）,则该指令的形式地址字段的值为(F7 )H (只需要填阿拉伯数字和大写字母,共需2位)