Provided that the release of the basilisk created a lot of terror in Hogwarts, I was wondering why it was a big thing for Dumbledore type wizards to hunt and kill the subject.
Harry didn't know Avada Kedavra at that time, but could a basilisk be killed using Avada Kedavra?
While there is not a canonical reference, it can be inferred that the killing curse would work on a basilisk. There are a few instances of it being used on both normal and fantastic animals.
These include
It can be argued whether or not Hedwig counts as a fantastic creature as she was markedly more intelligent than "normal" owls, but Fawkes definitely counts as a fantastic creature and was affected by the spell.
It is not mentioned in Fantastic Beasts and Where to Find Them whether or not the basilisk is resistant to spells.
I would imagine Avada Kedavra would kill a basilisk; the difficulty is in casting the spell without dying yourself. If it went hunting in the castle, the basilisk had a much better chance of killing as it had the element of surprise.
The support for my speculation comes from the fact that basilisks must have been killed before. I doubt every wizard happened to be able to stab it through the head. However you can also take it as another way as we only have two canon examples of basilisks:
Herpo the Foul's Basilisk is believed to have lived for close on nine hundred years.
Avada Kedavra certainly can affect both mundane animals, such as the spider that Barty Crouch Jr. used to demonstrate the spell, and some magical beasts, such as phoenixes (as demonstrated when Fawkes swallowed the curse meant for Dumbledore in Order of the Phoenix).
However, we have good reason to believe that Avada Kedavra is not a generic "kill anything" spell.
For example, the Lethifold is said to be vulnerable only to the Patronus Charm:
As Belby so dramatically reveals, the Patronus is the only spell known to repel the Lethifold. Since it generally attacks the sleeping, though, its victims rarely have a chance to use any magic against it.
—Fantastic Beasts and Where to Find Them
Of course, given the infrequency of Lethifold attacks, and the unlikelihood that a potential victim will use any magic against the Lethifold, it is entirely possible that, as of the time of writing, no one had even tried to cast Avada Kedavra on such a creature.
What should really make us suspect that some creatures are immune to Avada Kedavra, though, is the Nudu.
A gigantic leopard that moves silently despite its size and whose breath causes disease virulent enough to eliminate entire villages, it has never yet been subdued by fewer than a hundred skilled wizards working together.
—Fantastic Beasts and Where to Find Them
Admittedly, the wording here is "subdued." But let's face it: if you are fighting a creature whose only purpose is to spread disease, and that can take on a hundred wizards without breaking a sweat, you probably are not shooting Stunning Spells. If it takes over one hundred (skilled!) wizards to kill it, it seems very unlikely that one wizard using the Avada Kedavra spell could do so. And it would certainly have been tried: there is no problem with using the Unforgivable Curses on non-humans (or at least non-sapient creatures).
Finally, of course, there is the fact that Quirrell opted to put Fluffy to sleep, rather than using a Killing Curse. True, he knocked out a troll later on, but that was a trivial task for him. He actually had to find a way of getting past Fluffy. This strongly suggests that Voldemort's usual go-to spell would not work.
Therefore, we should not assume that the Basilisk would be vulnerable to the Killing Curse.
