  A maximal $\varepsilon$-near perfect matching is a maximal matching which
covers at least $(1-\varepsilon)|V(G)|$ vertices. In this paper, we study the
number of maximal near perfect matchings in generalized quasirandom and dense
graphs. We provide tight lower and upper bounds on the number of
$\varepsilon$-near perfect matchings in generalized quasirandom graphs.
Moreover, based on these results, we provide a deterministic polynomial time
algorithm that for a given dense graph $G$ of order $n$ and a real number
$\varepsilon>0$, returns either a conclusion that $G$ has no $\varepsilon$-near
perfect matching, or a positive non-trivial number $\ell$ such that the number
of maximal $\varepsilon$-near perfect matchings in $G$ is at least $n^{\ell
n}$. Our algorithm uses algorithmic version of Szemer\'edi Regularity Lemma,
and has $O(f(\varepsilon)n^{5/2})$ time complexity. Here $f(\cdot)$ is an
explicit function depending only on $\varepsilon$.
