CSCI 211 Test 2

Question 1

a tree is a

Answer 1

non-linear structure in which elements are organized into a hierarchy; it is comprised of a set of nodes in which elements are stores and edges connect one node to another, and each node is located on a particular level

Question 2

a node can have ? parent(s)

Answer 2

only one

Question 3

a node with no children

Answer 3

leaf node

Question 4

not the root node or a leaf node

Answer 4

internal node

Question 5

a subtree is

Answer 5

a tree structure that makes up part of a larger tree

Question 6

one important criterion for classifying trees is

Answer 6

the number of children it can have

Question 7

defining trees (3 things)

Answer 7

1. Nodes connected by edges
2. Can be classified by max # children
3. Do not have cycles or “loops” - they are recursive structures

Question 8

binary tree

Answer 8

tree in which nodes have at most two children

Question 9

a tree is balanced if

Answer 9

all of the leaves of the tree are on the same level or within one level of each other

Question 10

a balanced n-ary tree with m elements will have a height of

Answer 10

log base n of m

Question 11

a tree is complete if

Answer 11

it is full, or full to the next-to-last level with all leaves af the bottom level on the left side of the tree

Question 12

all tree traversals start at the ? of the tree

Answer 12

root

Question 13

each node can be thought of as the ? of a subtree

Answer 13

root

Question 14

list the four classic types of tree traversals

Answer 14

1. Preorder
2. Inorder
3. Postorder
4. Level-order

Question 15

Preorder

Answer 15

Visit the root, then traverse the subtrees left to right

Question 16

Inorder

Answer 16

Traverse the left subtree, then visit the root, then traverse the right subtree

Question 17

Postorder

Answer 17

Traverse the subtrees from left to right, then visit the root

Question 18

Level-order

Answer 18

Visit each node at each level of the tree from top to bottom and left to right

Question 19

expression tree

Answer 19

a tree that shows the relationships among operators and operands in an expression; evaluated from the bottom up

Question 20

decision tree

Answer 20

a tree whose nodes represent decision points, and whose children represent the options available

Question 21

binary search trees

Answer 21

elements are organized to facilitate finding a particular element when needed - the left subtree of each node n contains elements less than the element stored in n and the right subtree of each node n contains elements greater than or equal to the element stored in n

Question 22

a LinkedList is more efficient than a BST for which operations?

Answer 22

removeFirst and first

Question 23

a right rotation on a BST

Answer 23

1. make the left child element of the root the new root element
2. make the former root element the right child element of the new root
3. make the right child of what was the left child of the former root the new left child of the former root

Question 24

a left rotation on a BST

Answer 24

1. make the right child element of the root the new root element
2. make the former root element the left child element of the new root
3. make the left child of what was the right child of the former root the new right child of the former root

Question 25

an AVL tree

Answer 25

ensures a BST stays balanced because for each node in the tree, there is a numeric balance factor (the diff between the heights of its subtrees)

Question 26

heap (technically a minheap)

Answer 26

a complete binary tree in which each element is less than or equal to both of its children

Question 27

is a heap a binary tree? a binary search tree?

Answer 27

yes; no

Question 28

adding a new element to a heap

Answer 28

1. add as leaf
2. move element upward toward root, exchanging positions with its parent, until the relationship among the elements is appropriate

Question 29

removing the min element of a heap

Answer 29

1. move the last leaf of the tree to be the new root of the tree
2. move it down the tree as needed until the relationships among the elements is appropriate

Question 30

priority queue

Answer 30

removes elements in priority order, independent of the order in which they were added; a heap is a classic mechanism for implementing

Question 31

we would rather implement heaps with ? than ?

Answer 31

arrays than links

Question 32

implementing heaps with arrays: a parent element at index n will have children stored at ? and ? of the array; conversely, for any node other than the root, the parent of the node is found at index ?

Answer 32

2n+1 and 2n+2; (n-1)/2

Question 33

heap sort

Answer 33

sorts a set of elements by adding each one to a heap, then removing them one at a time

Question 34

set

Answer 34

a collection with no duplicates; primary purpose is to determine whether an element is a member

Question 35

map

Answer 35

a collection that establishes a relationship between keys and values; the goal is to have an efficient way to obtain a value given its key

Question 36

keys of a map must be ?, but multiple keys could map to the same object

Answer 36

unique

Question 37

implementation of sets and maps using trees

Answer 37

all of the basic operations are performed with O(logn) efficiency

Question 38

an element in a hash table is stored in a location based on a ?

Answer 38

hash function

Question 39

a hash function makes some calculation based on the ?

Answer 39

element

Question 40

multiple elements may be stored in the same location of a hash table

Answer 40

“collision”

Question 41

a hash function that maps each element to a unique location is called a ?

Answer 41

perfect hashing function

Question 42

hash code

Answer 42

a short sequence of bits computed from the contents of a longer piece of data (desirable for diff data to produce diff hash codes)

Question 43

hash function

Answer 43

maps a data value (or its hash code) to an array index (use to decrease the number of possible indexes)

Question 44

each location in a hash table is called a

Answer 44

“cell” or “bucket”

Question 45

access time to a particular element in a hash table is ? of the number of elements stored

Answer 45

independent