先排最高位，最高位上的数字只能为1、2、3，共有方法

A

13

种．
再排其它位，其它位上的数字不作要求，任意排列，共有

A

44

种，
由分步计数原理可得，由数字1、2、3、4、5可以组成没有重复数字且比40000小的五位数的个数为：

A

13

•

A

44

=72，
故选C．