Brainscape's Knowledge GenomeTM

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


See full index

Computer Science Ongoing Flashcards > Set 7 > Flashcards

Set 7 Flashcards

1
Q

What is an array?
How are items accessed in an array?

A
  • A collection of items with a fixed size
  • Arrays use index numbers to access individuals elements of the array
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is an abstract data type?

A

A theoretical description of a way of organising a collection of data, with particular features and access restrictions, that is independent of any particular data structure.

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

What is a data structure?

A

The concrete realisation of an abstract data type in code.

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

What is a static data structure?

A

A data structure that reserves a fixed amount of memory, specified by the programmer in advance of its use

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

What is a dynamic data structure?

A

Data structures that have no fixed size. The memory used grows and shrinks as items are added/removed

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

Give two advantages of static data structures over dynamic data structures:

A
  • Data is quicker to access directly, with minimal overhead
  • No additional memory is needed to store all of the pointers
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Give two advantages of dynamic data structures:

A
  • There is no wasted memory
  • There is no theoretical limit on the number of items that can be added
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Is a queue FIFO or LIFO?

A

FIFO (First in first out)

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

Give the four key operations of a queue:

A
  • Enqueue - adds item to rear of the queue
  • Dequeue - removes item and returns item from the front of the queue
  • IsEmpty - checks if the queue is empty
  • IsFull - checks is the queue is full
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Describe briefly the data structures and pointers used by a linear queue:

A
  • Linear queues are implemented with arrays (or lists)
  • They use a front and rear pointers to point to:
  • front → the next item to dequeue
  • rear → last item enqueued
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Disadvantages of linear queues if you
1. Don’t shuffle down the items
2. If you do

A
  1. There is a limit on the number of items that can be added and removed (maxSize)
  2. Implementing a linear queue where you “shuffle” the items down each time an item is dequeued is very processing intensive
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is the key difference between a circular queue and a linear queue?

A
  • Circular queues virtually connect the end to the start of the array
  • This overcomes the problem of reusing spaces in the array
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What happens to the rear pointer when enqueuing an item to a circular queue?

A

rear ← (rear + 1) % maxSize

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

What is a priority queue? How does enqueuing work?

A
  • A queue where each element in the queue has a priority
  • When new elements are enqueued, they are inserted ahead of those of lower priority and behind elements of equal or greater priority
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

Name an algorithm that can be implemented with a priority queue

A

Dijkstra’s Algorithm

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

Is a stack FIFO or LIFO?

A

LIFO (Last in first out)

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

Give the five core operations of a stack:

A
  • Push - adding to top of stack
  • Pop - removing from top of stack and returning
  • Peek - returns top item without removing it
  • IsEmpty - checking if stack is empty
  • IsFull - checking if stack is full (only relevant when stored in a static structure)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

Describe the implementation of a stack

A
  • Using an array or list to store the items
  • Initialise a pointer variable that points to the current top item
  • The pointer is initialised as -1
  • The pointer is incremented if an item is pushed, and vice versa
  • The pointer will be -1 if stack is empty.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

Is a graph static or dynamic?

A

Dynamic, they can grow and shrink in size

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

What is a graph?

A

Graphs are sets of vertices (nodes) and the edges (arcs) that connect them

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

What is a graph with a high ratio of edges to vertices called?

A

Dense

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

What is a graph with a low ratio of edges to vertices called?

A

Sparse

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

What is a weighted graph?

A

A graph that has weights (number values) on each edge

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

What is a connected graph?

A

A graph where there is a path between each pair of vertices

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

Suggest three things that graphs could be used to model

A
  • Social networking: the nodes could be individual people. An edge could represent that two people are acquaintances.
  • Transport networks: the nodes could be towns. An edge could represent that a train line connects two towns.
  • The internet: the nodes could be routers. An edge could represent that two routers are connected.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
26
Q

Give two ways to represent graphs:

A

Adjacency matrix and adjacency list

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

How do you represent no edge for a weighted graph?

A

“-” or “∞” (can’t use zero)

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

How could an adjacency list be implemented if graph is 1. weighted 2. unweighted?

