me podrian ayudar para realizar un ejercicio

[AlEzHiThOp]

hola...bueno soy nuevo en este foro..un profe mio me lo recomendo y bueno quisiera ayuda para realizar un programa que cree una lista de empleados que pueda almacenar la sig informacion...
Nombre
Direccion
Telefono
Sueldo_mensual
.........
debe de preguntar numero de empleados
los datos de cada empleado deben sde ser pedidos por pantalla
se debe listar a todos los empleados
mostrar promedio de sueldos
mostrar sueldo mas alto y mas bajo
numero de empleados con sueldo mayor al promedio
numero de empleados con sueldo menor al promedio
.............
este programa se tiene que acer sin arreglo ni registro

no pido que lo resuelvan (claro que si me ayudan que mejor) solo tengo unas cuantas dudas
me dijeron que se podia hacer con estructuras dinamicas...lo que no se es como aplicarla...o alguna sugerencia???
otra cosa mas, se tiene que realizar sin declarar demasiadas variables