I love clever algorithms, and really enjoyed algorithm and data structure classes at university. However, despite having worked for over 20 years as a programmer in several software-intense companies (big and small) in the telecommunications and VoIP field, I have almost never had a need to know the answers to these questions.
Did you ever need to write an algorithm to process some large volume of data, and you had to make choices related to performance, e.g. to avoid a combinatorial explosion in some searching problem which trivial implementation would be a full cartesian product of several dimensions of data (i.e. a bunch of deeply nested loops)?
Speaking of cartesian product, did you ever wrote a huge database query that you had to optimize through smart usage of join methods, indexing structure, caching (eg materialized views), decisions like subqueries versus joins versus procedural code etc.?
Did you ever had to pick a library collection -- not implement your own hashmap or tree, but just select the ideal implementation -- to allow optimal searches in a given dataset?
If answer='Y' to any of these, then you needed that knowledge, and I guess you do in a regular basis. The thing about CS theory is that it structures and formalizes these problems so they can be precisely analyzed; used as basis for further inventions and improvements; reliably predict the result of some design choice, etc. You have some empirical knowledge of things like computational complexity, but having formal knowledge would often allow to replace hunches with objective certainty, or arrive to the optimal answer to some problems much quicker and more reliably.
I absolutely agree that knowing basic CS is a good thing, and it will make you a better developer. Also, we do internalize a lot of the concepts so they become second nature. That being said, it surprised me how much code there is where this doesn't matter.
As for the specific questions: It's definitely good to know big O notation, so maybe I was a bit quick to dismiss the first question. However, a more realistic/useful comparison would be between O(n^2) and O(n log n).
For picking a collection to use – definitely knowing when to use a hash map versus a list. Asymptotic run-time behavior of Quicksort – no.
Binary search tree – that's the one example I mentioned in my blog post, so yes, useful.
Graphs – never needed in the applications I've worked with. Same for using a heap, never seen/needed.
Graphs are an interesting case in this debate. I agree that you very rarely run into real-world problems that look like a traveling salesman or bipartite test etc. But the thing about graphs is that they are the foundation of ALL data structures, and lots of algorithms. Lists, hashing, trees, arrays and more -- just special cases of graphs. If you can describe anything at all with a boxes-and-arrows diagram, it's a graph problem ;-) so if you know at least the core concepts of graphs, including some fundamental techniques (e.g. advantages of each representation such as adjacency matrix vs. node list vs. edge list), then you have the tools to work through any data structure problem; and any algorithm that's focused on searching or manipulation of specific data structures. And this can take you very, very far.
Once again, of course you can learn most of these foundational concepts more empirically, or in a more "bottom-up" way by starting with the standard data structures and algorithms that you use in practice, but gradually deducing general concepts that unify them. But I wonder if this can ever result in the same deep insight that some study of graph theory can give.
In fact, it was the second biggest surprise for me when starting out as a programmer after university. I wrote this up in "Top 5 Surprises When Starting Out as a Software Developer" http://henrikwarne.com/2012/08/22/top-5-surprises-when-start...