A não é possível ter ambas cadastradas com NOT NULL, pois ao cadastrar o primeiro departamento, um empregado deverá existir, mas não pode existir um empregado sem departamento associado.
B não é possível ter ambas cadastradas com NOT NULL, mesmo com a avaliação postergada das restrições, pois no momento do COMMIT o registro referenciado pela chave estrangeira já precisa estar no banco de dados, para ser validado.
C ambas podem ser NOT NULL, desde que o nível de isolamento das transações permita leitura suja (read uncommitted).
D ambas podem ser NOT NULL, desde que o primeiro empregado e o primeiro departamento sejam inseridos na mesma transação e que as chaves estrangeiras sejam avaliadas somente ao final dela (no momento do COMMIT), o que pode ser conseguido declarando-as como sendo de avaliação postergada (DEFERRABLE).
E ambas podem ser NOT NULL, mas os sistemas não poderão usar transações para cadastrar os dados nessas tabelas.