百度笔试题

1、数组，链表的优缺点：这个问题比较简单不过我自己经常会忽略的一点是数组是固定空间，链表是可变空间

数组和链表都是线性表，但数组是一组元素有序地存储在连续的内存单元中，而链表的节点元素存储的内存单元并不是连续的。

由于存储性质，导致数组的查找可根据下标直接定位，而链表的查找需要遍历，因此查找的效率数组比链表要高，而插入和删除一个元素，数组需要平均移动二分之一的元素，而链表可以直接通过断链和指针实现插入和删除。

对于树的操作一般用到链表，对于图的操作一般用到数组。

数组应用场景：
1、注重存储密度；
2、经常做的运算是按序号访问数据元素；
3、数组更容易实现，任何高级语言都支持；
4、构建的线性表较稳定。
链表应用场景：
1、对线性表的长度或者规模难以估计；
2、频繁做插入删除操作；
3、构建动态性比较强的线性表。

2、a[N][20]输入N个长度不超过20的字符串，比较这些字符串中是否有完全相同的字母，且相同字母数是否相等。如何改进该算法，降低复杂度。

3、黑：A Q 4
红：J 8 4 2 7 3
梅：K Q 5 4 6
方：A 5
有以上16张扑克牌老板从中选择了一张，之后把这张牌的点数告诉了员工甲，把花色告诉了员工乙。之后按以上方式将16张牌平摊在桌面上。
————甲说：我不知道这张牌是什么。
————乙说：我知道你不知道。
————甲说：我现在知道了。
————乙说：我也知道了。
这张牌是什么？

应该是方5.

3.1、从甲的第一句话可以分析，这张牌不是J、8、2、7、3、K、6。

3.2、从乙的第一句话可以分析，这张牌不是红或者梅。

3.3、从甲的第二句话可以分析，这张牌不是A。其实甲在说谎，他还不确定是黑Q、4还是方5。

3.4、从乙的第二句话可以分析，这张牌就是方5，因为黑中有两个Q和4，而方只有一个5。

4、A:M*M矩阵，求字符串S是否存在A的连续对角线上。（这题应该有涉及到一个之字二维矩阵方面的知识）   A若为内存装不下的大矩阵该如何处理？