Когда речь идет о выделении памяти, т.е. создании динамических массивов или просто указателей на блоки памяти. То выглядит это следующим образом:
int size = ...
int *array = new int[size];
или 
int* p = NULL;
p = new int;
 замень, тут всегда идет указатель на выделенный блок памяти. 
 Соотвественно и деструкторе для массивов  идет
delete [] array;
или delete p;
В твоем примере 
Polynomial::Polynomial(int stepen)
{
  deg = stepen;
  data = new int[deg + 1];
  for (int i = deg; i >= 0; i--) data[i] = 0;
}
Polynomial::~Polynomial()
{
  delete[] data;
}
 все вроде бы верно, при условии, что дата это указатель, который декларирован где-то в классе заранее.