45.（14分）某计算机采用页式虚拟存储管理方式，按字节编址，虚拟地址为32位，物理地址为24位，页大小为8KB;TLB采用全相联映射;Cache数据区大小为64 KB，按2路组相联方式组织，主存块大小为64 B。存储访问过程的示意图如下。
请回答下列问题。
（1）图中字段A～G的位数各是多少?TLB标记字段B中存放的是什么信息?
（2）将块号为4099的主存块装入到Cache中时，所映射的Cache 组号是多少?对应的H字段内容是什么?
（3）Cache缺失处理的时间开销大还是缺页处理的时间开销大?为什么?
（4）为什么Cache可以采用直写（Write Through）策略，而修改页面内容时总是采用回写（Write Back）策略?
46.（6分）某进程调度程序采用基干优先数（prioritv）的调度策略，即选择优先数最小的进程运行，进程创建时由用户指定一个nice作为静态优先数。为了动态调整优先数，引入运行时间cpuTime和等待时间waitTime，初值均为0。进程处于执行态时，cpuTime定时加1，且waitTime 置O;进程处于就绪态时，cpuTime置0，waitTime定时加1。请回答下列问题。
（1）若调度程序只将nice的值作为进程的优先数，即priority=nice，则可能会出现饥饿现象，为什么?
（2）使用nice、cpuTime和waitTime设计一种动态优先数计算方法，以避免产生饥饿现象，并说明waitTime的作用。
47.（9分）某磁盘文件系统使用链接分配方式组织文件，簇大小为4 KB。目录文件的每个目录项包括文件名和文件的第一个簇号，其他簇号存放在文件分配表FAT中。
（1）假定目录树如下图所示，各文件占用的簇号及顺序如下表所示，其中dir、dir1是目录，file1、file2是用户文件。请给出所有目录文件的内容。
41.（15分）请设计一个算法，将给定的表达式树（二叉树）转换为等价的中缀表达式（通过括号反映操作符的计算次序）并输出。例如，当下列两棵表达式树作为算法的输入时:
输出的等价中缀表达式分别为（a+b）*（c *（-d））和（a*b）+（-（c-d））。
二叉树结点定义如下∶
typedef struct node
{ char data[ 10]; //存储操作数或操作符
struct node * left,*right;
}BTree;
要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，采用C或C++语言描述算法，关键之处给出注释。
42.（8分）使用Prim（普里姆）算法求带权连通图的最小（代价）生成树（MST）。请回答下列问题。
（1）对下列图G，从顶点A开始求G的MST，依次给出按算法选出的边。
（2）图G的MST是唯一的吗?
（3）对任意的带权连通图，满足什么条件时，其MST是唯一的?
43.（13分）已知f（n）=Σ2i=2n+1-1=11L 1B，计算f（n）的C语言函数f如下∶
1 int f1( unsigned n)
2{ int sum=1, power=1;
3 for(unsigned i=0;i<= n-1;i ++)
4 { power *=2;
5 Sum += power;
6 }
7 return sum;
8 }
将f中的int都改为float，可得到计算f（n）的另一个函数f2。假设unsigned和int型数据都占32 位，float采用IEEE 754单精度标准。
请回答下列问题。
（（1）当n=0时，f1会出现死循环，为什么?若将f1中的变量i和n都定义为int型，则f1是否还会出现死循环?为什么?
（2）f1（23）和f2（23）的返回值是否相等?机器数各是什么（用十六进制表示）?（3）f1（24）和f（24）的返回值分别为33554 431和33554432.0，为什么不相等?
（4）f（31）=232-1，而f1（31）的返回值却为-1，为什么?若使f1（n）的返回值与f（n）相等，则最大的n 是多少?
（5）f2（127）的机器数为7F80 0000H，对应的值是什么?若使f2（n）的结果不溢出，则最大的n是多少?若使f2（n）的结果精确（无舍入），则最大的n是多少?
44.（10分）在按字节编址的计算机M上，题43中f1的部分源程序（阴影部分）与对应的机器级代码（包括指令的虚拟地址）如下：
int f1(unsigned n)
1 00401020 55 push ebp
····· ····· ·····
for(unsigned i=0; i<= n-1; i++)
····· ····· ·····
20 0040105E 39 4D F4 cmp dword ptr[ebp-OCh],ecx
····· ····· ·····
{ power * = 2;
····· ····· ·····
23 00401066 D1E2 shl edx,1
····· ····· ·····
return sum;
····· ····· ·····
35 0040107F C3 ret
其中，机器级代码行包括行号、虚拟地址、机器指令和汇编指令。
请回答下列问题。
（1）计算机M是RISC还是CISC?为什么?
（2）fl的机器指令代码共占多少字节?要求给出计算过程。
（3）第20条指令cmp通过i减n-1实现对i和n-1的比较。执行fl（0）过程中，当i=0时，cmp指令执行后，进/借位标志CF的内容是什么?要求给出计算过程。
（4）第23条指令shl通过左移操作实现了power*2运算，在f中能否也用shl指令实现power*2?为什么?
45.（7分）假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式如下∶
页目录号（10位）|页表索引（10位）|页内偏移量（12位）
请针对题43的函数fl和题44中的机器指令代码，回答下列问题。
（1）函数fl的机器指令代码占多少页?
（2）取第1条指令（push ebp）时，若在进行地址变换的过程中需要访问内存中的页目录和页表，则会分别访问它们各自的第几个表项（编号从0开始）?
（3）M的I/O采用中断控制方式。若进程P在调用f1之前通过scanf（）获取n的值，则在执行scanf（ ）的过程中，进程P的状态会如何变化?CPU是否会进入内核态?
46.（8分）某进程中有3个并发执行的线程thread1、thread2和thread3，其伪代码如下所示。
//复数的结构类型定义
typede struct
}
float a;
float b
}cnum;cnumx，y，z;//全局变量
//计算两个复数之和
cnum add(cnum p, cnum q)
{
cnum S;
S.a=p.a+q.a;
s.b=p.b+q.b;
return s;
}
Thread1
{
cnum w;
w=add(x,y);
·····
}
thread2
}
cnum w;
w=add(y, z);
·····
}
thread3
{
cnum w;
w.a=1;
w.b=1;
z=add(z,w);
y=add(y, w);
·····
}
请添加必要的信号量和P、V（或wait（ ）、signal（ ）操作，要求确保线程互斥访问临界资源，并且最大程度地并发执行。
47.（9分）甲乙双方均采用后退N帧协议（GBN）进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000 B。Sx，y和Rx，v分别表示甲方和乙方发送的数据帧，其中∶x是发送序号;y是确认序号（表示希望接收对方的下一帧序号）;数据帧的发送序号和确认序号字段均为3比特。信道传输速率为100 Mbps，RTT=0.96 ms。下图给出了甲方发送数据帧和接收数据帧的两种场景，其中to为初始时刻，此时甲方的发送和确认序号均为0，tu时刻甲方有足够多的数据待发送。
请回答下列问题。
（1）对于图（a），to时刻到t;时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少?正确接收的是哪几个帧（请用Sx，y形式给出）?
（2）对于图（a），从t时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧?其中第一个帧和最后一个帧分别是哪个（请用Sx，y形式给出）?
（3）对于图（b），从t;时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧?重发的第一个帧是哪个（请用Sx，y形式给出）?
（4）甲方可以达到的最大信道利用率是多少?
