data structures 2

Question 1

graph

Answer 1

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

Question 2

undirected graph

Answer 2

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

Question 3

directed/ digraph

Answer 3

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

Question 4

weighted edges

Answer 4

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

Question 5

computer needs to represent connections and weighting in a ___ representation

Answer 5

structured and numerical

Question 6

ways of implementing a graph

Answer 6

adjacency matrix and adjacency list

Question 7

adjacency matrix

Answer 7

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

Question 8

adv/disadv adjacency matrix

Answer 8

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

Question 9

adjacency list

Answer 9

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

Question 10

adv adjacency list

Answer 10

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

Question 11

depth first traversal

Answer 11

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

Question 12

breadth first search/traversal

Answer 12

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

Question 13

applications of graphs

Answer 13

• 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

Question 14

tree

Answer 14

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

Question 15

uses of trees

Answer 15

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

Question 16

rooted tree

Answer 16

a tree with a root

Question 17

tree node

Answer 17

contains tree data

Question 18

tree edge

Answer 18

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

Question 19

root of tree

Answer 19

only node with no incoming edges

Question 20

tree children

Answer 20

set of nodes that have incoming edges from the same node

Question 21

tree parent

Answer 21

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

Question 22

subtree

Answer 22

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

Question 23

leaf node

Answer 23

node with no children

Question 24

rooted tree in terms of graphs

Answer 24

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.

Question 25

binary tree

Answer 25

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

Question 26

binary search tree

Answer 26

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

Question 27

ways of traversing a tree. The names refer to...

Answer 27

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

Question 28

pre order

Answer 28

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

Question 29

in order traversal

Answer 29

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

Question 30

post order traveral

Answer 30

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

Question 31

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

Answer 31

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

Question 32

in order traversal pseudocode

Answer 32

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

Question 33

post order and pre order traversal pseudocode

Answer 33

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