Data Structures Trivia Quiz

Answer: Hash table

A hash table allows you to look up data based on a key, much like you look up a definition in a dictionary based on the word it applies to.

A tree lets you build a hierarchical structure, with parents and children. A hash is an array with a special interpretation, and a linked list is just a list.

Answer: Integer division, i / 2

A heap is an array that is being interpreted as a binary tree (every node in the tree has two children). The root of the tree is in index 1, and its two children have indices 2 and 3.

From there, 2 will have children 4 and 5, and 3 will have children 6 and 7. Notice how the first child of a node has an index equal to 2 * its parent, and the second has an index of the first plus one? That makes traversal very easy. To find the parent, we need to do *integer* division because otherwise an odd child index will result in a fractional index, which is not what we want.

Answer: Linked list

A common vector implementation uses a linked list of arrays, which gives reasonable lookup time, depending of course on the size of the arrays and the size of the vector itself.

Answer: 'p' 'a' 't'

A stack is just what it sounds like. You put things on top of it (you 'push' them onto the stack), and you take things back off the top (you 'pop' them off the stack). So when you push 't' 'a' 'p' onto a stack in that order, the 't' is at the bottom and the 'p' is at the top. So when you pop them back off, you will first get the 'p', then the 'a', and finally the 't'.

Answer: 'm' 'a' 'r'

A queue is basically a line; the first thing into it is the first thing out. So everything stays in order.

Answer: Roads connecting cities

A graph is made up of a set of vertices (points) connected by edges (lines). The edges may have a direction associated with them (think of one-way streets), or a cost (think of toll roads). They are useful for trying to find the cheapest route between two points (a trucker trying to save money or time), or the shortest route that will allow you to visit every point (the Traveling Salesman Problem).

Answer: Four

A balanced binary tree with 15 elements in it will have four levels. Starting at the top, you can tell whether the element is searching for in equal to, less than, or greater than the root. Based on that, you will either be done (1 step), or you will have to visit the left or right child. If the element you are searching for is less than the root, you will travel left, and otherwise you will travel right. That was one step, and you just eliminated half of the tree (the other child and its descendants). So there are only seven nodes left.

The second step will reduce the search to three nodes, the third down to one. Checking that last node makes four steps.

This type of problem is used to determine how long it will take to execute a sequence of instructions. In this case, since the number of steps taken is approximately the logarithm (base 2) of the size of the tree, it would be called a O(log n) problem. That means no matter how large the tree is, the upper-bound on the amount of time it will take to search it is proportional to the log of the tree size.

Answer: Stack

The stack would help if you push each '(' onto it as you see it, and you pop one off each time you see a ')'. If you never try to pop an empty stack, and the stack is empty when you're done, then the expression has balanced parenthesis.

Answer: There are no duplicates

A set enforces uniqueness, since if an item is in a set, there is no sense in it being in the set a second time. Imagine if someone asked you to tell him what kinds of cereal you have. You are going to give him a set of names, since even if you have two boxes of something, you probably won't read it off more than once.

The elements of a set have no order guarantees, and as you just saw, a set can have anything in it, even other sets!

Answer: B+Trees

The B+Tree is similar to the B-Tree in that they are both balanced trees, but it has some significant differences that make it ideal for filesystems. Most importantly, data is only stored at the leaves of a B+Tree. For more information, explore Wikipedia or simply search the web.