The theory of linear viscoelasticity of rod-like cholesteric liquid crystals subjected to small-amplitude oscillatory shear flow is formulated and applied to the cholesteric helix along the flow, velocity gradient, and vorticity directions. Expressions for the zero- and infinite-frequency viscosities are derived and their ordering is predicted. Based on the classical ordering of the Miesowicz shear viscosities and anisotropies of torque coefficients, it is found that the largest (smallest) zero-frequency viscosity obtains with the helix along the flow (gradient) direction. In addition, the difference between the zero- and infinite-frequency viscosities is found to be sensitive to the helix orientation, such that it is largest (smallest) when the helix is along the flow (gradient) direction. The complex viscosity corresponds to a viscoelastic material with a single relaxation time. The relaxation time depends on the Frank elastic constants involved in the deformation, such that when the helix is along the vorticity it is twist dependent, and splay-bend otherwise. The strength of the viscoelasticity is largest (smallest) when the helix is along the flow (gradient) direction. The hard-rod theory of Doi is used to confirm the predicted dependence of the strength of the viscoelastic response on the cholesteric helix orientation.