Intro to DSA

Question 1

what is a data structure?

Answer 1

a way of organizing, storing, and performing operations on data

Question 2

record

Answer 2

ds that stores subitems. called fields, with a name associated with each subitem (typically found in databases)

Question 3

array

Answer 3

ds stores an ordered list of items and is accessible by a positional index

Question 4

linked list

Answer 4

• ds stores an ordered list of items in nodes
• each node stores data and has a pointer to next node

Question 5

binary tree

Answer 5

ds where each node stores data and has up to two children (left and right child)

Question 6

hash table

Answer 6

ds stores unordered items by mapping (or hashing) each item to a location in an array

Question 7

max-heap

Answer 7

tree maintains simple property that node’s key is greater than or equal to node’s childrens’ keys

Question 8

min-heap

Answer 8

tree maintains simple property that node’s key is less than or equal to node’s childrens’ keys

Question 9

graph

Answer 9

ds for representing connections among items, and has vertices connected by edges

Question 10

vertex in graph ds

Answer 10

represents an item in a graph

Question 11

edge in graph ds

Answer 11

represents a connection between two vertices in a graph

Question 12

algorithm

Answer 12

set of commands that must be followed for computer to perform calculations or solving a problem

Question 13

characteristics of an algorithm

Answer 13

unambiguity, finiteness, well-defined inputs, well-defined outputs, effectiveness, feasibility, and language independence

Question 14

abstract data type (adt)

Answer 14

data type described by predefined user operations

Question 15

9 common ADTs

Answer 15

list, dynamic array, stack, queue, deque, bag, set, priority queue, dictionary (map)

Question 16

ADT: list

Answer 16

holds ordered data

ex. array, linked list

Question 17

ADT: dynamic array

Answer 17

holds ordered data and allows indexed access

ex. array

Question 18

ADT: stack

Answer 18

items only inserted on or removed from top of stack

ex. linked list

Question 19

ADT: dictionary (map)

Answer 19

associates or maps keys with values

ex. hash table, binary search tree

Question 20

ADT: queue

Answer 20

items inserted at end of queue and removed from front of queue

ex. linked list

Question 20

ADT: priority queue

Answer 20

each item has a priority and items with higher priority are closer to front of queue than items with lower priority

ex. heap

Question 20

ADT: deque (pronounced “deck”)

Answer 20

items can be inserted and removed at both front and back

ex. linked list

Question 21

ADT: bag

Answer 21

stores items and order does no matter and duplicate items are allowed

ex. array, linked list

Question 22

ADT: set

Answer 22

for collection of distinct items

ex. binary search tree, hash table

Question 22

huffman coding

Answer 22

common compression technique that assigns fewer bits to frequent items, using a binary tree