创新梦工厂笔试题2013年校园招聘

时间：2012年9月27日地点：鼎好大厦10层

考试时长：1小时

一，选择题

1，求z的结果

1 [cpp] view plaincopyprint?
2 
3     #define N 3  
4     #define Y(n) ((N+1)*n)  
5     z = 2*（N+Y(5+1)）;

解答：48

2,有关多线程，多进程的描述错误的是

A，子进程获得父进程的数据空间，堆和栈的复制品

B，线程可以与同进程的其他线程共享数据，但是它拥有自己的栈空间且拥有独立的执行序列

C，线程执行开销小，但是不利于资源管理和保护

D，进程适合在SMP机器上进行，而线程则可以跨机器迁移

解答：D

3，

1 [cpp] view plaincopyprint?
2 
3     struct s  
4     {  int x:3;  
5        int y:4;  
6        int z:5;  
7      double a;  
8     }

求sizeof（s）

解答：

：是取位的作用，前三个变量是为两个字节，最后double变量是8个字节，

结构体以8字节对齐，则为16字节。

4，序列{2,1,4,9,8,10,6,20}是某排序算法第二轮排序的结果，则该算法只能是

A快速排序 B冒泡排序

C选择排序 D插入排序

解答：A

5，我们需要监听一个事件状态，让它在状态发生改变时主动发出通知，请问需要哪种设计模式？

A装饰者模式 B建造者模式

C创新工场模式 D观察者模式

解答：D

6，有2012瓶矿泉水，其中有一瓶有毒，请问需要多少只老鼠才能一次性找到有毒的矿泉水？

解答：11只

二，问答题

1，有0-n这n+1个数，但是其中丢了一个数，请问如何找出丢了哪个数？

解答：

求这n个数的sum，然后计算n(n+1)/2-sum可得。

2，解释

1 [cpp] view plaincopyprint?
2 
3     #typedef char (*func)(int,char*)

解答：

定义了一个函数指针的数据类型；

该数据类型可以用来定义函数指针；

定义的函数指针指向的函数的参数为

1 [cpp] view plaincopyprint?
2 
3     (int,char*)

返回值为char型。

3，求输出结果

1 [cpp] view plaincopyprint?
2 
3     int a[2][2][3]= { {{1,2,3},{4,5,6}},{{7,8,9},{10,11,12}}};  
4     int *ptr=(int *)(&a+1);  
5     printf(“%d %d”, *(int*)(a+1), *(ptr-1));

解答：

7 12 （已修定）

考察多级指针，一定要明确指针指向的是什么，才能知道它加1后跳过了多少字节。

&a是个四级指针，指向的是a这样的数组，所以它加1，就会跳过整个数组。

4，求输出结果

 1 [cpp] view plaincopyprint?
 2 
 3     #include <iostream>  
 4     using namespace std;  
 5     class A  
 6     {  
 7     public:  
 8         virtual void print()  
 9         { cout << "A::print()" <<endl;}  
10     };  
11     class B: public A  
12     {  
13     public:  
14         virtual void print()  
15         { cout << "B::print()" <<endl;}  
16     };  
17     class C: public A  
18     {  
19     public:  
20         virtual void print()  
21         { cout << "C::print()" <<endl;}  
22     };  
23     void print(A a)  
24     {  
25         a.print();  
26     }  
27     void main()  
28     {  
29         A a,*aa,*ab,*ac;  
30         B b;  
31         C c;  
32         aa=&a;  
33         ab=&b;  
34         ac=&c;  
35         a.print();  
36         b.print();  
37         c.print();  
38         aa->print();  
39         ab->print();  
40         ac->print();  
41         print(a);  
42         print(b);  
43         print(c);  
44     }

解答：

A::print();

B::print();

C::print();

A::print();

B::print();

C::print();

A::print();

三，算法编程题

1，有1分,2分,5分,10分四种硬币，每种硬币数量无限，给定n分钱，求有多少种组合可以组合成n分钱？

解答：

思路：

①，四层循环

②，使用回溯法在空间中搜索

代码为思路2：

 1 [cpp] view plaincopyprint?
 2 
 3     // chuangxingongchan.cpp : 定义控制台应用程序的入口点。  
 4     //  
 5       
 6     #include "stdafx.h"  
 7     #include <vector>  
 8     #include <iostream>  
 9     using namespace std;  
