Data Structures and algorithms

Question 1

What are the types of list?

Answer 1

1. Linear list - starage order is logical order (can be sorted and unsorted)
2. Linked list - stores pointers to next location

Question 2

what lists can be searched using binary search?

Answer 2

• Sorted linear list

Question 3

Advantages/disadvantages of linear lists?

Answer 3

• Fast acess time as items are stored consectivly. (direct access)
• Can be sorted and use binary search
• Easy to code
• Static array has fixed size
• Static array wastes memory
• Slow inserting/deletion in a sorted list as items must move.

Question 4

What must be checked when inserting into a linear list?

Answer 4

that the list isnt full

Question 5

What is meant by the term dynamic structure?

Answer 5

memory space is allocated when required. The size of the structure is free to change at runtime.

Question 6

What is the heap?

Answer 6

the memory locations available to application programs for dynamic allocation

Question 7

how is new memory allocated at runtime?

Answer 7

The heap stores the new data, the stack stores the heap loation as a pointer.

Question 8

What is the stack?

Answer 8

used for static memory alocation, has a predefined size . (often stores pointers to the heap )

Question 9

Advantages and disadvanteges of linked lists?

Answer 9

• Memory usage is very efficent
• Inserting and deletion is very efficent as no items are move, just pointers change.
• Acess speed is slower
• Cant do binary search

Question 10

Stuff needed for a stack?

Answer 10

• Top pointer
• Pop (removes top item)
• Push (adds new item)
• Isempty
• Create

Question 11

what is a stack known as?

Answer 11

last in first out data type

Question 12

Uses for a stack?

Answer 12

• Balancing brackets
• Reverse polish notation
• Funtion calls - stores the variable values, current position, register values.

Question 13

Advantages of reverse polish notation?

Answer 13

• Simpler for macine to evaluate
• Do not need brackets
• no need for order of operations

Question 14

what is a queue known as

Answer 14

first in first out data type

Question 15

Stuff needed for a queue?

Answer 15

• Add
• remove
• isfull/isempty
• Rear pointer - points to where you are adding to
• Front pointer - points to where you are removing from

Question 16

what is a priority queue

Answer 16

A queue where certain things added to the queue have prority over other things and go infort of them

Question 17

Whats a circular queue?

Answer 17

If an array is used to store the queue and people leave a full queue, this means that theres no space at the end of the array so it gets added to the start of the array.

Question 18

what is a model?

Answer 18

an abstraction of an entity in the real world/problem. The abstaction is a representation of the problem that leaves out unnessary details.

Question 19

Whats an entities attributes?

Answer 19

A property of an object.

Question 20

Simulating a queue

Answer 20

Needs random number generators for stuff like server time, rate of people arriving.

Question 21

whats a psudo random number generator?

Answer 21

A generator that makes apparently random numbers but the algorithm with the same seed will produce the same number.

(is useful if you want to recreate a simulaton twice)

Question 22

What is a recursive routine

Answer 22

a routine defined in terms of itself

Question 23

Pros and cons of recursion

Answer 23

• concise code
• easier to code some problems
• Can get v slow after many repeat calls
• Infinite reapeats can happen
• Uses more memory to store all the local variable etc

Question 24

Types of sorting algothims and how they work

Answer 24

• Insertion sort - each data item is chose where it goes
• Selection sort - finds smallest first then next smallest
• Bubble sort - compares adjacent data

Question 25

improvements to bubblesort

Answer 25

* Doesnt compare the sorted part of the list * stops loop when list is sorted

Question 26

Complexity of bubble, selectiona and insertion sort

Answer 26

O(n²)

Question 27

Ways to compare complexity of aproblem?

Answer 27

* time complexity * memory complexity

Question 28

What is problem complexity and what is algothrim complexity

Answer 28

* Problem - The best algothrim complexity for that specfic problem. * Algothrithm- The highest (worst case) degree that effects operations in a specific algothrim as data size changes.

Question 29

Complexity of linear search?

Answer 29

O(n)

Question 30

complexitiy of binary search?

Answer 30

O(logn)

Question 31

What is an algothritm?

Answer 31

a sequence of finte instructions for solving a problem, for obtaining a required output for each input. Can be represented by a turing machine.

Question 32

Why dont you use seconds for mearing complexity

Answer 32

as the time will be dependant on the system speed

Question 33

What is a graph?

Answer 33

A diagram consisting of circles (vertices) joined by lines (edges).

Question 34

Whats the degree of a vertex?

Answer 34

the number of neighbours for that vertex.

Question 35

what can graphs have?

Answer 35

* weighted edges * Directed edges

Question 36

Advantages of a adjacency matic over adjacency list?

Answer 36

* Easier for computers to read * will always be the same size * faster to access * better for graphs with many edges * searching is easier

Question 37

disadvantages of adjaceny matrix over adjaceny list

Answer 37

* less compact * harder for humans to reads * needs more memory for sparse graphs

Question 38

What are adjacency matirxes and lists?

Answer 38

Ways of representing a graph so that a computer can process it.

Question 39

What is a tree?

Answer 39

a connected undirected graph with no cycles

Question 40

what is the root of a tree, and the leaf,internal node, and branch?

Answer 40

Root is the vertex chosen to be the start, all edges are directed away from this. Leaf's are the terminal vertexs internal node is a node that isnt a leaf or the root branches connect nodes

Question 41

how are trees labled?

Answer 41

root is level 0, each level down is 1,2,3 etc

Question 42

difference between multiway tree and binary tree?

Answer 42

multiway can have many desendants per vertex. Binaray tree can only have 2

Question 43

What is pre order tree traversal?

Answer 43

* Visit the root (e.g. print the value of the data item at the root) * Traverse the left sub-tree in pre-order * Traverse the right sub-tree in pre-order Prints the data as it meets a node for the first time.

Question 44

what is in order tree traversal?

Answer 44

* Traverse the left sub-tree in in-order * Visit the root * Traverse the right sub-tree in in-order Prints the data when each vertexs descendants have been visited

Question 45

what is post order tree traversal?

Answer 45

* . Traverse the left sub-tree in post-order * Traverse the right sub-tree in post-order * Visit the root Prints the vertexes data when all of that vertexs descentants have been visited.

Question 46

What is breadth first traversal?

Answer 46

spreads out from the node.

Question 47

Advantages of storing ordered list as a binary tree not linked list?

Answer 47

* You can binary search at O(logn) complexity if its balanced * The worst case complexity is O(n) for a completly unbalanced list-(same as linked list) * Can be constructed from any start point.

Question 48

2 ways of storing a binary tree

Answer 48

* an array of records with each record having the data and a left n right pointer. * 3 arrays with each array showing data ,left or right pointer for that index.

Question 49

What is an intractable problem?

Answer 49

The problem is solvable but its impractical as the complextity is above polynomial time.

Question 50

What is a heuristic algothrithm?

Answer 50

Describes an appraoch tha uses expericane to make informed guesses which help to provide a good (not nessesarlity best) solution in below polynomial time to an intracable problem.

Question 51

what is a undecidable problem?

Answer 51

describes a descion type algothrithmic problem that is non computable

Question 52

what is a non computable problem?

Answer 52

describes an algothrithmic problem that has no algothrithm

Question 53

what is the halting problem

Answer 53

a noncomputable problem An algothrithm that would analyse another program to see if it will halt.

Question 54

what is an algothrithmic problem?

Answer 54

* has set of imputs * Outputs as a function of the input * Can be done in finite time and finite resources * halts for all legal inputs with correct anser