2009年408真题

1. 完全二叉树结点分析

结点总数 = 边数 + 1 = 各节点度数之和

2. 无向连通图的特性

无向图的度等于顶点数 * 2

边数大于顶点个数-1 错误 边数 =2 顶点数 = 3

不存在度为1的顶点

3. m阶B树和B+树的区别

叶子结点

b树：所有叶子结点都处于同一层

b+数：叶子结点包含所有关键字信息，起到索引的作用，并且通过链接指针连起来

4. 插入排序

直接插入，折半插入

希尔排序，每趟不可确定一个元素的最终位置

5. 浮点数的运算

对阶 （小阶向大阶看齐）阶码相等

尾数加减（注意隐含位）

尾数规格化（左归右归）

尾数舍入（丢失精度）不影响结果是否溢出

溢出判断

6. 相对寻址

PC + ‘1’ + 偏移量（补码）

7. 外部中断和内部中断

故障，异常，中断

8. 数据传输速率

奈奎斯特定理：

极限码元传输速率为 2W（波特率） W为信道频率带宽 V表示码元的离散点平数

理想情况极限数据传输速率 = 2W log2V （b/s）

香农定理：

信道极限数据传输速率 = Wlog2(1 + S/N)

信噪比 = 10 log10(S/N)

最大速率需要对比是否为理想信道 算出奈式准则下的速率和香农速率 综合对比

9. FTP

基于TCP

控制链接21，在整个会话期间保持打开（持久）

数据链接 20（非持久）

10. 指令执行

ADD (R1), R0 功能为将 (R0) + ((R1)) 结果存入 (R1) 功能描述：将寄存器R0中的内容与寄存器R1中的内容所指主存单元相加，并将结果存入寄存器R1所指的主存单元中 | 时钟 | 功能 | 有效控制信号 | | C1 | MAR <- (PC)| PCout,MARin | | C2 | MDR <- M(MAR), PC <- (PC) + 1| MDRin,MemR,PC+1 | | C3 | IR<-(MDR)| MDRout,IRin | | C4 | 指令译码| | | C5 | MAR <- (R1) | R1out,MARin | | C6 | MDR <- M(MAR)| MARout,MDRin.MemR | | C7 | A <- (MDR) | MDRout,Ain | | C8 | ALU <- (A) + (R0) | Aout,R0out,ALUin | | C9 | AC <- ALU | ALUout,ACin | | C10 | MDR <- (AC)| ACout,MARin | | C11 | M(MAR) <- (MDR) | MDRout,MemW |

11. IO控制方式

CPU用于该IO控制方式的IO时间占整个CPU时间的百分比是多少?

程序轮训方式：

中断方式：每秒钟产生多少次中断 * 处理中断所需时钟周期数 / 主频

DMA方式：每秒钟产生多少次DMA请求 * 处理DMA所需时钟周期数 / 主频

12. 信号量

缓冲区的访问 需要互斥mutex，缓冲区的容量empty = N

同步问题 p1 = 0，p2=0

13. 路由表

路由表结构：目的ip 子网掩码 下一跳ip 接口

域名服务器的子网掩码为255.255.255.255

默认路由目的ip：0.0.0.0 子网掩码：0.0.0.0