Mathematics MCQ Quiz Hub

1. The column sum in an incidence matrix for a simple graph is __________
depends on number of edges
always greater than 2
equal to 2
equal to the number of edges

2. What are the dimensions of an incidence matrix?
Number of edges*number of edges
Number of edges*number of vertices
Number of vertices*number of vertices
Number of edges * (1⁄2 * number of vertices)

3. The column sum in an incidence matrix for a directed graph having no self loop is __________
0
1
2
equal to the number of edges

4. Time complexity to check if an edge exists between two vertices would be ___________
O(V*V)
O(V+E)
O(1)
O(E)

5. If a connected Graph (G) contains n vertices what would be the rank of its incidence matrix?
n-1
values greater than n are possible
values less than n-1 are possible
insufficient Information is given

6. A Graph Structured Stack is a _____________
Undirected Graph
Directed Graph
Directed Acyclic Graph
Regular Graph

7. If a Graph Structured Stack contains {1,2,3,4} {1,5,3,4} {1,6,7,4} and {8,9,7,4}, what would be the source and sink vertices of the DAC?
Source – 1, 8 Sink – 7,4
Source – 1 Sink – 8,4
Source – 1, 8 Sink – 4
Source – 4, Sink – 1,8

8. Graph Structured Stack finds its application in _____________
Bogo Sort
Tomita’s Algorithm
Todd–Coxeter algorithm
Heap Sort

9. Which is the most appropriate data structure for reversing a word?
queue
stack
tree
graph

10. What will be the word obtained if the word “abbcabb” is reversed using a stack?
bbabbca
abbcabb
bbacbba
bbacabb

11. How many stacks are required for reversing a word algorithm?
one
two
three
four

12. What are the set of functions that are to be executed to get the following output? cat
push(c, s); push(a, s); push(t, s); pop(s); pop(s); pop(s);
push(c,s); pop(s); push(a,s); pop(s);push(t,s);pop(s);
pop(c ); pop(a); pop(t);
push(c,s); push(a,s); pop(t);

13. Binary Decision Diagram is a type of __________
Multigraph
Cyclic Graph
Directed Acyclic Graph
Directed Acyclic Word Graph

14. In which of the following case does a Binary Decision Diagram is used for?
Representation of Boolean Functions
String Matching
Searching
Sorting of number

15. In a Binary Decision Diagram, how many types of terminal exists?
1
2
3
4

16. In a Binary Decision Diagrams 0 values by a _________ line and the 1 values are represented by a _________ line.
dashed, bold
bold, dashed
dotted, bold
dotted, dashed

17. Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is number of ________ gates on the __________ path from a primary input to a primary output.
AND, AND, average
AND, OR, longest
OR, OR, shortest
AND, AND, longest

18. And Inverter Graph is a type of __________
Multigraph
Cyclic Graph
Directed Acyclic Graph
Directed Acyclic Word Graph

19. Which of the following logical operation can’t be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams?
Conjunction
Disjunction
Negation
Tautology Checking

20. Express -15 as a 6-bit signed binary number.
001111
101111
101110
001110

21. Which is the predefined method available in Java to convert decimal to binary numbers?
toBinaryInteger(int)
toBinaryValue(int)
toBinaryNumber(int)
toBinaryString(int)

22. How many children does a binary tree have?
2
any number of children
0 or 1 or 2
0 or 1

23. What is/are the disadvantages of implementing tree using normal arrays?
difficulty in knowing children nodes of a node
difficult in finding the parent of a node
have to know the maximum number of nodes possible before creation of trees
difficult to implement

24. What are the children for node ‘w’ of a complete-binary tree in an array representation?
2w and 2w+1
2+w and 2-w
w+1/2 and w/2
w-1/2 and w+1/2

25. What is the parent for a node ‘w’ of a complete binary tree in an array representation when w is not 0?
floor(w-1/2)
ceil(w-1/2)
w-1/2
w/2

26. If the tree is not a complete binary tree then what changes can be made for easy access of children of a node in the array?
every node stores data saying which of its children exist in the array
no need of any changes continue with 2w and 2w+1, if node is at i
keep a seperate table telling children of a node
use another array parallel to the array with tree

27. Consider a situation of writing a binary tree into a file with memory storage efficiency in mind, is array representation of tree is good?
yes because we are overcoming the need of pointers and so space efficiency
yes because array values are indexable
No it is not efficient in case of sparse trees and remaning cases it is fine
No linked list representation of tree is only fine

28. Can a tree stored in an array using either one of inorder or post order or pre order traversals be again reformed?
Yes just traverse through the array and form the tree
No we need one more traversal to form a tree
No in case of sparse trees
Yes by using both inorder and array elements

29. What is the location of a parent node for any arbitary node i?
(i/2) position
(i+1)/ position
floor(i/2) position
ceil(i/2) position

30. Given an array of element 5, 7, 9, 1, 3, 10, 8, 4. Which of the following are the correct sequences of elements after inserting all the elements in a min-heap?
1,3,4,5,7,8,9,10
1,4,3,9,8,5,7,10
1,3,4,5,8,7,9,10
1,3,7,4,8,5,9,10

31. Topological sort can be applied to which of the following graphs?
Undirected Cyclic Graphs
Directed Cyclic Graphs
Undirected Acyclic Graphs
Directed Acyclic Graphs

32. Most Efficient Time Complexity of Topological Sorting is? (V – number of vertices, E – number of edges)
O(V + E)
O(V)
O(E)
O(V*E)

33. In most of the cases, topological sort starts from a node which has __________
Maximum Degree
Minimum Degree
Any degree
Zero Degree

34. Which of the following is not an application of topological sorting?
Finding prerequisite of a task
Finding Deadlock in an Operating System
Finding Cycle in a graph
Ordered Statistics

35. Topological sort of a Directed Acyclic graph is?
Always unique
Always Not unique
Sometimes unique and sometimes not unique
Always unique if graph has even number of vertices

36. Topological sort can be implemented by?
Using Depth First Search
Using Breadth First Search
Using Depth and Breadth First Search
Using level ordered search

37. Topological sort is equivalent to which of the traversals in trees?
Pre-order traversal
Post-order traversal
In-order traversal
Level-order traversal

38. A man wants to go different places in the world. He has listed them down all. But there are some places where he wants to visit before some other places. What application of graph can he use to determine that?
Depth First Search
Breadth First Search
Topological Sorting
Dijkstra’s Shortest path algorithm

39. When the topological sort of a graph is unique?
When there exists a hamiltonian path in the graph
In the presence of multiple nodes with indegree 0
In the presence of single node with indegree 0
In the presence of single node with outdegree 0

40. Which of the following statements for a simple graph is correct?
Every path is a trail
Every trail is a path
Every trail is a path as well as every path is a trail
Path and trail have no relation

41. What is the number of edges present in a complete graph having n vertices?
(n*(n+1))/2
(n*(n-1))/2
n
Information given is insufficient

42. A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
15
3
1
11

43. If a simple graph G, contains n vertices and m edges, the number of edges in the Graph G'(Complement of G) is ___________
(n*n-n-2*m)/2
(n*n+n+2*m)/2
(n*n-n-2*m)/2
(n*n-n+2*m)/2

44. Which of the following properties does a simple graph not hold?
Must be connected
Must be unweighted
Must have no loops or multiple edges
Must have no multiple edges