算法、数据结构

算法、数据结构

1.数组和链表什么区别?

•数组是将元素在内存中连续存放，由于每个元素占用内存相同，可以通过下标迅速访问数组中任何元素。但是如果要在数组中增加一个元素，需要移动大量元素，在内存中空出一个元素的空间，然后将要增加的元素放在其中。同样的道理，如果想删除一个元素，同样需要移动大量元素去填掉被移动的元素。如果应用需要快速访问数据，很少或不插入和删除元素，就应该用数组。

•链表恰好相反，链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起。比如：上一个元素有个指针指到下一个元素，以此类推，直到最后一个元素。如果要访问链表中一个元素，需要从第一个元素开始，一直找到需要的元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以了。如果应用需要经常插入和删除元素你就需要用链表数据结构了。

*C++语言中可以用数组处理一组数据类型相同的数据，但不允许动态定义数组的大小，即在使用数组之前必须确定数组的大小。而在实际应用中，用户使用数组之前有时无法准确确定数组的大小，只能将数组定义成足够大小，这样数组中有些空间可能不被使用，从而造成内存空间的浪费。链表是一种常见的数据组织形式，它采用动态分配内存的形式实现。需要时可以用new分配内存空间，不需要时用delete将已分配的空间释放，不会造成内存空间的浪费。

(1)从逻辑结构角度来看

a,数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。

b,链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项）

(2)从内存存储角度来看

a,(静态)数组从栈中分配空间,对于程序员方便快速,但自由度小。

b,链表从堆中分配空间,自由度大但申请管理比较麻烦.

2.手写实现冒泡

