阅读下列说明和C代码,回答问题1至问题3,将解答写在答题纸的对应栏内。 【说明】 ????在一块电路板的上下两端分别有n个接线柱。根据电路设计,用(i,π(i))表示将上端接线柱i与下端接线柱π(i)相连,称其为该电路板上的第i条连线。如图4-1所示的π(i)排列为{8,7,4,2,5,1,9,3,10,6}。对于任何1≤i<j≤n,第i条连线和第j条连线相交的充要条件是π(i)>π(j)。 【问题1】(6分) 根据以上说明和C代码,填充C代码中的空(1)~(3)。 【问题2】(6分)??? ????据题干说明和以上C代码,算法采用了??(4)?算法设计策略。?????? 函数maxNum和constructSet的时间复杂度分别为??(5)??和???(6)?(用O表示)。? 【问题3】(3分)??? ????若连接排列为{8,7,4,2,5,1,9,3,10,6},即如图4-1所示,则最大不相交连接数为???(7)??,包含的连线为??(8)??(用(i,π(i))的形式给出)。
【问题1】(6分) (1)size[i][j]=1; (2)size[i][j]=size[i-1][j]; (3)net[m++]=i; 【问题2】(6分) (4)动态规划算法;(5)O(n2);(6)O(n) 【问题3】(3分) 若连接排列为{8,7,4,2,5,1,9,3,10,6},即如图4-1所示,则最大不相交连接数为 (7) ,包含的连线为 (8) (用(i,π(i))的形式给出)。 (7) 4 (8)(9,π(9),(7,π(7)),(5,π(5)),(3,π(3))