While I'm reasonably good at these style of questions, I'd be very unsurprised if there were a few that'd just catch me cold, even today. And I'm probably working in a field that's a lot more day-to-day data structure heavy than most (RDBMS internals).
It's not that it's difficult. It's that it's stupid.
edit: Let me put it this way... if you're hiring a senior/lead level code security analyst, the odds that they will be implementing (or even reading for comprehension) a binary tree are effectively nil. The odds of having to show how to mark false positives in a Fortify scan are very, very high. Can they explain buffer overflows, html encoding, etc? Can they write a description of unsafe practices in plain English, for both developers and managers? Do they have experience in conducting training classes for developers to reduce security problems? Do they have a working knowledge of HIPAA, SOX, or other relevant industry regulations? Can they do good Powerpoint presentations on this stuff?
Being a security analyst isn't about writing homework assignments from freshman year of college. It's about regulations, about training others, about using high end tools that aren't taught in college, and a bunch of other stuff. Ask questions about the actual job.