Skip to content

Latest commit

 

History

History
78 lines (64 loc) · 2.55 KB

data_structures.md

File metadata and controls

78 lines (64 loc) · 2.55 KB

Data Structures Quiz

LIFO (last-in-first-out) describes the behavior of which of the following?

  • Queue
  • Set
  • Stack
  • Map
Answer:Stack
Explanation:When you stack things on top of each other, you have to remove the item off the top first. We can remove the item at the bottom until all of the other items on top of it have been removed. So the first thing that goes in is actually the last thing that comes out.
        N
        / \
      N   N
      / \   
    N   N
    /
  N

Is the above graph a binary tree?

  • No
  • Yes
Answer:Yes
Explanation:A binary tree is a graph with the constrant that a node can have at most two children.

BFS (breadth first search) uses which of the following ADTs?

  • Queue
  • Set
  • Stack
  • Map
Answer:Queue
Explanation:As we are looking at each node, we want to add their children to our list of nodes to look at. A queue allows us to utilize FIFO (first in first out) so that the order in which the nodes are added to our list is the order in which they will be dealt with.
        1   
        / \
      2   5
      /   / \
    3   6   9
    /   / \
  4   7   8

If we used DFS to try and find the node with value 6 in the graph above, what is a possible ordering of nodes that would be visited?

  • 1-2-5-3-6
  • 1-2-3-4-5-6
  • 4-3-2-1-7-8-6
  • 8-7-4-9-6
Answer:1-2-3-4-5-6
Explanation:For DFS, we will look at a node, and then look at it's first child, and then that nodes first child and so on until we hit a leaf node or find the node we are searching for. When we hit a leaf node, we will begin popping off the stack of recursive calls (going back up the tree a level at a time) and looking at the next child for that node. Once we find the node we are looking for, we start popping off the stack of recursive calls returning the node we found that has the value we are looking for.
        D   
        / \
      A   E
      / \   \
    I   C   G
    / \     /
  H   F   B

Which node in the above graph is the root?

  • A
  • B
  • D
  • F
  • H
  • I
Answer:

D

Explanation:The root node refers to the top most node that has no parent node.