1.4.2 Data Structures Flashcards

You may prefer our related Brainscape-certified flashcards:
1
Q

1.4.2 A)
What is an array
And what are the different types of arrays

A

An ordered finite set of elements of a single data type.

A 1D array is an linear array always zero indexed

A 2D array can be like a table or spreadsheet you go up and down the toes then across the columns to find a given position

A 3D array can be a visualised as multiple 2D arrays example : print(array[x,y,z]) where x = the array number , y = row , z= column

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

1.4.2 A)
What is a record

A

A row in a file, made up of values from fields the variable must be declared

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

1.4.2 A)
What is a list

A

A data structure consisting of ordered items where items can occur more than once. They can contain multiple data types.

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

1.4.2 A)
How to access a list

A

Similar to 1D array in his they can be access, however values stored non contagiously meaning they don’t need to be next to eachother In memory

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

1.4.2 A)
Operations of a list

A

IsEmpty()
Append(value)
Remove(value)
Search(value)
Length()
Index(value)
Insert(pos,value)
Pop()
Pop(pos)

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

1.4.2 A)
What is a tuple?

A

An ordered set of values of any types. It’s immutable which means cannot be changed elements can’t be added or removed once it’s created.
Attempting to add or remove will cause an error

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

1.4.2 B)
What is a stack
What is a stack used for

A

Last in first out (LIFO) data structure.
Used as a undo / reverse action

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

1.4.2 B)
What are the two types of stacks

A

Static or dynamic
If max size required is known in advance use static as it’s easier to implement and make more efficient use of memory.

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

1.4.2 B)
How are stacks implemented

A

Using a pointer which check top of the stack where next piece of data will be inserted

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

1.4.2 B)
What are the operation of a stack

A

IsEmpty()
Push(value) - adds a new value to end of list need to check list is not full
Peek() - returns top value make sure stack isn’t empty
Pop() same as peek but removed value
Size()
IsFull()

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

1.4.2 B)
What is a queue

A

First in first out (FIFO) data structure

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

1.4.2 B)
What are queues used for

A

Printers linear queue consisting of an array

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

1.4.2 B)
How is data added / removed from a queue

A

Items added to the next available
Space starting from the front. Items are removed from the front. Used two pointers one at front and one at back.

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

1.4.2 B)
What makes linear queues ineffective

A

As items are removed address cannot be reused in efficient use of space

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

1.4.2 B)
How can queues become more efficient

A

Circular queues.
When the rear pointer = max size of the array it can be looped around to the front of the array uses space more efficiently but harder to implement
Only works if front of queue is empty

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

1.4.2 B)
Operation for circular queue

A

EnQueue() - Adds new item to end of queue. Incriminating back pointer by one
DeQueue() - removes item from front of the queue incrementing front pointer by one
IsEmpty ()
IsFull()

17
Q

1.4.2 B)
What is a linked list

A

Dynamic data structure uses to hold an ordered Sequence. Don’t have to be in contiguous data location. Each item is a node containing data field along side a link or pointer

18
Q

1.4.2 B)
How can linked list be demonstrated

A

Table with index data and pointer
Data field contains value of actual data
Pointer field contains the address of the next item in the list

19
Q

1.4.2 B)
What other variables do linked list contain

A

The start or the first item in the list and also next free stores the index of the next available pos

20
Q

1.4.2 B)
How to add a new value to the end of the linked list

A

1) add the new value to end of linked list and update “next free “ pointer
2) pointer field of previous last value is updated to point to the new value
3) the pointer field of the new value is updated

21
Q

1.4.2 B)
Removing a node from a linked list

A

Update the pointer so previous pointer is not pointing to empty node

22
Q

1.4.2 B)
Adv of linked list

A

Values can be easily added or removed by editing pointer

23
Q

1.4.2 B)
Dadv of linked list

A

1) nodes is not truly removed from list but just ignored this is a waste of memory
2) as items stored in sequence cannot be individually access like an array
3) more space then an array as needs to store pointers asw

24
Q

1.4.2 B)
What is a graph
What are the types of graphs
What can graphs be used for / their adv

A

A set of vertices connected edges / arcs
Directed - can only be traveled in one direction
Undirected
Weighted - cost attached to each edge

Can be used to find the shortest path and are easy way to understand complex data

25
Q

1.4.2 B)
How are computers able to process graphs
And there adv

A

Adjacency matrix ( two way table)
Quicker access time easy to add nodes
Adjacency list
More space eff for large networks

26
Q

1.4.2 B)
How can you traverse a graph

A

Breath first search (BFS) & Depth first search ( DFS)

27
Q

1.4.2 B)
What is BFS and how does it work

A

Is a node based method of finding the shortest path though a graph
Uses a queue first in first out method
One node is selected visited and marked then adjacent node

28
Q

1.4.2 B)
The steps for BFS

A

1) set root vertex as the current vertex
2) add current vertex to the list of the visited vertex if it’s not on the list
3) for every edge connect to try r vertex if not already visited
A) enqeue the linked vertex
B) add it too visited list
4) dequeue and set the vertex removed as current
5) repeat from step 2 until queue empty
6) output all visited vertices

29
Q

1.4.2 B)
How does DSF work

A

Uses stacks LIFO method
Visited nodes pushed into the stack
When no nodes left to visit nodes are popped off the stack

30
Q

1.4.2 B)
Steps of BFS

A

1) step the root node as the current node
2) add the current node to the list of visited node if isn’t already in the list
3) for every edge connected to the node if the connected node is not in the visited list
4) pop stack and set the removed item as current node
5) repeated from 2 until no nodes left and output

31
Q

1.4.2 B)
BFS v DFS

A

BFS
Queue finds shortest path of an unweighted graph
Good for close solutions
Not good for puzzles and problems solving

DFS

Stack
May traverse though more edges
Suitable for far solutions and problem solving

32
Q

1.4.2 B)
What is a tree
Properties of a tree

A

A connected form of a graph have a root node which is the top node in any tree

Node - an item in the tree
Edge - connect two nodes together aka branch or arc
Root - single node without incoming nodes
Sub tree - subsection of tree consisting of a parent and all its children
Leaf - node without any children

33
Q

1.4.2 B)
What common data structure is used with a tree

A

Binary tree each node has max of two children used to represent info in binary search. Most commonly using left and right pointers implemented using 2D array

34
Q

1.4.2 B)
Method of traversing a binary tree

A

Pre order
In order
Post order

35
Q

1.4.2 B)
Explain pre order traversal

A

Follow the order root node > left subtree > right subtree
Uses in programming languages where operation written before value “A+B” would be written as “+AB “

36
Q

1.4.2 B)
Explain in order traversal

A

Left subtree > root node > right subtree
Useful for traversing in sequential order

37
Q

1.4.2 B)
Explain post order traversal

A

Left subtree > right subtree > root node

38
Q

1.4.2 B)
How to add data to a tree

A

1) check there is a free memory space for a new node if not output an error
2) create a new node and inset data into it
3) if tree empty new node becomes first node
4) if not

  • follow left or right pointer depending on if it’s > or < current node
  • u till leaf node is teachers if new node > leaf put new node in its right
  • if leaf > new nodr put new node in the left
39
Q

1.4.2 B)
How to remove an node from a tree

A

1) start at the root node and set it as the current node
2) while the current node is not the one to be deleted set previous node to the same as current node
Follow the pointer to where the node to be deleted is set new node to current

If node has no children
3) set left or right pointer of previous node to null. Left or right depends on if greater or less then