Week 3 + 4 + 5

Question 1

Define stack.

Answer 1

Container with insertion and removal based on LIFO (Last-In-First-Out).

Question 2

Define push, pop, top with stack.

Answer 2

push, inserts onto top of stack
pop, removes off of top of stack
top is last item pushed.

Question 3

How is stack implemented using array?

Answer 3

Top of stack is number of elements in stack - 1. pop reduces top by 1 push adds element to top + 1 space and increments top. top = -1 for empty stack.

Question 4

How is stack implemented using linked list?

Answer 4

Top of stack is set to first node. pop is removeFirst. push is addFirst. top points to null for empty stack.

Question 5

Explain String Builder syntax. Why use string builder?

Answer 5

StringBuilder sb = new StringBuilder();
sb.append(“String”);

+ all other normal string functions.

String builder is mutable so a new String is not created after every modification unlike with normal Strings.

Question 6

Define queue.

Answer 6

Container with insertion at back and removal from front. Based on FIFO (First-In-First-Out) data structure.

Question 7

Define enqueue, dequeue and front for queue.

Answer 7

Enqueue inserts at rear of queue
Dequeue removes the element at the front of the queue.
Front returns the front of the queue.

Question 8

How is queue implemented using array.

Answer 8

Front variable keeps track of front of queue, rear location is always empty. Enqueue grows the rear and dequeuing grows the front variable. Elements crawl to right in array as we modify the queue. We use circular arrays so when we reach the end of the array the elements circle back to the start.

Implementing Circular Array:
For enqueue: Insertion position set to (front + size) % CAPACITY
For dequeue: Front set to (front + 1) % CAPACITY.

Question 9

How is queue implemented using linked list?

Answer 9

Doubly Linked List used. Enqueue, performs addLast, Dequeue performs removeFirst.

Question 10

Define deque.

Answer 10

A queue where we can insert and delete from both the front and the end.

Question 11

Define a tree.

Answer 11

A tree consists of nodes, where each node (except the first) has a parent and all nodes have zero or more children.

Question 12

Define root.

Answer 12

First node which has no parent.

Question 13

Define internal node.

Answer 13

A node with at least one child.

Question 14

Define external node.

Answer 14

A node without children.

Question 15

Define subtree.

Answer 15

Tree within a tree consisting of a node and its descendants.

Question 16

Define depth of node.

Answer 16

Number of ancestors of p other than p itself.

Question 17

Define height of tree.

Answer 17

Maximum depth of any node. The height of its root node.

Question 18

What is the ordering in a tree?

Answer 18

Siblings are arranged left to right, from lowest to greatest.

Question 19

Define binary tree.

Answer 19

A tree consisting of a single node or a tree whose root has an ordered pair of children each of which is a binary tree.

Question 20

Define height of a node.

Answer 20

Number of edges on longest path from the node to a leaf which has a height of 0. Defined recursively. H (Node) = 1 + Height (child node). Where H (leaf) = 0

Question 21

Define proper or full binary tree.

Answer 21

A binary tree where each node has either zero or two children.

Question 22

T or F. In a binary tree at level/depth d there is at most 2^d nodes.

Answer 22

True

Question 23

In a non-empty binary tree what is the minimum and maximum number of nodes n.

Answer 23

h + 1 <= n <= 2^(h + 1) - 1

Question 24

In a non-empty binary tree what is the minimum and maximum number of external nodes.

Answer 24

1 <= ne <= 2^h

Question 25

In a non-empty binary tree what is the minimum and maximum number of internal nodes.

Answer 25

h <= ni <= 2^h - 1

Question 26

In a non-empty binary tree what is the minimum and maximum height in terms of the nodes.

Answer 26

log(n + 1) - 1 <= h <= n - 1

Question 27

In a non-empty PROPER binary tree, what is the number of external nodes.

Answer 27

ne = ni + 1

Question 28

Explain inorder traversal.

Answer 28

Left subtree -> Node -> Right subtree

Question 29

Explain preorder traversal.

Answer 29

Node -> Left subtree -> Right subtree. Moves top to bottom.

Question 30

Explain postorder traversal.

Answer 30

Left subtree -> Right subtree -> Node. Moves bottom to top.

Question 31

Explain breadth-first traversal.

Answer 31

Pushes all nodes at a particular depth onto stack and visits them first before moving down to next level. Moves top to bottom.

Question 32

What is the Catalan number?

Answer 32

The number of full binary trees with n + 1 leaves. Cn = 1 / n+1 (2n C n)

Question 33

What is the expected height for a random binary tree of size n = 30.

Answer 33

3.3 log (30) = 11

Question 34

Distinguish between iterable and iterator.

Answer 34

Iterable: Represents a collection that can be iterated over using a for-each loop. When implementing an Iterable, we need to override the iterator() method. Doesn't store the iteration state. Removing elements during the iteration isn't allowed. Iterator: Represents an interface that can be used to iterate over a collection. When implementing an Iterator, we need to override the hasNext() and next() methods. Stores the iteration state Removing elements during the iteration is allowed.

