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 bounded hyperbolic 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 triangu- lations without non-trivial normal surfaces. Here, triangulations of bounded manifolds are actually ideal tri-angulations. We also calculate the number of normal surfaces of nonnegative Euler characteristics which are contained in the conjecturally minimal triangulations of all lens spaces L _{p, q} .