学步园

      额，第一次面试题目很简单，但是，自己由于在纸上写代码很不习惯，所以做得一沓糊涂。现在把题目公布如下，自己写的代码也附上。然后，把关于第一次笔试考到的相关知识整理一下。呵呵，偶很笨，但是，不能笨到在同一个地方摔倒两次。

      1、 给定排好序的数组A（从小到大），大小为n，现在给定数X，插入到给定的数组A中，保持排序（二分法）。
      额，这个题目如此之简单......以至于偶当时没有完全做出来......早知如此，在写插入排序的时候插入一个元素就要使用二分插入的......嗯，不多说了，看我后来写的代码吧。

#include<stdio.h><br /> #include<stdlib.h></p> <p>const int MAX = 100;</p> <p>int cmp(const void *a, const void *b)<br /> {<br /> return *(int *)a - *(int *)b;<br /> }</p> <p>/*对于有n个数的数组a[]，在位置pos插入数X*/<br /> void insert(int a[], int n, int pos, int X)<br /> {<br /> printf("pos = %d/n", pos);<br /> int i;<br /> for(i=n-1; i>=pos; --i)<br /> a[i+1] = a[i];<br /> a[pos] = X;<br /> }</p> <p>/*二分查找插入的位置*/<br /> int Binary(int a[], int n, int X)<br /> {<br /> int begin = 0, end = n, middle;<br /> while(begin <= end)<br /> {<br /> middle = (begin + end)/2;<br /> if(a[middle] > X)<br /> {<br /> end = middle - 1;<br /> }<br /> else if(a[middle] < X)<br /> {<br /> begin = middle + 1;<br /> }<br /> else<br /> {<br /> return middle;<br /> }<br /> }<br /> return middle;<br /> }</p> <p>void print(int a[], int n)<br /> {<br /> int i;<br /> for(i=0; i<n; ++i)<br /> printf("%d ", a[i]);<br /> printf("/n");<br /> }</p> <p>int main()<br /> {<br /> // freopen("in.txt", "r", stdin);<br /> int i, n, a[MAX], insertNum;<br /> while(scanf("%d", &n) != EOF)//数组的个数<br /> {<br /> for(i=0; i<n; ++i)//输入n个数<br /> scanf("%d", &a[i]);</p> <p> qsort(a, n, sizeof(a[0]), cmp);//对输入的n个数调用库函数排序</p> <p> scanf("%d", &insertNum);//输入需要插入的数字</p> <p> int pos = Binary(a, n, insertNum);//二分查找插入的位置<br /> insert(a, n, pos, insertNum);//插入</p> <p> print(a, n+1);<br /> }<br /> return 0;<br /> }

      2、写一个栈的实现，并将1-10入栈和出栈。
      额，这个更无语……就是考栈的知识，话说偶以前写过栈的，但忘记了……甚是郁闷……

#include<iostream><br /> using namespace std;</p> <p>typedef int ElementType;</p> <p>struct stack<br /> {<br /> int top;<br /> ElementType *element;<br /> int MaxSize;<br /> };</p> <p>typedef struct stack Stack;</p> <p>void Init(Stack *S,int sz)//初始化栈<br /> {<br /> if(sz>0)<br /> {<br /> S->top = -1;<br /> S->MaxSize = sz;<br /> S->element = new ElementType[S->MaxSize];<br /> }<br /> }</p> <p>bool IsFull(Stack *S)//判断栈是否为满<br /> {<br /> return (S->top == S->MaxSize-1);<br /> }</p> <p>bool IsEmpty(Stack *S)//判断栈是否为空<br /> {<br /> return (-1 == S->top);<br /> }</p> <p>void Push(Stack *S, ElementType x)//进栈<br /> {<br /> if(!IsFull(S))<br /> S->element[ ++S->top ] = x;<br /> }</p> <p>ElementType Pop(Stack *S)//出栈<br /> {<br /> if(!IsEmpty(S))<br /> return S->element[S->top--];<br /> else<br /> {<br /> return -1;<br /> }<br /> }</p> <p>ElementType GetTop(Stack *S)//得到栈顶元素<br /> {<br /> if(!IsEmpty(S))<br /> return S->element[S->top];<br /> else<br /> {<br /> return -1;<br /> }<br /> }</p> <p>void MakeEmpty(Stack *S)//栈置空<br /> {<br /> S->top = -1;<br /> }</p> <p>void Free(Stack *S)//释放栈<br /> {<br /> delete S;<br /> }</p> <p>int main()<br /> {<br /> int i;<br /> Stack *S = new Stack;<br /> Init(S,100);//初始化栈<br /> for(i=1; i<=10; ++i)<br /> Push(S, i);//按照1~10的顺序进栈；</p> <p> while(!IsEmpty(S))<br /> {<br /> cout<<Pop(S)<<" ";//出栈<br /> }<br /> cout<<endl;</p> <p> Free(S);</p> <p> return 0;<br /> }

      3、编写一个函数，要求输入年月日时分秒，输出此事件的下一秒。
      额……这个题目偶本来想写一个经过n秒之后的代码的，但感觉考虑细节比较多，先实现增加1秒的代码。