10       
11     int count=0;  
12     int Target=0;  
13       
14     int coin[4]={1,2,5,10};  
15     int total=0;  
16     vector<int> solution;  
17       
18     void dfs(int index)  
19     {  
20         if( total == Target )  
21         {  
22             count++;  
23             cout << count <<":" ;  
24             for( int i=0; i<(int)solution.size(); i++)  
25             {  
26                 cout  << solution[i]<<" ";  
27             }  
28             cout << endl;  
29             return;  
30         }  
31       
32         if( total > Target )  
33             return;  
34       
35         for( int i=index; i<4; i++)  
36         {  
37             total += coin[i];  
38             solution.push_back( coin[i] );  
39             dfs(i);  
40             solution.pop_back();  
41             total -=coin[i];  
42         }  
43     }  
44       
45     int _tmain(int argc, _TCHAR* argv[])  
46     {  
47         while(1)  
48         {  
49             count=0;  
50             cin >> Target;  
51             dfs(0);  
52             cout << count <<endl;  
53         }  
54         return 0;  
55     }

2，马戏团里有个叠罗汉的表演，为了便于美观，下面的人身高和体重都要大于上面的人。现在知道n个演员的身高和体重，请问最多能叠多少层？

解答：

思路：

首先生成一个有向图，用连接矩阵的方式来表示。

map[i][j]==1表示第i个人上面可以放第j个人。

然后开始对每个人进行深度搜索，这个图中不可能有环。

所以对于每个人来说就是一棵树，搜索树的高度。

再找出最高的高度即是答案。

  1 [cpp] view plaincopyprint?
  2 
  3     #include "stdafx.h"  
  4     #include <iostream>  
  5     #include <fstream>  
  6     #include <vector>  
  7     #include <cstdlib>  
  8     using namespace std;  
  9       
 10     int N=0;  
 11     double *weight;  
 12     double *height;  
 13       
 14     int **map;  
 15     int maxDepth=0;  
 16       
 17     vector<int> bestPath;  
 18       
 19     int dfs( int index, vector<int> &path )  
 20     {  
 21         int flag=0;  
 22         int depth = 0;  
 23         vector<int> bestPath;  
 24         for( int i=0; i<N;i++)  
 25         {  
 26             if( map[index][i] != 0)  
 27             {   
 28                 flag = 1;  
 29                 vector<int> tPath;  
 30                 int t = dfs(i, tPath);  
 31                 if( t > depth )  
 32                 {  
 33                     path = tPath;  
 34                     depth = t;  
 35                 }  
 36             }  
 37         }  
 38       
 39         if( flag==0 )  
 40         {     
 41             path.clear();  
 42             path.push_back(index);  
 43             return 1;  
 44         }  
 45         else  
 46         {  
 47     //      path = bestPath;  
 48             path.push_back(index);  
 49             return depth+1;  
 50         }  
 51     }  
 52       
 53     void CreateMap()  
 54     {  
 55         map = new int*[N];  
 56       
 57         for( int i=0; i<N; i++)  
 58         {  
 59             map[i] = new int [N];  
 60             memset( map[i], 0, N*sizeof(int) );  
 61         }  
 62       
 63         for( int i=0; i<N; i++)  
 64         {  
 65             for( int j=0; j<N; j++)  
 66             {  
 67                 if( weight[j]<weight[i] && height[j]<height[i] )  
 68                     map[i][j]=1;  
 69             }  
 70         }  
 71     }  
 72       
 73     void CreateData()  
 74     {  
 75         ofstream out( "in.txt" );  
 76         int N = 30;  
 77         out << N <<endl;  
 78         for( int i=0; i<N; i++)  
 79             out << rand() << " ";  
 80         out << endl;  
 81       
 82         for( int i=0; i<N; i++)  
 83             out << rand() << " ";  
 84     }  
 85       
 86     int main()  
 87     {  
 88         CreateData();     
 89         freopen( "in.txt", "r", stdin );  
 90         cout << "Please input N:" <<endl;  
 91         cin >> N;  
 92         height = new double[N];  
 93         weight = new double[N];  
 94         for( int i=0; i<N; i++)  
 95             cin >> height[i];  
 96         for( int i=0; i<N; i++)  
 97             cin >> weight[i];  
 98       
 99         CreateMap();  
100         int depth=0;  
101         for(int i=0; i<N;i++)  
102         {  
103             vector<int> tPath;  
104             int t=dfs(i,tPath);  
105             if( t>depth )  
106             {  
107                 bestPath = tPath;  
108                 depth = t;  
109             }  
110         }  
111         cout << depth <<endl;  
112         for( int i=0; i<(int)bestPath.size(); i++)  
113         {  
114             cout << height[bestPath[i]]<< " " << weight[bestPath[i]]<<endl;  
115         }  
116         return 0;  
117     }

转自：http://blog.csdn.net/huangxy10/article/details/8026464