阅读下列说明和C代码，回答问题1至问题3，将解答写在答题纸的对应栏内。 【说明】 在一块电路板的上下两端分别有n个接线柱。根据电路设计，用(i，π(i))表示将上端接线柱i与下端接线柱Ⅱ(i)相连，称其为该电路板上的第i条连线。如图4．1所示的π(i)排列为{8，7，4，2，5，1，9，3，10，6}。对于任何l≤i π(j)。 在制作电路板时，要求将这n条连线分布到若干绝缘层上，在同一层上的连线不相交。现在要确定将哪些连线安排在一层上，使得该层上有尽可能多的连线，即确定连线集Nets={(i，π(i))，1≤i≤n}的最大不相交子集。 [*] 【分析问题】 记N(i，j)={t｜(t,n(t))~Nets，t≤i，7c(t)≤j)。N(i，j)的最大不相交子集为MNS(i，j)，size(i，j)=IMNS(i，j)｜。 经分析，该问题具有最优子结构性质。对规模为n的电路布线问题，可以构造如下递归式： [*] 【C代码】 下面是算法的C语言实现。 (1)变量说明 size[i][j]：上下端分别有i个和j个接线柱的电路板的第一层最大不相交连接数 pi[i]：π(i)，下标从1开始 (2)C程序 #include“stdlib” #include #define N 1 0 ／*问题规模*／ int m=0； ／*记录最大连接集合中的接线柱*／ void maxNum(int pi[]，int si ze IN+1][N+1]，int n) { ／*求最大不相交 连接数*／ int i，j； for(j=0；j=π(1)时*／ for(i=2；i=C[i]时，考虑两种情况*／ size[i][j]=size[i一1][j]>=size[i一1][pi[i]一1]+l?size[i一1][j]： size[i一1][pi[i]一1]+1； } } ／*最大连接数*／ size[n][n] =size[n一1][n] >=si ze[n一1][pi[n]一1]+1? size[n一1][n]： si ze[n一1][pi[n]一1]+1； } ／*构造最大不相交连接集合，net[i]表示最大不相交子集中第i条连线的上端接线柱的序号*／ void constructSet(int pi[]， int size[N+ 1][N+ 1]， int n， int net[n]} { int i， j=n； m=0； for(i=n；i>1；i一一) { ／*从后往前*／ if(size[i][j]!=size[i一1][j]){ ／*(i，pi[i])是最大不相交子集的一条连线*／ (3) ； ／*将i记录到数组net中，连接线数自增1*／ j=pi[i]－1； ／*更新扩展连线柱区间*／ } } if(j >=pi[1]) net[m++] =1； ／*当i=1时*／ }
问答题 根据以上说明和C代码，填充C代码中的空(1)～(3)。
【正确答案】正确答案：(1)size[1][j]=1 (2)size[i][j]=size[i-1][i] (3)net[m++]=i或其等价形式
【答案解析】解析：本题考查算法设计和C语言实现算法的能力。 本题要求考试对常用的算法设计策略，包括分治法、动态规划、贪心算法、回溯法等有基本的掌握，并理解每类算法策略中的几个典型实例。 一般不要求考生设计问题的求解算法，但要求考生能够理解题目给出的算法设计思路，并补充C程序。如本题中的空(1)，可以根据题干中递归式第一部分和C代码中的注释，得到答案size[1][j]=1。空(2)则根据阅读题干中递归式第二部分和C代码中的注释，得到答案size[i][j]=size[i-1][i]。
问答题 根据题干说明和以上C代码，算法采用了(4)算法设计策略。函数maxNum和constructSet的时间复杂度分别为(5)和(6)(用O表示)。
【正确答案】正确答案：(4)动态规划 (5)O(n 2 ) (6)O(n)
【答案解析】解析：题干在叙述过程中，较明显的提到了动态规划策略的几个特点，如最优子结构，递归式，自底向上求解等，因此这是一个动态规划算法。算法的时间复杂度分析也较简单。函数maxNum中有两重循环，时间复杂度为O(n 2 )。函数constructSet中有一重循环，时间复杂度为O(n)。
问答题 若连接排列为{8，7，4，2，5，1，9,3，10,6}，即如图4-1所示，则最大不相交连接数为(7)，包含的连线为(8) (用(i，π(i))的形式给出)。
【正确答案】正确答案：(7)4 (8)(3，4)(5，5)(7,9)(9，10)
【答案解析】解析：本问题考查该算法的一个实例，理解了题干就可以直接计算出该实例的解，即最大不相交连接数为4，连线为：(3，4)(5,5)(7,9)(9，10)。