#include<stdio.h></p> <p>int monthDays[] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};<br /> int year, month, day, hour, minute, sec;</p> <p>int isLeapYear(int year)<br /> {<br /> if ((0 == year%400 ) || (0 != year%100) && (0 == year%4))<br /> return 1;<br /> else<br /> return 0;<br /> }</p> <p>void addSecond(int increaseSec)<br /> {<br /> sec += increaseSec;<br /> if(isLeapYear(year))<br /> monthDays[2] += 1;<br /> if(sec>59)<br /> {<br /> sec = 0;<br /> minute += 1;<br /> if(minute>59)<br /> {<br /> minute = 0;<br /> hour += 1;<br /> if(hour>23)<br /> {<br /> hour = 0;<br /> day += 1;<br /> if(day>monthDays[month])<br /> {<br /> day = 1;<br /> month += 1;<br /> if(month>12)<br /> {<br /> month = 1;<br /> year += 1;<br /> }<br /> }<br /> }<br /> }<br /> }<br /> monthDays[2] = 28;//一定要把二月份记得重置为28天<br /> }</p> <p>void print()<br /> {<br /> printf("%d年%d月%d日%d时%d分%d秒/n", year, month, day, hour, minute, sec);<br /> }</p> <p>int main()<br /> {<br /> while(6 == scanf("%d %d %d %d %d %d", &year, &month, &day, &hour, &minute, &sec))<br /> {<br /> printf("你当前输入的时间是:");<br /> print();<br /> addSecond(1);<br /> printf("增加1秒后的时间是:");<br /> print();<br /> }<br /> return 0;<br /> }

4、记录如下
2005-05-09 胜
2005-05-09 胜
2005-05-09 负
2005-05-09 负
2005-05-10 胜
2005-05-10 负
2005-05-10 负
如果要生成下列结果，该如何写sql语句？
胜 负
2005-05-10 2 2
2005-05-10 1 2
果断鄙视一下自己，完全不会。好吧......那就从今天开始学数据库吧......

      好吧，把这次面试考到的知识总结一下。

      第一个题目，关于二分思想的知识。 
      额，二分思想最早我是见于在一个有序列表中查找一个数字。果断百度之，贴二分查找的优缺点。
      二分查找法的优点是比较次数少，查找速度快，平均性能好;其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
      好吧，偶贴偶写的二分查找的代码。不要二分查找的代码很容易些……先自己写一个……然后，通过数组中的所有数字的时候你就可以说很容易写了。
#include<iostream><br /> using namespace std;</p> <p>int binarySearch(int a[], int n, int num)<br /> {<br /> int begin = 0, end = n-1, middle;<br /> while(begin<=end)<br /> {<br /> middle = begin+ (end - begin) / 2;// 写成(begin+end)/2 可能会整数溢出<br /> if(a[middle]<num)<br /> {<br /> begin = middle+1;<br /> }<br /> else if(a[middle]>num)<br /> {<br /> end = middle-1;<br /> }<br /> else<br /> {<br /> return middle;<br /> }<br /> }<br /> return -1;<br /> }</p> <p>int main()<br /> {<br /> int a[] = {1, 3, 4, 5, 7, 9, 12, 23, 34, 45, 67, 88};<br /> int n = sizeof(a)/sizeof(a[0]), num;</p> <p> while(cin>>num)<br /> {<br /> int pos = binarySearch(a, n, num);<br /> if(-1 == pos)<br /> cout<<"The num can't find int the arrary/n";<br /> else<br /> cout<<num<<" int the array is the "<<pos+1<<" postion/n";<br /> }<br /> return 0;<br /> }