120分钟满分100，闭卷。手写代码C++。

P1

(10pts) public protected private成员对（类内部、子类、外部、友元）的可见性？

P2

(15pts)

有形如这样的单链表：

struct Node{int data; Node* link;}

满足data在链表上严格递增。

给出两个链表头first和second，判断这两个链表有没有相同的尾部。（即存不存在一个节点又是first的某个后继又是second的某个后继）

要求：额外空间常数级，每个链表上的每个节点访问不超过1次。

P3

(1)

(10pts)
用泛型和数组实现栈：class Stack，其数据类型为TYPE,数组最大大小为N。要求实现push, pop, isEmpty和构造函数。

（2）

(5pts)
用两个上述Stack实现int类型的Queue，要求实现push和dequeue。

P4

(15pts)
用数学归纳法证明该程序一定终止并且能将A数组的[L,R)区间从小到大排序。

void Sort(int A[], int L, int R){
    if(L+1>=R){
        return;
    }
    if(L+2==R){
        if(a[L]>a[L+1]){
            swap(a[L],a[L+1]);
        }
        return;
    }
    int mid1=L+(R-L)/3;
    int mid2=R-(R-L)/3;
    Sort(A,mid1,R);
    Sort(A,L,mid2);
    Sort(A,mid1,R);
}

P5

(10pts)
给出整数数组A和大小N.求A的最大连续区间和。

要求：额外空间常数，A中每个元素访问不超过1次。

P6

(15pts)
给定字符串S，判断S是identifier（字母+字母/数字），int（数字），float（数字+点+数字）还是error（其他情况）。S末尾可能有空格。返回值要求是enum TokenType{INT,FLOAT,IDENTIFIER,ERROR}

P7

有虚基类Figure和虚函数：
- draw() :不要求实现
- Rectangle getRect()：Rectangle是一个结构，有top,bottom,left,right四个参数。getRect应该返回包括该图形的最小矩形。
- Move(int x,int y)： 向左移动x，下移动y。

*没错，原题就是命名方式大小写不一致的

另有复合图形是多个图形的组合，在移动时所有的子图形都会移动。

(1)

(15pts)

请设计：
- Circle和Rectangle类
- 复合图形类

(2)

(5pts)

假设有bool isValid Rectangle rect Figure* parent三个新成员变量，其中rect只有在isValid为真时有意义。重写Move()和getRect()以实现getRect()的高效求解方法，使得如果该图形和其子图形没有移动过，getRect()是O(1)的。