12.01 - 每日一题 - 408
每日一句：做一切好事要把握时机，也要把握因缘；因缘消逝才想做，就来不及了！
数据结构
1 高度为8的平衡二叉树的结点数至少为______
A. 15B. 54C. 87D. 255
答案：B
解析：不妨假设非空的高度为h的平衡二叉树的结点数至少为f（h）。它是由1个根结点及其左右子树构成的，那么左右子树可以分别是树高为h一1和h一2的具有最少结点数的平衡二叉树。由此，
f（8）=1+f（7）+f（6）=1+［1+f（6）+f（5）］+f（6） =2+2f（6）+f（5）
=2+2［1+f（5）+f（4）］+f（5）=4+3f（5）+f（4）
=……=33+21f（1） +13f（0）
显而易见，高度为1的平衡二叉树的结点数f（1）=1，高度为0的平衡二叉树的结点数f（0）=0，代人上式，有
f（8）=33+21×1+13×0=54。
计算机网络
2 在CSMA/CD中，假设站点发送数据帧所需的时间为1，任意两个站点之间的传播延迟时间为r，若能正常检测到冲突，对于基带总线网络，r的值应为______
A r<=0.5B r<0.5C r>=1D 0.5答案：A
解析：假设任意两个站点之间的传播延迟时间为r，现在考虑由于两个结点A与B发送数据而造成冲突的情形，结点A从开始发送数据到检测到冲突的最短时间为r（即结点B和结点A同时开始发送数据），而最长时间为2r（即结点B在即将接收到结点A的数据时开始发送数据）。为了防止结点A没能检测到冲突而继续发送数据从而造成网络陷入无休止的“发送→冲突→发送→冲突”的循环，应该使结点A在数据发送结束前检测到冲突并停止发送数据，这样就有2r<=1（1为结点A发送数据帧所需的时间），即r<=0.5。
拓展：
CSMA/CD发送数据帧所学的时间和计算方式，详细请查看该文档
https://blog.csdn.net/Auroraxsn/article/details/121144699
操作系统
3 位示图可用于磁盘空间的管理。设某系统磁盘共有 500 块，块号为 0~499 ，第 0 行的第 0 位表示第 0 块，第 0 行的第 1 位表示第 1 块，以此类推。若用位示图管理这 500 块的磁盘空间，当字长为 32 位时，第 i 个字节第 j 位对应的块号是______
A 32 × i+jB 32 × i+j-1C 32 × i+j-32D 32 × i+j -32 -1
答案：A
解析：n =32 ，第 i 个字节第 j 位的块号，即前面有 0 ~i -1 行 ,共 i 行，每行 n 位，并且第 i 行有 j 位，所以对应的块号为： n × i +j= 32 × i +j 。
计算机组成原理
4 某机器字长16位，主存按字节编址，转移指令采用相对寻址，由两个字节组成，第一字节为操作码字段，第二字节为相对位移量字段。假定取指令时，每取一个字节PC自动加1。若某转移指令所在主存地址为2000H，相对位移量字段的内容为06H，则该转移指令成功转移后的目标地址是______
A. 2006HB. 2007HC. 2008HD. 2009H
答案：C
解析：主存按字节编址，取指令时，每取一个字节PC自动加1。由于转移指令由两个字节组成，取出这条转移指令之后的PC值等于2002H，所以转移指令成功转移后的目标地址PC=2000H+2+06H=2008H。
拓展：
相对寻址以程序计数器PC的当前值（R15中的值）为基地址，指令中的地址标号作为偏移量，将两者相加后得到操作数的有效地址。
七种寻址方式介绍：
https://blog.csdn.net/Hardworking666/article/details/123637260