(2) Fundamentals of Data Structures Flashcards

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

What is data structures?

A

Containers that store and organise data in a specific way

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

What does the following operations do in a stack data structure PUSH, POP, IsEmpty?, IsFull?, Peek

A

Push - Adds a value in the stack
Pop - Removed a value in the stack
Peek - Checks what’s at the top of the stack
IsEmpty? - Checks if the whole stack is empty
IsFull? - Checks if the whole stack is full

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

What is a static data structure with an example?

A

Static data structures have storage size determined before program is run. Has fixed maximum size

Eg an array

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

What is dynamic data structure with an example?

A

Dynamic data structures can grow/shrink during execution

Eg a list

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

What is the advantages and disadvantages of static data structures?

A

+Easy to program
+An array allows random access
+Easy to check for overflows

  • The programmer has to estimate the maximum amount of space that is going to be added
  • Can waste a lot of space
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the advantages and disadvantages of dynamic data structures?

A

+Only uses the space needed at any time
+Makes efficient use of memory

  • Difficult to program
  • Can be slow to add searches
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is abstract data type?

A

Data types which are not defined by their implementation

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

Describe a stack data structure and where is it used?

A
  • Uses Last In First Out (LIFO) to determine when data is executed
  • Uses one pointer at the top of the stack

Used anywhere you need to back track

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

Describe a queue data structure and where is it used?

A
  • Uses a First In First Out rule (FIFO) to determine when data is executed
  • Uses two pointers, one for the front and back of the queue

Eg print jobs waiting to be printed

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

What is a graph data structure?

A

A set of vertices connected by edges. The edges may be one or two way

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

What is a linear queue?

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

What is a circular queue?

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

What is a priority queue and where can it be used?

A

Works the same way as a regular queue however they are ranked by their priority. The highest priority items are at the front of the queue and lowest priority at the back of the queue.

Eg a hospital

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

What is a front and rear pointer?

A

Indicates what’s the first and last element of the queue

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

What is the typical uses of a graph data structure?

A

Internet (Vertices: Web pages, Edges: Hyperlinks)
Social networks (Vertices: People, Edges: Friendships)
Transportation (Vertices: Airports, Edges: Air routes)

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

What two elements make up a graph?

A

Vertices and edges

17
Q

What are neighbours in the graph data structure?

A

Two vertices directly connected

18
Q

What are degrees in the graph data structures?

A

The number of neighbours connected to a vertex

19
Q

What is a weighted/ labelled graph?

A

Graphs where the edges are labelled

20
Q

What is directed graph/ Digraph?

A

A diagram consisting of vertices (circles), joined by directed lines called edges

21
Q

What is a vertex/ node in graphs?

A
22
Q

What is a edge/ arc in graphs?

A
23
Q

What is an undirected graph?

A
24
Q

What are the two ways of representing a graph so that it can be processed by a computer?

A

Adjacency Matrix

Adjacency List

25
Q

What is a adjacency matrix and the advantages and disadvantages?

A

Representing a graph using a two dimensional matrix

26
Q

What is a adjacency list and the advantages and disadvantages?

A

A list used to store which vertices are next to each other