fundamentals of data structure Flashcards

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

what is a static data structure

A
  • a data structure fixed in size which cannot increase in size or free up memory while the programming is running.
    e. g. an array
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

what is a dynamic data structure

A
  • a collection of data in memory which can increase or decrease in size using heap
  • heap allocates and de-allocates space as its needed
    e. g. linked list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what is a queue

A
  • a first in first out (FIFO) data structure.
  • elements are added to the end of the queue and removed form the front.
  • this sequence is determined by the order they are placed in the queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

what is a linear queue

A
  • a queue implemented with pointers to the front and rear of the queue.
  • rear points to the last item in queue and front points to the first
  • an integer holding the arrays max size is created
  • a variable holding the number of current items is created
  • items cannot be added to the front even if those elements are free
  • they are added to the back until the rear pointer points to the last element in queue
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

what is a circular queue

A

-a queue where the rear pointer points to the fist element when another item is added if the first element is free and the array is full

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

what is a priority queue

A
  • a queue where items are removed from the front but their place in queue is determined by priority.
  • this makes it possible for items to join the front of the queue.
  • this can be implemented by checking each new items priority against the the current
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

what is a stack

A
  • a last in, first out(LIFO) data structure

- items are added to the top and removed form the top

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

name 4 uses for stacks

A
  • calculations
  • subroutines: hold and return memory addresses when subroutines are called
  • browsers: hold webpages allowing you to move back and forth between them
  • undo: last operation is popped from the stack and undone
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

name 5 stack operations

A
  • push(item) :adds new item to the top of the stack
  • pop() :removes item form the top of the stack
  • peek() : returns item on the top of the stack but does not pop it
  • isEmpty() : checks if stack is empty
  • isFull() : checks if stack is full
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

name 3 uses of a queue

A
  • print jobs: first jobs put in are printed first.
  • character typed: held in queue on keyboard buffer.
  • simulation problems: customers arriving at checkouts
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

name 4 queue operations

A
  • enQueue(item) :adds new item to the end of the queue
  • deQueue() :removes item form the front of the queue
  • isEmpty() :checks if queue is empty
  • isFull() :checks if queue is full
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

what are stack underflow and stack overflow

A
  • stacks have a maximum size as memory cannot grow
  • if a stack is full and an attempt to push an item is made an overflow error will occur
  • if a stack is empty and an attempt to pop an item is made an underflow error will occur
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

what is a call stack

A

a stack data structure is used to store information about a subroutine while the program is running

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

what are 3 functions of a call stack

A
  • holding the return address: keeping track of the address of the instruction that control should return to
  • holding parameters:
  • local variables: each call to a subroutine gets its own space for its local variables without using heap space
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

what is a graph

A

-a data structure used to

represent more complex relationships. using a set of vertices/nodes connected by edges/arcs

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

directed graph vs undirected graph

A
  • undirected: the edges are bi-directional

- directed: the edges are one-way

17
Q

what is a weighted graph

A

-a graph where the edges show the cost of moving from one vertex to another

18
Q

what is an adjacency matrix (3)

A
  • a way to implement a graph using a two dimensional array to store the information
  • each row and column represent a node
  • if the graph is weighted the value will be stored if not 1s will be used.
19
Q

what is an adjacency list

A
  • a more space efficient way to implement a graph using a list.
  • a list of all the nodes which point to the nodes they are directly linked with. the weight can be held next to each linked node
20
Q

5 applications of graphs

A
  • computer networks - weight=bandwidth
  • roads between towns - weights=distance
  • tasks in projects
  • states in finite state machine
  • web links and pages
21
Q

what is a tree

A

a connected undirected graph with no cycles

22
Q

name the 7 parts of a tree

A
  • node: contains tree data
    edge: connects 2 nodes
  • root: only node with no incoming edges or parent
  • child: set of nodes with the same parent/ incoming edges form the same node
  • parent: connects with outgoing edges
  • subtree: set of nodes made of a parent and descendent
  • leaf node: a node with no children
23
Q

what is a rooted tree

A

a tree with only one root node ( a node with no parents)

24
Q

3 uses of a rooted tree

A
  • manipulating hierarchical data
  • making information easier to search
  • manipulating sorted lists of data
25
Q

what is a binary tree

A

a rooted tree with a maximum of two children per parent which is used to search for items quickly

26
Q

benefits of binary trees

A
  • easy to search for a specific item
  • easy to add an item
  • easy to print the whole tree in sequence
27
Q

what are the three ways of traversing a binary tree

A
  • pre order traversal: output data as you pass its left
  • in order traversal: output data as you pass under it
  • post order traversal: output data as you pass its right
28
Q

how to implement a binary tree

A

a binary tree is implemented using an array of records with each node consisting of a left pointer, the data item and a right pointer

29
Q

what can 1-D arrays be used to represent

A

vectors
each element of the array hold a sequential number in the vector

array
vector[0]= 2.0
vector[1]= 3.14159
vector[2]= 1.0
vector[3]=2.71
30
Q

what is an array

A

an array is a finite ordered set of elements of the same type

31
Q

what is a 1 dimensional array

A

a 1 dimensional array can be thought of as a simple table

32
Q

what is a 2 dimensional array

A

a 2 dimensional array has 2 dimensions.

can be thought of as having a x and y axis

33
Q

what is a multi dimensional array or an array of n dimensions

A

an array that is a set of elements of the same type indexed by a tuple of n integers.

a tuple is an ordered list of elements

34
Q

adjacency list pros and cons

A

con: Time efficient
Slow to query, as each item in a list must
be searched sequentially until the desired
edge is found

pro: Memory efficient
Only stores the edges that exist in the
graph.

Well suited to sparse graphs, where there
are few edges.

35
Q

adjacency matrix pros and cons

A

con: Memory inefficient.
Stores every possible edge between
nodes, even those that don’t exist.
Almost half of the matrix is repeated data.

pro: Time efficient
Allows a specific edge to be queried very
quickly, as it can be looked up by its row
and column.

Well suited to dense graphs, where there
are a large number of edges.

36
Q

pros, cons and best use of static data structure

A

pros: doesn’t need to store pointers
cons: can end up with empty element which is memory inefficient

best use: when the amount of data is known

37
Q

pros, cons and best use of dynamic data structure

A

pros: can increase in size

cons: has to store pointers which takes up memory
- complicated to keep track off

best use: when there is no max size of the data structure