C#面试题汇总(netSQL几百道)

《C#面试题汇总(netSQL几百道)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、、二叉树遍历算法设计，涉及指针问题，暂不看二、设计包含min函数的栈:题目：定义栈的数据结构，要求添加一个min函数，能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是0（1）。分析：这是去年google的一道面试题。我看到这道题H时，第-•反应就是每次push—个新元素时,将栈里所有逆序元素排序。这样栈顶元素将是故小元素。但由于不能保证故后push进栈的元索最先出栈，这种思路设计的数据结构已经不是一个栈了。（排序不行）在栈里添加一个成员变量存放最小元素（或最小元素的位置）。每次push-*个新元素进栈的时候，如果该元索比当前的最小元索还要小，

2、则更新最小元索。乍一看这样思路挺好的。但仔细一想，该思路存在一个巫要的问题：如果当前最小元素被pop出去，如何才能得到下一个最小元素？（添加变量來记录也不行）因此仅仅只添加一个成员变量存放故小元索（或最小元索的位置）是不够的。我们需要一个辅助栈。每次push-个新元素的时候，同时将最小元素（或最小元素的位置。考虑到栈元素的类型可能是复杂的数据结构，用最小元素的位置将能减少空间消耗）push到辅助栈中；每次pop-个元素出栈的时候，同时pop辅助栈。（辅助栈，记录最小元素的存储位置）举个例子演示上述代码的运行过程:步骏数振栈辅朋栈最小值1・push33032.push

3、43.40,033.push23.4.200224.push13.4.2.10.0,2,315・pop3.4.20.0.226.pop3.40.037・push03.4.00.0.20三.求子数组的最大和题输入一个整形数组，数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组，每个子数组都冇一个和。求所冇子数组的和的最大值。要求时间复杂度为0（n）。例如输入的数组为1,・2,3,10,-4,7,2,・5,和最大的子数组为3,10,-4,7,2,因此输出为该子数组的和18。分析：木题最初为2005年浙江大学计算机系的考研题的最后一道程序设计题，在2006年里

4、包括google在内的很多知名公司都把木题当作面试题。由于木题在网络中广为流传，木题也顺利成为2006年程序员面试题中经典屮的经典。如果不考虑吋间复杂度，我们可以枚举出所有子数组并求出他们的和。不过非常遗憾的是，由于长度为n的数组有0(()个了数组；而且求一个长度为n的数组的和的时间复杂度为O(n)。因此这种思路的时间是O(n3)o很容易理解，当我们加上一个正数时，和会增加；当我们加上一个负数时，和会减少。如果当前得到的和是个负数，那么这个和在接下来的累加小应该抛弄并重新淸零，不然的话这个负数将会减少接下来的和“基于这样的思路，我们可以写出如下代码。boolFind

5、GreatestSumOfSubArray(int*pData,//anarrayunsignedintnLength,//thelengthofarrayint&nGreatestSum//thegreatestsumofallsub-arrays){//iftheinputisinvalid,returnfalseif((pData==NULL)

6、

7、(nLength==0)):returnfalse;intnCurSum=nGreatestSum=0;"逐个向后面加，如果出现了负数的和值，就抛弃，重新开始加这样也有个问题，如果后面的是负数，加上了，但和依然是止数

8、，则不能说就是最大值，建议再定义一个数组，用來存放每次加后如果是正数的和值，用來最后判断一下取岀最大值。然后再和数组中的每一个元素进行对比，如果的确是最大则取之*/for(unsignedinti=0;inGreatestSum)nGreatestSum=nCurSum;}//i

9、falldataarenegative,findthegreatestelementinthearray//输入冇一类特殊情况需耍特殊处理。当输入数组中所冇整数都是负数时，子数组和的最大值就是数组中的最大元素。if(nGreatestSum==0)nGreatestSum=pDate[0];for(unsignedinti=1;inGreatestSum)nGreatestSum=pData[i];}}returntrue;}小的k个元素分析：这道题最简单的思路莫过于把输入的n个整数排序，这样排在最前面的k个数