School

2024春南京大学信计强基信息与计算科学实践考试题目速报(Prof. Jianhua Zhao)

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

P1

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

P2

(15pts)

有形如这样的单链表：

1
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)$区间从小到大排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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)$的。