fundamentals of data structure

Question 1

what is a static data structure

Answer 1

• a data structure fixed in size which cannot increase in size or free up memory while the programming is running.
  e. g. an array

Question 2

what is a dynamic data structure

Answer 2

• 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

Question 3

what is a queue

Answer 3

• 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

Question 4

what is a linear queue

Answer 4

• 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

Question 5

what is a circular queue

Answer 5

-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

Question 6

what is a priority queue

Answer 6

• 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

Question 7

what is a stack

Answer 7

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

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

Question 8

name 4 uses for stacks

Answer 8

• 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

Question 9

name 5 stack operations

Answer 9

• 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

Question 10

name 3 uses of a queue

Answer 10

• print jobs: first jobs put in are printed first.
• character typed: held in queue on keyboard buffer.
• simulation problems: customers arriving at checkouts

Question 11

name 4 queue operations

Answer 11

• 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

Question 12

what are stack underflow and stack overflow

Answer 12

• 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

Question 13

what is a call stack

Answer 13

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

Question 14

what are 3 functions of a call stack

Answer 14

• 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

Question 15

what is a graph

Answer 15

-a data structure used to

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

Question 16

directed graph vs undirected graph

Answer 16

• undirected: the edges are bi-directional

- directed: the edges are one-way

Question 17

what is a weighted graph

Answer 17

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

Question 18

what is an adjacency matrix (3)

Answer 18

• 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.

Question 19

what is an adjacency list

Answer 19

• 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

Question 20

5 applications of graphs

Answer 20

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

Question 21

what is a tree

Answer 21

a connected undirected graph with no cycles

Question 22

name the 7 parts of a tree

Answer 22

• 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

Question 23

what is a rooted tree

Answer 23

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

Question 24

3 uses of a rooted tree

Answer 24

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

Question 25

what is a binary tree

Answer 25

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

Question 26

benefits of binary trees

Answer 26

- easy to search for a specific item - easy to add an item - easy to print the whole tree in sequence

Question 27

what are the three ways of traversing a binary tree

Answer 27

- 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

Question 28

how to implement a binary tree

Answer 28

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

Question 29

what can 1-D arrays be used to represent

Answer 29

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 ```

Question 30

what is an array

Answer 30

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

Question 31

what is a 1 dimensional array

Answer 31

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

Question 32

what is a 2 dimensional array

Answer 32

a 2 dimensional array has 2 dimensions. can be thought of as having a x and y axis

Question 33

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

Answer 33

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

Question 34

adjacency list pros and cons

Answer 34

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.

Question 35

adjacency matrix pros and cons

Answer 35

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.

Question 36

pros, cons and best use of static data structure

Answer 36

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

Question 37

pros, cons and best use of dynamic data structure

Answer 37

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