Revision notes

What is the best definition of a collision in a hash table?

Two entries with different keys have the same hash value.

Which one of the following definitions describes a hierarchical data structure?

A data structure where each node has a unique predecessor and many successors

Which statement describes the meaning of O(n)?

An algorithm operates in linear time

If you know the index of an element stored in an array of N unsorted elements. What is the order of complexity of an algorithm to retrieve the element?

O(1)

A queue consisting of n elements is implemented using a 1D array with the position of the head fixed. What is the time complexity (Big-O) of removing the next element from the queue (dequeue)?

O(n)

what stack operation could result in a stack underflow?

pop

Given the following recursive algorithm: example (int n) if (n > 0) then example(n / 2); example(n / 2); end if; Output ("#"); end; How many hashes (#) are printed by the method call example(5)? (Note: Integer division is used throughout this method.)

15

Test (int Number) Output Number; if Number > 0 then Test(Number-2); end if; Output Number; end; What is printed by the call Test(4)?

4 2 0 0 2 4

cheers (int times) Output ("Hip"); if (times > 0) then cheers(times - 1); Output ("Hooray"); end if; end cheers; What is printed by the call cheers(2)?

Hip Hip Hip Horray Hooray

What is the effect of the statement: p = p. link on a singly linked list consisting of one node referenced by p?

The statement is valid. After execution of the statement, P will be assigned the value null.

To easily remove a node that is not the head of a SLL conveniently, you need to have a reference to...

the node that precedes it

What is the best definition of a collision in a hash table?

Two entries with different keys have the same hash value.

A binary tree is a binary search tree if...

Every left child has a key less than the parent and every right child has a key greater or equal to the parent.

What is the least number of leaf nodes in a binary tree of height 4?

1

What is a leaf node?

an end child node

Which formula gives the maximum number of nodes in a binary tree of height h?

2^h-1

Which data structure is used in a determining a Depth First Traversal of a graph?

Stack

convert the postfix expression A B C - / D E * + to prefix

+ / A - B C * D E

what is the value of prefix expression: * + 2 5 - / 8 2 2

+14

Given the infix expression: 2 ^ 3 + 5 * 2 ^ 2 - 8 / 6 Which operator is stored in the root node of the corresponding parse tree?

- (subtract)

What is the method for creating a parse tree?

find the final operator to be executed this is the root. the 2 child nodes are the 2 halves of the expression. Read the expression from right to left the operands are written first

how can you identify the rot node from a preorder traversal output?

The first value is the rot node with preorder traversal

Which data structure is used in a determining a Depth First Traversal of a graph?

Stack