民生银行-民芯计划-专业笔试
民生银行-民芯计划-专业笔试
三部分：30道单选+2道问答+2道编程
一、单选
-
经典算法
-
贪婪算法
贪心算法（也叫贪婪算法）是指在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，只做出在某种意义上的局部最优解。贪心算法不是对所有问题都能得到全局最优解，得到的是局部最优解，关键是贪心策略的选择，不同的贪婪策略会导致得到差异非常大的结果。选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。
一般步骤： 建立数学模型来描述问题； 把求解的问题分成若干个子问题； 对每一子问题求解，得到子问题的局部最优解； 把子问题的局部最优解合成原来问题的一个解。
-
动态规划
动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。
动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的（即下一个子阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解）。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。
我们可以用一个表来记录所有已解的子问题的答案。
不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。
应用场景： 适用动态规划的问题必须满足最优化原理、无后效性和重叠性。
-
分治法
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。 求出子问题的解，就可得到原问题的解。
运用分治策略解决的问题一般来说具有以下特点：
原问题可以分解为多个子问题。这些子问题与原问题相比，只是问题的规模有所降低，其结构和求解方法与原问题相同或相似。
原问题在分解过程中，递归地求解子问题。由于递归都必须有一个终止条件，因此，当分解后的子问题规模足够小时，应能够直接求解。
在求解并得到各个子问题的解后应能够采用某种方式、方法合并或构造出原问题的解。
不难发现，在分治策略中，由于子问题与原问题在结构和解法上的相似性，用分治方法解决的问题，大都采用了递归的形式。在各种排序方法中，如归并排序、堆排序、快速排序等，都存在有分治的思想。
-
回溯法
回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯法就是对隐式图的深度优先搜索算法。 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含（剪枝过程），则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。
回溯法为了避免生成那些不可能产生最佳解的问题状态，要不断地利用限界函数(bounding function)来处死(剪枝)那些实际上不可能产生所需解的活结点，以减少问题的计算量。具有限界函数的深度优先生成法称为回溯法。
（回溯法 = 穷举 + 剪枝）
两个常用的剪枝函数：
约束函数：在扩展结点处减去不满足约束的子数
限界函数：减去得不到最优解的子树
用回溯法解题的一个显著特征是在搜索过程中动态产生问题的解空间。
-
分支定界法
分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。 此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所需的解或活结点表为空时为止。
分支限界法的搜索策略：
在当前节点（扩展节点）处，先生成其所有的儿子节点（分支），然后再从当前的活节点（当前节点的子节点）表中选择下一个扩展节点。为了有效地选择下一个扩展节点，加速搜索的进程，在每一个活节点处，计算一个函数值（限界），并根据函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间上有最优解的分支推进，以便尽快地找出一个最优解。分支限界法解决了大量离散最优化的问题。
-
-
Socket通信使用的底层协议-------TCP/IP
-
线程
一旦一个线程被创建，它就立即开始运行。----x
-----解释：进程被创建首先进入就绪队列，之后根据调度算法进行运行
一个线程可能因为不同的原因停止并进入就绪状态。-----√
------解释：有可能是时间片用完进入就绪状态，有可能是被优先级高的线程抢占而进入就绪状态！
当一个线程因为抢先机制而停止运行，它被放在可运行队列的前面。----x ------解释：因为抢先机制而停止运行，说明该线程的优先级比较低，不可能排到可运行队列的前面。
使用start()方法可以使一个线程成为可运行的，但是它不一定立即开始运行。-----√
-
下面哪条语句把方法声明为抽象的公共方法?（ B ）
A．public abstract method();
B．public abstract void method();
C．public abstract void method(){}
D．public void method() extends abstract;
-
攻击者在远程WEB页面的HTML代码中插入具有恶意目的的数据,用户认为该页面是可信赖的,但是当浏览器下载该页面嵌入其中的脚本将被解释执行。这是那种类型的漏洞 D
A.缓冲区溢出
B. SQL注释
C、设计错误
D、跨站脚本
-
利用FTP进行文件传输时的主要安全问题存在于：（）D 信息安全工程
A、 匿名登录不需要密码
B、 破坏程序能够在客户端运行
C、 破坏程序能够在服务器端运行
D、 登录的用户名和密码会明文传输到服务器端
-
消息的数字签名其实是一个数值，它依赖于只有签名者知道的某个秘密数和待签的消息内容。数字签名应具有如下性质。 信息安全工程
● 能够验证签字产生者的身份
● 能用于证实被签消息的内容
● 数字签字可由第三方验证，从而能够解决通信双方的争议。
-
由多个源文件组成的C程序，经过编辑、预处理、编译、链接等阶段会生成最终的可执行程序。下面哪个阶段可以发现被调用的函数未定义？
预处理
编译
链接
执行
正确答案：C
-
Hive --数据仓库的工具
- hive的优点
(1)简单容易上手：提供了**类SQL查询语言HQL**(2)**可扩展**：为超大数据集设计了计算/扩展能力（MR作为计算引擎，HDFS作为存储系统）一般情况下不需要重启服务Hive可以自由的扩展集群的规模。 (3)提供统一的**元数据管理** (4)延展性：Hive支**持用户自定义函数**，用户可以根据自己的需求来实现自己的函数 (5)容错：**良好的容错性，节点出现问题SQL仍可完成执行**-
hive的缺点（局限性）
(1)hive的HQL表达能力有限 1)迭代式算法无法表达，比如pagerank 2)数据挖掘方面，比如kmeans (2)hive的效率比较低 1)hive自动生成的mapreduce作业，通常情况下不够智能化 2)hive调优比较困难，粒度较粗 3)hive可控性差
-
时间复杂度大小的比较：
O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
-
信息安全的基本属性主要表现在以下5个方面:
(1)保密性(Confidentiality)
即保证信息为授权者享用而不泄漏给未经授权者。
(2)完整性(Integrity)
即保证信息从真实的发信者传送到真实的收信者手中，传送过程中没有被非法用户添加、删除、替换等。
(3)可用性(Availability)
即保证信息和信息系统随时为授权者提供服务，保证合法用户对信息和资源的使用不会被不合理的拒绝。
(4)可控性(Controllability)
即出于国家和机构的利益和社会管理的需要，保证管理者能够对信息实施必要的控制管理，以对抗社会犯罪和外敌侵犯。
(5)不可否认性(Non-Repudiation)
即人们要为自己的信息行为负责，提供保证社会依法管理需要的公证、仲裁信息证据。
-
int *p=malloc(100); 求 sizeof(p)
sizeof(p) = 4;
-
在关系数据库设计中，设计关系模式是（ 逻辑设计阶段）的任务
-
国际权威的学术组织the IEEE International Conference on Data Mining (ICDM) 2006年12月评选出了数据挖掘领域的十大经典算法：C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART.
-
用栈实现递归与非递归的转换
-
实例中，bin文件的第一个属性用"d"表示。"d"在Linux中代表该文件是一个目录文件。
在Linux中第一个字符代表这个文件是目录、文件或链接文件等等。
当为[ d ]则是目录 当为[ - ]则是文件； 若是[ l ]则表示为链接文档(link file)； 若是[ b ]则表示为装置文件里面的可供储存的接口设备(可随机存取装置)； 若是[ c ]则表示为装置文件里面的串行端口设备，例如键盘、鼠标(一次性读取装置)。 接下来的字符中，以三个为一组，且均为『rwx』 的三个参数的组合。其中，[ r ]代表可读(read)、[ w ]代表可写(write)、[ x ]代表可执行(execute)。 要注意的是，这三个权限的位置不会改变，如果没有权限，就会出现减号[ - ]而已。
每个文件的属性由左边第一部分的10个字符来确定(如下图)。
从左至右用0-9这些数字来表示。
第0位确定文件类型，第1-3位确定属主(该文件的所有者)拥有该文件的权限。
第4-6位确定属组(所有者的同组用户)拥有该文件的权限，第7-9位确定其他用户拥有该文件的权限。
其中，第1、4、7位表示读权限，如果用"r"字符表示，则有读权限，如果用"-"字符表示，则没有读权限；
第2、5、8位表示写权限，如果用"w"字符表示，则有写权限，如果用"-"字符表示没有写权限；第3、6、9位表示可执行权限，如果用"x"字符表示，则有执行权限，如果用"-"字符表示，则没有执行权限。
所以说-rw-r–-r--，表示这是一个普通文件，创建文件的用户的权限为rw-，创建文件的用户所在的组的权限为r–，其他用户的权限为r–。
-
公钥密码算法和对称密码算法相比，在应用上的优势是 D
A、密钥长度更长
B、加密速度更快
C、安全性更高
D、密钥管理更方便
-
TCP/IP协议中，TCP协议提供可靠的连接服务，采用三次握手建立一个连接，如图1所示。
（1）第一次握手：建立连接时，客户端A发送SYN包（SYN=j）到服务器B，并进入SYN_SEND状态，等待服务器B确认。
（2）第二次握手：服务器B收到SYN包，必须确认客户A的SYN（ACK=j+1），同时自己也发送一个SYN包（SYN=k），即SYN+ACK包，此时服务器B进入SYN_RECV状态。
（3）第三次握手：客户端A收到服务器B的SYN＋ACK包，向服务器B发送确认包ACK（ACK=k+1），此包发送完毕，客户端A和服务器B进入ESTABLISHED状态，完成三次握手。
完成三次握手，客户端与服务器开始传送数据。
确认号：其数值等于发送方的发送序号 +1(即接收方期望接收的下一个序列号)。
-
HDFS中负责数据存储的是
NameNode
DataNode -----√
SecondaryNameNode
JobTracker
二、问答
-
SQL的一些操作
select SC1.S# from SC SC1 JOIN SC SC2 ON SC1.S#=SC2.S# WHERE SC1.C#='001' AND SC2.C#='002' AND SC1.score>SC2.score -
分布式系统应该有哪些功能组件，各具备什么功能。
三、编程
- 回文序列
- 输入1，统计非空行的个数 输入Q，输出quit，输入其他，输出‘error input’，再返回一个菜单：1：count line Q：quit
