Data Structures

Stacks, queues, trees, matrices, heaps, graphs

12 flashcards · Computer Science · by lakesare

1. LIFO/FIFO stands for?

   Last/First In First Out

2. What is a stack?

   A stack is an ordered collection of items that follows the LIFO principle.

3. Name 2 sides of a stack.

   top and base

4. What is a queue?

   A queue is an ordered collection of items that follows the FIFO principle.

5. What's a priority queue?

   Priority Queue is like a regular queue or stack, but where additionally each element has a priority associated with it. Element with high priority is served before an element with low priority.

6. Name 3 ways to store trees in relational database.

   1. parent-child, where each child stores parentId. { name: apple, parentId: 5 } 2. materialized path, where each element stores the full path to the very root. { name: apple, path: '5,4,1' } 3. nested set model, where you execute a preorder tree traversal and store lft and rgt indexes. { name: apple, lft: 5, rgt: 6 } Links: trees in Rails, trees in relational dbs

7. What's a linked list?

   Linked list stores ordered collection of elements; but unlike arrays, in linked lists the elements are not placed contiguously in memory. Each element consists of a node that stores the element itself and also a reference (also known as a pointer or link) that points to the next element.

8. What's a matrix?

   Array of arrays in any n of dimensions. This is a 2-dimensional matrix: [ [12, 7, 21], [45, -2, 14] ] This is a 3-dimensional matrix: [ [ [7, 2, 3], [5, 3, 5] ], [ [8, 9, 3], [1, 2, 2] ] ]

9. The defining characteristic of a tree is absence of loops, children never point back to parents. What data structure would that be instead?

   A graph.

10. Which of these structures are trees and why?

    No, cycle A→A No, cycle B→C→E→D→B Yes No, more than one root No, undirected cycle 1-2-4-3

11. What's a leaf in a tree?

    Node that doesn't have any children.

12. What's a heap?

    Any tree, where child <= parent.