Following Matveev, a k-normal surface in a triangulated 3-manifold is a generalization of both normal and (octagonal) al-
most normal surfaces. Using spines, complexity, and Turaev-Viro invariants of 3-manifolds, we prove the following results:
a minimal triangulation of a closed irreducible or a boundedhyperbolic 3-manifold contains no non-trivial k-normal sphere;
every triangulation of a closed manifold with at least 2 tetra-hedra contains some non-trivial normal surface;
every manifold with boundary has only finitely many triangulations without non-trivial normal surfaces. Here, triangulations of bounded manifolds are actually ideal triangulations. We also calculate the number of normal surfaces of nonnegative Euler characteristics which are contained in the conjecturally minimal triangulations of all lens spaces Lp,q.