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的接口名构造出来的网络拓扑。

题42表 R1所维护的LSI
R1的LSIR2的LSIR3的LSIR4的LSI备注
RouterID10.1.1.110.1.1.210.1.1.510.1.1.6标识路由器的IP地址
Link1ID10.1.1.210.1.1.110.1.1.610.1.1.5所连路由器的RouterID
IP10.1.1.110.1.1.210.1.1.510.1.1.6Link1的本地IP地址
Metric3366Link1的费用
Link2ID10.1.1.510.1.1.610.1.1.110.1.1.2所连路由器的RouterID
IP10.1.1.910.1.1.1310.1.1.1010.1.1.14Link2的本地IP地址
Metric2424Link2的费用
Net1Prefix192.1.1.0/24192.1.6.0/24192.1.5.0/24192.1.7.0/24直连网络Net1的网络前缀
Metric1111到达直连网络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的最短路径及费用?

𝟛、如下表。

目的网络最短路径最少费用
步骤1192.1.1.0/24R1→N11
步骤2192.1.5.0/24R1→R3→N53
步骤3192.1.6.0/24R1→R2→N64
步骤4192.1.7.0/24R1→R2→R4→N78

「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/2410.1.1.10L1
192.1.6.0/2310.1.1.2L0

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,对应的汇编代码和机器代码如下表所示。

编号地址机器代码汇编代码注释
10x080481000x00022080loop: sll R4, R2, 2(R2) << 2 → R4
20x080481040x00083020add R4, R4, R3(R4) + (R3) → R4
30x080481080x8C850000load R5, 0(R4)((R4) + 0) → R5
40x0804810C0x00250820add R1, R1, R5(R1) + (R5) → R1
50x080481100x20420001add R2, R2, 1(R2) + 1 → R2
60x080481140x1446FFFAbne R2, R6, loopif (R2) != (R6) goto loop

执行上述代码的计算机M采用32位定长指令字,其中分支指令bne采用如下格式:
OP为操作码;Rs和Rd为寄存器编号;OFFSET为偏移量,用补码表示。

31 26 25 21 20 16 OP Rs Rd
15 0 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();
}
最后修改于:2024年09月03日
如果觉得我的文章对你有用请狠狠地打赏我