Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Computer Science A Level > Unit 7 - Data Structures > Flashcards

Unit 7 - Data Structures Flashcards

1
Q

define array

A

a finite, ordered set of elements of the same type.

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

what is a 2-dimensional array

A

a collection of data elements arranged in a grid-like structure with rows and columns

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

define tuple

A

an ordered set of values, which could be elements of any type (images, sound files, strings,etc) that is immutable, which means that elements cannot be changed, and you cannot dynamically add elements or delete elements form a tuple.

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

what’s the difference between static and dynamic data types

A

dynamic data types - change size when required (lists grow when items are added and shrink when items are removed). it does this with the aid of heap (specific area of memory)
static data types - cannot change size (array)

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

what is an abstract data type

A

one that is created by a programmer
- 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
6
Q

what is an elementary data type

A

defined within the programming language

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

what are the four operations with a queue

A
  • enQueue(item)
  • deQueue
  • isEmpty
  • isFull
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

what is a queue

A

a queue is a first in first out data structure. new elements can only be added to the end of the queue, and elements may only be retrieved from the front of the queue

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

applications of queues

A
  • printing from computers (print queue)
  • typing on a keyboard
  • simulations
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

what does enQueue(item) do

A

add a new item to the rear of the queue

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

what does deQueue() do

A

remove the front item from the queue

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

what does isEmpty() for queues do

A

test to see whether the queue is empty

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

what does isFull() for queues do

A

test to see whether queue is full

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

what is a circular queue

A

one way of overcoming the limitation of a static data structure by reusing the spaces that have been freed by dequeuing from the front of the array. If you see a MOD and a length function when looking at lists you will know that it is a circular queue.

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

pseudocode to initialise a circular queue

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

pseudocode to test for an empty queue

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

pseudocode to test for a full queue

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

pseudocode to add an element to the queue

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

pseudocode to remove an item from the queue

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

what is a priority queue

A

it acts like a queue in that items are dequeue by removing them from the font of the queue. however, the logical order of items within the queue is determined by their priority, with the highest priority items at the front of the queue and the lowest priority items at the back.

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

what is a list

A

an abstract data type consisting of a number of items in which the same item may occur more than once

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

what are the main operations on lists

A
  • isEmpty()
  • append(item)
  • remove(item)
  • search(item)
  • length()
  • index(item)
  • insert(pos, item)
  • pop()
  • pop(pos)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

what does isEmpty() on lists do

A

test for empty list

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

what does append(item) do

A

