Microsoft经典数据结构题,进Microsoft的日子不远了!!!
以下是Microsoft经典数据结构题,大家把答案写一写吧,看看能不能答上来,测试一下自己的水平.
1.链表和数组的区别在哪？
2.请问一种链表排序的算法。为什么你会选择些种算法？
3.编程实现strstr函数一样的功能，或者其它的字符串库函数。
4.编程反转字符串，优化速度，优化空间。
5.编程计算一个整数的位数优化速度，优化大小。
6.如何在链表里发现循环链接？
7.给出一个洗牌的算法，并将一个洗好的牌放在一个整数数组里。
8.写一个函数检查字符串是否为整数，如果是返回其整数值。
9.给出一个函数来输出一具字符串的所有排列。
10.实现malloc()内存分配函数
11.给出一个函数输出Fi-bonacci 数列
12.给出一个函数来复制两个字符串A和B字符串，A的后几个字节和B的前几个字节相同。
13.怎么从顶部开始逐层打印二叉树节点数据。
问题点数：0、回复次数：12Top
1 楼happycock（SSWW）回复于 2003-08-04 14:43:12 得分 0
13题这几天刚刚做过，不试几次我是做不出来，不过最后还是完成了。可能题目的要求和我的做法不一致——我的是按照树的形状输出，而不是仅仅输出数据。Top
2 楼loewe（可怜没人爱）回复于 2003-08-04 16:34:42 得分 0
我来UP，看看都会不回做，呵呵Top
3 楼zhenming_liu（）回复于 2003-08-05 04:53:56 得分 0
我试试
1.链表和数组的区别在哪？
前者容易扩展, 后者较难
前者O(1)插入, 后者O(N),
前者O(N)存取, 后者O(1)
2.请问一种链表排序的算法。为什么你会选择些种算法？
MERGESORT,
现成的资料库有针对LIST的MERGE函数,暗示MERGESORT有优越性
不选QSORT的理由:
1) MEAN-OF-THREE不好写
2) DATA-SWAPTING涉及到大量的指针运算, 不一定会比MERGESORT快
3.编程实现strstr函数一样的功能，或者其它的字符串库函数。
...
4.编程反转字符串，优化速度，优化空间。
速度最快是O(N), 空间最小是一个CHAR
5.编程计算一个整数的位数优化速度，优化大小。
除一百, 不考虑RECURSIVE, 增加浮点运算量
6.如何在链表里发现循环链接？
两个PT一快一慢,
7.给出一个洗牌的算法，并将一个洗好的牌放在一个整数数组里。
不会
8.写一个函数检查字符串是否为整数，如果是返回其整数值。
int toInt(char* p){
if (!p) return NON_VALUE;
int i = 0;
int r = 0;
int s = 1;
if (p[0] == '-'){
i++; s =-1;
}
for (i = 0; p[i] != '\0'; i++) r = r * 10 + p[i] - '0';
return r;
}
9.给出一个函数来输出一具字符串的所有排列。
大概:
void print(char* s)
{
sort(s);
while (printNext(s) != 0) { }
}
void printNext(s)
{
int len;
if ((len = str(s)) == 1) return 0;
int p = len;
while (p > 1 && s[p] > s[p - 1]) p--;
if (p == 0) return 0;
int q = p - 1;
int val = s[q];
while (p < len && val < s[p]) p++;
swap(s[q], s[--p]);
for (int i = p + 1; i < (p + 1 + len) / 2; i++) swap(s[i], s[len - i + p]);
printf("%s\n", s);
return 1;
}
10.实现malloc()内存分配函数
LinkList
11.给出一个函数输出Fi-bonacci 数列
不用RECURSIVE
12.给出一个函数来复制两个字符串A和B字符串，A的后几个字节和B的前几个字节相同。
不懂说什么
13.怎么从顶部开始逐层打印二叉树节点数据。
广度优先
Top
4 楼zhenming_liu（）回复于 2003-08-05 04:56:13 得分 0
//sorry:P, 八错了...
int toInt(char* p){
if (!p) return NON_VALUE;
int i = 0;
int r = 0;
int s = 1;
if (p[0] == '-'){
i++; s =-1;
}
for (i = 0; p[i] != '\0'; i++) r = r * 10 + p[i] - '0';
return r * s;
}Top
5 楼aliceZOOZ（alice）回复于 2003-08-05 11:22:19 得分 0
>>6.如何在链表里发现循环链接？
>> 两个PT一快一慢,
果真是高手，我曾一度为之苦恼
>>2.请问一种链表排序的算法。为什么你会选择些种算法？
>>MERGESORT,
MergeSort是O(nlogn), QSort用于单链表>>O(n^2)，双向链表无法随机划，又慢又复杂；
另外toInt()忘了检测了，只是在字符串是整数的时候，可以返回整型，
另外无法处理+12的情况。Top
6 楼zgzjw（object）回复于 2003-08-05 15:10:04 得分 0
数组和链表???????????????????????
出这个题的人有点绝哈
数组可以由链表来实现
也可以不由链表来实现
链表是数据结构上的概念,数组是一个逻辑概念Top
7 楼wolfzhu（晚晨）回复于 2003-08-05 15:50:18 得分 0
全排列的问题用递归
循环链接在结点中设标志，第二次被指中说明有循环Top
8 楼FlatHuge（FlatHuge）回复于 2003-08-05 20:10:16 得分 0
洗牌应该可以模仿真实的情况：
弄一个数组，把1~54放进去，然后随机交换
行不？Top
9 楼sjjf（水晶剑锋）回复于 2003-08-06 13:48:21 得分 0
请问？怎么用linklist来分配内存？linklist本身也要调用malloc来分配内存的阿？
Top
10 楼tudou614（魔蟹座的SATAN）回复于 2003-08-14 14:55:17 得分 0
MARK！！
UP！！Top
11 楼ejiue（阿喀硫斯的脚跟）回复于 2003-08-14 17:35:18 得分 0
mark。
这个问题好象在csdn还有一个帖子。
有人解答得不错。大家可以搜搜。
Hoho。Top
12 楼ZhangYv（迎着朝阳,走向地狱）回复于 2003-08-16 12:54:42 得分 0
http://expert.csdn.net/Expert/topic/2108/2108256.xml?temp=.7635157Top
