我的大纲样题解析
-
1、A
低级排序（插排、折半插排、冒泡、简选）都是O（n*n），空间都是O（1），且都稳定。（简选可以稳定也可以不稳定，关键是看每次选择最小数的算法是否稳定）。
高级排序（shell排、堆排、快排、归并）中shell不讨论其性能，因为它的性能跟步长有关，只需记住他是不稳定的即可。
堆排、快排、归并的平均时间复杂度都是O（nlogn）。其中，
快排最快，可以最坏情况退化为冒泡；
堆排的特点是辅助空间少（为O（1））；
归并排的特点是稳定。
讨论排序的稳定是因为基数排序的LSD策略要求算法稳定。
2、A（画一下就清楚了，A是一个大根堆。）
3、D
PC本质上存放的是一个主存地址。
IR长度与指令长度有关。
MDR与主存的编制有关，如果是按字节编址（即一个地址存放一个字节）那么它就有8位。
PSW跟计算机系统设计的状态位有关。但通常其位数跟通用寄存器位数一样，这样便于处理。
4、B（这个比较简单，比较快的做法是100H-42H=BEH）
5、C（没什么好讲的）
6、B（每个进程先分配3个，剩下一个无论怎么分配都不会死锁了）
7、B
Lmin=CT（C是数据率，T是来回传输时延）
CSMA/CD协议中最小帧长的计算公式
（标准以太网C=10Mbps，T=51.2us，所以Lmin=512b=64B）
8、B（以下Wt—发送方端口，Wr—接收方窗口，n—窗口序号位数）
简单ARQ（带确认和超时的停等协议）：Wt=Wr=1
连续ARQ（回退N帧协议）：Wr=1，Wt<=(2^n)-1；
但最佳Wt是满足以下条件：（Wt-1）Tframe=2Tprop（传完窗口帧后正好收到第一个帧的回复）
选择重传ARQ：Wt<=2^(n-1)，Wr<=2^(n-1)
41、
终点
i=1
i=2
i=3
i=4
V2
4
(v1,v2)
4
(v1,v2)
4
(v1,v2)
—
V3
2
(v1,v3)
—
—
—
V4
∞
(v1,v4)
3
(v3,v4)
—
—
V5
8
(v1,v5)
8
(v1,v5)
6
(v4,v5)
6
(v4,v5)
Vj
V3
V4
V2
V5
S
{v1,v3}
{v1,v3,v4}
{v1,v2,v3,v4}
{v1,v2,v3,v4,v5}
42、这里我给出一种非递归的算法：该算法基于非递归的后续遍历（去掉红色部分）
http://bbs.kaoyan.com/thread-2409365-1-1.html（这里有递归的算法）
void LongestPath ( BiTree T , BiTree longestPath[] )
{
if(T==null) return; //空树直接返回
BiTree bt, s[]; //s是栈，元素为树的节点，容量足够大
int top=0; //栈顶指针，s[0]为栈底，不放元素
int tag[]; //标记数组容量足够大，元素是0或1，0表示节点右子树还未访问
int longest=0; //最长路径长度
while(bt!=null || top>0) //栈非空或节点非空时循环
{ while(bt!=null)
{ s[++top]=bt; //当前节点入栈
tag[top]=0; //置标记：右子树还未访问
bt=bt->lchild; //沿左分支向下
}
if(s[top]==1)
{ if(s[top]->lchild==null && s[top]->rchild==null)
//当前节点是叶子
{ if(top>longest)
//根到当前叶子的路径大于最长路径
{ for(int i=1;i<=top;i++)
//更新最长路径
longestPath=s;
longest=top
//更新最长路径长度
}
}
}
while(top>0 && s[top]==1)
{ cout<<s[top]->data; //访问节点（本题事实上不需要这句）
top--; //出栈
}
if(s[top]==0) //右子树未访问过
{ bt=s[top]->rchild; //访问右子树
tag[top]=1; //置标记：右子树访问过了
}
}
}
注：如果对递归算法不是很精通的同学，不妨背一下非递归的遍历算法，树的算法设计肯定是基于某种遍历算法的！！
43、块大小为64B，所以块内地址是6位(2^6=64);
“采用4路组相联”，这句话的解读是每组内分成四个小块，于是128块被分成32组，所以组号为5（2^5=32）。
至此已经可以把主存和Cache的地址结构描绘出来了：
Tag（32-5-6=21位）
Index（5位）
Offset（6位）
组内块号（2位）
Index（5位）
Offset（6位）
有效位（1位）
脏位（1位）
上面的是主存，下面的是Cache。由此可见Cache共15位 。
44、（1）
a：MDR （只有MDR可与主存双向传输）
b：IR （主存中传给CPU的要么是数据，要么是指令）
c：MAR （只有MAR单向传输到主存）
d：PC （很明显的+1标记）
（2）主存->IR->控制器。（简述略）
（3）MAR->主存->ALU->(AC->ALU-> MDR->主存。（说明略）
45、（1）LRU算法：
1
2
3
4
2
1
5
6
2
1
2
3
7
6
3
2
1
2
3
6
1
1
2
1
2
3
4
2
3
√
4
2
1
4
5
1
6
5
1
6
5
2
6
1
2
√
3
1
2
3
7
2
3
7
6
√
3
2
6
3
2
1
√
√
3
2
6
共缺页20-5=15次
（2）FIFO算法：
1
2
3
4
2
1
5
6
2
1
2
3
7
6
3
2
1
2
3
6
1
2
1
3
2
1
4
3
2
√
1
4
3
5
1
4
6
