Brainscape's Knowledge GenomeTM

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


See full index

Computer Science > Unit 7 - ADTs > Flashcards

Unit 7 - ADTs Flashcards

1
Q

Elementry Data Types Examples

A

Boolean, char, integer, real

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

Composite Data Types

A

Array, String

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

Abstract Data Types examples

A

Stacks, Queues, Dictionaries

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

Abstract Data Types (definition)

A

A logical description of how we view data and possible operations

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

Static Data Types Definition

A

Fixed in size, cannot change size once program is running

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

Dynamic Data types defininition

A

Can grow/shrink in size once program is running as it uses the heap

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

The heap (memory)

A

A portion of memory which space is automatically allocated/ deallocated to as required

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

Dynamic Data Structure Uses

A

Queues, as maximum size is not known before implementation

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

Record Structure

A

Consists of a fixed number of variables called fields, each field can have a different data type

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

Records in C#

A

Must be defined using a dictionary or using a class

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

Tuples

A

Tuples are mutable data structures –> declared like a list

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

Array Limitations

A

Size must be declared when created, cannot grow in size, one data type (in some languages including C#)

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

Array Benefits

A

Can be any dimension, uses 0 based indexing, values are mutable

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

Mutable Definition

A

Values can be changed whilst the programming is running

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

enqueue(data)

A

Adds an element to the queue

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

dequeue()

A

Removes (and returns) element from the queue

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

peek()

A

returns element from queue without removing it from queue

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

is_empty()

A

Checks if queue is empty

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

is_full()

A

Check if queue is full (if it is static)

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

What is a Queue

A

It is a mutable fifo data structure, meaning that items are added at the back and removed from the front

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

Why circular queues exist?

A

When an item is dequeued, a space of memory is left however this is left at the front of the queues and data in a queue is only added at the back, this leaves memory being wasted and queues filling up fast, circular queues solve this problem

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

How do circular queues work?

A

Let the queue be defined as an array. If the end is pointer is at the end of the array, however the start pointer is not at the front, a circular queue means that the next item to be enqueued will be added to the first slot on the array. The pointer for the end also points to here, this means that whilst the array is not full, data can keep being enqueued and it will go around in circles

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

Application of Queues

A

Printer Queues, the thing that was printed first will be the first to be printed.
Simulations of actual queues eg in a supermarket

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

How do priority queues work?

A

Each data is given a priority, the ones with the higher priorities are nearer to the front of the queue which means they are more likely to get dequeued sooner. When data is added it is added as the last one with that priority making it possible for it to be added at the front or in the middle

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

Why use a list instead of an array?

A

Lists are dynamic, arrays are static.

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

Similarity between Lists and Arrays

A

Both use zero based indexing,

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

Name of elements in linked list

A

Node

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

What must each node in a linked list store?

A

The data relating to that element, and a pointer, pointing to the next node

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

Advantages of linked lists

A

Dynamic, contiguous memory locactions are not required, can be used to implememtn stacks and queues, easy to insert data

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

Disadvantages of linked lists

A

Random access is not allowed so you have to sequencially access each element starting from the first one, extra memory space is required for each pointer, reverse traversing is difficult (unless a second pointer is used)

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

How to add data into a linked list? (simple)

A

Where the data is wanting to be added, change the pointer of the one before to point to that one and make the pointer of that element point to the next one.

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

How do you traverse a linked list?

A

Starting at the head, follow the pointers of each node until you reach a pointer pointing to null which means that you have reached the end of the list.

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

How hard is deleting data in a linked list?

A

Very easy as you just have to change the pointer in the node before it.

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

What is a doubly linked list?

A

A linked list with pointers pointing both forward and backwards.

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

What are graphs used to represent?

A

Complex, non-linear relashonships between objects.

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

What is the degree of a node on a graph?

A

The number of other nodes it is connected to. (the number of neighbours)

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

What is are neighbours on a graph?

A

Two nodes that are connected by an edge

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

What is a loop on a graph?

A

It is an edge that connects a node to itself.

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

What is a path on a graph?

A

A sequence of nodes that are connected by edges.

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

What is a cycle on a graph?

A

A cycle is a closed path, a path that starts and ends at the same node. However no iterim node can be visisted more than once.

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

Examples of what graphs can represent.

A

Social networks (whos friends with who etc), transport networks (the London Underground), the internet (each router is a node), the world wide web (each node is a webpage, edges show which ones are linked)

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

What is an undirected graph?

A

A graph which means that you can travel both to and from each node.

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

What is a directed graph?

A

Each edge of the graph has a direction (showing that you can only move in the specified direction between nodes).

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

What is a weighted graph?

A

On each edge of a weighted graph, there is a value. This can be used to represent many thing eg the distance between towns etc. Weights enable you to find the shortest paths.

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

Ways to implement a graph in code:

A

Adjacency matrix or adjacency list

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

What is an adjaceny matrix?

A

An adjaceny matrix is a two dimensional array where each node is represented by the index. If the data stored at [x,y] is not 0, eg in an unweighted graph it will be 1, in a weighted graph it will be the weight, there is an edge between x and y. If the graph is undirectionaly, the matrix will be simetrical.

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

What is an adjaceny list?

A

An adjacency list stores each node, and then what it is connected too. This could be implemented using a linked list or an array.

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

How are weights stored in an adjacency list?

A

Each list has both the node and the weight of that node eg. B links to D,15; H,40; F,46.

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

Pros of Adjacency Lists (compared to adjacency matrix)

A

They are space efficient for graphs with few edges and many nodes, it is easier to frequently add/ delete nodes from an adjacency list

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

Pros of Adjaceny Matrix (compared to adjacency list)

A

Easier to test for the presence/ absence of edges as each piece of infomation can be easily accessed by an index, it is also easier to remove edges from an adjacency matrix (not add them, they are the same)

51
Q

What is a tree?

A

A tree is a connected, undirected graph with no cycles.

52
Q

What is the root of the tree?

A

It is the start node for traverals, it also has no parents, if a tree has a root, it is rooted.

53
Q

What is a branch on a tree?

A

A branch is a path from the root to an end point.

54
Q

What is a leaf on a tree?

A

A leaf is an end point on a tree (a node which has no children)

55
Q

How many edges does a tree have in terms of nodes?

A

N - 1, where N = number of nodes.

56
Q

What are the relashonsips between nodes on a rooted tree?

A

They have parent-child relashonships.

57
Q

What is a parent node?

A

It is a node which comes directly before another adjacent node (which is considered the child)

58
Q

What is special about a binary tree?

A

In a binary tree, each node has a maximum of two children.

59
Q

What is a binary search tree?

A

A rooted tree where the nodes of the tree are ordered.

60
Q

If the nodes are ordered low to high, where are the lower values in relation to the root.

A

The lower values are on the left of the root.

61
Q

In what order will an algerbraic expression tree give expressions?

A

It will give them in reverse polish notation, also known as post-fix.

62
Q

Uses of binary trees:

A

Binary trees are used in compilers to build syntax trees, and are used within routers to store routing tables.

63
Q

Uses of expression trees:

A

Represent boolean and algerbraix expressions in a way that simplifies the processing of the expression.

64
Q

Unique way that binary trees can be implemented:

A

An array of records

65
Q

What does each record represent in an array of records?

A

Each record represents a node.

66
Q

What does each record store in an array of records?

A

Each records stores an index, the data for the node, the left child node, the right child node

67
Q

Types of tree traversals:

A

Pre-order, post-order, in-order

68
Q

What is the first node “visisted” in pre order traversal?

A

The root

69
Q

Which branch do you traverse first in a pre order traversal?

A

Left

70
Q

Uses of pre order traversals:

A

Can be used to duplicate the data to create an identical binary tree as parents are always read before children.

71
Q

What would be the first node you visit using an in order traversal?

A

The leftest most node on the tree.

72
Q

Uses of in order data:

A

Used to read data in order.

73
Q

First node in a post order traversal:

A

Leftest most node.

74
Q

Uses of post order tree traversals;

A

Used to delete data, as children are deleted first to avoid “hanging” children.

75
Q

2+3 in post fix notation

A

2 3 +

76
Q

Advantages of reverse polish notation (RPN)

A

RPN expressions do not need brackets, RPN is simpler for machines to calculate, there is need for backtracking

77
Q

What is a stack?

A

Stacks are LIFO structures (last in first out), meaning data is added at the top AND taken from the top.

78
Q

push(data)

A

This pushes the data onto the top of the stack (adds data to the stack)

79
Q

pop()

A

This returns and removes data from the top of the stack

80
Q

peek()

A

This returns the data from the top of the stack without removing it from the stack

81
Q

is_empty()

A

Checks whether the stack is empty

82
Q

is_full()

A

Checks whether the stack is full

83
Q

Applications of stacks

A

Converting postfix notation to infix notation, used to maintain a list of operations on an undo button, stacks are used in call stacks

84
Q

What is overflow in a stack?

A

When a stack is full and another item is attempted to be pushed, this causes overflow.

85
Q

What is underflow?

A

When the stack is empty but something is attempted to by popped.

86
Q

What is the function of a call stack?

A

A call stack holds information about active subroutines whilst a program is running (the details are hidden from the user)

87
Q

What can the called stack hold?

A

Return addresses, parameters, and local variables.

88
Q

Why are return addresses held in call stacks?

A

They are held so that when they are popped, they are returned, severat subroutines can be within one.

89
Q

What is a hash table?

A

A hash table is a data structure that implements an associative array

90
Q

What is an associative array?

A

(A dictionary) It is where data is stored as key, value pairs.

91
Q

How is the position data in a hash determined?

A

It is determined by applying a hashing function (algorithm) to the key,

92
Q

How to find data stored in the hash table?

A

You use the same hashing algorithm as the output will be the same if the input is the same.

93
Q

Why use a hash table?

A

Hash tables are VERY efficient at searching, (best case constant time!!) So is adding and deleting.

94
Q

What would you use to implement a hash function?

A

You must use an array so that you can use the index,

95
Q

What size should a hash table be?

A

It should be large enough to store the values but not too large so that there is too much empty space but there should also be some empty space.

96
Q

What is the load factor?

A

The load factor is n/k, where n is the number of occupied positions and k is the number of total positions.

97
Q

What is the optimal load factor for a hash table?

A

0.75

98
Q
A
99
Q

What is a collision in a hash function?

A

This is where two keys will give the same index in the hash function.

100
Q

What happens after a collision in a hash table?

A

Open Addressing (linear probing) or Closed Addressing (Seperate Chaining)

101
Q

What is open addressing (linear probing)?

A

Placing data in the next free position or in the 2nd next position until a free position is found and so on depending on the algorithm.

102
Q

What is seperate chaining (closed addressing)?

A

At each index, rather than the data being stored, there is a pointer to where the data is stored, if there is only one piece of data stored, it will point to null, however if a collision happens it will point to another piece of data stored at that index, creating a chain of nodes with the same index.

103
Q

When are collisions more likely to happen?

A

As the size increases.

104
Q

How to retrieve data if linear addressing has happened?

A

Hash the key, check if data in position is correct, if not use probing method to check the next locaction, keep going until correct data is found or an empty position is found (which means that the data is not in the hash table) .

105
Q

How to retrieve data if closed chaining has happened?

A

Hash key to generate index, exam key to find head of the list, go through each piece of the list until you find the data or an empty position. If there is an empty position, the data is not in the hash table.

106
Q

What is rehashing?

A

Rehashing is when a new hash table is created, the key for each item in the existing table is rehashed, and the item will be inserted into the new hash table. If the new table is larger, the hash function may need to be changed as it will need to generate a larger range of values.

107
Q

Why can hashing be considered a type of encryption?

A

The hash function will be very easy to carry out one way, however almost impossible to do the reverse.

108
Q

Why is hashing not foolproof for passwords?

A

Most hashing algorithms are well known, and hackers can use rainbow tables to store pre-hashed values, when a match is found, the password is revealed.

109
Q

What can be used to prevent hackers from being able to use rainbow tables?

A

A salt- which is a random piece of data added to the password before it is hashed, therefore the same password on different systems may have different hash values.

110
Q

What is a dictionary?

A

A data structure that holds data as a key-value pair.

111
Q

What must keys be in a dictionary?

A

Keys must be unique and are normally simple data types (integers or strings)

112
Q

Why should you use keys?

A

Keys are good to use as they provide direct access to the values even if they are unordered –> which is much quicker than othwise having to linear search through every one.

113
Q

What is a vector?

A

A vector is an ADT that can represent both direction and magnitude, they are commonly used to represent movement.

114
Q

How are vectors represented in maths and physics?

A

They are represented as arrow, the length is the magnitude the arrow is the direction.

115
Q

How can a vector be represented?

A

A list, a 1-d array, a dictionary, graphically, using set notation.

116
Q

What is set notation for a vector?

A

Using the set they are drawn from eg R for real numbers, N for natrual numbers etc, and the number of dimensions in the array = y, it would be written as R^y (if it is from the real set).

117
Q

How would you say R^2?

A

A 2 vector over R

118
Q

What is a position vector?

A

A position vector represents a point in space in relation to an origin.

119
Q

What is the convex combination of two vectors?

A

It is a line that goes from a point where two vectors meet, to the line between the heads of two vectors.

120
Q

What is the equation for the convex combination of two vectors u and v?

A

αu + βv, where u and v are vectors, α and β are both greater than 0 and add to1

121
Q

What is the dot product used for?

A

Multiplying to vectors together.

122
Q

Equation for dot product.

A

u * v = u_1v_1 + u_2v_2, u_3v_3 +.. + u_nv_n

123
Q

Useage of the dot product:

A

If x holds price of products and y holds number of products sold, xy is the total revenue.
Can be used to calculate angle between vectors.

124
Q

Equation of angle between vectors:

A

cosθ = (u*v)/ |u||v|

Computer Science (8 decks)

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