Result 25 Sept Python Test
For Complete Video course of CS and IP of class 11 and 12 Download and Install "S P SHARMA CLASSES" Android App Now
https://play.google.com/store/apps/details?id=com.classcast.spsharmaclasses
Result 25 Sept Python Test
For Complete Video course of CS and IP of class 11 and 12 Download and Install "S P SHARMA CLASSES" Android App Now
https://play.google.com/store/apps/details?id=com.classcast.spsharmaclasses
Graph
Graph:
A Graph is a non-linear data structure
It consists of a finite set of nodes (or vertices) and a set of edges connecting nodes.
A pair (x,y) is referred to as an edge, which communicates that the x vertex connects to the y vertex.
G=(V,E)
V={v1,v2,...............vn}
E={e1,e2,.............en}
Edge:
An edge connects two vertices.
Circles represent vertices, while lines represent edges.
Graphs are used to solve real-life problems that involve representation of the problem space as a network. Examples of networks include telephone networks, circuit networks, social networks (like LinkedIn, Facebook etc.).
For example, a single user in Facebook can be represented as a node (vertex) while their connection with others can be represented as an edge between nodes.
Each node can be a structure that contains information like user’s id, name, gender, etc.
In an undirected graph, nodes are connected by edges that are all bidirectional. For example if an edge connects node 1 and 2, we can traverse from node 1 to node 2, and from node 2 to 1.
An undirected graph can have at most n(n-1)/2 edges.
A dense graph is a graph in which the number of edges is close to the maximal number of edges.
Simple Graph
A graph with no loops and no parallel edges is called a simple graph.
The maximum number of edges possible in a single graph with 'n' vertices is nC2 where nC2 = n(n – 1)/2.
Degree of vertex can be considered under two cases of graphs −
An undirected graph has no directed edges. Consider the following examples.
Take a look at the following graph −
In the above Undirected Graph,
deg(a) = 2, as there are 2 edges meeting at vertex 'a'.
deg(b) = 3, as there are 3 edges meeting at vertex 'b'.
deg(c) = 1, as there is 1 edge formed at vertex 'c'
So 'c' is a pendent vertex.
deg(d) = 2, as there are 2 edges meeting at vertex 'd'.
deg(e) = 0, as there are 0 edges formed at vertex 'e'.
So 'e' is an isolated vertex.
Take a look at the following graph −
In the above graph,
deg(a) = 2, deg(b) = 2, deg(c) = 2, deg(d) = 2, and deg(e) = 0.
The vertex 'e' is an isolated vertex. The graph does not have any pendent vertex.
Indegree of vertex V is the number of edges which are coming into the vertex V.
Notation − deg−(V).
Outdegree of vertex V is the number of edges which are going out from the vertex V.
Notation − deg+(V).
Consider the following examples.
Take a look at the following directed graph. Vertex 'a' has two edges, 'ad' and 'ab', which are going outwards. Hence its outdegree is 2. Similarly, there is an edge 'ga', coming towards vertex 'a'. Hence the indegree of 'a' is 1.
The indegree and outdegree of other vertices are shown in the following table −
Vertex | Indegree | Outdegree |
---|---|---|
a | 1 | 2 |
b | 2 | 0 |
c | 2 | 1 |
d | 1 | 1 |
e | 1 | 1 |
f | 1 | 1 |
g | 0 | 2 |
Take a look at the following directed graph. Vertex 'a' has an edge 'ae' going outwards from vertex 'a'. Hence its outdegree is 1. Similarly, the graph has an edge 'ba' coming towards vertex 'a'. Hence the indegree of 'a' is 1.
The indegree and outdegree of other vertices are shown in the following table −
Vertex | Indegree | Outdegree |
---|---|---|
a | 1 | 1 |
b | 0 | 2 |
c | 2 | 0 |
d | 1 | 1 |
e | 1 | 1 |
Regular graph
a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency
Eulerian Graph
A graph is considered Eulerian if the graph is both connected and has a closed trail (a walk with no repeated edges) containing all edges of the graph. Definition: An Eulerian Trail is a closed walk with no repeated edges but contains all edges of a graph and return to the start vertex.
"Find a trail starting at one of the four islands (
We will now look at criterion for determining if a graph is Eulerian with the following theorem.
Theorem 1: A graph |
Consider the graph representing the Königsberg bridge problem. Notice that all vertices have odd degree:
Vertex | Degree |
---|---|
Graph MCQ - 1
1- Which of the following data structure is nonlinear type?
A). Strings
B). Lists
C). Stacks
D). Graph
2- Which of the following is nonlinear data structure?
A). Stacks
B). List
C). Strings
D). Trees
Herder node is used as sentinel in …..
A). Graphs
B). Stacks
C). Binary tree
D). Queues
3- Which of the following statements for a simple graph is correct?
A). Every path is a trail
B). Every trail is a path
C). Every trail is a path as well as every path is a trail
D). None of the mentioned
4- In the given graph identify the cut vertices.
A). B and E
B). C and D
C). A and E
D). C and B
5- For the given graph (G), which of the following statements is true?
A). G is a complete graph
B). G is not a connected graph
C). The vertex connectivity of the graph is 2
D). The edge connectivity of the graph is 1
6- What is the number of edges present in a complete graph having n vertices?
A). (n*(n+1))/2
B). (n*(n-1))/2
C). N
D). Information given is insufficient
7- The given Graph is regular.
A). True
B). False
8- A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
A). 15
B). 3
C). 1
D). 11
9- Which of the following properties does a simple graph not hold?
A). Must be connected
B). Must be un-weighted
C). Must have no loops or multiple edges
D). All of the mentioned
10- What is the maximum number of edges in a bipartite graph having 10 vertices?
A). 24
B). 21
C). 25
D). 16
11- For a given graph G having v vertices and e edges which is connected and has no cycles, which of the following statements is true?
A). v=e
B). v = e+1
C). v + 1 = e
D). None of the mentioned
12- For which of the following combinations of the degrees of vertices would the connected graph be Eulerian?
A). 1, 2, 3
B). 2,3,4
C). 2,4,5
D). 1,3,5
13- A graph with all vertices having equal degree is known as a __________
A). Multi Graph
B). Regular Graph
C). Simple Graph
D). Complete Graph
14- Which of the following ways can be used to represent a graph?
A). Adjacency List and Adjacency Matrix
B). Incidence Matrix
C). Adjacency List, Adjacency Matrix as well as Incidence Matrix
D). None of the mentioned
15- The number of elements in the adjacency matrix of a graph having 7 vertices is __________
A). 7
B). 14
C). 36
D). 49
16- If A[x+3][y+5] represents an adjacency matrix, which of these could be the value of x and y.
A). x=5, y=3
B). x=3, y=5
C). x=3, y=3
D). x=5, y=5
1 - What is common in three different types of traversals (Inorder, Preorder and Postorder)?
2 - The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
A d e b f g c a
B e d b g f c a
C e d b f g c a
D d e f g b c a
3 - Which of the following pairs of traversals is not sufficient to build a binary tree from the given traversals?
A Preorder and Inorder
B Preorder and Postorder
C Inorder and Postorder
D None of the Above
4 - Which traversal of tree resembles the breadth first search of the graph?
A Preorder
B Inorder
C Postorder
D Level order
5 - Which of the following tree traversal uses a queue data structure?
A Preorder
B Inorder
C Postorder
D Level order
6 - Which of the following cannot generate the full binary tree?
A Preorder and Inorder
B Preorder and Postorder
C Inorder and Postorder
D None of the Above
What is the result of the given postfix expression? abc*+ where a=1, b=2, c=3.
a) 4
b) 5
c) 6
d) 7
What is the result of the following postfix expression?
ab*cd*+ where a=2,b=2,c=3,d=4.
a) 16
b) 12
c) 14
d) 10
Evaluate the postfix expression ab + cd/- where a=5, b=4, c=9, d=3.
a) 23
b) 15
c) 6
d) 10
Evaluate and write the result for the following postfix expression
abc*+de*f+g*+ where a=1, b=2, c=3, d=4, e=5, f=6, g=2.
a) 61
b) 59
c) 60
d) 55
For the given expression tree, write the correct postfix expression.
a) abc*+
b) abc+*
c) ab+c*
d) a+bc*
What would be the Prefix notation for the given equation?
A+(B*C)
a) +A*CB
b) *B+AC
c) +A*BC
d) *A+CB
What would be the Prefix notation for the given equation?
(A*B)+(C*D)
a) +*AB*CD
b) *+AB*CD
c) **AB+CD
d) +*BA*CD
What would be the Prefix notation for the given equation?
A+B*C^D
a) +A*B^CD
b) +A^B*CD
c) *A+B^CD
d) ^A*B+CD
What would be the Prefix notation for the given equation?
A^B^C^D
a) ^^^ABCD
b) ^A^B^CD
c) ABCD^^^
d) AB^C^D
What would be the Prefix notation for the given equation?
a+b-c/d&e|f
a) |&-+ab/cdef
b) &|-+ab/cdef
c) |&-ab+/cdef
d) |&-+/abcdef
What would be the Prefix notation for the given equation?
(a+(b/c)*(d^e)-f)
a) -+a*/^bcdef
b) -+a*/bc^def
c) -+a*b/c^def
d) -a+*/bc^def
What would be the Prefix notation and Postfix notation for the given equation?
A+B+C
a) ++ABC and AB+C+
b) AB+C+ and ++ABC
c) ABC++ and AB+C+
d) ABC+ and ABC+
What would be the Prefix notation for the given equation?
a|b&c
a) a|&bc
b) &|abc
c) |a&bc
d) ab&|c
What is the postfix expression for the corresponding infix expression?
a+b*c+(d*e)
a) abc*+de*+
b) abc+*de*+
c) a+bc*de+*
d) abc*+(de)*+
What is the postfix expression for the infix expression?
a-b-c
a) -ab-c
b) ab – c –
c) – -abc
d) -ab-c
What is the postfix expression for the following infix expression?
a/b^c-d
a) abc^/d-
b) ab/cd^-
c) ab/^cd-
d) abcd^/-
What is the corresponding postfix expression for the given infix expression?
a*(b+c)/d
a) ab*+cd/
b) ab+*cd/
c) abc*+/d
d) abc+*d/
What is the corresponding postfix expression for the given infix expression?
a+(b*c(d/e^f)*g)*h)
a) ab*cdef/^*g-h+
b) abcdef^/*g*h*+
c) abcd*^ed/g*-h*+
d) abc*de^fg/*-*h+
What is the correct postfix expression for the following expression?
a+b*(c^d-e)^(f+g*h)-i
a) abc^de-fg+*^*+i-
b) abcde^-fg*+*^h*+i-
c) abcd^e-fgh*+^*+i-
d) ab^-dc*+ef^gh*+i-
From the given Expression tree, identify the correct postfix expression from the list of options.
a) ab*cd*+
b) ab*cd-+
c) abcd-*+
d) ab*+cd-
What would be the solution to the given prefix notation?
- + 5 / 10 5 5
a) 2
b) 5
c) 10
d) 7
What would be the solution to the given prefix notation?
/ / / / 16 4 2 1
a) 1
b) 4
c) 2
d) 8
What would be the solution to the given prefix notation?
+ 9 * 3 / 8 4
a) 14
b) 15
c) 18
d) 12
What would be the solution to the given prefix notation?
- + 1 2 * 3 / 6 2
a) 6
b) -6
c) 3
d) -3
What would be the solution to the given prefix notation?
- * 1 5 / * / 6 3 6 2
a) 1
b) 0
c) -1
d) -2
What would be the solution to the given prefix notation?
* / + 1 2 / 4 2 + 3 5
a) 12
b) 7.5
c) 9
d) 13.5
The postfix expression abc+de/*- is equivalent to which of the following infix expression?
a) abc+-de*/
b) (a+b)-d/e*c
c) a-(b+c)*(d/e)
d) abc+*-(d/e)
The equivalent infix expression and value for the postfix form 1 2 + 3 * 4 5 * – will be ___________
a) 1 + 2 * 3 – 4 * 5 and -13
b) (2 + 1) * (3 – 4) * 5 and 13
c) 1 + 2 * (3 – 4) * 5 and -11
d) (1 + 2) * 3 – (4 * 5) and -11
What is the value of the postfix expression 2 3 + 4 5 6 – – *
a) 19
b) 21
c) -4
d) 25
The prefix expression of the postfix expression AB+CD-* is __________
a) (A+B)*(C-D)
b) +AB*-CD
c) A+*BCD-
d) *+AB-CD
Consider the postfix expression 4 5 6 a b 7 8 a c, where a, b, c are operators. Operator a has higher precedence over operators b and c. Operators b and c are right associative. Then, equivalent infix expression is
a) 4 a 5 6 b 7 8 a c
b) 4 a 5 c 6 b 7 a 8
c) 4 b 5 a 6 c 7 a 8
d) 4 a 5 b 6 c 7 a 8
The result of the postfix expression 5 3 * 9 + 6 / 8 4 / + is _____________
a) 8
b) 6
c) 10
d) 9