2016年12月考研的408试题，本篇为大题部分，小题见上一篇。

声明：

• 0x和0b分别表示十六进制数和二进制数，其余为十进制数。
• 0y和0c分别表示十六进制形式补码和二进制形式补码。
• exp()和log()分别是以2为底的指数和对数，exp10()以10为底。
• 乘除号用最朴素的×÷，分数用/，参与计算的英文字母变量用手写体。
• ⌊⌋⌈⌉分别是向上向下取整。
• 〔〕里的斜体为补充文字，另外对原题一些容易误会的文字做了修改。
• 图片使用亿图图示等绘制。

二、综合应用：

第41～47题，共70分。

「41」（15分）、

请设计一个算法，将给定的表达式树转换为等价的中缀表达式并输出，通过括号反映操作符的计算次序。例如，如下两棵表达式树作为算法的输入时，输出的等价中缀表达式分别为(a+b)×(c×(-d))和(a×b)+(-(c-d))。二叉树结点定义如下：

typedef struct node
{
    char data[10];    // 操作数或运算符
    struct node *left, *right;
} BinTree;

问答：

1️⃣给出算法的基本设计思想？

𝟙、基于二叉树的中序遍历，递归实现，往左子树深入前打左括号，从右子树回来打上右括号。但是要注意根结点表达式不能打括号，叶结点操作数也不能打括号。

2️⃣根据设计思想，采用C/C++描述算法，关键之处给出注释？

𝟚、如下👇。

void ParseExpress(BinTree* root, int depth=1)
{
    if (!root->left && !root->right)
        printf("%s", root->data);
        return            // 若是叶结点则输出操作数并返回
    if (depth > 1)
        printf("(");     // 非根分枝结点所表示的表达式要打括号
    if (root->left)
        ParseExpress(root->left, depth+1);
    printf("%s", root->data); // 输出操作符
    if (root->right)
        ParseExpress(root->right, depth+1);
    if (depth > 1)
        printf(")");     // 非根分枝结点所表示的表达式要打括号
}

「42」（分）、

对如下图G，使用普里姆"Prim"算法求带权连通图的最小生成树"MST"，从顶点A开始。

问答：

1️⃣依次给出按算法选出的边？

𝟙、(A,D), (D,E), (E,C), (C,B)。

2️⃣G的MST是唯一的吗？

𝟚、𝟙中给出的MST包含了G中权值最小的4条边，故G的MST唯一。

3️⃣对任意的带权连通图，满足什么条件时，其MST是唯一的？

𝟛、一个充分不必要条件：带权连通图的任一个环中所包含的边的权值均不相同时。一个充要条件：对于不在T中的每一条边e，e的权重大于T+e所产生的圈中其它每条边的权重。

「42」（13分）、

已知$\mathrm{𝒇(𝓃)}=\sum _{\mathrm{𝒾=0}}^n\mathrm{(2^𝒾)}=\mathrm{2^(𝓃+1)-1}=\mathrm{0b11...1(共n+1个1)}$，计算𝒇(𝓃)的C语言函数f1如下👇，将f1中的int都改为float，可得到计算𝒇(n)的另个函数f2。假设unsigned和int型数据都占32位，float采用IEEE754单精度标准。

int f1(unsigned n)
{
    int sum = 1, power = 1;
    for (unsigned i = 0; i <= n - 1; i++)
    {
        power *= 2;
        sum += power;
    }
    return sum;
}

问答：

1️⃣当n=0时，f1会出现死循环，为什么？若将f1中的变量i,n都定义为int型，则f1是否还会出现死循环？为什么？

𝟙、n-1=-1会被当作无符号数0xFFFFFFFF=exp(32)-1，unsigned i永远不会大于exp(32)-1，死循环。变量i,n改为int型就不会死循环，n-1=-1被当作有符号数0yFFFFFFFF=-1，正确。

