Fs Of Data Structures

Question 1

What are the 4 categories for data types?

Answer 1

Strong types
Static types
Dynamic types
Abstract types

Question 2

Define strong data types.

Answer 2

Standard data types; integer, character etc. They’re the basis for all other types, and a fixed amount of memory is defined.

Question 3

Define static data types?

Answer 3

Those that require a fixed amount of memory, such as arrays and sets. But are not included in the pre-defined data types.

Question 4

Define dynamic data types?

Answer 4

Those that may be expanded given the limitation of the memory. For example files and pointers.

Question 5

What are abstract data types

Answer 5

Abstract means they don’t usually exist as a pre-built data structure but instead must be manually built. Such as stacks and queues.

Question 6

What structure does a stack have?

Answer 6

LIFO (last in first out)

Question 7

What sort of structure does a queue have?

Answer 7

FIFO (First in first out)

Question 8

What are the 3 commands used in stacks?

Answer 8

Pushing = adding an item
Popping = taking an item off
Peeking = finds the start (bottom) of the stack

Question 9

What happens to the pointer as an item is pushed or popped?

Answer 9

When an item is popped the pointer moves down.

When an item is pushed the pointer moves up.

Question 10

What are stack overflow and underflow errors?

Answer 10

Overflow - When an item is pushed onto a full stack.

Underflow - When an item is popped from an empty stack.

Question 11

What is an advantage and disadvantage of implementing a queue as an array.

Answer 11

Advantage - faster and more memory efficient than a linked list.
Disadvantage - fixed size

Question 12

What is an advantage and disadvantage to implementing a queue as a linked list?

Answer 12

Advantage - Dynamic size. Means no wasted memory.

Disadvantage - Not as memory efficient as an array. Requires more memory per element.

Question 13

What operations are needed in a queue?

Answer 13

Add item 
Remove item 
Front item
Is queue empty
Is queue full

Question 14

What are the 3 types of queue?

Answer 14

Linear queue
Circular queue
Priority queue

Question 15

Define a linear queue.

Answer 15

A queue with a fixed amount of memory. Usually implemented using a 1D array. Items added to the back and removed from the front, memory can not be re-used.

Question 16

Define a circular queue.

Answer 16

A queue with a fixed amount of memory.
The back of is connected to the front.
Memory can be re-used.
This is often used to store data waiting to be transferred from one device to another.

Question 17

Define a priority queue.

Answer 17

Elements in the queue are ordered into levels of priority.

Question 18

What are vertices in a graph?

Answer 18

Objects in the graph (represented by a circle)

Question 19

What is an edge in a graph?

Answer 19

A connection between two vertices (or nodes)

Question 20

What does neighbour mean (graphs)?

Answer 20

A vertex connected to another vertex via an edge is a neighbour.

Question 21

What is the degree of a vertex (graphs)?

Answer 21

The number of neighbours it has.

Question 22

What are some uses of graphs?

Answer 22

Mapping 
Game theory 
Electrical circuits 
Social networks 
The internet

Question 23

What are undirected graphs?

Answer 23

Graphs without arrows (direction)

Question 24

What is a weighted/labelled graph?

Answer 24

A graph with values attached to edges (usually numerical)

Question 25

What is a directed graph?

Answer 25

A diagram with arrows (direction)

Question 26

What is a graph?

Answer 26

A graph is an abstract data type used to model the relationship between 2 or more vertices.

Question 27

What are the two ways of storing a graph of a computer?

Answer 27

Adjacency lists

Adjacency matrices

Question 28

How do adjacency lists work?

Answer 28

By recording the relationship between all relevant vertices.

Only records vertices with edges between them.

Question 29

What are all separate values separated by on an adjacency list?

Answer 29

;

For example: D,15; H,10; C,20

Question 30

What is an advantage and disadvantage of an adjacency list?

Answer 30

Advantage - Good for graphs with fewer edges than nodes.

Disadvantage- Bad for graphs with more edges than nodes.

Question 31

How do adjacency matrices work?

Answer 31

By recording the relationship between vertices in 2D array or grid populated with 1s or 0s.
An adjacency matrix also records when there isn’t an edge between vertices.

Question 32

What is an advantage and disadvantage of an adjacency matrix?

Answer 32

Advantage - Good for graphs with more edges than nodes.

Disadvantage - Bad for graphs with less edges than nodes.

Question 33

Adjacency List vs matrix?

Answer 33

List:
Stores data only when there is edge = less memory.
Has to check if adjacencies exist = more time.
Quicker for sparse graphs.

Matrix:
Stores data for every combination = more memory
Because of ^ easier to ID adjacencies = less time
Quicker for dense graphs

Question 34

What is a tree?

Answer 34

An abstract data structure with a structure similar to a graph but with a hierarchical structure.

Question 35

How does a tree differ from a graph?

Answer 35

It has a hierarchical structure.
It is undirected.
It has no loops.

Question 36

What is a rooted tree?

Answer 36

A tree with one vertex designed as the root in which all other vertices spread out from.

Question 37

How do you construct a binary tree?

Answer 37

1. Create a root node
2. Insert data into root node
3. Compare new item with root node
4. If it’s > root follow the right pointer otherwise follow the left
5. Compare until left of right pointer is null
6. Create node, insert right and left pointers and set them to null
7. Connect the node to the tree

Question 38

What methods can be used to traverse a tree?

Answer 38

Breadth first

Depth first

Question 39

What methods can be used to traverse a tree?

Answer 39

Breadth first
Depth first
Pre-order
In-order
Post-order

Question 40

What are the four CRUD operations?

Answer 40

Create
Retrieve
Update
Delete

Question 41

What are the four CRUD operations in their SQL and HTTP method format?

Answer 41

(SQL , HTTP):

INSERT , POST
SELECT , GET
UPDATE , PUT
DELETE , DELETE

Question 42

What is a priority queue and how does it work?

Answer 42

It has different points at which items can join according to priority.
They join at the back of their priority section.
If there are no items in correct priority section they join the front of the next lower section.