A
  1. List of dictionaries if weighted
  2. List of lists if unweighted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
29
Q

Give two advantages of adjacency lists:

A
  • Adjacency lists are very space efficient, as no memory is needed to store the empty spaces
  • It is easy to add / delete nodes
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
30
Q

What is the disadvantage of an adjacency list:

A

Slow to query (e.g. to check the presence of an edge), as each item in the list must be searched sequentially until the desired edge is found

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

Give two disadvantages of adjacency matrices:

A
  • If the graph is sparse, then there are lots of empty spaces, which is wasted memory
  • It can be hard to add / delete nodes if a 2D static array is used
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
32
Q

What is a tree?

A

A connected, undirected graph with no cycles

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

What is a rooted tree?

A
  • A tree in which one vertex has been designated as the root
  • Rooted trees have parent-child relationships between adjacent nodes
  • The root is the only node with no parent. All other nodes are descendants of the root
34
Q

What is an internal node?

A

A node in a rooted tree which has a parent and at least one child

35
Q

What is a leaf node?

A

A node in a rooted tree that has a parent but is not the parent of other nodes (no child nodes)

36
Q

Suggest a use for rooted trees

A

A game tree, where edges represent moves, and nodes represent all possible positions in the game

37
Q

What is a binary tree?

A

A rooted tree in which each node has at most two child nodes

38
Q

Name a common application of binary trees

A

Binary search trees

39
Q

What is an ordered binary tree?

A
  • A type of binary tree where the data items are in a particular order
  • Items left of a node have a value less than the node
  • Items right of a node have a value greater than the node
40
Q

What is a hash table?

A

A data structure that creates a mapping between keys and values

41
Q

What is the purpose of a hash table?

A
  • To provide a way of storing a list of values in which a key is used to locate values in the list without searching through all other values
  • They are used so that records can be retrieved quickly
42
Q

What does a hash function/algorithm do in a hash table?

A

Computes the array index for the value to be stored or retrieved

43
Q

What is hashing?

A

Hashing is the irreversible process of converting data of arbitrary length into data of a fixed length.

44
Q

When does a collision occur (hashing)?

A

When two or more keys hash to the same index

45
Q

When are collisions unavoidable (hashing)?

A

When the number of possible keys is larger than the number of available spaces

46
Q

What is a dictionary?

A
  • A collection of key-value pairs in which the value is accessed via the associated key
  • There can be no duplicate keys
47
Q

Name an application of dictionaries

A

Dictionary based compression

48
Q

What is the meaning of the symbol ↦ ?

A

Maps to

49
Q

Describe the steps involved in rehashing

A
  • A larger hash table is created
  • Each value in the existing table is inserted into the new table in a position determined by a new hashing algorithm
50
Q

Describe the steps involved in rehashing

A
  • A larger hash table is created
  • Each value in the existing table is inserted into the new table in a position determined by a new hashing algorithm
51
Q

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

A
  • Hash algorithm applied to key, which returns the location (often an array index) in table where the record should be stored
  • If location is not empty, a collision has occurred
    – Open addressing is used (the next free location is used, wrapping round at the end of the array)
    – Or rehashing occurs (starting from scratch with a larger array)
    – Or chaining is used (a pointer to a list is stored at each location a collision has occurred)
52
Q

Name three methods of collision handling (for a hash table)

A
  • Rehashing
  • Chaining
  • Open addressing
53
Q

How are collisions resolved with chaining?

A

A pointer to a list is stored at each location that points to a list of items that have collided at that location

54
Q

How are collisions resolved with open addressing?

A

The item is stored in the next available location in the hash table (wrapping around at the end)

55
Q

Example of where parity bits are typically used

A

In the transmission of 7-bit standard ASCII codes

56
Q

What is a downside of majority voting?

A

If you choose a large odd number of repetitions, there is lots of redundant information that needs to be transmitted across the channel

57
Q

What is a checksum?

A
  • A checksum is a piece of data that is added to a block of data to enable error detection.
  • It is produced by applying a checksum algorithm (often MOD to limit magnitude of checksum).
  • The receiver recalculates the checksum and if it doesn’t match the data’s checksum then there is an error in the data
