Is it possible for the Normal Force to do work? Can a normal force do work?
Note: work = $Fd\cos(\theta)$, where $F$ is the magnitude of the force, $d$ is the magnitude of the displacement, and $\theta$ is the angle between the two.
Attempt at an answer:
My textbook's answer:

No the normal force does not cause an object to be displaced, it's perpendicular to the direction of motion.
My logic:

But what if the displacement is in a vertical direction, so now the normal force with is at either 0 degrees or 180 degrees? 
For example, in an elevator if it is accelerating upwards doesn't the normal force do work? Or for example, when someone jumps up he pushes down on the ground, then by Newton's third law the ground pushes back up, so that's a normal force that causes him to be displaced.
Which answer is correct and if my examples are wrong what is wrong in them?
 A: In the elevator example, you are correct. The elevator floor does work on you as you stand in a rising elevator.
In the jumping example, the floor is not doing work. After all, it is just a floor, it has nowhere to get the energy from to do work on you. (The floor of the elevator gets it from the motor running the elevator.) When you jump, the force from the floor on your shoes increases, but there is no displacement between the floor and your shoes until your shoes leave the floor, and at that point there's no force any more. Your torso is moving upwards while you jump, but there's no force from the floor on your torso, so the floor isn't doing work. All the energy of a jump comes from internal energy, not external work.
In fact, the floor does a bit of negative work when you jump, taking energy away from you, because it deflects a bit, moving down as you jump up.
When you lift an object off a table, the table does a tiny bit of work on the object for a similar reason. When the object sits on the table, the table deforms a bit. As you lift, the table goes back to its original shape, so there's a small bit of force*distance work being done. The deflection is usually so small as to be unnoticeable. On a trampoline it is much larger; enough to make jumping a very different experience.
A: Normal forces are not, as your elevator example illustrates, "perpendicular to the direction of motion", in general.
They are perpendicular, but the perpendicularity in question - which is what the word "normal" refers to - is to the surface on which the object is in contact with. That is, the vector along which the force is directed is the surface normal at the point of contact, not the normal vector to the moving object's path. There is no reason, then, to assume the two normals must always be the same in direction.
Your textbook is wrong. This is not an unheard-of symptom. If something feels off to you in a lecture or a book, you should question it. Science is all about asking questions. There are no dumb questions, only "dumbly" refusing to admit you were wrong if you were (e.g. the book was, in fact, right).
A: Yes, depending on your frame of reference.
Consider a block sliding down an incline plane. In the lab frame the normal force is always perpendicular to the path of the block, so it doesn't do work.
But what if you are moving to the right? Then in that frame the path of the block is no longer a straight line, but a curve, and the normal force is no longer perpendicular to the path or velocity of the block.
A: If a force acts through a distance the force does work; otherwise the force does not do work.  So for the elevator example the normal force does work.  Note: the change in kinetic energy is due to the net force (normal up and gravity for going up in an elevator).  If the force does not act through a distance it does no work, such as: (a) jumping off a fixed floor, (b) for rolling friction (no relative motion between force of friction and instantaneous point of contact), (c) and for the no-slip condition of a fluid flowing along a surface (fluid sticks to surface so no relative motion between force of friction and surface).  Also, work is the dot product of force and distance so a force perpendicular to distance does no work, such as centripetal force on a particle moving at constant speed in a circle.
