微软算法题和参考答案

　　六.算法题（说明：这些题就不是什么花样了，考的是你的基础知识怎么样。再聪明而没有实学的人都将会被这些题所淘汰。）
　　1.链表和数组的区别在哪里？
　　2.编写实现链表排序的一种算法。说明为什么你会选择用这样的方法？
　　3.编写实现数组排序的一种算法。说明为什么你会选择用这样的方法？
　　4.请编写能直接实现strstr()函数功能的代码。
　　5.编写反转字符串的程序，要求优化速度、优化空间。
　　6.在链表里如何发现循环链接？
　　7.给出洗牌的一个算法，并将洗好的牌存储在一个整形数组里。
　　8.写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）
　　9.给出一个函数来输出一个字符串的所有排列。
　　10.请编写实现malloc()内存分配函数功能一样的代码。
　　11.给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。
　　12.怎样编写一个程序，把一个有序整数数组放到二叉树中？
　　13.怎样从顶部开始逐层打印二叉树结点数据？请编程。
　　14.怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？

参考答案：仅供参考！（待增加）
　　1 顺序表（即数组）的主要优点体现在没有使用指针，节省存储空间，而且线性表元素的读访问非常简洁便利。
　　链表的主要优点则体现在无需事先确定线性表的长度，可以根据需要动态申请，且允许线性表的长度有很大变化，能够适应在线性表中经常插入、删除内部元素的情况。
　　需要根据具体的应用来选择采用何种存储方式的线性表。当线性表经常要进行插入、删除元素的操作时，不宜使用顺序表，另外，当无法事先确定线性表的长度时也不应选择顺序存储方式。而当需要经常对线性表进行按位置访问，且读操作比插入删除操作频率大时，则不应该选择链表。

　　2 对链表而言：直接插入排序，简单；归并排序，效率高，STL就使用的归并排序。
直接插入排序：
归并排序:（说明和源码）Mergesort For Linked Lists

　　3 对数组而言：快速排序，效率最高。
　　（附：快速排序和归并排序的比较：From PKU
　　快速排序首先从待排序序列Array中任意选择一个记录k作为轴值，然后将剩余的记录分割成两个子序列L和R。L中包含所有小于或等于轴值k的记录，都放在记录k的左边；R中包含所有大于轴值k的记录，都放在记录k的右边。原问题分解为子序列L和R这两个规模更小的同结构子问题，对L和R子序列递归进行快速排序，直到子序列中只含有0或1个元素时退出递归。
　　实际上快速排序名副其实，它几乎是最快的排序算法，被评选为20世纪十大算法之一。快速排序之所以快，主要因为它在分组时不是随便划分而是尽量将原数组划分为两半。
　　归并排序将序列划分为两个子序列，分别对两个子序列递归进行归并排序，将这两个已排好序的子序列合并为一个有序序列。快速排序侧重于分割过程，归并排序侧重于归并过程。归并排序比快速排序多了一个归并过程，但快速排序的不足之处在于轴值的选择对算法效率的影响太大。归并排序避免了这种最差情况，不依赖于原始数组中记录的有序程度。另外，归并排序是稳定的）
快速排序：Wikipedia（可能要代理）

（未完待续）