Part 3

Question 1

Stacks and queues are examples of ________ adts

Answer 1

Linear

Question 2

Trees are ____________ ADTs

Answer 2

Non-linear / Recursive

Question 3

The child of a tree has the type

Answer 3

Tree

Question 4

A tree with no children is called

Answer 4

A leaf

Question 5

What word is used to refer to positions in a tree?

Answer 5

Node

Question 6

The root node of a tree is a node with no _____

Answer 6

parent

Question 7

What makes a tree a binary tree?

Answer 7

Each node will have no more than 2 children

Question 8

What are the primitive operations of binary trees, and their semantics?

Answer 8

createtree - creates a new empty tree

maketree - takes data item, two trees and creates a new tree with the data item in the root and two trees as children

isempty - deduce whether the tree is empty

leftchild/rightchild - return references to the children

value - return the data item at the root (node)

Question 9

What are the three orders of tree traversal?

Answer 9

pre-order

post-order

in-order

Question 10

what is pre-order traversal?

Answer 10

visit root, then left child in pre-order, then right child in pre-order

Question 11

what is post-order traversal?

Answer 11

visit the left child in post-order, then the right child in post-order, then the root

Question 12

what is in-order traversal?

Answer 12

visit he left child in-order, then the root, then the right child in-order

Question 13

What is binary chop?

Answer 13

Look at middle of array, if its greater than the number searching for, look at middle of left half, else middle of right half & repeat till you find the number

Question 14

What is a binary search tree?

Answer 14

A binary tree where all the left children are less than the root and all the right children are greater

Question 15

How are non-binary trees typically implemented?

Answer 15

Left child right sibling

Question 16

What is the left-child-right-sibling representation?

Answer 16

Each node may has one child

More than one child = the children are stored as references from the first child

A

/

B - C - D

/

E

Question 17

When deleting a node in a binary search tree, if the node has one child, what is the procedure?

Answer 17

Replace the reference from the parent to the node with a reference to the node’s child

Question 18

When deleting a node in a binary search tree, if the node has two children, what is the procedure?

Answer 18

Replace the reference to the node with a reference to either largest value in left child or smallest value in right child

Question 19

The time taken for insertion, deletion and searching binary search trees are approximately ________

Answer 19

proportional to the depth of the tree

Question 20

What is the average depth of a binary search tree if the items are inserted in a random order?

Answer 20

2.5log₂n

Question 21

What are the average and best times for insertion deletion and searching (big O)?

Answer 21

Average: O(logn)

Worst: O(n)

Question 22

When writing a generic class how can it be restricted so the Type must extend comparable?

Answer 22

public class BST<t>&gt;</t>