可用分押宝游戏火热进行中...	专题改版：Java Web 专题

微软面试题算法部分:

楼主superhasty（鸟儿自空中飞过）2005-03-22 01:06:01 在专题开发/技术/项目 / 数据结构与算法提问

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

问题点数：100、回复次数：17Top

1 楼chunhai12（小海）回复于 2005-03-22 10:42:14 得分 5

晕，我看是数据结构的考试题吧

楼主太不厚道了

Top

2 楼hatita（悠远的风景）回复于 2005-03-22 11:03:36 得分 10

5:
int[] iArray = new[10];
int index = 0;
int iLength = iArray.Length - 1;

while(index < iLength)
{
int iTemp = iArray[index];
iArray[index] = iArray[iLength];
iArray[iLength] = iTemp;

index++;
iLength--;
}Top

3 楼conquer2004（狗样年华）回复于 2005-03-22 14:16:42 得分 5

mark
有空研究Top

4 楼junmayang（笨猪）回复于 2005-03-22 17:38:43 得分 5

这是微软件的题目，怀疑。。。Top

5 楼happy__888（[顾问团]寻开心 www.e-jjj.com）回复于 2005-03-22 18:07:31 得分 5

是不是微软的不管
不过这些问题当作数据结构的考题确实不错，收藏收藏。Top

6 楼mydo（侯佩|hopy|ks）回复于 2005-03-22 18:48:26 得分 5

ｓｅｅ　ｓｅｅTop

7 楼mmmcd（超超）回复于 2005-03-22 19:55:17 得分 5

考几个小时的题目？Top

8 楼galois_godel（）回复于 2005-03-22 20:54:18 得分 5

这是第几轮阿Top

9 楼greenteanet（扎扎实实打基础，保持一颗平常心。）回复于 2005-03-31 22:05:17 得分 5

值得看看..Top

10 楼angeldai（海豚）回复于 2005-04-11 11:19:01 得分 5

关注Top

11 楼lvjinhua（硬件&软件）回复于 2005-04-12 12:15:29 得分 5

很难！Top

12 楼bigc2000（公元2005年4月9日）回复于 2005-04-12 12:55:36 得分 10

楼住不厚道啊，数据结构的考试题也拿过来。
不过，有几道题有意思，
9题没有明白是什么意思是不是说这样的
123 132 231,321等等下面这个可以否
#include<stdio.h>
#define M 4
#define TRUE 1
#define FALSE 0
static int visited[M] ={0};
static char count[M]={0};
int total =0;
void DFS(const char *a,int);
void main(int argc,char *argv)
{
int i;
char a[]="bsJP";

for(i =0;i<M;i++)
{
DFS(a,i);
visited[i]=FALSE;
total =0;
}

}
void Visit(const char *str,int n)
{
for(int i=0;i<M;i++)
printf("%c\t",str[i]);
printf("\n");
}

void DFS(const char *str,int k)
{
int u =0;
visited[k]=TRUE;
count[total++]=str[k];

if(total == M)
{
Visit(count,M);
return;
}
for(;u<M;u++)
{
if(visited[u] == FALSE)
{
DFS(str,u);
visited[u]=FALSE;
total--;
}
}
}

第8题也挺有意思。虽然说有许多现成的图atol，strtod等
可以逐个判断但是速度就不好了，可以先把串转换为int*型一下就可以比较4个char了
然后用整数比较。但是这样如果长度不为4的整数倍，就麻烦了

Top

13 楼zdnet（Qoo.NET）回复于 2005-04-13 16:02:52 得分 5

第9题的方法很多~最笨的方法是递归
Private Function Print(ByVal input As String) As ArrayList
Dim str As String = ""
Dim rarray() As Char = input.ToCharArray()
Dim rarraylist As New ArrayList
Dim i As String
Dim j As String
If rarray.Length = 1 Then
rarraylist.Add(input)
Return rarraylist
ElseIf rarray.Length = 2 Then
rarraylist.Add(rarray(0) + rarray(1))
rarraylist.Add(rarray(1) + rarray(0))
Return rarraylist
Else
For Each i In rarray
str = input.Replace(i, "")
For Each j In Print(str)
rarraylist.Add(j + i)
Next
Next
rarraylist.Sort()
Return rarraylist
End If
End FunctionTop

14 楼zdnet（Qoo.NET）回复于 2005-04-13 16:04:25 得分 5

快一点的方法是拼字符串
12 312
1 --《21 -- 132 再如此添加下一个
123

Private Function PrintStack(ByVal input As String) As ArrayList
Dim myStack As New Stack(input.ToCharArray())
Dim rarraylist As New ArrayList
Dim returnArray As New ArrayList
Dim i As Integer
Dim j As Integer
Dim k As Integer
Dim a As String
While myStack.Count > 0
Dim rstr As String = ""
Dim str As String = myStack.Pop()
If rarraylist.Count = 0 Then
rarraylist.Add(str)
Else
For i = 0 To rarraylist.Count - 1
For j = 0 To rarraylist(i).ToString().Length
rstr = rarraylist(i).ToString().Insert(j, str)
rarraylist.Add(rstr)
'If (rstr = input.Length - myStack.Count - 1) Then
' rarraylist.Add(rstr)
'End If
Next
Next
End If
End While
For k = 0 To rarraylist.Count - 1
If (rarraylist(k).ToString().Length = input.Length) Then
returnArray.Add(rarraylist(k))
End If
Next
returnArray.Sort()
Return returnArray
End FunctionTop

15 楼dragonfly001（I want to fly!）回复于 2005-04-13 16:13:34 得分 5

數據結構的考題,很不錯的阿 ;0Top

16 楼skys712（）回复于 2005-04-14 13:02:19 得分 5

第8题只用两行:

int StoL(char in[],int &L){
sscanf(in,"%d",&L):}Top

17 楼wangdongyu3d（）回复于 2005-04-14 21:17:31 得分 10

我对8题的想法：
long Myatol(char * ptr)
{
long x;
static int n = 0;
if ( *ptr == '\0')
x=0;
else
{ x = Myatol(ptr++); x =x+ mod(*ptr/48)*pow(10,n); n++;}
return x;
}
没有测试，如果错误，见谅。
Top