58
Q

What is a check digit?

A
  • An extra digit that is placed at the beginning or end of a number and is used to identify a product or verify a user
  • It allows for error detection
  • They are produced by algorithms that often use modulo arithmetic
59
Q

What is a recursive subroutine?

A

One that calls itself (or is defined in terms of itself)

60
Q

Give three advantages of recursion:

A
  1. Can lead to very elegant, short code
  2. People think recursively (sometimes)
  3. It is sometimes the only way to solve a problem
61
Q

Give two disadvantages of recursion:

A
  1. Can be slower than iterative solutions
  2. Can use more memory than iterative solutions
62
Q

What is meant by a ‘base case’?

A

The terminating situation in a recursive procedure that does not use recursion to produce a result

63
Q

Name an application of breadth-first search

A

Finding the shortest path for an unweighted graph

64
Q

Name an application of depth-first search

A

Navigating a maze

65
Q

Give two differences between depth-first traversal and breadth-first traversal:

A

DF: Chooses to explore the most recent node to be discovered
BF: Chooses to explore the least recent node to be discovered

DF: Implemented using a stack (when implemented iteratively)
BF: Implemented using a queue (when implemented iteratively)

66
Q

Depth-first traversal algorithm (beyond spec)

A

Each node has a binary flag discovered which is updated whenever we pop a node off the stack and consider its neighbours

  1. Add the start node to the stack and mark it as discovered
  2. If the stack is empty, we’re done. Otherwise, pop the top node and visit it
  3. Push each of the current node’s undiscovered neighbours to the stack, and mark them as discovered
  4. Go back to step 2
67
Q

Breadth-first traversal algorithm (beyond spec)

A

Each node has a binary flag discovered which is updated whenever we dequeue an item and consider its neighbours

  1. Add the start node to the queue and mark it as discovered
  2. If the queue is empty, we’re done. Otherwise, dequeue the front node and visit it
  3. Enqueue each of the current node’s undiscovered neighbours to the queue, and mark them as discovered
  4. Go back to step 2
68
Q

What is tree traversal?

A

Visiting the nodes of a tree in a specific order

69
Q

Use of pre-order traversal

A

Copying a tree

70
Q

Give two uses of in-order traversal:

A
  • Outputting the contents of a binary search tree in ascending order
  • Producing infix expression from an expression tree
71
Q

Give two uses of post-order traversal:

A
  • Infix to RPN conversions
  • Producing a postfix (RPN) expression from an expression tree
72
Q

Describe pre-order traversal operation

A
  1. Visit the node
  2. Traverse the left hand sub tree
  3. Traverse the right hand sub tree
73
Q

Describe in-order traversal operation

A
  1. Traverse the left hand sub tree
  2. Visit the node
  3. Traverse the right hand sub tree
74
Q

Describe post-order traversal operation

A
  1. Traverse the left hand sub tree
  2. Traverse the right hand sub tree
  3. Visit the node
75
Q

What are the steps for converting postfix to infix?

A
  • Convert “num num op” triplets one at a time, adding brackets each time
  • Remove any unnecessary brackets
76
Q

What are the steps for converting infix to postfix?

A
  • Add brackets around every operation
  • Draw arrow from operator to end of its bracket
  • Write expression, keeping numbers in the same order
77
Q

What are the steps for linear search on a list?

A
  1. Start at beginning of list
  2. Compare each item to one you want until
    • you find it or
    • you reach the end of the list

(use an indefinite while loop!)

78
Q

What are the steps for binary search on a value X (in English)?

A
  1. Look at item in centre of sorted list (or array) (sort first if needed)
  2. If it isn’t X…
    2.1. If it is larger than X, you can ignore all of the items above
    2.2. If it is smaller than X, you can ignore all of the items below
  3. Check middle of halved list and repeat, until you find X or the sublist cannot be halved any more.
79
Q

What is the while condition when coding binary search?

A

lower<= upper && !found

80
Q

What does it mean if you reach a leaf node before you find X in a binary tree search?

A

X is not in the tree

Computer Science Ongoing Flashcards (11 decks)

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