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 (dynamic)?

• 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

What is the purpose of the pointers in a queue?

Answer 7

• 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 enqueued

Question 8

How many pointers are used in a stack?

Answer 8

1 - Top

Question 9

What pointer is impacted when you enqueue an item in a queue

Answer 9

Rear/Tail - Incremented by one

Question 10

What pointer is impacted when you dequeue an item from a queue?

Answer 10

Front/Head - incremented by one

Question 11

Which data structure operates on a FIFO basis?

Answer 11

Queue

First in first out

Question 12

Which data structure operates on a LIFO basis?

Answer 12

Stack

Last in first out

Question 13

Where might a queue be used?

Answer 13

• Printer Queue
• Keyboard Buffer
• Breadth-first Traversal

Question 14

Where might a stack be used?

Answer 14

• Web Browser History
• Undo button in a word processor
• Depth-first Traversal

Question 15

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

Answer 15

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

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

Question 16

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

Answer 16

Overflow Error

Question 17

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

Answer 17

Underflow Error

Question 18

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

Answer 18

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

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

Question 19

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

Answer 19

• 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 20

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

Answer 20

• 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 21

How does a hash table function? What is the benefits of using one?

Answer 21

A data structure which allows direct access to a record, and takes the same time to search no matter how big it gets (Big-O - Constant)

• Item is hashed using a hash function. This function produces an index.
• The hash result points to a bucket in the hash table
• If a collision (synonym) occurs, then it is stored in the next available bucket.

Question 22

What is linear probing?

Answer 22

• 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 23

What keywords can be used to describe a Binary Search Tree (BST)?

Answer 23

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

Question 24

How is data found when searching a Binary Search Tree (BST)?

Answer 24

• 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 25

Why can a **Binary Search Tree (BST)** be searched quicker than an **array**?

Answer 25

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

Question 26

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

Answer 26

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

Question 27

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

Answer 27

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

Question 28

What types of edges can be used in a **graph**?

Answer 28

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

Question 29

How do you differentiate between a **tree and a graph**?

Answer 29

* Trees cannot have **cycles** - graphs can have cycles * Trees have a **root** node - graphs do not have a root node * 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 30

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

Answer 30

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

Question 31

What are the keywords and facts to describe a **multi-branch tree** (aka 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