Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

Computer Science > Chapter 7 > Flashcards

Chapter 7 Flashcards

1
Q

What is an array?

A

An array is defined as a finite, ordered set of elements of the same type, such as an integer, real or char.

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

How to write an array?

A

my Array = [51, 72, 35, 37, 0, 100]

X = myArray [2]

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

2D array?

A

A two dimensional array can be visualised as a table rather than a spreadsheet.

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

Records

A

A ​record ​is more commonly referred to as a​ row in a file​ and is made up of ​fields​. Records are used in databases.

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

Lists

A

A list is a data structure consisting of a number of ​ordered ​items where the items can occur more than once​. Lists are similar to 1D arrays and elements can be accessed in the same way. The difference is that list values are stored ​non-contiguously​. This means they do not have to be stored next to each other in memory, as data in arrays is stored. Lists can also contain elements of ​more than one data type​, unlike arrays.

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

Empty

A

List.isEmpty()
» False

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

Add

A

List.append(15)

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

Remove

A

List.remove(23)
»

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

Search

A

List.search(38)
» False

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

Length

A

List.length()
» 7

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

Index

A

List.index(23)
» 0

Returns the position of the item

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

Insert

A

insert(position, value)

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

Pop

A

pop()
pop(position)

Returns and removes the last value in the list

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

Tuples

A

An ​ordered set of values of any type​ is called a tuple. A tuple is ​immutable​, which means it cannot be changed​: elements cannot be added or removed once it has been created. Tuples are initialised using regular brackets instead of square brackets.

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

Linked Lists

A

A linked list is a ​dynamic data structure​ used to hold an ordered sequence. The items which form the sequence do not have to be in contiguous data locations. Each item is called a ​node​, and contains a ​data field​ alongside another address called a ​link ​or ​pointer field

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

Graphs

A

A graph is a set of ​vertices/nodes​ connected by ​edges/arcs​. Graphs can be placed into the following categories:
- Directed Graph: The edges can only be traversed in one direction.
- Undirected Graph: The edges can be traversed in both directions.
- Weighted Graph: A cost is attached to each edge.

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

Static

A

Structure size cannot change at runtime

18
Q

Dynamic

A

Structure size can change at runtime

19
Q

Immutable

A

Structure/data cannot be changed at runtime

20
Q

Mutable

A

Structure/data can be changed at runtime

21
Q

Adjacency Matrix Advantages

A

Easy to add nodes

Convenient to work with due to quicker access times

22
Q

Adjacency List Advantages

A

More space efficient for large, sparse network

23
Q

Stacks

A

A stack is a ​last in first out (LIFO)​ data structure. Items can only be added to or removed from the top of the stack. Stacks are key data structures in computer science; they are used to reverse an action​, such as to go back a page in web browsers. The ‘undo’ buttons that applications widely make use of also utilise stacks. A stack can be implemented as either a static structure or a dynamic structure. Where the maximum size required is known in advance, static stacks are preferred, as they are easier to implement and make more efficient use of memory.

24
Q

Stack operations

A

isEmpty()
push(value)
peek()
pop()
size()
isFull()

25
Queues
A queue is a​ first in first out (FIFO)​ data structure; items are added to the end of the queue and are removed from the front of the queue. Queues are commonly used in printers, keyboards and simulators. There are a few different ways in which a queue can be implemented, but they all follow the same basic principles.
26
linear queue​
A ​linear queue​ is a data structure consisting of an array. Items are added into the next available space in the queue, starting from the front. Items are removed from the front of the queue. Queues make use of two pointers: one pointing to the front of the queue and one pointing to the back of the queue, where the next item can be added.
27
Circular queues​
A circular queue operates in a similar way to a linear queue in that it is a FIFO structure. However, it is coded in a way that once the queue’s rear pointer​ is equal to the maximum size of the queue, it can loop back to the front of the array and store values here, provided that it is empty. Therefore, circular queues can use space in an array more effectively, although they are harder to implement.
28
Queue operations
enQueue(value) deQueue() isEmpty() isFull()
29
Trees
A tree is a connected ​form of a graph​. Trees have a ​root node​ which is the top node in any tree. Nodes are connected to other nodes using branches, with the lower-level nodes being the children of the higher-level nodes.
30
Trees
A tree is a connected ​form of a graph​. Trees have a ​root node​ which is the top node in any tree. Nodes are connected to other nodes using branches, with the lower-level nodes being the children of the higher-level nodes.
31
Binary Tree
A binary tree is a type of tree in which each node has a​ maximum of two children. ​These are used to represent information for binary searches​, ​as information in these trees is​ easy to search​ through. The most common way to represent a binary tree is storing each node with a​ left pointer​ and a ​right pointer​. This information is usually implemented using two-dimensional arrays.
32
Traversing a binary tree
There are three methods of traversing a binary tree: Pre-order, In-order and Post-order. A simple way of remembering these is using the ​outline method​, which is described below.
33
Pre-order Traversal
Pre-order traversal follows the order: root node, left subtree, then right subtree. Using the outline method, nodes are traversed in the order in which you pass them on the left, beginning at the left-hand side of the root node.
34
In-order Traversal
In-order traversal follows the order: left subtree, root node, right subtree. Using the outline method, nodes are traversed in the order in which you pass under them, beginning at the first node from the left which does not have two child nodes. This is useful for traversing the nodes in sequential order.
35
Post-order Traversal
Post order traversal follows the order: left subtree, right subtree, root node. Using the outline method, nodes are traversed in the order in which you pass them on the right.
36
Hash Tables
A hash table is an array which is coupled with a ​hash function.​ The hash function takes in data (​a key​) and releases an output (​the hash​). The role of the hash function is to ​map the key to an index​ in the hash table. Each piece of data is mapped to a unique value using the hash function. However, it is sometimes possible for two inputs to result in the same hashed value. This is known as a collision​. A ​good hashing algorithm​ should have a ​low probability of collisions​ occurring but in the event that it does occur, the item is typically placed in the next available location. This is called collision resolution. Hash tables are normally used for ​indexing​, as they provide fast access to data due to keys having a unique, one-to-one relationship with the address at which they are stored.
37
Overflow
Attempting to push onto a stack that is full
38
Underflow
Attempting to pop from a stack that is empty
39
Elementary data type
integer, real, Boolean, char
40
Composite data type
string, array [list may also be in this section, depending on programming language]
41
Abstract data type
list, stack, queue

Computer Science (12 decks)

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