2️⃣f1(23)和f2(23)的返回值是否相等？十六进制的机器数各是什么？

𝟚、相等，分别是16777215和16777215.0。f1(23)的机器数是0x00FFFFFFF，f2(23)的机器数是0x4B7FFFFFF。

3️⃣f1(24)和f2(24)的返回值分别为33554431和33554432.0，为什么不相等？

𝟛、float型只能保留24个有效1，f2(24)却有25个1，舍入处理了。

4️⃣𝒇(31)=exp(32)-1，而f1(31)的返回值却为-1，为什么？若使f1(n)的返回值与𝒇(𝓃)相等，则最大的𝓃是多少？

𝟜、int型机器数0yFFFFFFFF被按照补码解析为-1。相等，𝓃最大30。

5️⃣f2(127)的返回值机器数为0x7F800000，对应的值是什么？若使f2(n)的结果不溢出，则最大的n是多少？若使f2(n)的结果无舍入，则最大的n是多少？

𝟝、0x7F800000怎么来的👈exp(128)-1有128个1，阶数127+127=254，尾数发生舍入变为全0，并使得阶数再+1=255。+1.0×exp(128)不对，阶数全1尾数全0表示的是+∞。不溢出，n最大126，此时阶数=254。无舍入，n最大23，此时尾数=2-exp(-23)。

「44」（10分）、

在按字节编址的机器M上，题43中函数f1的部分C语言源程序和对应机器级语言的第一行如下👇，机器级语言包括行号，虚拟地址，机器代码，汇编语句，位于C语句下方的白色部分。

      int f1(unsigned n)
 1    00401020   55         push ebp                     

          for (unsigned i = 0; i < n; i++)
20    0040105E   39 4D F4   cmp dword ptr [ebp-0x0C], ecx
              power *= 2;
23    00401066   D1 E2      shl edx, 1                   

          return sum;
35    0040107F   C3         ret                          

问答：

1️⃣M的指令集架构是RISC还是CISC？

𝟙、CISC，指令字长短不一。

2️⃣f1的机器代码共占多少字节？

𝟚、看机器级代码第一行和最后一行的虚拟地址，(0x0040107F+1-0x00401020)×1B=96B。

3️⃣第20行cmp指令通过i - (n-1)实现对i和n-1的比较。执行f1(0)过程中，当i=0时，cmp指令执行后，进／借位标志CF的内容是什么？

𝟛、回顾一下ACC减法过程，sub信号为1，0x00000000-0xFFFFFFFF=0x00000000-0x00000000+1=0x00000001，进位输出carry=0，CF=carry⊕sub=1。

4️⃣第23行shl指令通过左移操作实现了power *= 2运算，在f2中能否也用shl指令实现power *= 2？

𝟜、不行，int型左移1位表示乘2，float型得用阶数加1表示乘2，也即add edx, 0x00800000。

「45」（7分）、

假定题44给出的计算机M采用二级分页虚拟存储管理方式，虚拟地址格式为：［页目录号10位｜页表索引10位｜页内偏移12位］，针对题43的函数f1和题44中的机器级语言。

问答：

1️⃣f1的机器代码占多少个页面？

𝟙、看虚拟地址的高20位，发现都在0x00401号页面里。

2️⃣取第1条汇编代码〔push ebp〕时，若在进行地址变换的过程中需要访问内存中的页目录和页表，编号从0开始，则会分别访问它们各自的几号表项？

𝟚、0x00401=0b 0000000001 0000000001，访问页目录1号表项，访问对应页表的1号表项。

3️⃣M的I/O采用中断控制方式。若进程P在调用f1之前通过scanf()获取n的值，则在执行scanf()的过程中，P的状态会如何变化？CPU是否会进入内核态？

𝟛、完整：❶获取输入时，P会变为阻塞态；❷中断返回，P被唤醒，变为就绪态；❸P被调度上机，变为运行态。涉及中断和调度，CPU会进入内核态。

