The question is in title. Let me repeat:
What are the number of states in NFA and DFA accepting strings from length 0 to n with alphabet $\Sigma = {0,1}$
I feel both NFA and DFA will take following form:
and thus both have $n+1$ states. Am I correct with this? Or the DFA needs to take following form?
I feel its not necessary to have transitions defined for every symbol for every state, mainly because it does not eliminate "deterministic" nature of the automaton. Am I right?
As mentioned in the other answer, there are two common definitions of DFA. One definition requires the transition function to be total, and the other allows it to be partial. The former one is somewhat more common.
Under the first definition, you need to include the additional state. Under the second definition, you don't have to.
Using Myhill–Nerode theory, it is easy to show that $n+2$ is the minimum number of states in a (total) DFA accepting the words of length between $0$ and $n$. Indeed, consider the words $\epsilon, 0, 0^2, \dots, 0^{n+1}$. These $n+2$ words are pairwise distinguishable. Indeed, if $0 \leq i < j \leq n+1$ then $0^j0^{n+1-j}$ doesn't belong to the language, but $0^i0^{n+1-j}$ does.
Using the "fooling set" method, it is easy to show likewise that $n+1$ is the minimum number of states in an NFA accepting the same language. Here is a statement of the method:
Let $L$ be a regular language. Suppose that there are $m$ pairs of words $x_i,y_i$ such that $x_iy_i \in L$ for all $i$, and for all $i \neq j$, either $x_iy_j \notin L$ or $x_jy_i \notin L$. Then every NFA for $L$ contains at least $m$ states.
We choose $x_i = 0^i$ and $y_i = 0^{n-i}$ for $0 \leq i \leq n$, in total $n+1$ pairs. Clearly $x_i y_i = 0^n \in L$ (denoting our language by $L$), whereas for $i < j$, $x_j y_i = 0^{n-i+j} \notin L$.
You can define DFAs in both ways. One can require the transition function to be total, but it is indeed fine to define DFAs without this requirement. You (or your lecturer) just choose one definition and stick with it.
