2009年计算机考研统一考试大纲样题解析

    低级排序（插排、折半插排、冒泡、简选）都是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（传完窗口帧后正好收到第一个帧的回复）

    ·更多请进入