88. OCR A Level (H446) SLR14 – 1.4 Data structures part 2 – Grap

What is a graph in data structures?

• A collection of nodes or vertices connected by edges

• A sequence of elements in a linear order

• A fixed-size container for data elements

• A hierarchical structure representing parent-child relationships

Answer explanation

A graph in data structures is a collection of nodes or vertices connected by edges, making it the correct choice among the options provided.

What distinguishes a graph from a linked list or binary tree?

• It cannot have cycles

• It has a root node and leaf nodes

• Each vertex can have more than two edges and point to any vertex

• Its ability to store elements in a linear order

Answer explanation

The correct choice is that each vertex in a graph can have more than two edges and point to any vertex, distinguishing it from a linked list or binary tree.

What is a directed graph?

• A graph that cannot have cycles

• A graph where each edge points from one vertex to another in a specific direction

• A graph where each vertex is connected to itself

• A graph where edges have no direction

Answer explanation

A directed graph is a graph where each edge points from one vertex to another in a specific direction, indicating the flow or relationship between vertices.

What does it mean for a graph to be weighted?

• It can only represent physical weights

• Each edge is given a value representing a relationship between vertices

• Each edge has a direction

• It contains only a single vertex

Answer explanation

A weighted graph assigns a value to each edge, representing a relationship between vertices.

What can edge values in a graph represent?

• The number of vertices in the graph

• The color of the edge in a visualization

• Only the cost of traversal

• Distance, time passed, or bandwidth

Answer explanation

Edge values in a graph can represent distance, time passed, or bandwidth, making them versatile in graph theory applications.

How are graphs typically stored?

• Using a stack

• Using a queue

• As objects or using a dictionary known as adjacency lists

• In a single continuous block of memory

Answer explanation

Graphs are typically stored as objects or using a dictionary known as adjacency lists, which represent the connections between vertices.

What is an adjacency matrix?

• A matrix with rows and columns representing vertices and edges

• A special type of graph with no edges

• A list of all vertices and their adjacent vertices

• A method to calculate the shortest path in a graph

Answer explanation

An adjacency matrix is a matrix with rows and columns representing vertices and edges, making it the correct choice.

What is one use of graphs in computer science?

• Performing simple calculations

• Storing static data in a database

• Mapping road networks for navigation systems

• To calculate arithmetic operations

Answer explanation

Graphs are used in computer science to map road networks for navigation systems, allowing for efficient route planning and optimization.

How is a binary tree related to graphs?

• A binary tree cannot have cycles, unlike graphs

• Graphs are a type of binary tree

• A binary tree is a special type of graph

• There is no relation between binary trees and graphs

Answer explanation

A binary tree is a special type of graph because it is a connected acyclic graph with each node having at most two children.

What is abstraction in the context of graphs?

• Removing all vertices from a graph

• Using only the necessary detail and discarding unnecessary detail

• Adding more vertices to increase complexity

• Converting a graph into a binary tree

Answer explanation

Abstraction in the context of graphs involves using only the necessary detail and discarding unnecessary detail to simplify the representation.