软件水平考试程序员精选题汇总(上)

《软件水平考试程序员精选题汇总(上)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、软件水平考试程序员精选题汇总(上）-在排序数组中查找和为给定值的两个数字　　题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。　　例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。　　分析：如果我们不考虑时间复杂度，最简单想法的莫过去先在数组中固定一个数字，再依次判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n2)。

2、　　我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字，那太好了，我们找到了要找的两个数字;如果小于输入的数字呢?我们希望两个数字的和再大一点。由于数组已经排好序了，我们是不是可以把较小的数字的往后面移动一个数字?因为排在后面的数字要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字了;同样，当两个数字的和大于输入的数字的时候，我们把较大的数字往前移动，因为排在数组前面的数字要小一些，它们的和就有可能等于输入的数字了。　　我们把前面的思路整理一下：最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大

3、于输入的数字时，把较大的数字往前移动;当两个数字的和小于数字时，把较小的数字往后移动;当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。　　问题是这样的思路是不是正确的呢?这需要严格的数学证明。感兴趣的读者可以自行证明一下。　　参考代码：    　　///////////////////////////////////////////////////////////////////////　　//Findtwonumberswithasuminasortedarray　　//Output:tureisfound

4、suchtwonumbers,otherwisefalse　　///////////////////////////////////////////////////////////////////////　　boolFindTwoNumbersWithSum　　(　　intdata[],//asortedarray　　unsignedintlength,//thelengthofthesortedarray　　intsum,//thesum　　int&num1,//thefirstnumber,output　　int&num2

5、//thesecondnumber,output　　)　　{　　boolfound=false;　　if(length<1)　　returnfound;　　intahead=length-1;　　intbehind=0;　　while(ahead>behind)　　{　　longlongcurSum=data[ahead]+data[behind];　　//ifthesumoftwonumbersisequaltotheinput　　//wehavefoundthem　　if(curSum==sum)　　{　　num1=dat

6、a[behind];　　num2=data[ahead];　　found=true;　　break;　　}　　//ifthesumoftwonumbersisgreaterthantheinput　　//decreasethegreaternumber　　elseif(curSum>sum)　　ahead--;　　//ifthesumoftwonumbersislessthantheinput　　//increasethelessnumber　　else　　behind++;　　}　　returnfound;　　}-查找链表中

7、倒数第k个结点　　题目：输入一个单向链表，输出该链表中倒数第k个结点。链表的倒数第0个结点为链表的尾指针。链表结点定义如下：　　structListNode　　{　　intm_nKey;　　ListNode*m_pNext;　　};　　分析：为了得到倒数第k个结点，很自然的想法是先走到链表的尾端，再从尾端回溯k步。可是输入的是单向链表，只有从前往后的指针而没有从后往前的指针。因此我们需要打开我们的思路。　　既然不能从尾结点开始遍历这个链表，我们还是把思路回到头结点上来。假设整个链表有n个结点，那么倒数第k个结点是从头结点开始的

8、第n-k-1个结点(从0开始计数)。如果我们能够得到链表中结点的个数n，那我们只要从头结点开始往后走n-k-1步就可以了。如何得到结点数n?这个不难，只需要从头开始遍历链表，每经过一个结点，计数器加一就行了。　　这种思路的时间复杂度是O(n)，但需要遍历链表两次。第一次得到链