Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Computer science A level > Programming - Data structures > Flashcards

Programming - Data structures Flashcards

1
Q

what are static data structures

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

features of static data structures

A
  • fixed memory allocation
  • predictable memory usage
  • elements are stored in contiguous memory locations
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what is an array

A

a list with a fixed size

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

what is a dynamic data structure

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

features of dynamic data structures

A
  • variable memory allocation
  • can adjust size based on the needs of the program
  • unused memory is allocated or reallocated as needed
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

advantages of dynamic structures

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

disadvantages of dynamic structures

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

advantages of static structures

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

features of a stack

A

LIFO - last in first out structure,

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

features of a queue structure

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What does a queue need to be able to do?

A
  • add items to the back - enqueue()
  • remove items from the front - dequeue()
  • test if the queue is empty or full isEmpty() or isFull()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

what does a stack need to be able to do

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

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

A

-Hash algorithm applied;
to key ;
- 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

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

A

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;

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

what are abstract data types

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

where are queues used

A
  • output waiting to be printed/print spooling
  • characters typed at a keyboard are held in a queue in a keyboard buffer
  • simulation programs
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

uses of static data structures

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

uses of dynamic data structures

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

How do you add an item to a linear queue

A

check the queue is not full.
if its not:
Place the item at the end (rear) of the queue.
Increment the rear pointer to the next position

22
Q

How do you remove an item from a linear queue?

A

check the queue is not empty.
- if empty:
Take the item from the front of the queue.
Increment the front pointer to the next position

23
Q

How do you test for an empty linear queue

How do you test for a full linear queue

A
  • 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)
24
Q

disadvantages of static data structures

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

How do you perform a push operation on a stack

A

Check Full: Ensure the stack is not full.
Insert: element is placed at the position pointed to by the stack pointer
Update Top: Increment the top pointer to point to the new top item

26
Q

How do you perform a pop operation on a stack?

A

Check Empty: Ensure the stack is not empty.
Remove: Take the item from the top of the stack.
Update Top: Decrement the top pointer to point to the new top item

27
Q

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

A

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

28
Q

How do you test if a stack is empty?

A

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

29
Q

How do you test if a stack is full?

A

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

30
Q

what is a hash table

A

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

31
Q

uses of a hash table

A

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

32
Q

How do you apply a simple hashing algorithm?

A

Hash Function: Convert the key into an integer (hash code).
Example: hash_code = key % table_size

Index Calculation: Use the hash code to determine the index in the table.
Example: index = hash_code % table_size

Insert/Lookup: Place the value at the computed index or retrieve it from there

33
Q

What is a collision in a hash table?

A
  • Occurs when two different keys produce the same hash code, resulting in the same index in the hash table
34
Q

How are collisions handled using rehashing

A

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.
35
Q

What is a graph as a data structure?

A

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

36
Q

What are some typical uses for graphs?

A

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

37
Q

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

A

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)

38
Q

why might a queue be implemented as a circular queue

A

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

39
Q

Compare the use of adjacency matrices and adjacency lists

A

Adjacency Matrix
- pros:
- Fast look-up to check if an edge exists
- Simple to implement
-cons :
- Requires O(V^2) space, where V is the
number of vertices.
- Inefficient for sparse graph

Adjacency List
- pros:
- Requires less space for sparse graphs
- Faster iteration over edges
- cons:
- Slower look-up to check if an edge exists

40
Q

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

A

Linear Queue:
- Simple FIFO processing.
- Suitable when space is not a concern, and elements are processed strictly in order of arrival

Priority Queue:
- Suitable for systems where some tasks or data have higher importance than 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

41
Q

What is a circular queue?

A

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

42
Q

What is a priority queue?

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

the rear pointer in a stack always points to

A

the last element in the stack

44
Q

the rear pointer in a queue always points to

A

the free space after the last item in the queue

45
Q

uses of stacks

A

storing info abt active subroutines while a computer is running

Computer science A level (23 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions