Data Structures Algorithms-II MCQs

Page No. 64

hich of the following is false?


aThe spanning trees do not have any cycles

✖


bMST have n – 1 edges if the graph has n edges

✖


cEdge e belonging to a cut of the graph if has the weight smaller than any other edge in the same cut, then the edge e is present in all the MSTs of the graph

✖


dRemoving one edge from the spanning tree will not make the graph disconnected

✓



Which of the following is not the algorithm to find the minimum spanning tree of the given graph?


aBoruvka’s algorithm

✖


bPrim’s algorithm

✖


cKruskal’s algorithm

✖


dBellman–Ford algorithm

✓



If all the weights of the graph are positive, then the minimum spanning tree of the graph is a minimum cost subgraph.


a True

✓


bFalse

✖


ceither A. or B.

✖


d None of these

✖


View Answer True

Consider a undirected graph G with vertices { A, B, C, D, E}. In graph G, every edge has distinct weight. Edge CD is edge with minimum weight and edge AB is edge with maximum weight. Then, which of the following is false?


aEvery minimum spanning tree of G must contain CD

✖


b If AB is in a minimum spanning tree, then its removal must disconnect G

✖


cNo minimum spanning tree contains AB

✓


dG has a unique minimum spanning tree

✖



The travelling salesman problem can be solved using _________


aA spanning tree

✖


bA minimum spanning tree

✓


cBellman – Ford algorithm

✖


dDFS traversal

✖



Consider a complete graph G with 4 vertices. The graph G has ____ spanning trees.


a15

✖


b8

✖


c16

✓


d13

✖


View Answer 16

Every graph has only one minimum spanning tree.


aTrue

✖


bFalse

✓


ceither A. or B.

✖


d None of these

✖


View Answer False

Which of the following is false in the case of a spanning tree of a graph G?


aIt is tree that spans G

✖


bIt is a subgraph of the G

✖


cIt includes every vertex of the G

✖


d It can be either cyclic or acyclic

✓



Consider the following statements.
S1. Kruskal’s algorithm might produce a non-minimal spanning tree.
S2. Kruskal’s algorithm can efficiently implemented using the disjoint-set data structure.


aS1 is true but S2 is false

✖


bBoth S1 and S2 are false

✖


cBoth S1 and S2 are true

✖


dS2 is true but S1 is false

✓



Kruskal’s algorithm is best suited for the dense graphs than the prim’s algorithm.


aTrue

✖


bFalse

✓


ceither A. or B.

✖


d None of these

✖


View Answer True

Goto Page No.

Page 64 of 149

Alphabetical MCQs Categories
—

Here below You find all kind of categories of MCQs in alphabetical order.


"Comprehensive Collection of MCQs: Alphabetically Organized by Subject"
—

"Discover an extensive collection of multiple-choice questions (MCQs) neatly categorized by subject from A to Z. This resource is designed for anyone eager to explore various topics in a straightforward and organized manner. Whether you're a student preparing for exams, an educator seeking supplementary materials, or simply curious about different subjects, this compilation offers a convenient way to learn and assess your knowledge. With questions arranged alphabetically, navigation is effortless, allowing you to delve into subjects of interest at your own pace. Engage, learn, and expand your understanding with this accessible and comprehensive repository of MCQs!"


BolPakistan

bolpakistan.com.pk includes Job Mcqs and Pak Mcqs is the Top Largest Mcqs Forum in World, in which you can read Mcqs of All Subjects, PPSC test preparation, FPSC, NTS and PPSC PAST PAPERS, PPSC PAST MCQS. A Collection of Repeated MCQs for JOBs seekers.

Copyright © 2024, Designed & Developed by BolPakistan