2013年12月考研的408试题,本篇为大题部分,小题见上一篇。
声明:
- 0x和0b分别表示十六进制和二进制数,其余为十进制数。
- exp()和log()分别是以2为底的指数和对数,exp10()以10为底。
- 乘除号用最朴素的×÷,分数用/,参与计算的英文字母变量用手写体。
- 〔〕里的斜体为补充文字,另外对原题一些容易误会的文字做了修改。
- 图片使用亿图图示绘制。
二、综合应用:
第41~47题,共70分。
「41」(13分)、
二叉树的带权路径长度〔WPL〕是二叉树中所有叶结点的带权路径长度之和。给定一棵二叉树T,采用二叉链表存储,结点结构为[left|weight|right],其中只在叶结点的weight域保存有非负权值。设root为指向T的根结点的指针,请设计求T的WPL的算法。
问答:
1️⃣给出算法的基本设计思想。
𝟙、基于对树的任一种遍历算法即可。
❶先序遍历,递归每个结点,需将结点的深度作为参数,针对参数中的当前结点,若是叶结点则将其权值×深度作为返回值;否则递归计算左右子树的wpl,若有一边子树为空则其wpl=0,最后将lwpl+rwpl作为返回值即可。
❷层序遍历,需借助队列,树中的结点绑定上其深度作为队列元素,当队列不空时,弹出队头元素,针对当前结点,若是叶结点则将其权值×深度累加进总的wpl里;否则判断其左右孩子是否为空,不为空则入队
2️⃣采用C/C++语言,给出二叉树结点的数据类型定义。
𝟚、
typedef struct BiNode{
int weight;
struct BiNode *left, *right;
}* BiTree; // 树结点指针类型
3️⃣根据设计思想,采用C/C++语言描述算法,关键之处给出注释。
𝟛、
/* 基于先序遍历 */
int WPLPreOrder(BiTree root, int depth=1)
{
if (!root->left && !root->right) // 遇到叶结点了
return root->weight * depth;
int lwpl = 0, rwpl = 0; // 准备接收左右子树的WPL
if (root->left) // 若左子树不空则递归到左子树
lwpl = WPLPreOrder(root->left, depth+1);
if (root->right) // 若右子树不空则递归到右子树
rwpl = WPLPreOrder(root->right, depth+1);
return lwpl + rwpl;
}
/* 基于层序遍历 */
#include <queue> // C++才有的队列模板类
#include <utility> // std::pair
int WPLLevelOrder(BiTree root)
{
std::queue<std::pair<BiTree, int>> que;
que.push({root, 1}); // 初始化队列
int wpl = 0;
while (!que.empty())
{
auto front = que.front();
que.pop(); // 获取队头元素并弹出
BiTree node = front.frist;
int depth = front.second;
if (!node->left && !node->right) // 遇到叶结点了
wpl += node->weight * depth;
if (node->left) // 非空左孩子及其深度入队
que.push({node->left, depth+1});
if (node->right) // 非空右孩子及其深度入队
que.push({node->right, depth+1});
}
return wpl;
}
「42」(10分)、
某网络中的路由器运行的路由协议为OSPF,题42表是路由器R1维护的主要链路状态信息LSI,题42图是根据题42表及R1的接口名构造出来的网络拓扑。
R1的LSI | R2的LSI | R3的LSI | R4的LSI | 备注 | ||
---|---|---|---|---|---|---|
RouterID | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | 标识路由器的IP地址 | |
Link1 | ID | 10.1.1.2 | 10.1.1.1 | 10.1.1.6 | 10.1.1.5 | 所连路由器的RouterID |
IP | 10.1.1.1 | 10.1.1.2 | 10.1.1.5 | 10.1.1.6 | Link1的本地IP地址 | |
Metric | 3 | 3 | 6 | 6 | Link1的费用 | |
Link2 | ID | 10.1.1.5 | 10.1.1.6 | 10.1.1.1 | 10.1.1.2 | 所连路由器的RouterID |
IP | 10.1.1.9 | 10.1.1.13 | 10.1.1.10 | 10.1.1.14 | Link2的本地IP地址 | |
Metric | 2 | 4 | 2 | 4 | Link2的费用 | |
Net1 | Prefix | 192.1.1.0/24 | 192.1.6.0/24 | 192.1.5.0/24 | 192.1.7.0/24 | 直连网络Net1的网络前缀 |
Metric | 1 | 1 | 1 | 1 | 到达直连网络Net1的费用 |
问答:
1️⃣本题中的网络可抽象为数据结构中的哪种逻辑结构?
𝟙、无向有环有权图。
2️⃣针对题42表中的内容,设计合理的链式存储结构,以保存题42表中的链路状态信息LSI。要求给出链式存储结构的数据类型定义,并画出对应题42表的链式存储结构示意图?示意图中可仅以ID标识结点。
𝟚、先给出图的两个基本要素:点和边,然后按题目意思用链表表示出整个图。
typedef struct {
string LID, LIP;
} LinkNode; // 路由器某边连另一个路由器时
typedef struct {
string Prefix, Mask;
} NetNode; // 路由器某边连网络时
typedef struct Edge {
enum flag; // 枚举值 0表示LinkNode 1表示NetNode
union {
LinkNode tolink;
NetNode tonet;
} LinkORNet; // 复用 连接路由器或网络
unsigned int Metric; // 费用
struct Node* NextEdge; // 某路由器的所有边信息都在一个链表中
}* EdgeInfo;
typedef struct Router {
string RID; // 路由器以ID标识
EdgeInfo LNE; // 指向边信息中的第一个结点
struct RouterNode* NextRouter; // 所有路由器的信息也串联成一个链表
}* RouterInfo;
3️⃣按照迪杰斯特拉算法的策略,依次给出R1到达题42图中子网192.1.x.x的最短路径及费用?
𝟛、如下表。
目的网络 | 最短路径 | 最少费用 | |
---|---|---|---|
步骤1 | 192.1.1.0/24 | R1→N1 | 1 |
步骤2 | 192.1.5.0/24 | R1→R3→N5 | 3 |
步骤3 | 192.1.6.0/24 | R1→R2→N6 | 4 |
步骤4 | 192.1.7.0/24 | R1→R2→R4→N7 | 8 |
「43」(9分)、
请根据题42描述的网络,继续回答下列问题。
问答:
1️⃣假设路由表项结构为[目的网络|下一跳|接口],请给出题42图中R1的路由表,要求包括到达题42图中子网192.1.x.x的路由,且路由表中的路由项尽可能少?
𝟙、考路由聚合技术,找公共前缀,192.1.6.0/24和192.1.7.0/24可以聚合成192.1.6.0/23,且R1到这2个子网的最短路都经由L0。
目的网络 | 下一跳 | 接口 |
---|---|---|
192.1.1.0/24 | 直连 | E0 |
192.1.5.0/24 | 10.1.1.10 | L1 |
192.1.6.0/23 | 10.1.1.2 | L0 |
2️⃣当主机192.1.1.130向主机192.1.7.211发送一个TTL=64的IP分组时,R1通过哪个接口转发该IP分组?主机192.1.7.211收到的IP分组TTL是多少?
𝟚、目的主机的IP地址192.1.7.211与R1路由表中目的网络为192.1.6.0/23的匹配,R1通过L0接口转发该IP分组。IP分组的生存时间TTL每经过1个路由器便减1,该IP分组走最短路要经过R1,R2,R4,故该IP分组到达接收方时TTL=64-3=61。
3️⃣若R1增加一条Metric为10的链路连接Internet,则题42表中R1的LSI需要增加哪些信息?
𝟛、增加一条特殊的直连网络,Internet = { Prefix: 0.0.0.0; Metric: 10; }。
「44」(12分)、
某程序中有如下循环代码段P: for (int i = 0; i < N; i++) sum += A[i];
。假设编译时变量sum和i分别分配在寄存器R1和R2中。常量N在寄存器R6中,数组A的首地址在寄存器R3中。程序段P起始地址为0x08048100,对应的汇编代码和机器代码如下表所示。
编号 | 地址 | 机器代码 | 汇编代码 | 注释 |
---|---|---|---|---|
1 | 0x08048100 | 0x00022080 | loop: sll R4, R2, 2 | (R2) << 2 → R4 |
2 | 0x08048104 | 0x00083020 | add R4, R4, R3 | (R4) + (R3) → R4 |
3 | 0x08048108 | 0x8C850000 | load R5, 0(R4) | ((R4) + 0) → R5 |
4 | 0x0804810C | 0x00250820 | add R1, R1, R5 | (R1) + (R5) → R1 |
5 | 0x08048110 | 0x20420001 | add R2, R2, 1 | (R2) + 1 → R2 |
6 | 0x08048114 | 0x1446FFFA | bne R2, R6, loop | if (R2) != (R6) goto loop |
执行上述代码的计算机M采用32位定长指令字,其中分支指令bne采用如下格式:
OP为操作码;Rs和Rd为寄存器编号;OFFSET为偏移量,用补码表示。
问答:
1️⃣计算机M的存储器编址单位是什么?
𝟙、P的机器代码为4字节定长,一条机器代码占了4个地址,可知M的存储器编址单位是字节,一个地址即一字节。
2️⃣已知sll指令实现左移功能,数组A中每个元素占多少字节?
𝟚、按位左移2位相当于乘4,汇编代码1,2告诉我们,数组中的元素是这样获取的:A[i] = *(A+4×i),A中每个元素占4B。
3️⃣题44表中bne指令的OFFSET字段的值是多少?已知bne指令采用相对寻址方式,当前PC内容为bne指令地址,通过分析题44表中指令地址和bne指令内容,推断出bne指令的转移目标地址计算公式?
𝟛、汇编代码6的低16位为0xFFFA=-6,题中说此时PC=0x08048114,正常往下执行得PC=(PC)+4,而跳转的目标是0x08048100,两者差了0x18=24,可知bne指令的转移目标地址计算公式是(PC)+4+4×OFFSET。似13年的第44题题干给的计算公式。
4️⃣若M采用如下“按序发射+按序完成”的5级指令流水线:IF〔取指〕,ID〔译码及取数〕,EXE〔执行〕,MEM〔访存〕,WB〔写回寄存器〕,且硬件不采取任何转发措施,分支指令的执行均引起3个时钟周期的阻塞,则P中哪些汇编代码的执行会由于数据相关而发生流水线阻塞?哪条汇编代码的执行会发生控制冒险?为什么汇编代码1的执行不会因为与汇编代码5的数据相关而发生阻塞?
𝟜、数据相关引起的流水线阻塞,汇编代码2,3,4,6的EXE,分别需等待汇编代码1,2,3,5的WB。汇编代码6会发生控制冒险,控制冒险主要与条件跳转指令有关。当前循环的汇编代码5和下一次循环的汇编代码1虽然有数据相关,但当前循环的汇编代码6引起3个时钟周期的阻塞,消除了该数据相关。
「45」(11分)、
假设对于44题中的计算机M和程序P的机器代码,M采用页式虚拟存储管理;P开始执行时,(R1)=(R2)=0,(R6)=1000,其机器代码已调入主存但不在Cache中;数组A未调入主存,且所有数组元素在同一页,并存储在磁盘同一个扇区。
问答:
1️⃣P执行结束时,R2的内容是多少?
𝟙、P执行结束时,i=N=1000,R2的内容是1000。
2️⃣M的指令Cache和数据Cache分离。若指令Cache共有16行,Cache和主存交换的块大小为32字节,则其数据区的容量是多少?若仅考虑程序段P的执行,则指令Cache的命中率为多少?
𝟚、指令Cache数据区的容量是16×32B=512B。逻辑地址可以这样划分:[主存块标记23位|Cache块号4位|块内偏移量5位],易知P的6条机器代码都在同一个块内,在1000次循环中,只有首次循环时取机器代码1会指令Cache缺失,命中率为1-1/6000=99.8%。
3️⃣P在执行过程中,哪条机器代码的执行可能发生溢出异常?哪条机器代码的执行可能产生缺页异常?对于数组A的访问,需要读磁盘和TLB至少各多少次?
𝟛、机器代码4累加sum可能发生溢出异常。机器代码3获取数组元素可能产生缺页异常。对于数组A,占磁盘一个扇区,读磁盘1次即可调到主存中的某一页,每次获取其中一个元素时就要读一次TLB,再加上获取A[0]的缺页异常前访问一次TLB,共1001次。
「46」(6分)、
文件F由200条记录组成,记录从1开始编号。用户打开文件后,欲将内存中的一条记录插入到文件F中,作为其第30条记录。
问答:
1️⃣P若文件系统采用连续分配方式,每个磁盘块存放一条记录,文件F存储区域前后均有足够的空闲磁盘空间,则完成上述插入操作最少需要访问多少次磁盘块?F的文件控制块内容会发生哪些改变?
𝟙、要把文件前29条记录前移,从当前磁盘块读出再写入前一个磁盘块,然后插入第30条记录,共访问磁盘块29×2+1=59次。F的FCB中起始块号和文件长度会因此改变。
2️⃣若文件系统采用链接分配方式,每个磁盘块存放一条记录和一个链接指针,则完成上述插入操作需要访问多少次磁盘块?若每个存储块大小为1KB,其中4个字节存放链接指针,则该文件系统支持的文件最大长度是多少?
𝟚、先找到第29条记录,再插入第30条记录,第30条记录的指针就是第29条记录的指针,最后要修改第29条记录的指针,共访问磁盘块29+1+1=31次。4B的指针支持exp(32)个寻址范围,文件最大长度是exp(32)×(1024-4)B=4080GB。
「47」(9分)、
系统中有多个生产者进程和多个消费者进程,共享一个能存放1000件产品的环形缓冲区,初始为空。当缓冲区未满时,生产者进程可以放入其生产的一件产品,否则等待;当缓冲区未空时,消费者进程可以从缓冲区取走一件产品,否则等待。要求一个消费者进程从缓冲区连续取出10件产品后,其他消费者进程才可以取产品。
问答:
1️⃣请使用信号量PV操作实现进程间的互斥与同步,要求写出完整的过程,并说明所用信号量的含义和初值?
𝟙、互斥信号量mutex控制各进程互斥地访问缓冲区,互斥信号量consumption控制一个消费者进程完成连续取出10件产品,同步信号量full控制生产者向消费者反馈生产了一件产品,同步信号量empty控制消费者向生产者反馈消费了一件产品。
semaphore mutex = 1, consumption = 1;
semaphore full = 0, empty = 1000;
Process producer()
{
produce();
P(empty);
P(mutex);
put();
V(mutex);
V(full);
}
Process consumer()
{
P(consumption);
for (int i = 0; i < 10; i++)
{
P(full);
P(mutex);
get();
V(mutex);
V(empty);
}
V(consumption);
consume();
}