Incense tends to be dark and rich, and most closely associated in my ex-Catholic mind, with aloes wood, frankincense and myrrh. Benzoin too, of course, and sometimes copal. (Had I been brought up Greek Orthodox, I might have said much of the same plus orange blossom, cinnamon, geranium, rose and more. Had I been brought up Buddhist, my idea of incense would lean far more heavily on the aloes wood, the sandalwood etc.)
"Smoke" to me indicates burning wood smoke, or sometimes burning leaves, but this is only my first thought. As we all know, smoke can run the olfactory gamut.
Tobacco? Depends. You have fresh, pure tobacco (e.g., Feuilles de Tabac, The Dreamer) and stale, dirty tobacco (e.g., Sung pour Homme).