Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

#A2 Computing > Data Structures and algorithms > Flashcards

Data Structures and algorithms Flashcards

1
Q

What are the types of list?

A
  1. Linear list - starage order is logical order (can be sorted and unsorted)
  2. Linked list - stores pointers to next location
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

what lists can be searched using binary search?

A
  • Sorted linear list
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Advantages/disadvantages of linear lists?

A
  • 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.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

What must be checked when inserting into a linear list?

A

that the list isnt full

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

What is meant by the term dynamic structure?

A

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

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

What is the heap?

A

the memory locations available to application programs for dynamic allocation

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

how is new memory allocated at runtime?

A

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

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

What is the stack?

A

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

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

Advantages and disadvanteges of linked lists?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Stuff needed for a stack?

A
  • Top pointer
  • Pop (removes top item)
  • Push (adds new item)
  • Isempty
  • Create
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

what is a stack known as?

A

last in first out data type

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

Uses for a stack?

A
  • Balancing brackets
  • Reverse polish notation
  • Funtion calls - stores the variable values, current position, register values.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

Advantages of reverse polish notation?

A
  • Simpler for macine to evaluate
  • Do not need brackets
  • no need for order of operations
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

what is a queue known as

A

first in first out data type

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

Stuff needed for a queue?

A
  • Add
  • remove
  • isfull/isempty
  • Rear pointer - points to where you are adding to
  • Front pointer - points to where you are removing from
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

what is a priority queue

A

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

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

Whats a circular queue?

A

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.

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

what is a model?

A

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

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

Whats an entities attributes?

A

A property of an object.

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

Simulating a queue

A

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

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

whats a psudo random number generator?

A

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)

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

What is a recursive routine

A

a routine defined in terms of itself

23
Q

Pros and cons of recursion

A
  • 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
24
Q

Types of sorting algothims and how they work

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

improvements to bubblesort

A
  • Doesnt compare the sorted part of the list
  • stops loop when list is sorted
26
Q

Complexity of bubble, selectiona and insertion sort

A

O(n2)

27
Q

Ways to compare complexity of aproblem?

A
  • time complexity
  • memory complexity
28
Q

What is problem complexity

and what is algothrim complexity

A
  • 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.
29
Q

Complexity of linear search?

A

O(n)

30
Q

complexitiy of binary search?

A

O(logn)

31
Q

What is an algothritm?

A

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

32
Q

Why dont you use seconds for mearing complexity

A

as the time will be dependant on the system speed

33
Q

What is a graph?

A

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

34
Q

Whats the degree of a vertex?

A

the number of neighbours for that vertex.

35
Q

what can graphs have?

A
  • weighted edges
  • Directed edges
36
Q

Advantages of a adjacency matic over adjacency list?

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

disadvantages of adjaceny matrix over adjaceny list

A
  • less compact
  • harder for humans to reads
  • needs more memory for sparse graphs
38
Q

What are adjacency matirxes and lists?

A

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

39
Q

What is a tree?

A

a connected undirected graph with no cycles

40
Q

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

A

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

41
Q

how are trees labled?

A

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

42
Q

difference between multiway tree and binary tree?

A

multiway can have many desendants per vertex.

Binaray tree can only have 2

43
Q

What is pre order tree traversal?

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

44
Q

what is in order tree traversal?

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

45
Q

what is post order tree traversal?

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

46
Q

What is breadth first traversal?

A

spreads out from the node.

47
Q

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

A
  • 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.
48
Q

2 ways of storing a binary tree

A
  • 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.
49
Q

What is an intractable problem?

A

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

50
Q

What is a heuristic algothrithm?

A

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.

51
Q

what is a undecidable problem?

A

describes a descion type algothrithmic problem that is non computable

52
Q

what is a non computable problem?

A

describes an algothrithmic problem that has no algothrithm

53
Q

what is the halting problem

A

a noncomputable problem

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

54
Q

what is an algothrithmic problem?

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

#A2 Computing (8 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions