(2) Fundamentals of Data Structures

Question 1

What is data structures?

Answer 1

Containers that store and organise data in a specific way

Question 2

What does the following operations do in a stack data structure PUSH, POP, IsEmpty?, IsFull?, Peek

Answer 2

Push - Adds a value in the stack
Pop - Removed a value in the stack
Peek - Checks what’s at the top of the stack
IsEmpty? - Checks if the whole stack is empty
IsFull? - Checks if the whole stack is full

Question 3

What is a static data structure with an example?

Answer 3

Static data structures have storage size determined before program is run. Has fixed maximum size

Eg an array

Question 4

What is dynamic data structure with an example?

Answer 4

Dynamic data structures can grow/shrink during execution

Eg a list

Question 5

What is the advantages and disadvantages of static data structures?

Answer 5

+Easy to program
+An array allows random access
+Easy to check for overflows

• The programmer has to estimate the maximum amount of space that is going to be added
• Can waste a lot of space

Question 6

What is the advantages and disadvantages of dynamic data structures?

Answer 6

+Only uses the space needed at any time
+Makes efficient use of memory

• Difficult to program
• Can be slow to add searches

Question 7

What is abstract data type?

Answer 7

Data types which are not defined by their implementation

Question 8

Describe a stack data structure and where is it used?

Answer 8

• Uses Last In First Out (LIFO) to determine when data is executed
• Uses one pointer at the top of the stack

Used anywhere you need to back track

Question 9

Describe a queue data structure and where is it used?

Answer 9

• Uses a First In First Out rule (FIFO) to determine when data is executed
• Uses two pointers, one for the front and back of the queue

Eg print jobs waiting to be printed

Question 10

What is a graph data structure?

Answer 10

A set of vertices connected by edges. The edges may be one or two way

Question 11

What is a linear queue?

Question 12

What is a circular queue?

Question 13

What is a priority queue and where can it be used?

Answer 13

Works the same way as a regular queue however they are ranked by their priority. The highest priority items are at the front of the queue and lowest priority at the back of the queue.

Eg a hospital

Question 14

What is a front and rear pointer?

Answer 14

Indicates what’s the first and last element of the queue

Question 15

What is the typical uses of a graph data structure?

Answer 15

Internet (Vertices: Web pages, Edges: Hyperlinks)
Social networks (Vertices: People, Edges: Friendships)
Transportation (Vertices: Airports, Edges: Air routes)

Question 16

What two elements make up a graph?

Answer 16

Vertices and edges

Question 17

What are neighbours in the graph data structure?

Answer 17

Two vertices directly connected

Question 18

What are degrees in the graph data structures?

Answer 18

The number of neighbours connected to a vertex

Question 19

What is a weighted/ labelled graph?

Answer 19

Graphs where the edges are labelled

Question 20

What is directed graph/ Digraph?

Answer 20

A diagram consisting of vertices (circles), joined by directed lines called edges

Question 21

What is a vertex/ node in graphs?

Question 22

What is a edge/ arc in graphs?

Question 23

What is an undirected graph?

Question 24

What are the two ways of representing a graph so that it can be processed by a computer?

Answer 24

Adjacency Matrix

Adjacency List

Question 25

What is a adjacency matrix and the advantages and disadvantages?

Answer 25

Representing a graph using a two dimensional matrix

Question 26

What is a adjacency list and the advantages and disadvantages?

Answer 26

A list used to store which vertices are next to each other