Data structures Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q
  1. How to find an element in a 2D array?
A
  1. To find an element in a 2D arrays you look at first the row, then the column
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q
  1. How to find an element in a 3D array?
A
  1. To find an element in a 3D arrays you look at the number array (z), the row (y), and then the column(x)
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q
  1. What is a record?
A
  1. A record is referred as a row in a file and it is made up of fields, commonly used in databases
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q
  1. How is a record declared?
A
  1. A record is declared in the following way:
    fighterDataType = record
    integer ID
    String
    FirstName
    Surname
    End record
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q
  1. How are list values stored in terms of order?
A
  1. List values are stored non-contiguously, i.e. not stored next to each other in memory
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q
  1. How many datatypes can a list contain?
A
  1. List can contain values of more than one datatype
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q
  1. What is a tuple?
A
  1. A tuple is an immutable object composed of an ordered set of values of any type
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q
  1. What is a stack?
A
  1. A stack is LIFO data structure, where items can be only added or removed from the top of the stack, that is pointed by a pointer.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q
  1. What is a stack used for?
A
  1. A stack is used to reverse an action, such as go back to a webpage in a web browser
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q
  1. How are stacks implemented?
A
  1. Stacks are implemented using a pointer which points to the top of the stack where the next data will be inserted
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q
  1. Show the code for push(value)
A
  1. Push(value) –> adds a value, but checks if stack is full before pushing
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q
  1. Show the code for peek()
A
  1. Peek() –> returns the value at the top of the stack, first checks if stack is empty
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q
  1. Show the code for pop() for a stack
A
  1. Pop() –> removes and returns the value at the top of the stack, first checks if the stack is empty by looking at the value of the top pointer
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q
  1. Function to show that stack is full?
A
  1. isFull()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q
  1. Function to show that stack is empty?
A
  1. isEmpty()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q
  1. Function to show that stack’s size ?
A
  1. Size()
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q
  1. What is an overflow?
A
  1. Trying to push on to a full stack is an overflow
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q
  1. What is an underflow?
A
  1. If you try to pop on an empty stack then it is an underflow
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q
  1. What is a queue?
A
  1. A queue is a FIFO data structure, commonly used in printers, keyboards, and simulators
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q
  1. What are the different types of queues?
A
  1. There are different types of queues: linear queue, circular queue
21
Q
  1. What is a linear queue?
A
  1. Linear queue is a data structure consisting of an array, making use of 2 pointers: one pointing to the front of the queue and the other to the back of the queue where the next data can be added
22
Q
  1. Show the code for enQueue()
A
  1. enQueue(item) –> adds items to the end of the queue
23
Q
  1. Show the code for deQueue()
A
  1. deQueue(item)/ deQueue() –> removes items from the front of the queue
24
Q
  1. Why is a linear queue ineffective?
A
  1. A linear queue is ineffective because there are spaces/addresses in the queue that can never be used again
25
Q
  1. What is a circular queue?
A
  1. A circular queue is a FIFO data structure that is harder to implement but more effective in terms of using vacated spaces in an array, by making the rear pointer to loop back to the start of the queue once the last space in the queue has been filled, provided that the beginning space of the queue is empty
26
Q
  1. What functions for a circular queue are not implemented the same as for a linear queue, and how do they differ?
A
  1. The same functions that a linear queue uses so does a circular queue does, with the exception:
    a. deQueue(item)/ deQueue() –> removes items from the front of the queue, increments the front pointer
    b. IsEmpty() –> by comparing the front pointer and the rear pointer
    c. IsFull() –> by comparing the rear pointer to the size of the queue
27
Q

What’s the purpose of a Sorted binary trees?

A

sorts text or numbers by inserting at the left if value is less than the value at the top of the branch and right if value is greater than the value at the top of the branch.

for example the list [3, 5, 1] will be in a sorted binary tree with 3 at the centre 5 at the right of 3 and 1 at the left of 3

28
Q

Explain how you implement a post order traversal of a depth first tree traversal

A

first you recursively traverse its left subtree, until you stop and then you go back at N
then you recursively traverse its right subtree, until you stop and then you go back at N
Finally N processes itself

29
Q

Explain how you implement a post order traversal of a breadth first tree traversal

A

you start from the top and visit both child branches from left to right, where going down by a branch signals the beginning of a new layer

30
Q

What is an array ?

A

An array is an ordered, finite set of elements of a single type.

31
Q

How can a field in the record can be identified?

A

Each field in the record can be identified by recordName.fieldName.

32
Q

How can a new record be created once it has already being declared?

A

When creating a record, a variable must first be declared:
fighter : fighterDataType

33
Q

What is a list ?

A

A list is a data structure consisting of a number of ordered items where the items can occur more than once or be of different data types.

34
Q

All list’s operations are

A

isEmpty()
append(value)
remove(value)
search(value)
length()
index(value)
insert(position, value)
pop()
pop(position)

35
Q

What is a linked list?

A

A linked list is a dynamic data structure used to hold an ordered sequence. Each item is called a node, and contains a data field alongside another address called a link or pointer field.

36
Q

What is a graph

A

A graph is a set of vertices/nodes connected by edges/arcs.

37
Q

Graphs can be placed into the following categories:

A
  • Directed Graph:
  • Undirected Graph:
  • Weighted Graph:
38
Q

What is the characteristic that distinguish a directed graph from the others?

A

The edges can only be traversed in one direction.

39
Q

What is the characteristic that distinguish a undirected graph from the others?

A

The edges can be traversed in both directions.

40
Q

What is the characteristic that distinguish a weighted graph from the others?

A

A cost is attached to each edge.

41
Q

Computers are able to process graphs by…

A

using an adjacency matrix or an adjacency list.

42
Q

An adjacency matrix can be represented as a…

A

a table

43
Q

An adjacency list can be represented as a…

A

linear array

44
Q

Adjacency Matrix Advantages

A

Convenient to work with due to quicker access times
Easy to add nodes

45
Q

Adjacency List Advantages

A

More space efficient for large, sparse networks

46
Q

A stack can be implemented as either a…

A

static structure or a dynamic structure

47
Q

Where the maximum size required is known in advance, static stacks are preferred, as they are….

A

easier to implement and make more efficient use of memory.

48
Q

Stack operations’ list

A

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