Programming - Data structures

Question 1

what are static data structures

Answer 1

organisation or collection of data in memory that is fixed in size
eg arrays

Question 2

features of static data structures

Answer 2

• fixed memory allocation
• predictable memory usage
• elements are stored in consecutive memory locations

Question 3

what is an array

Answer 3

a list with a fixed size

Question 4

what is a dynamic data structure

Answer 4

a collection of data in memory that has the ability to grow or shrink in size
eg lists

Question 5

features of dynamic data structures

Answer 5

• variable memory allocation
• can adjust size based on the needs of the program
• unused memory is allocated or reallocated as needed

Question 6

advantages of dynamic structures

Answer 6

• makes efficient use of memory because the data structure only uses as much memory as it needs
• Can grow as more data is added to the data structure
• no limit on number of items
  that can be added
• Resources only allocated as they are needed

Question 7

disadvantages of dynamic structures

Answer 7

• runs the risk of overflow. can also have under flow if empty
• Additional memory needed for pointers;
• can lead to memory leak
• Can take longer to access an item directly

Question 8

advantages of static structures

Answer 8

• memory allocation is fixed so there will be no issues with adding and removing items from the data structure
• easier to program as there isn’t a requirement to check on the size of the data structure at any point before accessing it
• predictable memory usage, easy to estimate and manage memory requirements
• Faster access time - elements are stored in contiguous memory, allowing for quick access
• doesnt use extra memory for pointers

Question 9

features of a stack

Answer 9

LIFO - last in first out structure,

Question 10

features of a queue structure

Answer 10

FIFO - first in first out
- you can add items onto the back of the queue and remove items from the front

Question 11

What does a queue need to be able to do?

Answer 11

• add items to the back - enqueue()
• remove items from the front - dequeue()
• test if the queue is empty or full isEmpty() or isFull()

Question 12

what does a stack need to be able to do

Answer 12

• add items to the stack, from the back
• remove items from the stack from the back
• look at the top item
• test if stack is empty or full

Question 13

Describe the steps involved in adding a record to a hash table.

Answer 13

-Hash algorithm applied;
to key value ;
- result is location in table where the record should be stored (key % number of slots)
- if location is not empty;
then use next free location by incrementing by one

Question 14

Describe the process that should be followed to add an item to a circular queue
implemented as a static data structure using an array.

Answer 14

1.  Check the queue is not already full;
2.  Compare the value of the (rear) pointer with the maximum size of the array;
3.  If equal then (rear) pointer becomes zero;
4.  Otherwise, add one to the (rear) pointer;
5.  Insert new item in position indicated by (rear) pointer;

Question 15

what are abstract data types

Answer 15

a logical description of how the data is viewed and the operations that can be performed on it

Question 16

where are queues used

Answer 16

• output waiting to be printed/print spooling
• characters typed at a keyboard are held in a queue in a keyboard buffer
• simulation programs

Question 17

what is a stack?
how does a stack operate?
what are some of the common uses of a stack?

Answer 17

• a stack is a linear data structure which follows the Last in first out principle
• elements are added (pushed) and removed (pop) from the top
• used in text editing, call management

Question 18

uses of static data structures

Answer 18

• arrays, static stacks and queues
• used when max size of the data structure is known in advance
• when memory usage needs to be predictable and consistent
  eg implementing simple buffers

Question 19

uses of dynamic data structures

Answer 19

• linked lists, dynamic stacks and queues, trees, graphs
• used in situations where the size of the data structure may change during runtime
• where flexibility and efficient memory usage are required
  
  • eg, implementing dta structures like trees and graphs

Question 20

How do you add an item to a linear queue

Answer 20

check the queue is not full.
- if full, report an overflow error and stop
- else, increment the rear pointer
- insert new data item into the location pointed to by the rear pointer

Question 21

How do you remove an item from a linear queue?

Answer 21

• Check queue is not empty
• if its empty report an underflow error and stop
• copy data item in the front pointer
• increment front pointer

Question 22

How do you test for an empty linear queue

How do you test for a full linear queue

Answer 22

• Check if the front pointer is greater than the rear pointer or if the queue size is 0
• Condition: Check if the rear pointer is at the last index of the array (size - 1)

Question 23

disadvantages of static data structures

Answer 23

