data structures 2 Flashcards

1
Q

graph

A

set of vertices or nodes connected by weighted or unweighted edges or arcs which are one or two way

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

undirected graph

A

set of vertices or nodes connected by weighted/unweighted edges or arcs which are bidirectional

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

directed/ digraph

A

set of vertices or nodes connected by weighted/unweighted edges or arcs which are all one way

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

weighted edges

A

there is a cost to go from one to another node eg distance

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

computer needs to represent connections and weighting in a ___ representation

A

structured and numerical

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

ways of implementing a graph

A

adjacency matrix and adjacency list

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

adjacency matrix

A

uses a 2D array, each row/column represents a node. A value in the intersection of (i,j) indicates edge connecting node i and node j.
Value stored in the cell is the weighting. If graph is unweighted then a 1 is stored in the cell.
Undirected graphs are symmetric and v.v

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

adv/disadv adjacency matrix

A

ADV: convenient, easy to add an edge
DISADV: if many nodes but sparse graph with few edges means most cells are empty: larger the graph the more memory wasted
if using a static 2D array, it is harder to add or delete nodes

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

adjacency list

A

a list of all the nodes is created, with all the nodes pointing to a list of all adjacent nodes (adjacency lists) to which it is directly linked. If weighted, adjacency list can be implemented as a dictionary: key= node being linked to, value= edge weight. If unweighted, dictionary data structure not necessary

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

adv adjacency list

A

uses much less memory to represent a sparsely connected graph: space efficient

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

depth first traversal

A

go as far down one route as possible before backtracking and taking next route

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

breadth first search/traversal

A

visit all the neighbours of a node then all the neighbours of the nodes just visited, before moving further away from the start node

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

applications of graphs

A
  • computer networks: node representing computers and weighted edges representing bandwidth between them
  • web pages and links eg Google PageRank
  • roads eg nodes: towns edges: distance, fare, time
  • states in a finite state machine
  • tasks in a project where some have to be completed before others
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

tree

A

non linear data structure for storing hierarchical data, made of a number of nodes and outgoing edges

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

uses of trees

A

storing hierarchical data eg game moves/folder structure
to make info easy to search
manipulating sorted lists of data

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

rooted tree

A

a tree with a root

17
Q

tree node

A

contains tree data

18
Q

tree edge

A

an edge connects two nodes; every node except root node has an incoming edge from exactly one other node

19
Q

root of tree

A

only node with no incoming edges

20
Q

tree children

A

set of nodes that have incoming edges from the same node

21
Q

tree parent

A

a node is a parent of all the nodes it connects to with outgoing edges

22
Q

subtree

A

the set of nodes compromised of a parent and all descendants of the parent. it can be a leaf

23
Q

leaf node

A

node with no children

24
Q

rooted tree in terms of graphs

A

its a connected graph. A node can only be connected to one parent node and to its children. It has no CYCLES as no edges between children or branches.

25
Q

binary tree

A

a rooted tree in which each node has a maximum of two children

26
Q

binary search tree

A

binary tree which holds items in a way they can easily and quickly be searched and items added, and the whole tree can be printed out in sequence

27
Q

ways of traversing a tree. The names refer to…

A

pre order
in order
post order
The names refer to whether the root of each subtree is visited before, between or after both branches have been traversed

28
Q

pre order

A

root, left, right. Used in prefix notation eg in functional programming notation ie x = sum a b (sum being root), used in some compilers and calculators

29
Q

in order traversal

A

left root right. used in infix notation eg a + b, outputs in alphabetical order

30
Q

post order traveral

A

left right root. used in post-fix notation, reverse polish notation- used by compilers to evaluate expressions

31
Q

you implement a binary search tree using..
tree[0] = 1, 17, 4 means..
pointer of ‘-1’ means..

A

array of records, list of tuples, 3 separate lists or arrays (for each pointer and the data items).
tree[0] = 1, 17, 4 means the first node holds data ‘17’ and has tree[1] on left and tree[4] on right.
Pointer of -1 is a rogue value ie no child on relevant side

32
Q

in order traversal pseudocode

A
procedure inorderTraverse(p)
  if tree[p].left != -1
    inorderTraverse(tree[p].left)
  endif
  print(tree[p].data);
  if tree[p].right != -1
    inorderTraverse(tree[p].right)
  endif
endprocedure
33
Q

post order and pre order traversal pseudocode

A

same as in order traversal but for
post order: tree[p].data is printed after left and right
pre order: tree[p].data is printed before left and right