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

You may prefer our related Brainscape-certified flashcards:
Biology 101 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 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

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

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

How do you add an item to a linear queue

A

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

21
Q

How do you remove an item from a linear queue?

A
  • Check queue is not empty
  • if its empty report an underflow error and stop
  • copy data item in the front pointer
  • increment front pointer
22
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)
23
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
24
Q

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

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

How do you perform a pop operation on a stack?

A
  • 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
26
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.

27
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)

28
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)

29
Q

what is a hash table

A

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

30
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

31
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

32
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
33
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.
34
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

35
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

36
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)

37
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

38
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

39
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

40
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
41
Q

the rear pointer in a stack always points to

A

the last element in the stack

42
Q

the rear pointer in a queue always points to

A

the free space after the last item in the queue

43
Q

uses of stacks

A

storing info abt active subroutines while a computer is running

44
Q

differences between static and dynamic structures

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

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

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

Computer science A level (30 decks)

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