2015年网易前端开发笔试题

　　总共有两大部分，第一部分为计算机科学基础题，所有技术岗的笔试者都要答。第二部分为「专业题」，根据所报岗位不同而分别出题。

　　表示试卷发下来，我就傻眼了，前面12道选择题+3道填空题，属于所有技术岗位都必须考的计算机专业基础题。

　　由于我不是计算机专业的，不少计算机科学很理论化的知识的确是不了解，刚刚搜到CSDN 已经有人放出了前面的一部分，自己也就先 COPY 过来吧，解析部分为自己整理，若出错，请指正。

　　1.(2分)对于多关键字而言，那种文件组织方便而又高效()

　　A、顺序文件 B、倒排文件 C、散列文件 D、B+树索引文件

　　解析:答案 B。

　　文件在外存上的基本的组织方式有四种：顺序组织，索引组织，散列组织和链组织;对应的的文件名称分别为：顺序文件、索引文件、散列文件和多关键字文件。选择哪一种文件组织方式，取决于对文件中记录的使用方式和频繁程度、存取要求、外存的性质和容量。

　　多关键字文件:包含有多个次关键字索引的文件称为多关键字文件。

　　倒排表的主要优点是：在处理复杂的多关键字查询时，可在倒排表中先完成查询的交、并等逻辑运算，得到结果后再对记录进行存取。这样不必对每个记录随机存取，把对记录的查询转换为地址集合的运算，从而提高查找速度。

　　2.(2分)以下哪些算法可用于遍历网络图()

　　A、广度优先搜索 B、深度优先搜索 C、线性规划策略 D、决策树

　　解析:答案 A、B。

　　广度优先搜索假设从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后再分别从这些邻接点出发依次访问它们的邻接点，并使先被访问的顶点的邻接点先于后被访问的顶点的邻接点被访问(因此需要用队列来存储顶点)，直到图中所有已被访问的顶点的邻接点都被访问为止。如果此时图中还有未被访问的顶点，则另选图中未被访问的顶点作为起点，重复上述过程，直到图中所有顶点都被访问为止。

　　深度优先搜索法是树的先根遍历的推广，它的基本思想是：从图G的某个顶点v0出发，访问v0，然后选择一个与v0相邻且没被访问过的顶点vi访问，再从vi出发选择一个与vi相邻且未被访问的顶点vj进行访问，依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则退回到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点w，从w出发按同样的方法向前遍历，直到图中所有顶点都被访问。

　　3.(2分)我们使用一个6元组来表示6个节点的无向图的顶点数，请问以下哪些6元组是可能的组合()

　　A、<1,2,3,4,5,6>

　　B、<2,4,4,2,3,5>

　　C、<1,3,4,2,2,1>

　　D、<1,2,2,4,5,2>

　　解析:

　　无向图:一个无向图(undirected graph)是一个二元组，其中：1.V是非空集合，称为顶点集。2.E是V中元素构成的无序二元组的集合，称为边集。

　　若一个图中每条边都是无方向的，则称为无向图。

　　若G是无向图，则0≤e≤n(n-1)/2

　　4.(2分)以下关于可计算性的说法正确的是()

　　A、 所有问题最终都可以抽象为一个计算模型，图灵机可以在一个有限的时间(虽然可能会占用非常久的时间)内完成计算：现代计算机的设计正是基于该理论。

　　B、 存在部分问题，我们无法在有限时间内，给出解答：但是，所有问题都可以在有限时间内验证其解答的正确性。

　　C、 Godel(哥德尔)第一定律指明不存在完备且相容的公理系统。

　　D、 以上说法都不正确。

　　5.(2分)16进制数值C396和8进制数值64474的异或结果值(10进制)为()

　　A、43690 B、16660 C、60350 D、20375

　　解析:

　　异或:Exclusive OR(异-或运算、模2和),异或(xor)是一个数学运算符。它应用于逻辑运算。异或符号为“^”。真异或假的结果是真，假异或真的结果也是真，真异或真的结果是假，假异或假的结果是假。就是说两个值不相同，则异或结果为真。反之，为假。 不同为1,相同为0.

　　若x是二进制数0101，y是二进制数1011，则x^y=1110。

　　只有在两个比较的位不同时其结果是1，否则结果为0