Brainscape's Knowledge GenomeTM

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


See full index

Computing > Programming: Data Structures > Flashcards

Programming: Data Structures Flashcards

1
Q

List some data types

A

•integer
•string
•float
•boolean
•character
•nothing

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

What is a data type?

A

They represent the category of data being stored, not the data itself

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

List some data structures

A

Built in:
•List
•Array
•Dictionary
•Tuple
•Set

User defined:
•Stack
•Queue
•Tree
•Graph
•Hash map

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

Define Static data types

A

The size of the data structure cannot be changed during run time. The content can be modified but the memory allocated to it stays the same

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

Is an array:
a) [1,2,3]
b) {1,2,3}
c) {1:’c’, 2:’a’,3:’t’}

A

b

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

Describe the meaning of “data structure”

A

A container within which information is stored

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

Give three properties of an array

A

-finite
-indexed
-only containing elements of the same data type
-mutable

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

Give examples of data types

A

-interger
-float
-string
-boolean
-null

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

Give examples of user defined data structures

A

-stack
-queue
-tree
-linked list
-graph
-hash map

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

Give examples of built in data structures

A

-list
-array
-dictionary
-tuple
-set

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

Describe a static data structure

A

Size of the data structure is fixed and cannot be changed in runtime. The data contained in the structure may be modified but the memory allocated to it does not.

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

Describe a dynamic data structure

A

The size of the data structure can be changed in run time. The data stored in the data structure as well as its memory space allowed can be modified

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

Difference between dynamic and static data structures:

A

-dynamic: memory is allocated dynamically/as the program executes
Static: memory is allocated at comple time. Fixed size

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

Advantage of static data structures:

A

-easier to add and remove elements, with fast access times
-locations of items within the structure do not need to be kept track of, simple indexing

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

Disadvantage of static data structures:

A

-if a large amount of memory is allocated to the structure, space could easily be wasted.
-stack overflow errors possible

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

Advantage of dynamic data structures:

A

-uses memory efficiently as the structure only takes up as much space as it needs

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

Disadvantage of dynamic data structures:

A

-harder to program with, as the size of the structure and the locations of items within it need to be monitered

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

Describe an abstract data structure:

A

Don’t exist as data structures in their own right, but use other data structures (like arrays) to form a new way of storing data

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

Give an example of an abstract data structure:

A

-queues
-stacks
-graphs

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

What data structure is a queue based on?

A

An array.

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

What type of abstract data structure is a queue?

A

FIFO structure

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

Where are queues used in a computer system?

A

-used in keyboard buffers. Each key pressed is added to the queue and removed once it has been processed/displayed- meaning letters appear in the same order they were pressed

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

Give other examples of queues in action:

A

-keyboard buffer
-printer management
-task scheduling
-breadth-first search algorithms

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

What is a BFS

A

breadth first search algorithm

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

What is a breadth first search algorithm?

A

Used in searching tree data structures for a specific node. Begins at the root and searches each node on a current depth before moving on to the nodes at the next depth level.

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

How is a queue used in breadth first search algorithms?

A

Keeping track of which nodes have been visited

27
Q

Describe a linear queue containing (in order) the numbers 1,2,3 and 4

A

Each number would occupy a space in the queue in order. The front queue pointer would point to the 1, at the front of the queue and the rear pointer would point to the EMPTY position after the 4.

28
Q

Describe the movement of the pointers if an item is added to a linear queue.

A

The rear pointer moves along a place, to point to the next available position after the most recently added value.

29
Q

Describe the movement of the pointers if an item is removed from a linear queue

A

The front pointer moves to the item after the removed item. The rear pointer does not change.

30
Q

Define a priority queue

A

A queue in which certain items have priority over others and are ordered as such. Items of a higher priority will leave the queue first.

31
Q

Give two examples of uses of a priority queue

A

-processor scheduling
some applications take priority over others when being handled by the processor, an application being used by a user would be prioritised over a background application.
-in a school printer queue, a teachers items may take priority over a students.

32
Q

describe the movement of pointers if an item is added to a circular queue

A

