42.(15分)一个长度为L(L≥1)的升序序列S，处在第éL/2ù个位置的数称为S的中位数。例如，若序列S1=(11, 13, 15, 17, 19)，则S1的中位数是15。两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若S2=(2, 4, 6, 8, 20)，则S1和S2的中位数是11。现有两个等长升序序列A和B，试设计一个在时间和空间两方面都尽可能高效的算法，找出两个序列A和B的中位数。要求：
(1)给出算法的基本设计思想。
(2)根据设计思想，采用C或C++或JAVA语言描述算法，关键之处给出注释。
(3)说明你所设计算法的时间复杂度和空间复杂度。
43.(11分)假定在一个8位字长的计算机中运行如下类C程序段：
unsigned int x = 134;
unsigned int y = 246;
int m = x;
int n = y;
unsigned int z1 = x–y;
unsigned int z2 = x+y;
int k1 = m–n;
int k2 = m+n;
若编译器编译时将8个8位寄存器R1 ~ R8分别分配给变量x、y、m、n、z1、z2、k1和k2。请回答下列问题。(提示：带符号整数用补码表示)
(1)执行上述程序段后，寄存器R1、R5和R6的内容分别是什么?(用十六进制表示)
(2)执行上述程序段后，变量m和k1的值分别是多少?(用十进制表示)
(3)上述程序段涉及带符号整数加/减、无符号整数加/减运算，这四种运算能否利用同一个加法器及辅助电路实现?简述理由。
(4)计算机内部如何判断带符号整数加/减运算的结果是否发生溢出?上述程序段中，哪些带符号整数运算语句的执行结果会发生溢出?
44.(12分)某计算机存储器按字节编址，虚拟(逻辑)地址空间大小为16 MB，主存(物理)地址空间大小为1 MB，页面大小为4 KB;Cache采用直接映射方式，共8行;主存与Cache之间交换的块大小为32 B。系统运行到某一时刻时，页表的部分内容和Cache的部分内容分别如题44-a图、题44-b图所示，图中页框号及标记字段的内容为十六进制形式。
531_131106130551t2dwR020cbmQ4YwX.jpg
请回答下列问题。
(1)虚拟地址共有几位，哪几位表示虚页号?物理地址共有几位，哪几位表示页框号(物理页号)?
(2)使用物理地址访问Cache时，物理地址应划分成哪几个字段?要求说明每个字段的位数及在物理地址中的位置。
(3)虚拟地址001C60H所在的页面是否在主存中?若在主存中，则该虚拟地址对应的物理地址是什么?访问该地址时是否Cache命中?要求说明理由。
(4)假定为该机配置一个4路组相联的TLB，该TLB共可存放8个页表项，若其当前内容(十六进制)如题44-c图所示，则此时虚拟地址024BACH所在的页面是否在主存中?要求说明理由。
45.(8分)某银行提供1个服务窗口和10个供顾客等待的座位。顾客到达银行时，若有空座位，则到取号机上领取一个号，等待叫号。取号机每次仅允许一位顾客使用。当营业员空闲时，通过叫号选取一位顾客，并为其服务。顾客和营业员的活动过程描述如下：
cobegin
{
process 顾客i
{
从取号机获得一个号码;
等待叫号;
获得服务;
}
process 营业员
{
while (TRUE)
{
叫号;
为顾客服务;
}
}
} coend
请添加必要的信号量和P、V(或wait()、signal())操作，实现上述过程中的互斥与同步。要求写出完整的过程，说明信号量的含义并赋初值。
46.(7分)某文件系统为一级目录结构，文件的数据一次性写入磁盘，已写入的文件不可修改，但可多次创建新文件。请回答如下问题。
(1)在连续、链式、索引三种文件的数据块组织方式中，哪种更合适?要求说明理由。为定位文件数据块，需在FCB中设计哪些相关描述字段?
(2)为快速找到文件，对于FCB，是集中存储好，还是与对应的文件数据块连续存储好?要求说明理由。
47.(9分)某主机的MAC地址为00-15-C5-C1-5E-28，IP地址为10.2.128.100(私有地址)。题47-a图是网络拓扑，题47-b图是该主机进行Web请求的1个以太网数据帧前80个字节的十六进制及ASCII码内容。
531_1311061307322nUjxgospHu1wed2.jpg
题47-b图 以太网数据帧(前80字节)
531_131106130803QVGLVMECMO8ZY8Af.jpg
531_131106130835U97dzSyZ3w3raZlv.jpg
| 
发表于 2016-7-29 22:02:36