add a new item to list to the end of the list

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
what does remove(item) do
remove the first occurrence of an item from list
26
what does search(item) do
search for an item in the list
27
what does length() do
return the number of items
28
what does index(item) do
return the position of item
29
what does insert(pos, item) do
insert a new item at position pos
30
what does pop() do
remove and return the last item in the list
31
what does pop(pos) do
remove and return the item at position pos
32
what is a linked list
a linked list is a dynamic data structure used to hold an ordered sequence - items which form the sequence are not necessarily held in contiguous data locations - each item in the list is called a node and contains a data field and a next address field called a link or pointer field - the data field holds the actual data associated with the list item, and the pointer field contains the next item in the sequence - the link field indicates that there are no further items by the use of a null pointer
33
pseudocode the enQueue() list
procedure enqueue(item) if q.isFull() then print ("queue full") else q.append(item) endif endprocedure
34
pseudocode for deQueue(item) on lists
procedure dequeue(item) if q.isEmpty() then print("queue empty") else q.pop(0) endif endprocedure
35
pseudocode for isFull() on lists
function isFull() return(len(q) == maxSize)) endfunction
36
pseudocode for isEmpty() on lists
isEmpty() return(len(q) == 0) endfunction
37
how to add nodes to a linked list
data is put into the node pointed to by the nextfree pointer
38
how to delete nodes from a linked list
adjust the nextfree pointer to the position of the deleted node
39
how to peek ahead in linked lists
examine the data and the pointer in the current node p and the next one function
40
define stack
a stack is a last in, first out data structure. this means that items are added to the top and removed from the top
41
applications of stacks
- calculations - return addresses when subroutines are called - back/undo button
42
what type of data structure is a stack
static or dynamic
43
5 main operations on stacks
1. push(item) 2. pop() 3. peek() 4. isEmpty() 5. isFull()
44
what does push(item) do on stacks
adds a new item to the top of the stack
45
what does pop() do on stack
removed and returns the top item from the stack
46
what does peek() do on stacks
returns the top item from the shack but does not remove jt
47
what does isEmpty() do on stacks
tests to see whether the stack is empty, and returns a boolean value
48
what does isFull() do on stacks
test to see whether the stack is fill, and returns a boolean value
49
pseudocode for isEmpty() stacks
50
pseudocode for isFull() stacks
51
pseudocode for push(item) stacks
52
pseudocode for pop() function stack
53
define hash tables
- abstract data type large data sets can be organised so each record is assigned a unique address. this unique address is calculated using a hashing algorithm or hash function. the algorithm uses some part of the record (e.g. the primary key)) to map the record to a unique destination address. the resulting data structure used to store the data is called a hash table.
54
what is a collision
happens when an algorithm generates the same address for different primary keys
55
how to search for an item with hash tables
- apply the hashing algorithm to the key field of the item - examine the resulting cell in the list - if the item is there, return the item - if there is another item in that spot, keep moving until either the item is found or blank cell is encountered, when it is apparent that the item is not in the table
56
what is the address in a hashing table
key MOD (num slots)
57
what is rehashing
finding an empty slot when a collision has occurred • an alternative algorithm is to increment the 'skip' value by adding 1,3,5,7 etc. instead of repeatedly incrementing by 1 to find a free space – to do this, the size of the skip value must be such that all slots in the table will eventually be reached
58
uses of hash tables
- efficient lookup - dictionary - graphs
59
what is the mid-square method for hash tables
1. square the item (assume it is numeric) 2. extract some portion of the resulting digits 3. perform the mod (remainder) step to get an address
60
what is the folding method for hash tables
1. divide the item into equal-size pieces (the last piece may not be of equal size) 2. add the pieces together 3. perform the mod (remainder) step to get an address
61
define graph
a set of vertices or nodes connected by edges or arcs.
62
edges in an undirected graph
bidirectional
63
edges in a directed graph
one-way
64
what does it mean if an edge is weighted
there is a cost to from one node to another
65
what is an adjacency matrix
2-D array can be used to site information about a graph. each of the rows and columns represent a node
66
adjacency matrix of an undirected graph
symmetric
67
advantage of a matrix
1. an adjacency matrix is convenient to work with 2. adding an edge is simple
68
disadvantage of a matrix
1. a sparse graph with not many connections (edges) will leave most of the cells empty wasting a lot of empty storage
69
what is an adjacency list
an alternative way of representing a graph. a list of nodes is created, and each node points to a list of adjacent nodes
70
advantage of adjacency list
1. it uses storage for the connections that exist, so it is more space efficient 2. it is a good way of representing a large sparsely connected graph
71
how can a weighted graph be represented by a dictionary
a weighted graph can be represented as a dictionary of dictionaries, with each key in the dictionary being a node, and the value, a dictionary of adjacent edges and edge weights
72
what are the two ways of traversing a graph
1.depth-first 2. breadth-first
73
what is a depth-first traversal
go as far down one route before backtracking and taking the next riute
74
what is a breadth-first traversal
visit all the neighbours of a node, and then the neighbours of the first node visited, all the neighbours of the second node and so on, before moving further away from the start node
75
applications of graphs
- computer networks - roads between towns - tasks in a project - web pages and links
76
define tree
a tree is a connected data structure with no cycles – there is a unique path from each node to any other node.
77
differences between trees and graphs
1. a graph doesn't have a route node, whereas a tree does not. 2. a graph has cycles, where as a tree does not.
78
what is a rooted tree
in a rooted tree, one node is identified as the root. every node except the root has one unique parent.
79
applications of rooted trees
- manipulating hierarchical data - making information easy to search - manipulating sorted lists of data
80
what does a node consist of in a binary rooted tree
- the data (primitive or complex) - a left pointer to a child - a right pointer to a child.
81
define leaf node
node that has no children
82
define edge
an edge connects two nodes. every node expect the root is connected by exactly one edge from another node
83
what are three types of traversal
1. pre-order 2. in-order 3. post-order
84
what is a pre-order traversal
visit the root, then traverse the left sub-tree, then the right sub-tree.
85
what is pre-order traversal normally used for
a pre-order traversal is used to produce pre-fix or Polish Notation for a mathematical expression
86
what is an in-order traversal
traverse the left sub-tree, then visit the root, then traverse the right sub-tree (sequential order)
87
what is a post-order traversal
traverse the left sub-tree, then traverse the right sub-tree, then visit the root.
88
what is a post-order traversal used for
a post-order traversal is used to produce postfix or Reverse Polish Notation for an expression
89
pseudocode for pre-order traversal
90
pseudocode for in-order traversal
91
pseudocode for post-order traversal
92
what is the main programming feature of tree traversal algorithms
recursion
93
use of in-order traversal
binary search tree, to perform an efficient search for any item

Computer Science A Level (12 decks)

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