Остаётся ли в ЛИНУКС мусор после удаления программ ?

"Программа" в Линухе - это, как правило, довольно размытое понятие.
БОльшая чать софта устанавливается из репоизториев того или иного
дистра. И у разработчиков есть возможность не устанавливать по 100500
раз одни и те же совместно используемые компоненты (библиотеки, кодеки и т. п. ) . И при установке того или иного пакета (через штатную систему
управления пакетами) , как правило, доустанавливаются все необходимые
компоненты (зависимости) . Однако, если пакет удаляется, система
управления пакетов либо оставляет совместно используемые компоненты.
либо запрашиывает пользователя, надо ли их удалять. Если же софт
собирается из исходников, то его полное (автоматическое) удаление
возможно - при сохранении дерева исходников. Ну и проприетарные пакеты - с ними сложнее всего и всегда всё по-разному. В лучшем случае, каждый пакет пишется в отдельный каталог, совсем красиво - если в /opt (как, например, SPSS). В таком случае, всегда можно доудалить остатки вручную.

В любом случае, на работу остальных программ оставшиеся "куски" никак не скажутся. Ибо нету единого "реестра", отвечающего за конфигурацию ВСЕЙ системы. Общесистемные конфигурационные файлы хранятся обычно в /etc, изменяемые польователем - в его домашнем каталоге. При удалении пакета они почти всегда остаются. Это позволяет, кстати, очень гибко переходить от одного дистра к другому - если /home вынесен на отдельный раздел. Либо - при необходимости - одним махом сбросить пользовательские настройки, удалив соответствующие конфиги.

sudo apt-get remove -purge yourpackage - и никакого мусора. В теории, по крайней мере.

не проверить и не доказать этот факт

максимум в твоей домашней папке ( настройки какие-нибудь )

смотря как удалишь

Да запросто, это тебе не Mac OS X.

угу, если стандартными методами или программами (типо rm)
данные на диске остаются, будет убрана только ссылка на фреймы (куски данных, разбросанные по диску)