We present the average rest-frame spectrum of high-redshift dusty , star-forming galaxies from { 250 - 770 } GHz . This spectrum was constructed by stacking ALMA 3 mm spectra of 22 such sources discovered by the South Pole Telescope and spanning z = 2.0 - 5.7 . In addition to multiple bright spectral features of ^ { 12 } CO , [ CI ] , and H _ { 2 } O , we also detect several faint transitions of ^ { 13 } CO , HCN , HNC , HCO ^ { + } , and CN , and use the observed line strengths to characterize the typical properties of the interstellar medium of these high-redshift starburst galaxies . We find that the ^ { 13 } CO brightness in these objects is comparable to that of the only other z > 2 star-forming galaxy in which ^ { 13 } CO has been observed . We show that the emission from the high-critical density molecules HCN , HNC , HCO ^ { + } , and CN is consistent with a warm , dense medium with T _ { \mathrm { kin } } \sim 55 K and n _ { \mathrm { H _ { 2 } } } \gtrsim 10 ^ { 5.5 } cm ^ { -3 } . High molecular hydrogen densities are required to reproduce the observed line ratios , and we demonstrate that alternatives to purely collisional excitation are unlikely to be significant for the bulk of these systems . We quantify the average emission from several species with no individually detected transitions , and find emission from the hydride CH and the linear molecule CCH for the first time at high redshift , indicating that these molecules may be powerful probes of interstellar chemistry in high-redshift systems . These observations represent the first constraints on many molecular species with rest-frame transitions from 0.4 - 1.2 mm in star-forming systems at high redshift , and will be invaluable in making effective use of ALMA in full science operations .