the rear pointer, previously pointing to the closest empty position in the queue to the front pointer, will move down by one space. The space previously occupied by the rear pointer will now contain the new value.

33
Q

describe the movement of pointers if a value is removed from a circular queue

A

the front pointer will move to the next available space

34
Q

what are some operations that may need to be carried out before enqueueing or dequeueing?

A

checking if a queue is empty or full

35
Q

Describe a stack

A

A first in, last out abstract data structure

36
Q

What data structures are stacks based on?

A

An array

37
Q

What are some functions that can be performed on a stack?

A

-push
-pop
-peek
-IsFull()
-IsEmpty()

38
Q

Errors with stacks and queues

A

-if an item is added/pushed to a queue or stack when there is no more space, an overflow error occurs
-if an item is removed/popped from a queue or stack when there are no items in the data structure, an underflow error occurs

39
Q

Describe a graph

A

An abstract data structure consisting of nodes(or vertices) and edges (or arcs).

40
Q

Describe a weighted graph

A

A weighted graph has values assigned to the edges between nodes.

41
Q

Describe a directed graph

A

Edges imply direction using arrows between nodes

42
Q

What is an adjacency matrix?

A

A grid that assigns a row and a column to each node. If an edge exists a one is placed, if not a 0. For weighted a graphs, the value of an edge can be placed instead of a 1 and infinity instead of 0.

43
Q

What is an adjacency list?

A

Each node is listed, with each node it has an edge with listed next to it.

44
Q

Disadvantage of adjacency matrix

A

Memory inefficient, stored every possible edge between nodes, even ones without edges. Almost half of the matrix is repeated data.

45
Q

Adjacency matrix advantage

A

Time efficient. Allows edge to be queried quickly, just by looking up its row and column

46
Q

Adjacency list advantage

A

Memory efficient, only stores edges that exist.

47
Q

Adjacency list disadvantage

A

Time inefficient. Each item in the list must be searched sequentially until the desired edge is found.

48
Q

In what situations should a matrix or a list be used?

A

Matrix for dense graphs with many edges, lists for sparse graphs with few edges.

49
Q

Describe three qualities of a tree

A

-connected
-undirected
-no cycles(circles)

50
Q

Define a rooted tree

A

A tree with a root node from which other nodes stem. Contains parent,child nodes and leaf nodes. A node can be both a child and a leaf, a parent and child or a root and a parent node.

51
Q

Define a binary tree

A

A rooted tree where each parent has no more than two child nodes.

52
Q

Describe a use of a rooted tree

A

-file systems on a computer hard drive

53
Q

Time complexity of a hash table

A

O(1)

54
Q

Describe the concept of a hashing algorithm (4)

A

-takes an input and returns a hash
-hash is unique to the input
-hash cannot be reversed to retrieve the input value
-hashing algorithms often include MOD function

55
Q

Describe the process of RECORDING values in a hash table

A

-the value being stored in the table is hashed, to produce a key.
-the value is then stored, alonside the key, in the table.

56
Q

Describe the process of RETRIEVING values from a hash table.

A

-the value being looked up is hashed to produce the key.
-the table is queried with the key generated and the information is located

57
Q

What happens if two different values produce the same hash value?

A

-COLLISION
-in a poorly designed hash table, data is overwritten
-rehashing can be used to generate a different position in the table: commonly searching for the next available spot.
-when this rehashing has occurred, the position is found and then each corresponding value is queried until the correct information is found.

58
Q

Describe a dictionary

A

-A collection of key value pairs
-a value is accessed by its key

59
Q

Vector addition can be completed in two ways:

A

-with arrows, tip to tail.
-adding each component

60
Q

What does scalar multiplication affect?

A

Magnitude, not direction

61
Q

Describe the convex combination of vectors:

A

for two vectors, a and b, convex combination is ax + by.

62
Q

Describe the dot/scalar product

A

A single number derived from the components of the vectors, determine the angle between two vectors.

63
Q

Perform the dot product (scalar product) on (12,3) (5,8).

A

(12 x 5) + (3 x 8) = 84

Computing (14 decks)

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