Data structures

Question 1

Abstract Data Type (ADT)

Answer 1

An interface for interacting with data

Question 2

ADT Examples

Answer 2

Lists, stacks, sets, queues, maps, trees

Question 3

Data Structure

Answer 3

Implementation of ADT

Question 4

Data Structure Examples

Answer 4

Array, Linked List, Stack, Queue, Binary Tree, BST, Heap, Hash Table

Question 5

Hash Function

Answer 5

maps an object (of some type) to an integer

Question 6

Hash Map Drawbacks

Answer 6

Requires a lot of extra memory and hash function must avoid collisions

Question 7

Root

Answer 7

Top node in a tree

Question 8

Siblings

Answer 8

Nodes with the same parents

Question 9

Descendant

Answer 9

Node reachable by repeated proceeding from parent to child

Question 10

Ancestor

Answer 10

Node reachable by repeaded proceeding from child to parent

Question 11

Leaf

Answer 11

A node with no children

Question 12

Edge

Answer 12

Connection between one node to another

Question 13

Path

Answer 13

Sequence of nodes and edges connecting a node with a descendant

Question 14

Level

Answer 14

The level of a node is defined by 1 + the number of connections between the node and the root

Question 15

Height

Answer 15

The height of a node is the number of edges on the longest downward path between the root and the leaf

Question 16

BST

Answer 16

node-based data structure in which each node has no more than two child nodes. Each child must either be a leaf node or the root of another binary search tree. The left sub-tree contains only nodes with keys less than the parent node; the right sub-tree contains only nodes with keys greater than the parent node.