Data Structures

Question 1

What is an Array

Answer 1

An array is an ordered, finite set of elements of a single type

Question 2

What Type of Array is a Linear Array

Answer 2

A one-dimensional array

Question 3

How can you visualise a two-dimensional array

Answer 3

A 2D array can be visualised as a table/spreadsheet and when searching this type of array, first go down the rows and then across the columns

Question 4

How can you visualise a three-dimensional array

Answer 4

A 3D array can be visualised as a multi-page spreadsheet

An element in a 3D array uses: threeDimensionalArray[z,y,x]

z = array number, y = row number, x = column number

Question 5

What is a Record

Answer 5

• A row in a file and is made up of fields
• Records are used in databases
• Each field in a record can be identified using the syntax

Question 6

What is a List

Answer 6

A data structure consisting of a number of ordered items where the items can occur more than once

Question 7

Describe the List Operations

Answer 7

Question 8

What is a Tuple

Answer 8

An immutable (cannot be changed) ordered set of values of any type

Question 9

How is a tuple initalised

Answer 9

Initialised with regular brackets rather than square brackets

Question 10

What is a Static and Dynamic Data Structure

Answer 10

Static - fixed size

Dynamic - can keep growing

Question 11

What is a Linked List

Answer 11

A linked list is a dynamic data structure used to hold an ordered sequence

Question 12

How is a Linked List Organised

Answer 12

• The items in a linked list are not necessarily in contiguous data locations (the order they occur in the sequence)
• Each item in the list is called a node and contains a data field and a next address field called a point field
• The data field holds the actual data of the next list item and the pointer field holds the address of the next item
• Also the list has a pointer variable showing the first node in the list

Question 13

What are the Disadvantages of using a Linked List

Answer 13

• They waste memory, storing pointers mean more memory is required compared to an array
• As items in linked lists are stored in a sequence, they can only be traversed in this order; an item cannot be directly accessed, as is possible in an array

Question 14

Describe the three different types of Graphs

Answer 14

• Directed Graph - The edges can only be traversed in one direction
• Undirected Graph - The edges can be traversed in both directions
• Weighted Graph - A cost is attached to each edge.

Question 15

Describe an example of an Adjacenecy Matrix

Answer 15

Question 16

What are the Advantages and Disadvantages of the adjacency matrix

Answer 16

• Convenient to work with due to quicker access times
• Easy to add nodes
• Most graphs leave most of the cells empty meaning the larger the graph the more memory space will be wasted

Question 17

Describe an example of an Adjacenecy List

Answer 17

Question 18

What is the Advantage of an Adjacenecy Lists

Answer 18

More space efficient for large, sparse networks

Question 19

What are the two ways of traversing a graph

Answer 19

Depth-first - you go as far down one route as you can before backtracking and taking the new route

Breadth-first - you visit all the neighbours of the first node and then all the neighbours of the second node and so on

Question 20

Describe some uses of graphs

Answer 20

• Computer networks
• Roads between towns
• Tasks in a projects
• Web pages and links

Question 21

What is a Stack

Answer 21

A data structure that operates on a first in last out basis

Question 22

What is a Queue

Answer 22

A data structure that acts on a first in first out bias

Question 23

Describe the Stack Operations and Names

Answer 23

Question 24

Describe the Queue Operations and Names

Answer 24

Question 25

Describe the pseudocode for a stack isEmpty

Answer 25

if(top == -1) return true else return false end if end function

Question 26

Describe the pseudocode for a stack isFull

Answer 26

if top = maxSize then return True else return False end if end function

Question 27

Describe the pseudocode for a stack push

Answer 27

If isFull() then Print "The stack is full” Else top = top + 1 arrStack[top]=newValue End if End function

Question 28

Describe the pseudocode for a stack pop

Answer 28

if isEmpty() then Print "The stack is empty" else item = arrStack[top] top = top -1 Return item End if End function

Question 29

Describe the pseudocode for a stack peek

Answer 29

if isEmpty() Print “Stack is empty” Else return arrStack[top] endif end function

Question 30

Describe the pseudocode for a Queue Enqueue

Answer 30

if(isFull() then Print "The queue is full" Else rear = (rear+1) % maxSize arrQueue[rear] = newValue size = size + 1 Endif End function

Question 31

Describe the pseudocode for a Queue Dequeue

Answer 31

int item if(isEmpty()) then Print "The queue is empty" Else item = arrQueue[front] front = (front+1) % maxSize size = size -1 Endif End function

Question 32

What are the Applications of Stacks and Queues

Answer 32

Stacks - Stacks are used to reverse an action, such as to go back a page in web browsers and in ‘undo’ buttons Queues - print tasks are stored on a print queue while waiting to be printed. When a set of tasks are waiting to be executed, a priority queue will be used to ensure that they are executed in the appropriate order

Question 33

What is a Tree

Answer 33

A connected form of a graph

Question 34

Describe the components of a Tree

Answer 34

* Node - an item in the tree * Edge - connects two nodes together and is also known as a branch, or arc * Root - a single node which does not have any incoming nodes * Child - a node with incoming edges * Parent - a node with outgoing edges * Subtree - subsection of a tree consisting of a parent and all the children of a parent * Leaf - a node with no children

Question 35

What are the Similarities and Differences between a Tree and a Graph Data Structure

Answer 35

Similarites * Both have nodes and edges * Both are non-linear data structures * Both are dynamic data structures Differences * A Tree is 1 directional whereas Graph is 2 directional * A Tree does not have cycles, a Graph does * A Tree will not be weighted whereas a Graphs edges can be weighted

Question 36

What are the three ways of traversing a binary tree

Answer 36

* Pre-order * In-order * Post-order

Question 37

How do you execute the three traverses and what do they tell you

Answer 37

* Pre-Order - order you pass the nodes on the left * In-Order - order you pass the nodes underneath * Post-Order - order you pass the nodes on the right * Pre-Order - gives the exact replication copy of the tree (allows duplication of tree) * In-Order - gives you the nodes in ascending order * Post-Order - gives you the the tree in a form that can be turned into any low level code

Question 38

What is a Hash Table

Answer 38

An array which is coupled with a hash function

Question 39

What is the main problem with a Hash Table

Answer 39

Collions may occur meaning the item has to be placed in the next available location

Question 40

What is the Appilcation of a Hash Table

Answer 40

Commonly used for indexing, as they provide fast access to data due to keys having a unique, one-to-one relationship with the address at which they are stored