data structures 2

Question 1

• How do you test for an empty circular queue?
• How do you test for a full circular queue

Answer 1

• Check if the front and rear pointers are equal (front == rear)
• Check if the tail pointer is 1 less than the front pointer

Question 2

How do you add an item to a priority queue?

Answer 2

• Ensure the queue is not full.
• Place the item according to its priority. Higher priority items are placed before lower priority items.
• Shift existing elements to accommodate the new item while maintaining the order

Question 3

How do you remove an item from a priority queue?

Answer 3

• Ensure the queue is not empty.
• Take the item with the highest priority (usually the first item).
• Shift remaining elements to fill the gap left by the removed item.

Question 4

How do you test for an empty priority queue?

Answer 4

Check if the size of the queue is 0 or if the front pointer is equal to the rear pointer.

Question 5

How do you test for a full priority queue?

Answer 5

Check if the rear pointer is at the last index of the array (size - 1)

Question 6

uses of graphs

Answer 6

• navigation systems
• data transmissions
• web page links
• social media trends

Question 7

differences between tree and graph

Answer 7

• graphs have cycles, trees dont
• theres one path between each node in a tree, there are multiple with a graph

Question 8

what are edges/arcs

Answer 8

the paths that link nodes together

Question 9

a graph with more edges than vertices is called

a graph with less edges than vertices is called

Answer 9

a dense graph

a sparse graph

Question 10

directed vs undirected graphs

Answer 10

where the edges go in one direction

undirected - all the edges are biderectional (arrowheads on both heads)

Question 11

how to represent:
- vertices
- edges
- edges with weights

Answer 11

vertices - inside curly brackets, eg {A,B,C,D,E,F}
edges - {(A,B),(A,C), (B,E), (C,A)}
edges with weights -
{ (A,B,8), (A,C,2), (B,E,4) }

Question 12

adjacency matrix

Answer 12

• A square 2D matrix used to represent a graph
• Each row and column represent a node (or vertex).

Question 13

adjacency list

Answer 13

• A list of dictionary where each node (or vertex) has a list of its adjacent nodes (or neighbors).
• implemented as a list of dictionaries
• key in each dictionary being the node and edge weight

Question 14

advantages and disadvantages of adjacency matrixes

Answer 14

• easy and quick to work with
• adding new edges/ checking for the presence of edges is quicker using this structure

however:
- if theres many nodes and few edges, it may result in empty space (wasted memory) and problem gets worse as size of the graph increases
- if matrix is implemented as a static 2D array, it can be hard to add or delete nodes

Question 15

advantages of adjacency lists

Answer 15

• more space efficient
• use less memory to store a sparse graph

Question 16

what is a tree

Answer 16

a connected, undirected graph with no cycles

Question 17

what is a root node

Answer 17

the node at the top of the tree

Question 18

what are the children of a tree

Answer 18

the node next down the structure

Question 19

what are branches

Answer 19

the lines that join nodes together

Question 20

what are leaf nodes

Answer 20

nodes without any sub nodes/children

Question 21

describe the operations of a binary tree

Answer 21

• Create a root node
• The root node has a right and left pointer
• If the value is smaller than the current node, insert it to the left.
• If the value is greater, insert it to the right.
• Repeat Recursively: For each node, follow the same rule until all values are inserted.
• Nodes with no children have both left and right pointers set to null.

Question 22

explain the circumstances in which it is more appropriate to represent a graph using an adjacency list instead of an adjacency matrix

Answer 22

• when there are few edges between vertices
• when graph is sparse
• when edges rarely change
• when presence of specific edges does not need to be tested frequently

Question 23

what is a weighted graph

Answer 23

a graph where each edge has a value associated with it