Section 2 Data structures

Question 1

What is a stack frame

Answer 1

Stack frames are used to store information about running a program. This is used as a call stack when running programs as it can be used when a subroutine is running to call functions and pass parameters and arguments.

Question 2

What is a stack?

Answer 2

A data structure that follows the LIFO (Last In, First Out) principle.

Question 3

What are common stack operations?

Answer 3

push, pop, peek/top, isEmpty.

Question 4

Example of stack use?

Answer 4

Undo/redo in editors, function call management (call stack).

Question 5

How is a stack implemented?

Answer 5

Using arrays or linked lists.

Question 6

What is a queue?

Answer 6

A data structure that follows the FIFO (First In, First Out) principle.

Question 7

Common queue operations?

Answer 7

Enqueue, dequeue, isEmpty, peek/front.

Question 8

What is a linear queue?

Answer 8

It is a FIFO structure organised as a line of data such as a list. The max size of this type of queue is fixed in this case. can be dynamic though

Question 9

What is a circular queue?

Answer 9

A queue that wraps around to reuse empty slots when the end is reached.

Question 10

What is a priority queue?

Answer 10

A priority queue adds a further element to the queue which is the apriority of each item.

Question 11

Example of queue use?

Answer 11

Print spooling, task scheduling, buffering in networks.

Question 12

What is a graph?

Answer 12

A collection of nodes (vertices) connected by edges.

Question 13

Difference between directed and undirected graphs?

Answer 13

Directed edges have a direction; undirected edges don’t.

Question 14

Difference between weighted and unweighted graphs?

Answer 14

Weighted graphs have numerical values (weights) on edges.

Question 15

Ways to represent graphs?

Answer 15

Adjacency list (sparse) or adjacency matrix (dense).

Question 16

Graph applications?

Answer 16

Social networks, maps, routing.

Question 17

Difference between an adjacency list and a matrix?

Answer 17

List: Only stores data where there is an edge, so it takes up less space. The list has to be passed to check for agencies, so it takes more time. Where there is fewer edges, lists are better.
Matrix: Stores a value for every combination of node adjacencies so it requires more memory. Adjacency can be identified more quickly as every combo is already stored. Acts as a look-up table. Where there are many adges this method would be more suitable where there are more edges

Question 18

What is a hash table?

Answer 18

A structure that maps keys to values using a hash function.

Question 19

What is a hash function?

Answer 19

A function that converts a key into an index in an array.

Question 20

What is a collision?

Answer 20

When two keys map to the same index.

Question 21

Collision resolution methods?

Answer 21

Linear probing, chaining (linked lists), rehashing.

Question 22

Example use of hash tables?

Answer 22

Symbol tables in compilers, caching, Python dictionaries.

Question 23

What is a dictionary in computing?

Answer 23

A collection of key–value pairs, where each key is unique.

Question 24

How are dictionaries implemented?

Answer 24

Often as hash tables.

Question 25

Key dictionary operations?

Answer 25

insert(key, value), lookup(key), delete(key).

Question 26

Example use of dictionary?

Answer 26

Word-meaning pairs, storing user data by ID.

Question 27

What is a vector?

Answer 27

A dynamic array that can resize automatically as elements are added.

Question 28

Difference between array and vector?

Answer 28

Arrays have fixed size; vectors can grow or shrink.

Question 29

Typical vector operations?

Answer 29

Append, insert, delete, access by index.

Question 30

How are vectors implemented?

Answer 30

When full, allocate a larger array and copy elements.

Question 31

What type of data is best stored using trees?

Answer 31

Data with an inherent hierarchical structure (e.g., file systems).

Question 32

Why are trees described as dynamic data structures?

Answer 32

Because they allow easy addition and deletion of nodes.

Question 33

Why are trees efficient for searching and sorting?

Answer 33

They can be searched and sorted using standard tree traversal algorithms (e.g., in-order traversal).

Question 34

How are trees used in programming languages?

Answer 34

They are used to process syntax of statements, such as in compilers and interpreters.

Question 35

What is a binary search tree (BST)?

Answer 35

A directed and rooted tree where each node has at most two branches (left and right).

Question 36

What type of data is commonly stored in a BST?

Answer 36

Data entered in a random order that needs to be automatically sorted.

Question 37

What is the rule for inserting items into a BST?

Answer 37

If the new item’s value is less than the current node, go left; if greater, go right.

Question 38

How does a BST maintain order?

Answer 38

The structure automatically sorts data as it is entered.

Question 39

What is meant by traversing a BST?

Answer 39

Moving through the nodes to search for or extract data.

Question 40

When does insertion stop in a BST?

Answer 40

When an empty branch is reached — the new value is placed there.

Question 41

Example use of BSTs?

Answer 41

Searching and sorting algorithms, symbol tables, and databases.