But you can do work without accelerating something. I'll explain in a second.
A man pushes against a wall: No displacement, so no work.
A) No displacement, so no work.
B) "constant velocity" means no acceleration. That means no net force, since net force = m * a. The word "frictionless" is important here. Since there's no frictional force, then "no net force" means there's no force at all acting. So F = 0, and there's no work.
BUT if there were friction, you would be exerting a force. "No net force" means the force you're providing is countered by friction. And the work F * d you're doing is going into heat from friction rather than into accelerating the object. You're still doing work. You're putting energy in.
C) There's a force (gravity) and displacement in the direction of the force. So there's work. Yes, it accelerates. It got energy. That energy came from the gravitational force doing work.
Next group:
A) If "overcome gravity" means "move upward", then yes. There's a force, and there's a displacement. If it just means "hold it up" like A above, then no.
B) Yes. The object is getting energy by something doing work on it.
C) Yes. See my discussion above. Something is putting energy into the system, and friction is doing work to take it out again. No net gain in energy.
Perhaps it would help to think in terms of energy rather than acceleration.