Friday 25 September 2020

Result 25 Sept Python Test

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

Thursday 24 September 2020

Graph

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.

Types of graphs:

Undirected Graph:

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.

Directed Graph

In a directed graph, nodes are connected by directed edges – they only go in one direction. For example, if an edge connects node 1 and 2, but the arrow head points towards 2, we can only traverse from node 1 to node 2 – not in the opposite direction.

A directed graph can have at most n(n-1) edges, where n is the number of vertices.

Sparse Graph

A graph in which the number of edges is much less than the possible number of edges.

Sparse graph is a graph in which the number of edges is close to the minimal number of edges.

Dense graph

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 ⁿC₂ where ⁿC₂ = n(n – 1)/2.

Degree of Vertex of a Graph

Degree of vertex can be considered under two cases of graphs −

Undirected Graph
Directed Graph

Degree of Vertex in an Undirected Graph

An undirected graph has no directed edges. Consider the following examples.

Example 1

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.

Example 2

Take a look at the following graph −

Undirected Graph 1

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 a Graph

Indegree of vertex V is the number of edges which are coming into the vertex V.
Notation − deg−(V).

Outdegree of a Graph

Outdegree of vertex V is the number of edges which are going out from the vertex V.
Notation − deg+(V).

Consider the following examples.

Example 1

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.

Directed Graph

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

Example 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.

Directed Graph 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.

The Seven Bridges of Königsberg

"Find a trail starting at one of the four islands ( $A$ , $B$ , $C$ , or $D$ ) that crosses each bridge exactly once in which you return to the same island you started on."

Determining if a Graph is Eulerian

We will now look at criterion for determining if a graph is Eulerian with the following theorem.

Theorem 1: A graph

G = (V (G), E (G))

is Eulerian if and only if each vertex has an even degree.

Consider the graph representing the Königsberg bridge problem. Notice that all vertices have odd degree:

Vertex	Degree
$A$	$3$
$B$	$5$
$C$	$3$
$D$	$3$

Graph MCQ - 1

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

Monday 21 September 2020

Result of C++ 13 Sep 2020

Max Marks 39

Result of Java Test 13 Sep 2020

Sunday 20 September 2020

Tree Traversals

1 - What is common in three different types of traversals (Inorder, Preorder and Postorder)?

A Root is visited before right subtree

B Left subtree is always visited before right subtree

C Root is visited after left subtree

D All of the above

E None of the above

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

20 Sep 2020 DS Result

20 Sep 2020 DS Result

Tuesday 15 September 2020

Stack Polish Notation Questions

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*