• cannot grow or shrink during runtime, which could lead to wasted memory or insufficient space
• not suitable for applications where data size can vary significantly
• lack flexibility when data requirements change
• Static structures have a predetermined size, which can lead to wasted memory if the data set is smaller than the allocated space

Question 24

How do you perform a push(insertion) operation on a stack

Answer 24

• Check that stack is not full
• if the stack is full, report error and stop
• increment the stack pointer
• insert new data item into location pointed to by the new pointer

Question 25

How do you perform a pop operation on a stack?

Answer 25

- check if stack is not empty - if it is report an error and stop - copy data item in location pointed to by the stack pointer - decrement the stack pointer

Question 26

How do you perform a peek or top operation on a stack

Answer 26

Check Empty: Ensure the stack is not empty. Retrieve: Access and return the item at the top of the stack without removing it.

Question 27

How do you test if a stack is empty?

Answer 27

Check if the top pointer is at the initial position (usually -1 or 0 depending on implementation)

Question 28

How do you test if a stack is full?

Answer 28

Check if the top pointer is at the last index of the stack (size - 1)

Question 29

what is a hash table

Answer 29

A hash table is a data structure that creates a mapping between keys and values.

Question 30

uses of a hash table

Answer 30

Fast Lookup: Efficiently retrieve data by key. - Useful in implementing sets, maps, and dictionaries. Database Indexing: Quick access to database records. Caching: Store frequently accessed data for quick retrieval. Symbol Tables: Used in compilers and interpreters for storing variables and function names

Question 31

What is a collision in a hash table?

Answer 31

- Occurs when two different keys produce the same hash code, resulting in the same index in the hash table

Question 32

How are collisions handled using rehashing

Answer 32

Linear Probing: If a collision occurs, check the next slot (index + 1) until an empty slot is found - Quadratic Probing: If a collision occurs, check slots at intervals of i^2 - Double Hashing: Use a second hash function to determine the step size - Separate Chaining: Store a list of all values that hash to the same index.

Question 33

What is a graph as a data structure?

Answer 33

A graph is a collection of vertices (or nodes) and edges (or arcs) that connect pairs of vertices

Question 34

What are some typical uses for graphs?

Answer 34

Social Networks: Represent relationships between people. Computer Networks: Model the connections between devices. Transportation Networks: Map out routes and connections. Web Graphs: Illustrate hyperlinks between web pages. Dependency Graphs: Show dependencies between tasks or modules

Question 35

Define the following terms: - Graph - Weighted Graph - Vertex/Node - Edge/Arc - Undirected Graph - Directed Graph

Answer 35

Graph: A collection of vertices connected by edges. Weighted Graph: A graph where edges have weights representing costs or distances. Vertex/Node: part of a graph representing an object. Edge/Arc: A connection between two vertices in a graph. Undirected Graph: A graph where edges have no direction (bidirectional). Directed Graph: A graph where edges have a direction (unidirectional)

Question 36

why might a queue be implemented as a circular queue

Answer 36

It uses memory more efficiently because it can reuse the space that becomes available when elements are dequeued

Question 37

How do you decide whether to use a linear queue, circular queue, or priority queue?

Answer 37

Linear Queue: - Simple FIFO processing. - Suitable when space is not a concern, and elements are processed strictly in order of arrival - a printer spooler where print jobs are stored and processed in the order they were submitted Priority Queue: - Suitable for systems where some tasks or data have higher importance than others - Task scheduling: A computer's operating system uses a priority queue to decide which tasks (should run first based on their importance or urgency. - Print queue: Documents sent to a printer are handled in a priority order, allowing urgent documents to be printed sooner. Air traffic control: Airplanes are handled in a priority queue, with emergency flights or those with low fuel taking precedence over others. Circular Queue: - Suitable for scenarios with a static data structure being used, so items leave the front of the queue and new items can take their place as the rear pointer “warps round” to the front - Memory Management: - Circular queues can be used to manage memory blocks, ensuring efficient allocation and deallocation of space. Process Scheduling: They can be used in process scheduling algorithms, particularly in scenarios where processes need to be executed in a cyclical or round-robin fashion. Embedded Systems: Due to their efficiency in fixed-size memory, circular queues are commonly used in embedded systems where memory allocation is restricted.

Question 38

What is a circular queue?

Answer 38

A circular queue is a linear queue that connects the end of the queue back to the front, forming a circle

