1.4.2 Data Structures

Question 1

Which of the following data structures are ordered?

• List
• Record
• Tuple
• Array

Answer 1

List
Array
Tuple

Question 2

Which of the following data structures can store multiple data types?

• List
• Record
• Tuple
• Array

Answer 2

List
Record
Tuple

Question 3

Which of the following data structures are immutable (read-only)?

• List
• Record
• Tuple
• Array

Answer 3

Tuple

Contents cannot be modified at run-time

Question 4

Which of the following data structures have no predefined scope?

• List
• Record
• Tuple
• Array

Answer 4

List

Question 5

Which of the following data structures can store multiple values under one identifier?

• List
• Record
• Tuple
• Array

Answer 5

All of them

List
Record
Tuple
Array

Question 6

Which of the following data structures are accessed using an index?

• List
• Record
• Tuple
• Array

Answer 6

List
Tuple
Array

Question 7

Which of the following data structures can have multiple dimensions?

• List
• Record
• Tuple
• Array

Answer 7

Array

2D | 3D

Question 8

What is the purpose of the pointers in a queue?

Answer 8

• Front/Head - Used to identify the first item in the queue i.e the one to dequeue next
• Rear/Tail- Used to identify the next free space in the queue i.e. the next element to be dequeued

Question 9

How many pointers are used in a stack?

Answer 9

1 - Top

Question 10

What pointer is impacted when you enqueue an item

Answer 10

Rear/Tail - Incremented by one

Question 11

What pointer is impacted when you dequeue an item

Answer 11

Front/Head - incremented by one

Question 12

Which data structure operates on a FIFO basis?

Answer 12

Queue

First in first out

Question 13

Which data structure operates on a LIFO basis?

Answer 13

Stack

Last in first out

Question 14

Where might a queue be used?

Answer 14

Printer Queue

Keyboard Buffer

Question 15

Where might a stack be used?

Answer 15

Web Browser History

Undo button in a word processor

Question 16

What is the process for pushing an item to a stack?

Answer 16

• If stack is full then report error and stop.
• Else increment pointer
• Add data item at position ‘pointer’

Question 17

What type of error could occur if an item is added to a full stack or queue?

Answer 17

Overflow Error

Question 18

What type of error could occur if an item is removed from to an empty stack or queue?

Answer 18

Underflow Error

Question 19

What is the process for enqueuing an item to a queue?

Answer 19

• If queue is full then report error and stop.
• If not full then increment tail by 1
• Add item to tail index

Question 20

What is the process for dequeuing an item from a queue?

Answer 20

• Check if the queue is empty, If it is then output message reporting an error.
• If it is not empty, then output the element located at the head
• Increment head by 1

Question 21

What is the process for popping an item from a stack?

Answer 21

• If stack is empty then report error & stop.
• Else output the data at the top
• decrement the top pointer

The last two bullet points could happen in the opposite order depending on the stack implementation

Question 22

Which data structure allows direct access to a record, and takes the same time to search no matter how big it gets?

Answer 22

Hash Table

Question 23

What is linear probing?

Answer 23

• Used if a collision/synonym occurs (same hash value created as something that already exists)
• Linear probing could be used to move through the hash table one space at a time to find the next free space.

Question 24

What keywords can be used to describe a binary search tree?

Answer 24

• Ordered Data Structure
• Child Node
• Parent Node
• Root
• Branch
• Leaf Node
• Sub-Tree

Question 25

How is data found when searching a BST?

Answer 25

* Start at the root node * If a search item is less than a root node, then go left. * If a search item is greater than a root node, then go right * REPEAT until found or leaf node reached

Question 26

Why can a BST be searched quicker than an array?

Answer 26

* Each node does not need to be searched * List is split every time a direction is chosen (left if less, right if more)

Question 27

What is a linked list? What is it made up of?

Answer 27

* A dynamic data structure * Made up of nodes * Each node consists of data and pointer * Pointer gives location of next node.

Question 28

As it grows in size, why does it take longer to search a linked list?

Answer 28

Requires every node to be checked (following pointers) until the desired record is found or the end is reached.

Question 29

What types of edges can be used in a graph?

Answer 29

* Directed * Undirected * Weighted * Unweighted ## Footnote Edges in a directed graph only go in one direction. Undirected edges can go in both directions.

Question 30

How do you differentiate between a tree and a graph?

Answer 30

* Trees cannot have **cycles** - graphs can have cycles * Trees have a **root** node - graphs do not * Trees have a **hierarchy** - graphs have no hierarchy * Trees are always **undirected** - graphs can be directed * Trees are always **connected** - graphs can be connected or disconnected

Question 31

What are the keywords and facts to describe a multi-branch tree?

Answer 31

* A dynamic data structure * Consists of nodes that have sub nodes (children) * First node is called the root * Lines that join nodes are called branches (one directional) * Can have more than two child nodes

Question 32

How does a binary tree differ from a multi-branch tree?

Answer 32

* Binary Tree cannot have more than two child nodes per parent. * Binary Tree is ordered

Question 33

What keywords can be used to describe a multi-branch tree?

Answer 33

* Dynamic Data Structure * Child Node * Parent Node * Root * Branch * Leaf Node * Sub-Tree