2011微软笔试题

微软笔试归来一选择题1stack的基本操作有哪些？Pushin,pushout,checkifempty(sort不是)2最坏情况下，合并两个大小为n的已排序数组所需要的比较次数答案：2n-1.3、求函数ninnxaxf0)()(的空间和时间复杂度答案：时间复杂度为O（n），空间复杂度O（1）PS：不知道我做的对不对4解释语言的特性：非独立效率低性5二叉树的前序遍历，中序遍历和后续遍历问题：类似与下面6最坏情况下insertsort,stacksort,quicksort,mergesort的复杂度分别是多少？冒泡排序：o(n*n)选择排序：o(n*n)插入排序：o(n*n)快速排序：O(nlogn)堆排序：O(nlogn)归并排序：O(nlogn)二主观题1、remove掉给定字符串中的多余空格，要求达到以下要求A无连续相邻的两个空格B字符串开头和结尾无空格C新的一行开头和结尾无空格要得到满分，必须满足以下两个条件A不能增加新的内存空间B只能循环字符串一次C可以用到ItIsspace检测空格和ItIsNewline检测新行，不准用其他库函数（貌似是这两个，具体怎么写我记不清了）2、写上面1的测试文件