Question 39

What is a priority queue?

Answer 39

- a type of queue where each element has a priority. - Elements are removed based on priority rather than the order they were added

Question 40

the rear pointer in a stack always points to

Answer 40

the last element in the stack

Question 41

uses of stacks

Answer 41

storing info abt active subroutines while a computer is running Browser History: - When you visit a new web page, it's pushed onto a stack. The back button pops the top page off the stack, allowing you to navigate backward Undo/Redo: - In word processors or code editors, actions like typing or deleting are pushed onto a stack. The "undo" function pops the last action off the stack, restoring the previous state. Function Call Stack: - When a program calls a function, information about the calling function is pushed onto a stack. This stack keeps track of the current function's state and allows the program to return to the calling function when the current function finishes. Expression Evaluation: - Compilers use stacks to evaluate complex mathematical expressions, particularly those with nested parentheses. Backtracking Algorithms: - In AI and game development, stacks are used to track the state of a problem and explore different solutions, often used in algorithms like backtracking. Memory Management: - Stacks play a role in allocating memory for variables and function calls within a program's runtime.

Question 42

differences between static and dynamic structures

Answer 42

- static data structures have storage size determined before program is run, dynamic data structures can grow or shrink during runtime - static data structures can waste storage space if number of data items stored is small, relative to the size of the structure. dynamic structures only take up the amount of storage space required for the actual data - static data structures have fixed size, size of dynamic structures can change - dynamic structures require more memory to store pointers , static data structures typically do not need - static data structures store data in consecutive memory, dynamic structures typically do not

Question 43

explain how a single stack can be used in the implementation of the repeat action and undo action

Answer 43

- stack/data structure is used to store the users action - each time an action is completed, it’s pushed on top of the stack - unless it is an undo or repeat action - when repeat action is used, the top item from the stack is used to indicate the action to complete - when undo action is used, the top item is popped from the stack of actions

Question 44

Describe the steps involved when adding an item to a priority queue, implemented as a static data structure using an array, that were not required when adding an item to a linear queue

Answer 44

- Starting with the item at the rear of the queue move each item back one place in the array - Until you (reach the start of the queue or) find an item with the same or higher priority than item - Add the new item in the position before that item;

Question 45

when should you use static or dynamic data structure

Answer 45

Static data structures are preferred when data size and structure are known beforehand and remain constant, offering efficiency in memory access and operations. Dynamic data structures are more suitable for situations where the data size and structure can change during program execution, providing flexibility for inserting, deleting, and modifying data. **When to use Static Data Structures:** Known, Fixed Data: When the size and structure of the data are predetermined and will not change. Memory Efficiency: When memory usage needs to be optimized, as static structures allocate memory upfront. Performance: When fast data access is crucial, as static structures have predictable memory locations. Simple Operations: When operations like accessing or updating elements by index are the primary needs. **When to use Dynamic Data Structures:** Variable Data: When the size and structure of the data can change during program execution. Flexibility: When inserting, deleting, or modifying data elements is a frequent requirement Unknown Data: When the exact size of the data is not known at compile time. Memory Management: When you need more control over memory allocation and deallocation. Complex Operations: When you need to perform complex operations beyond simple access and update. Examples: Static: Arrays, which have a fixed size declared at compile time. Dynamic: Linked lists, stacks, queues, and trees, which can grow or shrink in size as needed.

Question 46

When a player gives up a card it is returned to the bottom of the deck. (a) Explain why a queue is a suitable data structure to represent the deck of cards in this game.

Answer 46

Values/cards need to be removed in the same order that they are added

Question 47

Which tree traversal algorithm is used to output the contents of a binary search tree in ascending order?

Answer 47

in order

Question 48

Name two applications of depth-first search and breadth-first search

Answer 48

DFS: Navigating a maze, topological sorting 2. Cycle Detection in Graphs: DFS can efficiently identify cycles in a graph by backtracking when it encounters a previously visited node. 3. Topological Sorting: DFS is used to determine a linear ordering of nodes in a directed acyclic graph (DAG), where each node comes before all nodes that it points to. BFS: Finding the shortest path in an unweighted graph, web crawlers BFS is used by web crawlers to systematically explore websites by starting at a root page and following links in a breadth-first manner. **web crawlers are automated programs that systematically browse the internet and collect information from websites**