Data Structures

Question 1

What is a data structure?

Answer 1

A conceptual way of arranging data

Question 2

What is the difference between a static and dynamic data structure?

Answer 2

Static:
- Stored contiguously in memory as a series of sequential memory locations
- Size is fixed in compilation

Dynamic:
- Change in size during run time
- Store pointers as well as data to point between to next memory location
- Data dynamically allocated from the heap

Question 3

What is overflow in static data structures?

Answer 3

Attempting to store more data than is available with set memory locations.

Question 4

What data structures are static and which are dynamic?

Answer 4

Static:
- Arrays
- Some stacks
- Some queues
- Graphs which use adjacency matrix

Dynamic:
- Some stacks
- Some queues
- Graphs which use an adjacency list
- Lists

Question 5

What is an array?

Answer 5

A finite, indexed set of related elements of the same data type.

Question 6

What is a stack?

Answer 6

An abstract data structure which operates on a FILO (first-in-last-out) basis

Question 7

What components are there in a stack?

Answer 7

Stack array / list - stores the items in the stack
Stack pointer - indicates the top of the stack

Question 8

What are the key operations we can perform on a stack?

Answer 8

1) Push (add item to top of stack)
2) Pop (remove item from top of stack)
3) Peek (return the value at the top of the stack)
4) Checking if a stack is empty
5) Checking if a stack is full

Question 9

How can you check if a stack is empty?

Answer 9

You can check if the index of the stack pointer is at -1 (initial value).
~~~
private bool IsEmpty() {
return stackPointer == -1;
}
~~~

Question 10

How to check if a stack is full?

Answer 10

Check if the index of the stack pointer is at the max size of the stack - 1;
~~~
private bool IsFull() {
return stackPointer == stack.Length - 1;
}
~~~

Question 11

How to push an item onto the stack?

Answer 11

1) Check if the array storing the stack is full. If it is, raise an error / exception.
2) If not full, increment the stack pointer by 1.
3) Store the item at the new memory that the stack pointer points to.
~~~
public int[] Push(int x) {
if (!IsFull()) {
stackPointer++;
stack[stackPointer] = x;
return stack;
} else {
System.Console.WriteLine(“The Stack is full.”);
return stack;
}
}
~~~

Question 12

How to pop an item off the stack?

Answer 12

1) Check if the array storing stack is empty. If empty, raise an error or throw an exception
2) If not, decrement the stack pointer by 1.
3) Return the value of the item at index stack pointer + 1.
~~~
public void Pop() {
if (!IsEmpty()) {
stackPointer–;
System.Console.WriteLine(stack[stackPointer + 1] + “ has been popped from the stack.”);
} else {
System.Console.WriteLine(“The list is empty! Cannot pop!”);
}
}
~~~

Question 13

How to peek an item in a stack?

Answer 13

1) Check if array storing stack is empty. If it is, raise an error
2) Return value of item at index of stack pointer.
~~~
public int? Peek() {
if (!IsEmpty()) {
System.Console.WriteLine(“Your number is “ + stack[stackPointer]);
return stack[stackPointer];
} else {
System.Console.WriteLine(“Stack is empty! Nothing to peek!”);
return null;
}
}
~~~

Question 14

What is a multi-dimensional array?

Answer 14

an n-dimensional array is a set of elements of the same data type with each element being of type array with n-1 dimension

Question 15

What is an abstract data stucture?

Answer 15

An unimplemented data structure which makes use of other data structures to form a new way of storing data. (e.g. stacks using arrays)

Question 16

Key differences between static and dynamic data structures

Answer 16

Question 17

What is a queue?

Answer 17

An abstract data structure that operates on a FIFO (first-in-first-out) basis.

Question 18

What are the types of queues?

Answer 18

1) Linear Queues
2) Circular Queues
3) Priority Queues

Question 19

What are the elements of a linear queue?

Answer 19

• Array or list for the items
• Front and rear pointer (for start and end of the queue)

Question 20

What are the key operations of a linear queue?

Answer 20

1) Check if the array for the queue is empty
2) Check if the array for the queue is full
3) Enqueue (add) an item to the end of the queue
4) Dequeue (remove) an item from the start of the queue

Question 21

How do you check if a LINEAR queue’s array is empty?

Answer 21

Check if the value of rear pointer is less than the value of the front pointer
~~~
public bool IsEmpty() {
if (rearPointer < frontPointer) {
return true;
else {
return false;
}
}
~~~

Question 22

How to check if a queue is full?

Answer 22

Check if the index of the rear pointer is at the max size - 1.
~~~
public bool IsFull() {
if (rearPointer == maxSize - 1) {
return true;
else {
return false;
}
}
~~~

Question 23

What are the advantages and disadvantages of linear queues?

Answer 23

Advantages:
- Simple to program

Disadvantages:
- Can lead to wasted capacity due as memory is stored statically (static)
- Process of shuffling is inefficient

Question 24

What is a circular queue?

Answer 24

A type of queue that allows the front and rear pointer over the ends of the queue. This makes it a more efficient structure.

Question 25

What mathematical operation do we use in implementation of a circular queue for indexing?

Answer 25

Modulo function e.g. with enqueue
~~~
public void Enqueue(T toAdd) {
if (!isFull()) {
rearPointer = (rearPointer ++) % maxSize;
items[rearPointer] = toAdd;
queueSize++;
} else {
System.Console.WriteLine(“The queue is full!”);
}
}
~~~

Question 26

What is a priority queue?

Answer 26

A queue that has each item assigned with a priority with items with the highest priority being dequeued before low priority happen.

Within a given priority, items are dequeued in a first-in-first-out basis.

Question 27

What are the uses for queues and stacks?

Answer 27