Question 35

Distinguish between the lazy and snapshot implementation of iterator.

Answer 35

Snapshot: Maintains its own private snapshot of element sequence Constructed when iterator object is created Unaffected by subsequent changes to original Lazy: Does not make an upfront copy. Piecewise traversal of original. Affected by subsequent changes to original.

Question 36

What is the definition of the stack ADT?

Answer 36

Stack is a container with insertion and removal based on LIFO (Last-In-First-Out). We can only insert, remove and get at the top of the stack. ADT functions: size() isEmpty() push(e) pop() top()

Question 37

Give two uses of stack.

Answer 37

Web page history in a web browser Undo sequence in a text editor

Question 38

What is the definition of the queue ADT?

Answer 38

Queue is a container with insertion and removal based on FIFO (First-In-First-Out). We can only insert at the rear and get/remove from the front of the queue. ADT functions: size() isEmpty() enqueue(e) dequeue() front()

Question 39

Give two uses of queue.

Answer 39

Waiting lists Access to shared resources

Question 40

What is the definition of the Deque ADT?

Answer 40

A deque is a collection of objects of the same type that is a mixture between a queue and a stack. Supports element insertion and removal at both ends. ADT Functions: size() isEmpty() first() last() addFirst() addLast() removeFirst() removeLast()

Question 41

What is the time complexity of all deque operations with doubly linked list implementation?

Answer 41

All operations O(1) time.

Question 42

What is the time complexity of all queue operations with linked list and array implementation?

Answer 42

Both: All operations O(1) time.

Question 43

What is the time complexity of linked based and array stacks?

Answer 43

Both: All operations O(1) time.

Question 44

What is the worst case running time of the depth function of binary tree?

Answer 44

O(n) is all nodes form a single branch we have a depth of n - 1.

Question 45

What is the definition of the Position ADT?

Answer 45

Position is the abstraction of a node of a tree. An element is stored at each position, and each one satisfies the parent child relationships within a given tree structure. ADT functions getElement() setElement(E e)

Question 46

What is the definition of the Tree ADT? (HINT: 4 accessor, 3 query, 4 general)

Answer 46

A tree consists of nodes, where each node (except the first) has a parent and all nodes have zero or more children. ADT Functions: Accessor: root() parent(p) children(p) numChildren(p) Query: isInternal(p) isExternal(p) isRoot(p) General: size() isEmpty() iterator() positions()

Question 47

Define the binary tree ADT?

Answer 47

A tree consisting of a single node or a tree whose root has an ordered pair of children each of which is a binary tree. So for all nodes z, the left child of z should be less than the right child of z. ADT Functions: left(p) right(p) sibling(p)

Question 48

In a proper binary tree what is the minimum and maximum number of internal nodes and hence, what is the same for external and total.

Answer 48

h <= ni <= 2^h - 1 (same as non-proper) h + 1 <= ne <= 2^h 2h + 1 <= n <= 2^(h + 1) - 1

Question 49

In a proper binary tree, what is the minimum and maximum height? If we have n the number of nodes in the tree how many ni and ne are there?

Answer 49

log(n + 1) - 1 <= h <= (n - 1) / 2 ni = n - 1 / 2 ne = n + 1 / 2

Question 50

Define a binary search tree.

Answer 50

A binary tree where for a given node x, all the values in the left subtree of x is less than x and all the values in the right subtree of x is greater than x.

Question 51

Explain the algorithm for constructing a binary tree from a given inorder and preorder traversal.

Answer 51

Let i be index of inorder[], let j be index of preorder[]. BUILD TREE() Create node with element preorder[j] j++ Set i to element index in inorder. call build tree with elements before i as left subtree of node. call build tree with elements after i as right subtree of node. return node.

Question 52

Explain breadth first traversal algorithm.

Answer 52

Starting at level 0 but levels in array from left to right. Add root to queue Then loop removing first element of queue (adding to result array) and adding all its children at the back starting with the leftmost child. When queue is empty return result array.

Question 52

Explain how a random binary tree is created.

Answer 52

Recursive function that receives random numbers in order. Randomly picks root makes it a node, and makes left subtree with recursive call with all to the left of the index chosen and makes right subtree with recursive call with all to the right of the index chosen.

Question 53

Describe in detail how a queue can be represented using a circular array.

Answer 53

We have two pointers front and rear which point to positions in the array. The front pointer always points to the top of the queue (next element to be removed), the rear always point to a blank space, the next available spot for insertion in the queue. front pointer starts at 0 and is incremented when we remove an item. Rear pointer starts at 0 and is incremented every time we add an item. When either pointer reaches end of array, the pointers can loop around back to the beginning of the array. The array is full when abs(rear - front) = capacity. The rear pointer will be level with the front pointer when the queue is empty.

Question 54

Pseudocode for enqueue and dequeue for queue implemented using a circular array.

Answer 54

enqueue: array[rear] = element rear ++; (mod size) dequeue value = array[front] array[front] = null front ++; (mode size) return value;