第一部分：没答案
1.以下是题目详情： 子序列的定义：对于一个序列a=a[1],a[2],......a[n]，则非空序列a'=a[p1],a[p2]......a[pm]为a的一个子序列，其中1<=p1<p2<.....<pm<=n。 例如：4,14,2,3和14,1,2,3都为4,13,14,1,2,3的子序列。 对于给出序列a，有些子序列可能是相同的，这里只算做1个，要求输出a的不同子序列的数量。 输入： 长度为n的数组1<=n<=100,数组元素0<=a[i]<=110 输出：子序列 的个数对1000000007取余数的结果（由于答案比较大，输出Mod 1000000007的结果即可）。 函数头部： C/C++: int run(cons int *a,int n);
2.以下是题目详情： 给定一个包含1-n的数列，我们通过交换任意两个元素给数列重新排序。求最少需要多少次交换，能把数组排成按1-n递增的顺序，其中，数组长度不超过100。 例如： 原数组是3,2,1， 我们只需要交换1和3就行了，交换次数为1，所以输出1。 原数组是2,3,1，我们需要交换2和1，变成1,3,2，再交换3和2，变为1，2，3，总共需要的交换次数为2，所以输出2。 函数头部： C/C++ int run(const int *a,int n);
3.给定一个字符串，仅由a,b,c 3种小写字母组成。当出现连续两个不同的字母时，你可以用另外一个字母替换它，如 有ab或ba连续出现，你把它们替换为字母c； 有ac或ca连续出现时，你可以把它们替换为字母b； 有bc或cb 连续出现时，你可以把它们替换为字母a。 你可以不断反复按照这个规则进行替换，你的目标是使得最终结果所得到的字符串尽可能短，求最终结果的最短长度。 输入：字符串。长度不超过200，仅由abc三种小写字母组成。 输出： 按照上述规则不断消除替换，所得到的字符串最短的长度。 例如：输入cab，输出2。因为我们可以把它变为bb或者变为cc。 输入bcab，输出1。尽管我们可以把它变为aab -> ac -> b，也可以把它变为bbb，但因为前者长度更短，所以输出1。 函数头部： C/C++ int minLength(const char *s);
4.用n个不同的字符（编号1 - n），组成一个字符串，有如下2点要求： 1、对于编号为i 的字符，如果2 * i > n，则该字符可以作为最后一个字符，但如果该字符不是作为最后一个字符的话，则该字符后面可以接任意字符； 2、对于编号为i的字符，如果2 * i <= n，则该字符不可以作为最后一个字符，且该字符后面所紧接着的下一个字符的编号一定要 >= 2 * i。 问有多少长度为M且符合条件的字符串。 例如：N = 2，M = 3。则abb, bab, bbb是符合条件的字符串，剩下的均为不符合条件的字符串。 输入：n,m (2<=n,m<=1000000000)； 输出：满足条件的字符串的个数，由于数据很大，输出该数Mod 10^9 + 7的结果。 函数头部 int validstring(int n,int m) { }
5.有两个容器，容积分别为A升和B升，有无限多的水，现在需要C升水。 我们还有一个足够大的水缸，足够容纳C升水。起初它是空的，我们只能往水缸里倒入水，而不能倒出。 可以进行的操作是： 把一个容器灌满； 把一个容器清空（容器里剩余的水全部倒掉，或者倒入水缸）； 用一个容器的水倒入另外一个容器，直到倒出水的容器空或者倒入水的容器满。 问是否能够通过有限次操作，使得水缸最后恰好有C升水。 输入：三个整数A, B, C，其中 0 < A , B, C <= 1000000000 输出：0或1，表示能否达到要求。 函数头部： c语言：1表示可以，0表示不可以 int can(int a,int b,int c); c++语言: true表示可以，false表示不可以 bool can(int a,int b,int c);
6.一个数组存储很多英文字母，问：怎么知道26个字母中哪些没有存储？
第二部分：带答案
一：简答题（30）
1：数据库以及线程发生死锁的原理及必要条件，如何避免死锁
答：
产生死锁的原因主要是：
（1） 因为系统资源不足。
（2） 进程运行推进的顺序不合适。
（3） 资源分配不当等。
产生死锁的四个必要条件：
（1）互斥条件：一个资源每次只能被一个进程使用。
（2）请求与保持条件：一个进程因请求资源而阻塞时，对已获得的资源保持不放。
（3）不剥夺条件:进程已获得的资源，在末使用完之前，不能强行剥夺。
（4）循环等待条件:若干进程之间形成一种头尾相接的循环等待资源关系。
避免死锁：
死锁的预防是通过破坏产生条件来阻止死锁的产生，但这种方法破坏了系统的并行性和并发性。
死锁产生的前三个条件是死锁产生的必要条件，也就是说要产生死锁必须具备的条件，而不是存在这3个条件就一定产生死锁，那么只要在逻辑上回避了第四个条件就可以避免死锁。
避免死锁采用的是允许前三个条件存在，但通过合理的资源分配算法来确保永远不会形成环形等待的封闭进程链，从而避免死锁。该方法支持多个进程的并行执行，为了避免死锁，系统动态的确定是否分配一个资源给请求的进程。
预防死锁：具体的做法是破坏产生死锁的四个必要条件之一
2：面向对象的三个基本元素，五个基本原则
答：
三个基本元素：
封装
继承
多态
五个基本原则：
单一职责原则（Single-Resposibility Principle）:一个类，最好只做一件事，只有一个引起它的变化。单一职责原则可以看做是低耦合、高内聚在面向对象原则上的引申，将职责定义为引起变化的原因，以提高内聚性来减少引起变化的原因。
开放封闭原则（Open-Closed principle）:软件实体应该是可扩展的，而不可修改的。也就是，对扩展开放，对修改封闭的。
Liskov替换原则（Liskov-Substituion Principle）:子类必须能够替换其基类。这一思想体现为对继承机制的约束规范，只有子类能够替换基类时，才能保证系统在运行期内识别子类，这是保证继承复用的基础。
依赖倒置原则（Dependecy-Inversion Principle）:依赖于抽象。具体而言就是高层模块不依赖于底层模块，二者都同依赖于抽象；抽象不依赖于具体，具体依赖于抽象。
接口隔离原则（Interface-Segregation Principle）:使用多个小的专门的接口，而不要使用一个大的总接口。
3：windows内存管理的机制以及优缺点
答：
分页存储管理基本思想：
用户程序的地址空间被划分成若干固定大小的区域，称为“页”，相应地，内存空间分成若干个物理块，页和块的大小相等。可将用户程序的任一页放在内存的任一块中，实现了离散分配。
分段存储管理基本思想：
将用户程序地址空间分成若干个大小不等的段，每段可以定义一组相对完整的逻辑信息。存储分配时，以段为单位，段与段在内存中可以不相邻接，也实现了离散分配。
段页式存储管理基本思想：
分页系统能有效地提高内存的利用率，而分段系统能反映程序的逻辑结构，便于段的共享与保护，将分页与分段两种存储方式结合起来，就形成了段页式存储管理方式。
在段页式存储管理系统中，作业的地址空间首先被分成若干个逻辑分段，每段都有自己的段号，然后再将每段分成若干个大小相等的页。对于主存空间也分成大小相等的页，主存的分配以页为单位。
段页式系统中，作业的地址结构包含三部分的内容：段号 页号 页内位移量
程序员按照分段系统的地址结构将地址分为段号与段内位移量，地址变换机构将段内位移量分解为页号和页内位移量。
为实现段页式存储管理，系统应为每个进程设置一个段表，包括每段的段号，该段的页表始址和页表长度。每个段有自己的页表，记录段中的每一页的页号和存放在主存中的物理块号。
二：程序设计题（40）
1：公司里面有1001个员工，现在要在公司里面找到最好的羽毛球选手，也就是第一名，每个人都必须参赛，问至少要比赛多少次才能够找到最好的羽毛球员工。
答：两两比赛，分成500组剩下一人，类似于归并排序的方式，比出冠军后，让冠军之间再比，主要是要想想多余的那一个选手如何处理，必然要在第一次决出冠军后加入比赛组。
#include <iostream.h>
#include <stdlib.h>
int i=0,j=0;
int fun(int n)
{
if(n!=1)
{
if(n%2==0)
{
n=n/2;
j+=n;
fun(n);
}
else
{
n=n/2;
j+=n;
fun(n+1);
}
}
else
return j;
}
int fun1(int n)
{
if(n!=1)
{
if(n%2==0)
{
i++;
n=n/2;
fun1(n);
}
else
{i++;
n=(n+1)/2;
fun1(n);
}
}
else
return i;
}
void main()
{
printf("%d\n%d\n",fun(1001),fun1(1001));
}
2：现在有100个灯泡，每个灯泡都是关着的，第一趟把所有的灯泡灯泡打开，第二趟把偶数位的灯泡制反（也就是开了的关掉，关了的打开），第三趟让第3,6,9....的灯泡制反.......第100趟让第100个灯泡制反，问经过一百趟以后有多少灯泡亮着
#include<stdio.h>
bool lights[100] = {0};
int main()
{
int n,step,i,numLighted = 0;
scanf("%i",&n);
for(step=1;step<=n;step++)
for(i=0;i<100;i+=step)
lights[i] ^= 1;
for(i=0;i<100;i++)
if(lights[i])
numLighted++;
printf("%i",numLighted);
return 0;
它们的编号分别是： 1、4、9、16、25、36、49、64、81、100。
3：有20个数组，每个数组有500个元素，并且是有序排列好的，现在在这20*500个数中找出排名前500的数
答：TOP-K问题，用个数为K的最小堆来解决
4. 字符串左移，void *pszStringRotate(char *pszString, intnCharsRotate),比如ABCDEFG，移3位变DEFGABC，要求空间复杂度O（1），时间复杂度O（n）
三：系统设计题（30）
现在有一个手机，手机上的键盘上有这样的对应关系，2对应"abc",3对应"def".....手机里面有一个userlist用户列表，当我们输入942的时候出来拼音的对应可能是“xia”，“zha”，“xi”，“yi”等，当我们输入9264的时候出来是yang，可能是“样”，“杨”，“往”等，现在我们输入一个字符串数字，比如926等，要在电话簿userlist中查找出对应的用户名和电话号码并返回结果。
C++语言: 电话号码对应的英语单词(注意此题的非递归做法)
1.#include <iostream>
2.#include <cstdlib>
3.#define N 4 //电话号码个数
4.
5.using namespace std;
6.
7.char c[][10] = {"","","ABC","DEF","GHI","JKL","MNO","PQRS","TUV","WXYZ"};//存储各个数字所能代表的字符
8.int number[N] = {2, 4 ,7, 9}; //存储电话号码
9.int total[10] = {0, 0, 3, 3, 3, 3, 3, 4, 3, 4}; //各个数组所能代表的字符总数
10.int answer[N]; //数字目前所代表的字符在其所能代表的字符集中的位置,初始为0
11.
12.void Search(int *number, int n); //非递归的办法
13.void RecursiveSearch(int *number, int cur, char *ps, int n); //递归的办法
1.int main()
2.{
3. //Search(number, N);
• char ps[N+1] = {0};
• RecursiveSearch(number, 0, ps, N);
• return 0;
•}
•
•
•void Search(int *number, int n)
•{
• int i;
• while(1)
• {
• for(i=0; i<n; ++i)
• printf("%c", c[number[i]][answer[i]]);
• printf("\n");
• int k = n-1; //用k和while循环来解决扩展性问题,模拟了递归
• while(k >= 0)
• {
• if(answer[k] < total[number[k]]-1)
• {
• ++answer[k];
• break;
• }
• else
• {
• answer[k] = 0;
• --k;
• }
• }
• if(k < 0)
• break;
• }
•}
•
•
•/*递归的解法: number为存储电话号码的数组,pos为当前处理的数字在number中的下标,初始为0
•*ps为一外部数组,用于存放字母,n代表电话号码的长度(个数)
•* 此递归的方法好理解,比上面非递归的办法好写易懂
•* */
•void RecursiveSearch(int *number, int pos, char *ps, int n)
•{
• int i;
• for(i=0; i<total[number[pos]]; ++i)
• {
• ps[pos] = c[number[pos]][i];
• if(pos == n-1)
• cout<<ps<<endl;
• else
• RecursiveSearch(number, pos+1, ps, n);
• }
•}