微软笔试归来
一选择题
1 stack的基本操作有哪些?
Push in ,push out ,check if empty (sort 不是)
2 最坏情况下,合并两个大小为n的已排序数组所需要的比较次数答案:2n-1.
3、求函数
∑
=
=
n
i
n
n
x
a
x
f
)
(
)
(
的空间和时间复杂度
答案:时间复杂度为O(n),空间复杂度O(1)PS:不知道我做的对不对4 解释语言的特性:
非独立
效率低性
5 二叉树的前序遍历,中序遍历和后续遍历问题:类似与下面
6最坏情况下 insert sort, stack sort, quick sort ,merge sort 的复杂度分别是多少?
冒泡排序: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的测试文件