WorksheetsGraphs - Revision
Total questions: 28
Worksheet time: 47mins
What is a graph in the context of data structures?
A) A visual representation of quantitative data
B) A data structure used to represent complex relationships
C) A chart used to track changes over time
D) A mathematical function plotted on a coordinate system
Which term describes a graph where weights are assigned to edges?
A) Directed graph
B) Undirected graph
C) Weighted graph
D) Bipartite graph
What is the difference between an undirected graph and a directed graph?
A) An undirected graph has cycles, while a directed graph does not
B) An undirected graph has no edge orientations, while a directed graph has edge orientations
C) An undirected graph cannot have weights, while a directed graph can have weights
D) An undirected graph is used for hierarchical data, while a directed graph is not
What are the two common ways to represent a graph in computer memory?
A) Adjacency matrix and adjacency list
B) Array and linked list
C) Stack and queue
D) Binary tree and hash table
What are the two common ways to represent a graph in computer memory?
A) Adjacency matrix and adjacency list
B) Array and linked list
C) Stack and queue
D) Binary tree and hash table
Which representation of a graph is more space-efficient when the graph is sparse?
A) Adjacency matrix
B) Adjacency list
C) Both are equally space-efficient
D) Neither, as space efficiency does not depend on graph sparsity
What is a graph in the context of data structures?
A visual representation of quantitative data
A set of vertices or nodes connected by edges or arcs
A chart used to monitor changes over time
A collection of interlinked web pages
What is the characteristic of an undirected graph?
All edges are one-way
All edges are bidirectional
All edges are weighted
All edges are unconnected
In a directed graph, how are the edges oriented?
Bidirectional
Multidirectional
One-way
Weighted
How can a computer represent the information about distances and connections in a structured, numerical way?
Using a physical map
Through an adjacency matrix
By writing descriptive paragraphs
With a list of instructions
What does each row and column in an adjacency matrix represent?
A) A specific edge in the graph
B) A node in the graph
C) The weight of the edge
D) The direction of the edge
In an unweighted graph, what does the item at [row, column] in an adjacency matrix indicate?
A) The weight of the connection
B) The direction of the connection
C) A connection between nodes
D) The number of edges
How would you represent a connection between nodes A and E in an unweighted graph using an adjacency matrix?
A) Place a 0 at [A, E] and [E, A]
B) Place a 1 at [A, E] and [E, A]
C) Place a 1 at [A, E] only
D) Place a 0 at [A, E] only
What is an advantage of using an adjacency matrix for graphs?
It uses less memory for sparse graphs.
It is convenient to work with and adding an edge is simple.
It automatically updates when new nodes are added.
It requires no memory for disconnected nodes.
Why is an adjacency list used in graph representation?
It requires more storage than other representations.
It is not suitable for representing large, sparsely connected graphs.
It only uses storage for the connections that exist, making it more space-efficient.
It is a good way to represent small, densely connected graphs.
What type of graph is best represented using an adjacency list?
A small, densely connected graph.
A large, sparsely connected graph.
A graph where every node is connected to every other node.
A graph with uniform weight on all edges.
Which of the following is an application of graphs where nodes represent computers and weighted edges represent bandwidth between them?
Social networks
Computer networks
Chemistry
Maps
In graph terminology, what do you call a graph where each edge has a direction associated with it?
Weighted
Undirected graph
Directed graph
Vertices
Which term refers to a graph that does not have any directed edges?
Digraph
Directed graph
Undirected graph
Weighted
What is the term used for a directed graph where all the edges are one-way?
Edges
Undirected graph
Weighted
Digraph
Describe the method that would need to be followed to attempt to remove an item from a circular queue implemented as a static data structure using an array.
Your method should deal appropriately with any issues which could arise - 4 marks
What value will be returned by applying the peek operation to S?
Jib
Skye
Harry
None
What value will be returned by applying the pop operation to S?
Jib
Skye
Harry
None
Explain how a single stack can be used to reverse the order of the items in a queue. - 2 marks
Describe the steps involved in adding an item to a linear queue that has been implemented as a static data structure using an array. Your answer should include a description of how any pointers are used and changed. - 3 marks
Complete the unshaded table
State one reason why the graph shown in Figure 1 is not a tree.
Instead of using an adjacency matrix, an adjacency list could be used to represent the graph. Explain the circumstances in which it would be more appropriate to use an adjacency list instead of an adjacency matrix. - 2 Marks
