创新工场 2022 研发面试题（求职面试回答资料）

1、 创新工场 2022 研发面试题第1题： 一、不定项选择 1、在一个有8个int数据的数组中，找出最大和其次大元素至少需要进行（）次比较： A、8 B、9 C、10 D、11 1、C 先取两个数 比较 1次， 找到 最大和其次大 然后取两个数， 这两个数先比较， 得到一大一小。 用大数去跟之前最大的比， 假如比之前最大的大， 就用小数再跟最大的比。 假如比之前最大的小， 就再跟其次大的比。总之 经过 这样的3次比较， 又可以找出最大的和其次大的。 以此类推。 8个数正好分成4组两个数， 所以总比较次数为 1+ 3+ 3+3 = 10 第2题： 2、在关系数据库中，用来表示实体之间联系的是（）

2、A、树结构 B、网结构 C、线性表 D、二维表 2、D 关系数据库中用二维表来表示实体之间的联系 第3题： 3、对于基本有序的序列，根据那种排序方式最快： A、快速排序 B、冒泡排序 C、归并排序 D、基数排序 3、B 冒泡排序、快速排序、堆排序的性能比较对比 排序方法 比较次数 移动次数 稳定性 帮助空间 最好 最差 最好 最差 最好 最差 冒泡排序 n n2 0 n2 是 1 1快速排序 nlogn n2 logn n 否 logn n堆排序 nlogn nlogn nlogn nlogn 否 1 1而当待排序列已基本有序时，对冒泡排序来说是最好状况，对快速排序来说就是最差状况，而堆排序则

3、最好最差都一样。因此本题答案是冒泡排序。 第4题： 4、位示图的用处为： A、主存空间的共享 B、文件的爱护和加密 C、磁盘空间的管理 D、文件名目的查找 4、C 位示图是利用二进制的一位来表示磁盘中的一个盘块的使用状况。当其值为“0”时，表示对应的盘块空闲；为“1”时，表示已经安排。有的系统把0作为盘块已安排的标记，把“1”作为空闲标志。(它们的本质上是相同的，都是用一位的两种状态表示 空闲和已安排两种状况。)磁盘上的全部盘块都有一个二进制位与之对应，这样，由全部盘块所对应的位构成一个集合，称为位示图。 A 用于分页式存储管理中主存空闲块的安排和回收 D 用于文件存储空间的管理 第5题： 5

4、、16进制数值31B6和8进制数值73615的异或结果值（10进制）为： A、18779 B、11503 C、17979 D、13561 5、C 1.分别将这两个数转换为二进制数： 31B6=11000110110110 73615 =111011110001101 2.两者异或，相同为0，不同为1则： 011000110110110 111011110001101 3.答案如下： 100011000111011 =17979 选c 第6题： 6、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是： A、10 B、11 C、12 D、13 6、B 全部点的入度和出度的和

5、相等， 下面等式左边为出度， 右边为入度（根节点入度为0， 其他节点入度为1） 10 * 2 + 5 * 1 = 10 + 5 + x -1 x等于11 第7题： 7、上网时候发觉网页不能访问，使用正常，消失此问题可能的缘由是： A、网线问题 B、DNS问题 C、IP地址冲突 D、网关错误 7、B DNS是将域名解析成IP地址的服务。DNS发生问题时无法通过域名访问网页；但是直接通过IP地址连接的应用程序仍可以使用。 第8题： 8、由权值为9,2,7,5的四个叶子节点构造一棵哈夫曼树，该树的带权路径长度为： A、23 B、37 C、44 D、27 8、C 带权路径长=5*3+2*3+7*2+9

6、*1=44 第9题： 9、在一个单链表中，若p所指结点不是最终结点，在p之后插入s所指结点，则执行？ A、s-next=p ; p-next=s ; B、s-next=p-next; p-next=s; C、s-next=p-next ; p=s; D、p-next=s ; s-next=p; 9、B 让s指向p的下一个节点；再让p指向x 第10题： 二、解答题 10、对于非负序列a1、a2、an，在数轴上做垂线连接点（i，0）和（i，ai）。选择这样的两条线和x轴可以形成一个容器，我们以面积代表所装的水，求以这种方式构成的容器能装的最大面积。比如选择a2=3、a5=6，则所装的面积为9. 1

7、0、 int maxArea(int height, int n) int head = 0, tail = n - 1; int max = 0, temp = 0; while (head tail) temp = tail - head; if (heighthead heighttail) temp *= heighthead; head+; else temp *= heighttail; tail-; if (temp max) max = temp; return max; 或者 class Program static void Main(string args) int n;

8、 int A=new int; int s = 0; for (int i = 0; i n; i+) s = A0 + An; Console.WriteLine(s); Console.ReadKey(); 第11题： 11、假设有如下一个链表： struct Node int value ; struct Node *next ; struct Node *random ; 其中，random指向该链表的任意一个节点或者NULL，请编程实现该链表的深拷贝。 Node *deepCopy (Node *head) 11、 struct Node int value ; struct Nod

9、e *next ; struct Node *random ; struct pair struct Node *one; struct Node *two; Node *deepCopy(struct Node *head) vectorstruct pair pa; struct Node *head1 = new struct Node; head1-value = head-value; struct pair pnode; pnode.one = head; pnode.two = head1; pa.push_back(pnode); struct Node *node = hea

10、d-next; struct Node *node1 = head1; while (node) struct Node *temp = new struct Node; temp-value = node-value; temp-next = NULL; temp-random = NULL; node1-next = temp; pnode.one = node; pnode.two = temp; node = node-next; node1 = temp; node = head; node1 = head1; while (node) if (node-random = NULL)

11、 node1-random = NULL; else node1-random = find(node-random,pa); node = node-next; node1 = node1-next; return head1; struct Node *find(struct Node *node, vectorstruct pair pa) for (int i=0; ipa.size(); i+) if (node = pai.one) return pai.two; return NULL; 或者 Node *deepCopy (Node *head) Node* now = head; Node* next = head-next; while( now != NULL ) Node * copy = new Node; copy-value = now-value; copy-next = now-next; now -next = copy; now = next; next = next-next; now = head; while( now != NULL ) now-next-random = now-random-next; now = now-next-next;