Post-starburst (E+A or k+a) spectra, characterized by their exceptionally strong Balmer lines in absorption and the lack of emission lines, belong to galaxies in which the star formation (SF) activity ended abruptly sometime during the past Gyr. We perform a spectral analysis of galaxies in clusters, groups, poor groups, and the field at z = 0.4-0.8 based on the ESO Distant Cluster Survey. We find that the incidence of k+a galaxies at these redshifts depends strongly on environment. K+a's reside preferentially in clusters and, unexpectedly, in a subset of the sigma = 200-400 km s(-1) groups, those that have a low fraction of O II emitters. In these environments, 20%-30% of the star-forming galaxies have had their SF activity recently truncated. In contrast, there are proportionally fewer k+a galaxies in the field, the poor groups, and groups with a high O II fraction. An important result is that the incidence of k+a galaxies correlates with the cluster velocity dispersion: more massive clusters have higher proportions of k+a's. Spectra of dusty starburst candidates, with strong Balmer absorption and emission lines, present a very different environmental dependence from k+a's. They are numerous in all environments at z = 0.4-0.8, but they are especially numerous in all types of groups, favoring the hypothesis of triggering by a merger. We present the morphological type, stellar mass, luminosity, mass-to-light ratio, local galaxy density, and clustercentric distance distributions of galaxies of different spectral types. These properties are consistent with previous suggestions that cluster k+a galaxies are observed in a transition phase, at the moment they are rather massive S0 and Sa galaxies, evolving from star-forming, recently infallen later types to passively evolving cluster early-type galaxies. The correlation between k+a fraction and cluster velocity dispersion supports the hypothesis that k+a galaxies in clusters originate from processes related to the intracluster medium, while several possibilities are discussed for the origin of the puzzling k+a frequency in low-O II groups.