Review of Fundamental Data Structures

Reading

• Read 1.4, pages 25-37
  • What are arrays and linked lists? What are the differences between then?
  • What are stacks and queues? What are their key operations? How can they be implemented using a double-linked list?
  • What is a priority queue? What are its key operations?
  • What are the two ways of representing graphs? What are the advantages and disadvantages of each approach?
  • How can we represent weighted graphs?
  • When do we say that a graph is connected?
  • What graphs do we call (free) trees?
  • What is the difference between a “free tree”, a “rooted tree” and an “ordered tree”?
  • What are binary search trees?
  • Describe the first child-next sibling representation of ordered trees. Illustrate with an example of an ordered tree presented both “normally” and via this alternative representation.
  • Work on exercises 1.4.2, 1.4.3, 1.4.4
  • Carefully and completely do exercise 1.4.5