Fundamentals of Data Structures

Question 1

What are the built in operations of a stack?

Answer 1

Push, Pop, Peek, Is Full, Is Empty

Question 2

What are the built in operations of a queue?

Answer 2

Peek, Enqueue, Dequeue, Is Full, Is Empty

Question 3

After extensive data changes a queue will become unusable. Explain why this is so.

Answer 3

Memory/queue will become full and space is not reusable.

Question 4

Explain the circumstances in which it would be more appropriate to use an adjacency list instead of an adjacency matrix.

Answer 4

• When the graph/matrix is sparse.
• When the edges are rarely changed.
• When the presence/absence of specific edges does not need to be tested (frequently).

Question 5

What is the definition of a Graph?

Answer 5

A collection of nodes and edges.

Question 6

What is the definition of a weighted graph?

Answer 6

A graph where each edge has a weight/value associated with it.

Question 7

What is the definition of a tree?

Answer 7

A graph that: is undirected, has no cycles/loops and is connected,

Question 8

A binary tree could be represented using one array of records or, alternatively, using three one-dimensional arrays.
Describe how the data stored in the array(s) could be structured for each of these two possible methods of representation.

Answer 8

For solution with 3 arrays:
One array stores data items
One array for left child pointers
One array for right child pointers
Pointers stored at same location in arrays as corresponding data item

For solution with 1 array of records:
Record created to store data item and pointers
One pointer to left child
One pointer to right child

For either of the above solutions:
Rogue value used to indicate no child
Root node stored at first location/start of array(s)

Question 9

What is the vector dot product of u and v?

Answer 9

(U.V) / (|U|.|V|) where |Vector| = Root [(X2 - X1)^2 + (Y2 - Y1)^2]