Eu recomendo que você reinstale todos os pacotes em seu sistema que são conhecidos por terem arquivos no diretório /usr/lib/gcc
excluído.
A saída de dpkg -S /usr/lib/gcc
nos informou quais pacotes são, no seu caso:
gcc-5-base:amd64, libgcc-5-dev:amd64, cpp-5, gcc-5, gcc-6-base:amd64
Agora, vamos reinstalar todos eles:
sudo apt-get install --reinstall gcc-5-base:amd64 libgcc-5-dev:amd64 cpp-5 gcc-5 gcc-6-base:amd64
Você pode, alternativamente, automatizar esse processo e deixar a análise da lista de pacotes em sed
.
Dessa forma, você só precisa executar esse comando:
sudo apt-get install --reinstall $(dpkg -S /usr/lib/gcc | sed 's/,\|: .*//g')