When I was teaching data structures, one of the things that commonly came up was the whole issue of “pass by value” versus “pass by reference.” This was a very difficult thing to teach; somehow I’ve internalized the common C/Java style memory model, and these things are fairly second nature. While lecturing, I was definitely guilty of resorting to mind-numbing aphorisms like “integers are passed by value while objects are passed by reference”. These rules of thumb just don’t work (and make it incredibly difficult to get your head around the idea that object references are passed by value). This (fabulous) article over at MSDN has a really nice description of the stack as an implementation detail. Perhaps the key to solving this problem is really to just make the first course in computer science programs a course in programing language implementation. Then you can move on to harder things like control flow and datastructures (I’m kind of kidding here).
But in reality, the vagaries of “value types” versus heap-allocated objects are too pointy for a data structures course. Their guts are easily exposed in something like C while being appropriately hidden in an everything-is-an-object language like Python. The Java/C# mix of these memory allocation strategies is confusing for the beginner. Expose the details or don’t. Exceptions to the rules breed bugs and confusion.