各位仁兄仁姐，小妹没学过数据结构，被迫帮别人要做几道题，在网上查了半天还有6道没有解决。无奈时间有限，自己现学已来不及，不过感觉应该是些基础的，或者某些课本的原题。请知情者指点迷津，不胜感激！！
     先将原题粘上，希望学过的朋友，指点一下！

1.用Step Table的方法计算下面算法的时间复杂性

template <class T>
void Insert(T a[],int & n,const T& x)
{//Insert x into the sorted array a[0:n-1].
 //Assume a is of size > n.
  int i;
  for (i = n-1;i >= 0 && x < a[i]; i--)
    a[i+1] = a[i];
  a[i+1] = x;
  n++; //one element added to a
}
解：

2.证明下面的渐进表达式成立
E4：

I2：

解：

3．分别用迭代展开和Master方法计算下面递归关系的复杂性


解：

4．考虑

而不是

的连续背包问题。一种可行的贪婪策略是：按价值密度非递减的顺序检查物品，若剩余容量能容下正在考察的物品，将其状如；否则，往背包中装入此物品的一部分。
1）对于n=3，w=[100,10,10],  p=[20,15,15]及c=105，上述装入方法获得的结果是什么？
2）证明这种贪婪算法总能获得最优解。
解：

5．使用2-优化方法求解以下0/1背包问题的实例并给出求解过程。n=4,c=20,w=(10,15,6,9),p=(2,5,8,1)

6．给出快速排序的非递归算法，要求堆栈中只需保存left和right中较小者的边界。证明所需要的栈空间大小为 。