2015 年 408 真题2015 年 408 数据结构 · 第 1 题选中文字高亮 · 下划线已知程序如下: int S(int n) { return (n <= 0) ? 0 : S(n - 1) + n; } void main() { cout << S(1); } 程序运行时使用栈来保存调用过程的信息,自栈底到栈顶保存的信息依次对应的是( )。Amain() → S(1) → S(0)BS(0) → S(1) → main()Cmain() → S(0) → S(1)DS(1) → S(0) → main()←上一题已知由 n(n≥2) 个正整数构成的集合 A=ak∣0≤k<n ,将其划分为两个不相交的子集 A1 和 A2 ,元素个数分别是 n1 和 n2 , A1 和 A2 中元素之和分别为 S1 和 S2 。设计一个尽可能高效的划分算法,满足 ∣n1−n2∣ 最小且 ∣S1−S2∣ 最大。要求: (1) 给出算法的基本设计思想。 (2) 根据设计思想,采用 C 或 C++ 语言描述算法,关键之处给出注释。 (3) 说明你所设计算法的时间复杂度和空间复杂度。下一题先序序列为 a,b,c,d 的不同二叉树的个数是()。→