西山居中大宣讲会现场笔试 游戏开发

9.24 15：00-17：00 西山居中大宣讲会现场笔试 游戏开发
一 填空题
1 判断while循环次数：

    int y = 2;
    while (y < 32)y = y + y;

答案： 4
次 1 2 3 4
y= 4 8 16 32

2 在[-2,2]区间取两个数，他们的和大于1的概率
答案： 9/32
解析： 画图 33/2/(44)

3 ping指令用到什么协议？
答案：ICMP协议 是TCP/IP协议的子协议

4 辗转相除法求最大公约数的时间复杂度，设较大的数为N
答案： O(logN)
由公式： m%n<=m/2 可知：每次递归调用，问题的规模减小一半，类似于二分查找，这显然是一个非常好的算法。

由于第2-5行，花费的时间为常量时间，同样，在第9-10行的if语句判断也是花费的常量时间，在第11行进行递归调用，问题规模减少一半。

可得出，T(N) = T(N/2)+O(1) 推出：时间复杂度为O(logN)
5：

8/（2*2.5）

6 在x86-64位的计算机上输出结果为：

void f(char str[100])
{
    char s[] = "hello"; //6 因为最后有'\0'
    char* p = s; //8，64位计算机
    int x = 4; //4
    cout << sizeof(str) << sizeof(s)<<sizeof(p)<<sizeof(x);
}

答案： 8684

二 描述你用程序解决的最难问题，可以画图。
三 两个有序链表归并
四 改错 分C++和Java
C++考察位运算和类的定义与使用；
32位的描述符可以描述32个ID的状态是开启还是关闭；

五 写一个类 Space代表空间，可以存成千上万个点，实现两个成员函数
1 给三维坐标，加入点
2 给两个点的三维坐标，它们构成一个长方体的容量盒，返回所有在盒内的点

struct Point
{
    int x;
    int y;
    int z;
};
class Space 
{
private:
    vector<Point> points;
public:
    Space(){}
    ~Space() { points.clear(); }
    void setpoint(int x, int y, int z)
    {
        Point p;
        p.x = x; p.y = y; p.z = z;
        points.push_back(p);
    }
    vector<Point> inbox(int x1, int y1, int z1, int x2, int y2, int z2);
};
bool isinbox(int minx, int maxx, int miny, int maxy, int minz, int maxz, Point p)
{
    return (p.x >= minx && p.x <= maxx && p.y >= miny && p.y <= maxy && p.z >= minz && p.z <= maxz);
}
vector<Point> Space::inbox(int x1, int y1, int z1, int x2, int y2, int z2)
{
    vector<Point> ps;
    int minx = x1 < x2 ? x1 : x2;
    int maxx = x1 > x2 ? x1 : x2;
    int miny = y1 < y2 ? y1 : y2;
    int maxy = y1 < y2 ? y1 : y2;
    int minz = z1 < z2 ? z1 : z2;
    int maxz = z1 > z2 ? z1 : z2;
    for (int i = 0; i < points.size(); i++)
        if (isinbox(minx, maxx, miny, maxy, minz, maxz, points[i]))
            ps.push_back(points[i]);    
    return ps;
}

六 奇妙的题目 ，我没有弄懂