实现代码如下：
#include <stdio.h>
#include "common.h"
void merge(int data[], int p, int q, int r)
{
int i, j, k, n1, n2
n1 = q - p + 1
n2 = r - q
int L[n1]
int R[n2]
for(i = 0, k = pi <n1i++, k++)
L[i] = data[k]
for(i = 0, k = q + 1i <n2i++, k++)
R[i] = data[k]
for(k = p, i = 0, j = 0i <n1 &&j <n2k++)
{
if(L[i] >R[j])
{
data[k] = L[i]
i++
}
else
{
data[k] = R[j]
j++
}
}
if(i <n1)
{
for(j = ij <n1j++, k++)
data[k] = L[j]
}
if(j <n2)
{
for(i = ji <n2i++, k++)
data[k] = R[i]
}
}
void merge_sort(int data[], int p, int r)
{
if(p <r)
{
int q = (p + r) / 2
merge_sort(data, p, q)
merge_sort(data, q + 1, r)
merge(data, p, q, r)
}
}
void test_merge_sort()
{
int data[] = {44, 12, 145, -123, -1, 0, 121}
printf("-------------------------------merge sort----------------------------\n")
out_int_array(data, 7)
merge_sort(data, 0, 6)
out_int_array(data, 7)
}
int main()
{
test_merge_sort()
return 0
}
4.对于有n个结点的线性表（e0，e1，…，en-1），将结点中某些数据项的值按递增或递减的次序，重新排列线性表结点的过程，称为排序。排序时参照的数据项称为排序码，通常选择结点的键值作为排序码。
若线性表中排序码相等的结点经某种排序方法进行排序后，仍能保持它们在排序之前的相对次序，称这种排序方法是稳定的；否则，称这种排序方法是不稳定的。
在排序过程中，线性表的全部结点都在内存，并在内存中调整它们在线性表中的存储顺序，称为内排序。在排序过程中，线性表只有部分结点被调入内存，并借助内存调整结点在外存中的存放顺序的排序方法成为外排序。
下面通过一个表格简单介绍几种常见的内排序方法，以及比较一下它们之间的性能特点。
排序方法
简介
平均时间
最坏情况
辅助存储
是否稳定
简单排序
选择排序
反复从还未排好序的那部分线性表中选出键值最小的结点，并按从线性表中选出的顺序排列结点，重新组成线性表。直至未排序的那部分为空，则重新形成的线性表是一个有序的线性表。
O( )
O( )
O(1)
不稳定
直接插入排序
假设线性表的前面I个结点序列e0，e1，…，en-1是已排序的。对结点在这有序结点ei序列中找插入位置，并将ei插入，而使i+1个结点序列e0，e1，…，ei也变成排序的。依次对i=1，2，…，n-1分别执行这样的插入步骤，最终实现线性表的排序。
O( )
O( )
O(1)
稳定
冒泡排序
对当前还未排好序的范围内的全部结点，自上而下对相邻的两个结点依次进行比较和调整，让键值大的结点往下沉，键值小的结点往上冒。即，每当两相邻比较后发现它们的排列顺序与排序要求相反时，就将它们互换。
O( )
O( )
O(1)
稳定
希尔排序
对直接插入排序一种改进，又称“缩小增量排序”。先将整个待排序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。
kn ln n
O( )
O(logn)
不稳定
快速排序
对冒泡排序的一种本质的改进。通过一趟扫视后，使待排序序列的长度能大幅度的减少。在一趟扫视后，使某个结点移到中间的正确位置，并使在它左边序列的结点的键值都比它的小，而它右边序列的结点的键值都不比它的小。称这样一次扫视为“划分”。每次划分使一个长序列变成两个新的较小子序列，对这两个小的子序列分别作同样的划分，直至新的子序列的长度为1使才不再划分。当所有子序列长度都为1时，序列已是排好序的了。
O(nlogn)
O( )
O(logn)
不稳定
堆排序
一种树形选择排序，是对直接选择排序的有效改进。一个堆是这样一棵顺序存储的二叉树，它的所有父结点（e[i]）的键值均不小于它的左子结点（e[2*i+1]）和右子结点（e[2*i+2]）的键值。初始时，若把待排序序列的n个结点看作是一棵顺序存储的二叉树，调整它们的存储顺序，使之成为一个堆，这时堆的根结点键值是最大者。然后将根结点与堆的最后一个结点交换，并对少了一个结点后的n-1结点重新作调整，使之再次成为堆。这样，在根结点得到结点序列键值次最大值。依次类推，直到只有两个结点的堆，并对它们作交换，最后得到有序的n个结点序列。
O(nlogn)
O(nlogn)
O(1)
不稳定
归并排序
将两个或两个以上的有序子表合并成一个新的有序表。对于两个有序子表合并一个有序表的两路合并排序来说，初始时，把含n个结点的待排序序列看作有n个长度都为1的有序子表所组成，将它们依次两两合并得到长度为2的若干有序子表，再对它们作两两合并……直到得到长度为n的有序表，排序即告完成。
O(nlogn)
O(nlogn)
O(n)
稳定
后面根据各种排序算法，给出了C语言的实现，大家在复习的时候可以做下参考。
u 选择排序
void ss_sort(int e[], int n)
{ int i, j, k, t
for(i=0 i< n-1 i++) {
for(k=i, j=i+1 j<n j++)
if(e[k]>e[j]) k=j
if(k!=i) {
t=e[i] e[i]=e[k] e[k]=t
}
}
}
u 直接插入排序
void si_sort(int e[], int n)
{ int i, j, t
for(i=0 i< n i++) {
for(t=e[i], j=i-1 j>=0&&t<e[j] j--)
e[j+1]=e[j]
e[j+1]=t
}
}
u 冒泡排序
void sb_sort(int e[], int n)
{ int j, p, h, t
for(h=n-1 h>0 h=p) {
for(p=j=0 j<h j++)
if(e[j]>e[j+1]) {
t=e[j] e[j]=e[j+1] e[j+1]=t
p=j
}
}
}
u 希尔排序
void shell(int e[], int n)
{ int j, k, h, y
for(h=n/2 h>0 h=h/2)
for(j=h j<n j++) {
y=e[j]
for(k=j-h k>0&&y<e[k] k-=h)
e[k+h]=e[k]
e[k+h]=y
}
}
u 堆排序
void sift(e, n, s)
int e[]
int n
int s
{ int t, k, j
t=e[s]
k=s j=2*k+1
while(j<n) {
if(j<n-1&&e[j]<e[j+1])
j++
if(t<e[j]) {
e[k]=e[j]
k=j
j=2*k+1
}else break
}
e[k]=t
}
void heapsorp (int e[], int n)
{ int i, k, t
for(i=n/2-1 i>=0 i--)
sift(e, n, i)
for(k=n-1 k>=1 k--) {
t=e[0] e[0]=e[k] e[k]=t
sift(e, k, 0)
}
}
u 快速排序
void r_quick(int e[], int low, int high)
{ int i, j, t
if(low<high) {
i=low j=high t=e[low]
while(i<j) {
while (i<j&&e[j]>t) j--
if(i<j) e[I++]=e[j]
while (i<j&&e[i]<=t) i++
if(I<j) e[j--]=e[i]
}
e[i]=t
r_quick(e,low,i-1)
r_quick(w,i+1,high)
}
}
另外，外排序是对大型文件的排序，待排序的记录存储在外存中，在排序过程中，内存只存储文件的一部分记录，整个排序过程需进行多次的内外存间的交换。
*** 查找
查找就是在按某种数据结构形式存储的数据集合中，找出满足指定条件的结点。
按查找的条件分类，有按结点的关键码查找、关键码以外的其他数据项查找或其他数据项的组合查找等。按查找数据在内存或外存，分内存查找和外存查找。按查找目的，查找如果只是为了确定指定条件的结点存在与否，成为静态查找；查找是为确定结点的插入位置或为了删除找到的结点，称为动态查找。
这里简单介绍几种常见的查找方法。
u 顺序存储线性表的查找
这是最常见的查找方式。结点集合按线性表组织，采用顺序存储方式，结点只含关键码，并且是整数。如果线性表无序，则采用顺序查找，即从线性表的一端开始逐一查找。而如果线性表有序，则可以使用顺序查找、二分法查找或插值查找。
u 分块查找
分块查找的过程分两步，先用二分法在索引表中查索引项，确定要查的结点在哪一块。然后，再在相应块内顺序查找。
u 链接存储线性表的查找
对于链接存储线性表的查找只能从链表的首结点开始顺序查找。同样对于无序的链表和有序的链表查找方法不同。
u 散列表的查找
散列表又称杂凑表，是一种非常实用的查找技术。它的原理是在结点的存储位置和它的关键码间建立一个确定的关系，从而让查找码直接利用这个关系确定结点的位置。其技术的关键在于解决两个问题。
I. 找一个好的散列函数
哎 我应聘了N家公司 给你一些题好了华为的
第一部分:选择题
QUESTION NO: 1
1、public class Test {
public static void changeStr(String str){
str="welcome"
}
public static void main(String[] args) {
String str="1234"
changeStr(str)
System.out.println(str)
}
}
Please write the output result :
QUESTION NO:2
1. public class Test {
2. static boolean foo(char c) {
3. System.out.print(c)
4. return true
5. }
6. public static void main( String[] argv ) {
7. int i =0
8. for ( foo('A')foo('B')&&(i<2)foo('C')){
9. i++
10. foo('D')
12. }
13. }
14. }
What is the result?
A. ABDCBDCB
B. ABCDABCD
C. Compilation fails.
D. An exception is thrown at runtime.
QUESTION NO: 3
1. class A {
2. protected int method1(int a, int b) { return 0}
3. }
Which two are valid in a class that extends class A? (Choose two)
A. public int method1(int a, int b) { return 0}
B. private int method1(int a, int b) { return 0}
C. private int method1(int a, long b) { return 0}
D. public short method1(int a, int b) { return 0}
E. static protected int method1(int a, int b) { return 0}
QUESTION NO: 4
1. public class Outer{
2. public void someOuterMethod() {
3. // Line 3
4. }
5. public class Inner{}
6. public static void main( String[]argv ) {
7. Outer o = new Outer()
8. // Line 8
9. }
10. }
Which instantiates an instance of Inner?
A. new Inner()// At line 3
B. new Inner()// At line 8
C. new o.Inner()// At line 8
D. new Outer.Inner()// At line 8//new Outer().new Inner()
QUESTION NO: 5
Which method is used by a servlet to place its session ID in a URL that is written to the servlet’s response output stream?
A. The encodeURL method of the HttpServletRequest interface.
B. The encodeURL method of the HttpServletResponse interface.
C. The rewriteURL method of the HttpServletRequest interface.
D. The rewriteURL method of the HttpServletResponse interface.
QUESTION NO: 6
Which two are equivalent? (Choose two)
A. <%= YoshiBean.size%>
B. <%= YoshiBean.getSize()%>
C. <%= YoshiBean.getProperty("size")%>
D.
E.
F.
G.
QUESTION NO: 7
Which of the following statements regarding the lifecycle of a session bean are correct?
1. java.lang.IllegalStateException is thrown if SessionContext.getEJBObject() is invoked when a stateful session bean instance is passivated.
2. SessionContext.getRollbackOnly() does not throw an exception when a session bean with bean-managed transaction demarcation is activated.
3. An exception is not thrown when SessionContext.getUserTransaction() is called in the afterBegin method of a bean with container-managed transactions.
4. JNDI access to java:comp/env is permitted in all the SessionSynchronization methods of a stateful session bean with container-managed transaction demarcation.
5. Accessing resource managers in the SessionSynchronization.afterBegin method of a stateful session bean with bean-managed transaction does not throw an exception.
第二部分:概念题
1. 描述Struts体系结构?对应各个部分的开发工作主要包括哪些?
3. JSP有哪些内置对象和动作?它们的作用分别是什么?
4、SQL问答题
SELECT * FROM TABLE
和
SELECT * FROM TABLE
WHERE NAME LIKE '%%' AND ADDR LIKE '%%'
AND (1_ADDR LIKE '%%' OR 2_ADDR LIKE '%%'
OR 3_ADDR LIKE '%%' OR 4_ADDR LIKE '%%' )
的检索结果为何不同?
5、SQL问答题
表结构:
1、 表名:g_cardapply
字段(字段名/类型/长度):
g_applyno varchar 8//申请单号(关键字)
g_applydate bigint 8//申请日期
g_state varchar 2//申请状态
2、 表名:g_cardapplydetail
字段(字段名/类型/长度):
g_applyno varchar 8//申请单号(关键字)
g_name varchar 30//申请人姓名
g_idcard varchar 18//申请人身份证号
g_state varchar 2//申请状态
其中，两个表的关联字段为申请单号。
题目:
1、 查询身份证号码为440401430103082的申请日期
2、 查询同一个身份证号码有两条以上记录的身份证号码及记录个数
3、 将身份证号码为440401430103082的记录在两个表中的申请状态均改为07
4、 删除g_cardapplydetail表中所有姓李的记录
")
