Basic CS-Data Structures [TCS Placement]: Sample Questions 3 - 4 of 28

Get unlimited access to the best preparation resource for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Question 3

Write in Short Short Answer▾

What are tuples?

Edit

Explanation

  • Tuple is a fixed-size collection that can have elements of either same or different data types.
  • Similar to arrays, a user must specify the size of a tuple at the time of declaration.
  • Tuples are allowed to hold 1 to 8 elements and if there are more than 8 elements, then the 8th element can be defined as another tuple.
  • Tuples can be specified as parameter or return type of a method.

Question 4

Describe in Detail Essay▾

What is a spanning tree?

Edit

Explanation

  • A spanning tree is associated with a network where all the nodes of the graph appear on the tree once.
  • A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.
    • The cost of the spanning tree is the sum of the weights of all the edges in the tree. There can be many spanning trees of a graph.
    • Minimum spanning tree is the spanning tree where the cost is minimum among all the spanning trees. There also can be many minimum spanning trees.
    • Minimum spanning tree has direct application in the design of networks. It is used in algorithms approximating the travelling salesman problem, multi-terminal minimum cut problem and minimum-cost weighted perfect matching.
    • Spanning trees are a subset of connected Graph G and disconnected graphs do not have spanning tree.
    • Thus, a spanning tree is a subset of Graph G, which has all the vertices covered with minimum possible number of edges- a spanning tree does not have cycles and it cannot be disconnected.
    • Every connected and undirected Graph G thus has at least one spanning tree but a disconnected graph does not have any spanning tree, as it cannot be spanned to all its vertices.
Given the Image is Define the Spanning Trees
  • In the figure above, there are three spanning trees or one complete graph.

Properties of Spanning Tree

  • A complete undirected graph can have maximum nn-2 number of spanning trees, where n is the number of nodes.
  • In the above addressed example, 33 − 2 = 3 spanning trees are possible.
  • From a complete graph, by removing maximum e - n + 1 edges, we can construct a spanning tree.
  • Spanning tree with n nodes has n-1 edges