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 test for an empty priority queue?

Answer 2

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

Question 3

How do you test for a full priority queue?

Answer 3

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

Question 4

uses of graphs

Answer 4

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

Question 5

differences between tree and graph

Answer 5

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

Question 6

what are edges/arcs

Answer 6

the paths that link nodes together

Question 7

a graph with more edges than vertices is called

a graph with less edges than vertices is called

Answer 7

a dense graph

a sparse graph

Question 8

directed vs undirected graphs

Answer 8

where the edges go in one direction

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

Question 9

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

Answer 9

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 10

adjacency matrix

Answer 10

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

Question 11

adjacency list

Answer 11

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

advantages and disadvantages of adjacency matrixes

Answer 12

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

advantages of adjacency lists

Answer 13

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

Question 14

what is a tree

Answer 14

a connected, unweighted, undirected graph with no cycles

Question 15

what is a root node

Answer 15

the node at the top of the tree

Question 16

what are the children of a tree

Answer 16

the node next down the structure

Question 17

what are branches

Answer 17

the lines that join nodes together

Question 18

what are leaf nodes

Answer 18

nodes without any sub nodes/children

Question 19

describe the operations of a binary tree

Answer 19

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

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

Answer 20

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

what is a weighted graph

Answer 21

a graph where each edge has a value associated with it

Question 22

what is a directed graph

Answer 22

a graph where edges have a direction, going from one vertex (node) to another.

Question 23

whys bubble sort seen as inefficient

Answer 23

It is inefficient because it repeatedly compares adjacent elements and has O(n²) time complexity

Bubble sort uses nested loops to compare and swap adjacent elements. The outer loop iterates through the list multiple times

Question 24

what is a data structure

Answer 24

a way of organizing and storing data

Question 25

what does reading a text file mean

Answer 25

accessing and loading its contents into memory

Question 26

difference between a text file and a binary file

Answer 26

A text file stores data as readable characters. A binary file stores data in binary format (non-readable by humans)

Question 27

directed vs undirected graph

Answer 27

In directed graphs, edges have direction; in undirected graphs, edges are bidirectional

Question 28

dictionaries do what and are used where

Answer 28

stores key–value pairs - used in Lookup table, storing student ID and names, etc

Question 29

what is a vector

Answer 29

A vector is an ordered list of numbers (a 1D array)