创新工场 2021 研发岗面试题

第一部分 单选题
1、在一个单链表中，若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;

第2题：

2、在关系数据库中，用来表示实体之间联系的是：
A. 树结构 B. 网结构 C. 线性表 D. 二维表

第3题：

3、对于基本有序的序列，按照那种排序方式最快：

A. 快速排序 B. 冒泡排序 C.归并排序 D. 基数排序

第4题：

4、位示图的用处为：
A.主存空间的共享
B.文件的保护和加密
C.磁盘空间的管理
D．文件目录的查找

第5题：

5、16进制数值31B6和8进制数值73615的异或结果值（10进制）为：
A. 18779 B. 11503 C. 17979 D. 13561

第6题：

6、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是：
A. 10 B. 11 C. 12 D. 13

第7题：

7、上网时候发现网页不能访问，QQ使用正常，出现此问题可能的原因是：
A. 网线问题 B. DNS问题 C. IP地址冲突 D. 网关错误

第8题：

8、由权值为9,2,7,5的四个叶子节点构造一棵哈夫曼树，该树的带权路径长度为：
A. 23 B. 37 C. 44 D. 27

第9题：

10、在一个有8个int数据的数组中，找出最大和第二大元素至少需要进行（）次比较：
A. 8 B. 9 C. 10 D. 11

第10题：

二、编程题：
1、有一个数组中所有元素均为非负数，如何调整数组汇总元素的顺序将0放在所有正数的后面
void f（int a[] , int size）

第11题：

2、对于非负序列a1、a2、……、an，在数轴上做垂线连接点（i，0）和（i，ai）。选择这样的两条线和x轴可以形成一个容器，我们以面积代表所装的水，求以这种方式构成的容器能装的最大面积。比如选择a2=3、a5=6，则所装的面积为9.

第12题：

3、假设有如下一个链表：
struct Node {
int value ;
struct Node * next ;
struct Node * random ;
}
其中，random指向该链表的任意一个节点或者NULL，请编程实现该链表的深拷贝。
Node * deepCopy (Node * head)