They may know in general where Alameda is, but probably only in relation to 23rd century landmarks. Take a city you're familiar with, drop you off at street level a few centuries out of your own time, and see if you'd be able to find your way around. I bet most people would be as lost as Chekov and Uhura.
What did we expect? They would have known where Alameda is, but they were in an unfamiliar city surrounded by unfamiliar landmarks, and the only way that they knew how to get there was to take the air tram or something. Not really an option in 1986.