I should have mentioned about the default category, dezertsuz. I am sorry about that.
Because of that one category requirement, the default is Uncategorized. You can change the default category, though. Create one category you wouldn't mind using on a post for when you forget or choose not to click on a category. Go to Dashboard>Posts>Categories and create a new one there. Then go to Settings> Writing and there is an option called Default Post Category. Don't forget to Save. I no longer have a category labelled Uncategorized, so I must have deleted it. Once you have a new default, you can go back to your Posts>Categories and remove it.
Try this first and see what happens to all the Uncategorized posts. I have changed tags and categories in bulk, but I don't know if it does more than one page worth of posts. You can change categories in bulk from your All Posts page.
I hope I did not confuse you in trying to explain this. I had a time with categories and tags when I first started blogging here, wanting to use exclusively tags as I was used to that from other places I have used. I tried both for awhile, but I felt it was just a mess of too much, so I converted all to categories and removed excess. I am down to 33 from the almost 200 tags/categories I had before.