「46」（8分）、

某进程中有3个并发执行的线程thread1,thread2,thread3，其伪代码如下👇。

// 复数的结构体定义
typedef struct
{
    float real, imag;
} complex;
// 全局变量定义
complex x, y, z;

// 两个复数相加
complex add(complex p, complex q)
{
    complex ans;
    ans.real = p.real + q.real;
    ans.imag = p.imag + q.imag;
    return ans;
}

thread1
{
    complex w;
    w = add(x, y);
    /***/
}
thread2
{
    complex w;
    w = add(y, z);
    /***/
}
thread3
{
    complex w;
    w = {1.0, 1.0};
    z = add(z, w);
    y = add(y, w);
    /***/
}

问答：

1️⃣请添加必要的信号量和P(wait)V(signal)操作，要求确保线程互斥访问临界资源，并且最大限度地并发执行？

𝟙、互斥信号量mutex_y13控制thread1,thread3对全局变量y的读互斥，互斥信号量mutex_y23控制thread2,thread3对全局变量y的读写互斥，互斥信号量mutex_z23控制thread2,thread3对全局变量z的访问读写互斥，没有同步关系要考虑。

semaphore mutex_y13 = 1, mutex_y23 = 1, mutex_z23 = 1;

thread1()              |thread3()
{                      |{
    complex w;         |    complex w;
    P(mutex_y13);      |    w = {1.0, 1.0};
    w = add(x, y);     |    P(mutex_z23);
    V(mutex_y13);      |    z = add(z, w);
    /***/              |    V(mutex_z23);
}                      |    P(mutex_y13);
thread2()              |    P(mutex_y23);
{                      |    y = add(y, w);
    complex w;         |    V(mutex_y23);
    P(mutex_y23);      |    V(mutex_y13);
    P(mutex_z23);      |    /***/
    w = add(y, z);     |}
    V(mutex_y23);      |
    V(mutex_z23);      |
    /***/              |
}                      |

「47」（9分）、

甲乙双方均采用后退N帧协议"GBN"进行持续的双向数据传输，且双方始终采用捎带确认，帧长均为1000B。S(x,y)和R(y,x)分别表示甲方和乙方发送的数据帧，其中x是发送序号，y是确认序号；数据帧的发送序号和确认序号字段均为3b。信道传输速率为100Mbps，RTT=0.96ms。下图👇给出了甲方发送数据帧和接收数据帧的两种场景，其中𝒕0为初始时刻，此时甲方的发送和确认序号均为0，𝒕1时刻甲方有足够多的数据待发送。

问答：

1️⃣对于图𝖆，𝒕0时刻到𝒕1时刻期间，甲方可以断定乙方已正确接收的数据帧数是多少？正确接收的是哪几个帧？帧用S(x,y)表示。

𝟙、甲收到R(3,3)，确认序号是3，断定乙已正确接收3个数据帧，分别是S(0,0),S(1,0),S(2,0)。甲的发送窗口最大exp(3)-1=7。

2️⃣对于图𝖆，从𝒕1时刻起，甲方在不出现超时且未收到乙方新的数据帧之前，最多还可以发送多少个数据帧？其中第一个帧和最后一个帧分别是哪个？帧用S(x,y)表示。

𝟚、5个，分别是S(5,2),S(6,2),S(7,2),S(0,2),S(1,2)。

3️⃣对于图𝖇，从𝒕1时刻起，甲方在不出现新的超时且未收到乙方新的数据帧之前，需要重发多少个数据帧？重发的第一个帧是哪个？帧用S(x,y)表示。

𝟛、3个，分别是S(2,3),S(3,3),S(4,3)。

4️⃣甲方可以达到的最大信道利用率是多少？

𝟜、单次最多发7个数据帧，(7×1000B÷100Mbps)÷(0.96ms+2×1000B÷100Mbps)=50%。