1、编写一个二分查找函数，下界为low，上界为high
递归法：
1. `template<class elemtype>`
2. `int BSearch(elemtype a[], elemtype x,int low,int high)`
3. `{`
4. `int mid;`
5. `if (low > high)`
6. `return -1;`
7. `mid = (low + high)/2;`
8. `if (x == a[mid])`
9. `{`
10. `return mid;`
11. `}`
12. `if (x < a[mid])`
13. `{`
14. `return BSearch(a, x, low, mid-1);`
15. `}`
16. `else`
17. `{`
18. `return BSearch(a,x, mid+1, high);`
19. `}`
20. `}`
非递归法：
1. `int BSearch(elemtype a[],elemtype key, int n)`
2. `{`
3. `int low,high,mid;`
4. `low = 0;`
5. `high = n-1;`
6. `while(low < high)`
7. `{`
8. `mid = (low + high)/2;`
9. `if (a[mid] == key)`
10. `return mid;`
11. `else if(a[mid] < key)`
12. `low = mid+1;`
13. `else`
14. `high = mid-1;`
15. `}`
16. `return -1;`
17. `}`
注意：二分查找算法前提是已经排好序的。
2、字符串逆序方法
具体的代码就不贴了，说两种方法：
- 一是原始字符串的头和尾进行交换；
- 二是另外开辟一个字符串空间， 将原始字符串逆序保存到新的字符串末；
3、链表反转（逆序）
1. `//常规方法：`
2. `struct Node`
3. `{`
4. `int data;`
5. `struct Node* next;`
6. `}`
7. `void reverse(Node* &head)`
8. `{`
9. `if (head == NULL)`
10. `return;`
11. `Node* pre, *cur, *ne;`
12. `pre = head;`
13. `cur = head->next;`
14. `while(cur)`
15. `{`
16. `ne = cur->next;`
17. `cur->next = pre;`
18. `pre = cur;`
19. `cur = ne;`
20. `}`
21. `head->next = NULL;`
22. `head = pre;`
23. `}`
24. `//递归方法：`
25. `Node* reverse(Node* head)`
26. `{`
27. `if (p == NULL || p->next == NULL)`
28. `{`
29. `return head;`
30. `}`
31. `Node* newHead = reverse(head->next);`
32. `head->next->next = head;`
33. `head->next = NULL;`
34. `return newHead;`
35. `}`
4、什么是平衡二叉树？
左右子树都是平衡二叉树， 且左右子树的深度差值的绝对值不大于1.
5、堆栈溢出一般是什么原因造成的？
数组越界访问
6、当申请的内存资源没有及时释放而一直重复申请时，会出现什么情况？
内存泄露，内存被占用会一直增长。
7、写出float x与“零值”比较的语句
if (x > -0.000001 && x<0.000001)
8、Internet采用哪种网络协议？该协议的主要层次结构是什么？
tcp/ip协议
主要层次结构采用5层结构：应用层/传输层/网络层/数据链路层/物理层，其中部分层次中常见协议如下：
- 应用层协议：telnet，ftp，http
- 传输层协议：tcp，udp
- 网络层协议：ip，icmp，igmp (7层结构：物理层、数据链路层、网络层、传输层、会话层、表示层、应用层)
9、IP地址的编码分为哪两部分
IP地址由两部分组成，网络号和主机号。不过要和“子网掩码”按位与之后才能区别哪些是网络位，哪些是主机位。
10、用户输入M、N值， 从1到N开始循环数数， 每次数到M就输出当前数据， 直到全部输出，写出C程序。
这是约瑟夫方法，可使用循环链表，用取余操作数，也可用数组，下面是c语言的数组程序:
1. `void yuesef(int M,int N)`
2. `{`
3. `int* p = new int[N];`
4. `int s = 0,r = 0;`
5. `for(int i=0;i<N;i++)`
6. `{`
7. `p[i] = 1;`
8. `}`
9. `for(int i=0;i<N;i++)`
10. `{`
11. `if (p[i] == 1)`
12. `s++;`
13. `if (s == M)`
14. `{`
15. `printf(“%d\n”,i+1);`
16. `p[i] = 0;`
17. `r++;`
18. `s = 0;`
19. `}`
20. `if (I == N-1 && r != N-1)`
21. `{`
22. `I = 0;`
23. `}`
24. `}`
25. `}`