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

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

P1

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

P2

(15pts)

有形如这样的单链表:

struct Node{int data; Node* link;}

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

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

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

P3

(1)

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

(2)

(5pts)
用两个上述Stack实现int类型的Queue,要求实现pushdequeue

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)的。

版权声明:
作者:XGN
链接:https://blog.hellholestudios.top/archives/1415
来源:Hell Hole Studios Blog
文章版权归作者所有,未经允许请勿转载。

THE END
分享
二维码
< <上一篇
下一篇>>
文章目录
关闭
目 录