The current accepted takes posts out of range too. Since it LEFT JOIN on wp_term_relationships without knowing that the first join might be a Category or a Post_tag, it gives false-positive, hence affecting posts that might not be without category.
Inspired from the current accepted answer, change the "37" for your actual wanted category:
INSERT IGNORE INTO wp_term_relationships
(object_id, term_taxonomy_id, term_order)
SELECT p.ID as `object_id`, 37 as `term_taxonomy_id`, 0 as `term_order`
FROM wp_posts p
WHERE p.post_type="post"
AND p.post_status='publish'
AND NOT EXISTS
(
SELECT *
FROM wp_term_relationships rel
JOIN wp_term_taxonomy tax
ON tax.term_taxonomy_id = rel.term_taxonomy_id
AND tax.taxonomy = 'category'
JOIN wp_terms term
ON term.term_id = tax.term_id
WHERE p.ID = rel.object_id
)