for (int index = 0;index < int_list_count;index++) {

for (int jindex = 0;jindex < int_list_count - index - 1; jindex++)

{

if (int_list[jindex] > int_list[jindex + 1]) {

int temp;

temp = int_list[jindex];

int_list[jindex] = int_list[jindex + 1];

int_list[jindex + 1] = temp;

}

}

9.如何优化冒泡排序

答：添加一个BOOL来标识当前的数组是否有序，在外层循环条件增加判断，无序（NO）的情况下再排序，每次进入循环假设是有序的（YES），无序的时候（进入if条件）把这个标识设置为无序（NO），如果没有进入if条件就说明当前的数组已经是有序的，则下次循环的时候会根据添加的条件自动停止循环

int flag = 0;

int numbers[5] = {4, 14, 88, 22, 60};

int count = sizeof(numbers) / sizeof(numbers[0]);

for (int i = 0; i < count - 1 && flag == 0; i++) {

flag = 1;

for (int j = 0; j < count - 1 - i; j++) {

if (numbers[j] > numbers[j + 1]) {

int temp = numbers[j];

numbers[j] = numbers[j + 1];

numbers[j + 1] = temp;

flag = 0;

}

}

}

9.写一个冒泡排序的函数

void sort(int array[], int count){

for (int i = 0; i < count - 1; i++) {

for (int j = 0; j < count - 1 - i; j++) {

if (array[j] > array[j + 1]) {

int temp = array[j];

array[j] = array[j + 1];

array[j + 1] = temp;

}

}

}

}

int main(int argc, const char * argv[]) {

int flag = 0;

int numbers[5] = {4, 14, 88, 22, 60};

//如果函数实现在main函数后面需要先声明sort函数

int count = sizeof(numbers) / sizeof(numbers[0]);

sort(numbers, count);

for (int i = 0; i < count; i++) {

printf("%d\n", numbers[i]);

}

return 0;

}

17.用变量a写出以下定义

a、一个整型数int a;

b、一个指向整型数的指针int *a;

c、一个指向指针的指针，它指向的指针是指向一个整型数int **a;

d、一个有10个整型数的数组int a[10];

e、一个有10个指针的数组，该指针是指向一个整型数的int *a[10];

f、一个指向有10个整型数数组的指针int (*a)[10];

g、一个指向函数的指针，该函数有一个整型参数，并返回一个整型数int(*a)(int);

94.二叉搜索树的概念，时间复杂度多少？

二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：

1.若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

2.若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

3.任意节点的左、右子树也分别为二叉查找树。

4.没有键值相等的节点（no duplicate nodes）。

93.MD5和Base64的区别是什么，各自场景是什么？

MD5:全称为message digest algorithm 5(信息摘要算法),可以进行加密,但是不能解密,属于单向加密,通常用于文件校验

Base64:把任意序列的8为字节描述为一种不易为人识别的形式,通常用于邮件、http加密.登陆的用户名和密码字段通过它加密,可以进行加密和解密.

5、RSA加密

RSA使用"秘匙对"对数据进行加密解密.在加密解密数据前,需要先生成公钥(public key)和私钥(private key).

•公钥(public key):用于加密数据.用于公开,一般存放在数据提供方,例如iOS客户端.

•私钥(private key):用于解密数据.必须保密,私钥泄露会造成安全问题.

虽然RSA加密算法作为目前最优秀的公钥方案之一，在发表三十多年的时间里，经历了各种攻击的考验，逐渐为人们接受。但是，也不是说RSA没有任何缺点。由于没有从理论上证明破译RSA的难度与大数分解难度的等价性。所以，RSA的重大缺陷是无法从理论上把握它的保密性能如何。在实践上，RSA也有一些缺点：

1产生密钥很麻烦，受到素数产生技术的限制，因而难以做到一次一密；

2分组长度太大，为保证安全性，n至少也要600 bits以上，使运算代价很高，尤其是速度较慢，。

http://blog.iamzsx.me/show.html?id=155002

4、对称加密算法

7）存入数据加密

http://www.cxyclub.cn/n/70879/

http://jingyan.baidu.com/article/fedf07375d695e35ac89772c.html

1、当前已经编程实现函数：int rand100().该函数可返回0-99的随机整数，且可以保证等概率，请利用该函数实现int rand10000(),要求等概率返回0-9999的随机数（不可使用其他的系统函数）

把rand()视为N进制的一位数产生器，那么可以使用rand()*N+rand()来产生2位的N进制数，以此类推，可以产生3位，4位，5位...的N进制数。这种按构造N进制数的方式生成的随机数，必定能保证随机概率平均。

*  http://blog.csdn.net/a925907195/article/details/39561009

int randN(int n){

return rand()%n;

}

int randomM(int n,int m)

{

//输入参数错误

if(n<1||m<1)

return -1;

//和n相同即可

if(m==n)

return randN(n);

int max=0;

int k=0;

while(max+1

{

k = k*n + randN(n);//转换成0到n-1的n进制数。一位时0到n-1，两位时0到(n-1)*n+n-1。此时保证了生成0到最大数之间的各个数的概率是相等的

max = max*n + n-1;//求n进制数当前位数下的最大数。一位数时n-1,两位数时(n-1)*n+n-1,三位数时(n-1)*n*n+(n-1)*n+n-1

//随机数超出了范围则重新计算。除m再乘m是为了对生成的k进行分组

//如m=7，n=5时此处k的范围是0到24，那么25/7=3，3*7=21。

//因为21、22、23、24都需要重新计算，所以后面返回值k/((max+1)/m)+1就能保证最大值为7了，即20、19、18除3加1都等于7

//此处也可以不进行分组，直接限定k+1<=m后面返回k即可，这样得到k的概率也是一样的，只不过更不容易得到k，因为大量的k将大于m

if(max+1>=m && k < (max+1)/m*m)

{

return k%m;

}else if(max+1>=m && k >= (max+1)/m*m){

k=0;

max=0;

}

}

return -1;

}

2、汤姆现在要在家里举行宴会，他虽然有很多筷子，但这些筷子的长度并不完全相同，现已知每已知每根筷子的长度，要求每位客人都能拿到两根长度相同的筷子，求最多可邀请的客人数。

编程实现：int getMax(int arrLength[N])

N / 2

3、现有一个整数序列，你可以交换其中的任意两个数以得到一个新序列，求共能得到多少种可能的结果（注意3，3，3，3，无论怎么交换，只能得到一个序列）

编程实现：int getTotal(int arrOrigin[N])

4、现有一个M行N列的数组，要求按照反向斜对角线（右上->左下）的方式，打印该数组。

编程实现：int printMatrix[int arrMartrix[M][N]]

下面样例的打印顺序为：

0->1->4->2->5->8->3->6->9->7->10->11

5、北京和上海之间有一趟专列，两个车站每个整点都会往对方发一辆列车，已知由北京出发的车全程需要13.5小时;由上海发往北京的列车，全程需要15.5小时。某人坐在了其中一辆由北京发往上海的列车，请问其途中会碰到多少辆迎面而来的列车。

6、请简单描述一下你所知道的排序算法，实现其中的一种，为一个整数数组排序，并分析其复杂度

冒泡，快速排序，直接插入，希尔排序，选择排序，堆排序，归并排序

http://blog.csdn.net/damacheng/article/details/6472717

/**

*冒泡排序

*

*  @param a数组

*  @param n数组长度

*时间复杂度

*外层循环（n - 1）次，内层循环：第一次（n - 1）,第二次（n - 2）。。。依次下去直到1次；时间复杂度计算为（n-1 + n - 2 +.....+ 1）= ( n - 1 + 1) * (n - 1) / 2 = (n^2 - n) / 2

时间复杂度为：O(n^2)

*/

void bubble_sort(int a[], int n);

void bubble_sort(int a[], int n)

{

int i, j, temp;

for (j = 0; j < n - 1; j++)

for (i = 0; i < n - 1 - j; i++)

{

if(a[i] > a[i + 1])

{

temp = a[i];

a[i] = a[i + 1];

a[i + 1] = temp;

}

}

}

7、有101硬币，其中100个真，1个假，真假的唯一区别在于重量。请问如何让用无砝码天平确认是真币重还是假币重，要求称重的次数越少越好。

使用二分查找

8、写一个函数，输入父字符串和子字符串，返回这个字符串在父字符串中首次出现的位置，（注：只能一个字符一个字符的比较，不能使用任何字符串的函数，和直接查找字符串的函数）

如：父串：ABCDEFEFGH子串：EF结果：4

父串：ABCDEFCDGH子串：CD结果：2

int i,j;

char s1[100],s2[100];

scanf("%s%s",s1,s2);

for(i=0;i<100;i++)

{

if(s1[i]=='\0' ) break;

for(j=0;j<100;j++)

if(s2[j]=='\0' || s2[j]!=s1[j+i]) break;

if(s2[j]=='\0' ) {printf("位置是：%d",i+1); break;}

}

if(s1[i]=='\0' ) printf("没找到");

9、写一个函数，求输入变量的阶乘？

int fun(int n)

{

int i,sum=1;

for (i=1;i<=n;i++) sum*=i;

return sum;

}

int main()

{

int i,n,sum=0;

scanf("%d",&n);

for (i=1;i<=n;i++) sum+=fun(i);

printf("%d\n",sum);

return 0;

}

43.内存中的栈和堆的区别是什么？

管理方式：对于栈来讲，是由编译器自动管理的，无需我们手动控制，对于堆来讲，释放工作有程序猿控制，这样就容易产生memory Leak

申请大小:栈是向低地址扩展的数据结构，是一块连续的内存区域。这句话的意思是栈顶上的地址和栈的最大容量是系统预先规定好的，在Windows下，栈的大小是2M（也有的说1M，总之是编译器确定的一个常数），如果申请的空间超过了栈的剩余空间时候，就overflow。因此，能获得栈的空间较小。

堆：堆是向高地址扩展的数据结构，是不连续的内存区域。这是由于系统是用链表来存储的空闲内存地址的，自然是不连续的，而链表的遍历方向是由低地址向高地址。堆的大笑受限于计算机系统中有效的虚拟内存。由此可见，堆获得的空间比较灵活，也比较大

碎片问题:

对于堆来讲，频繁的new/delete势必会造成内存空间的不连续，从而造成大量的碎片，使程序效率降低。对于栈来讲，则不会存在这个问题，因为栈是先进后出的队列，他们是如此的一一对应，以至于永远都不可能有一个内存快从栈中弹出

分配方式:

堆都是动态分配的，没有静态分配的堆。栈有两种分配方式：静态分配和动态分配。静态分配是编译器完成的，比如局部变量的分配。动态分配是有alloc函数进行分配的，但是栈的动态分配和堆是不同的，他的动态分配由编译器进行释放，无需我们手工实现。

分配效率：

栈是机器系统提供的数据结构，计算机会在底层堆栈提供支持，分配专门的寄存器存放栈的地址，压栈出栈都有专门的指令执行，这就决定了栈的效率比较高。堆则是C/C++函数库提供的，他的机制是很复杂的。

44.那些数据在栈上，哪些在堆上？

由编译器自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放

开发人员创建的一些对象 方法 缓存和持久化数据一般存储在堆上