Basic CS-Data Structures (TCS Papers): Sample Questions 1 - 2 of 28

Examrace Placement Series prepares you for the toughest placement exams to top companies.

Question number: 1

» Basic CS » Data Structures

Essay Question▾

Describe in Detail

In tree construction which is the suitable efficient data structure? (Array, Linked list, stack, Queue)

Explanation

  • In tree construction linked list is efficient data structure

  • Linear data structure where each element is a separate object.

Image of the linked list

Image of the Linked List

Given the image is define the linked list data structure

  • Each element of a list comprises of two items - the data and a reference to the next node.

  • The last node has a reference to null. The entry point into a linked list is called the head of the list- head is not a separate node, but the reference to the first node. If the list is empty then the head is a null reference.

  • A linked list is a dynamic data structure- number of nodes in a list is not fixed and can grow and shrink on demand.

  • Any application dealing with unknown number of objects like in a tree should use a linked list.

  • Diagram shows the linked list implementation of a binary tree.

Linked list implementation of binary tree

Linked List Implementation of Binary Tree

Given the image is define the linked list implementation of binary tree.

Question number: 2

» Basic CS » Data Structures

Essay Question▾

Describe in Detail

What is the algorithm used in solving the 8 queen’s problem?

Explanation

  • Backtracking algorithm used in solving the 8 queens problem

  • Backtracking is modified brute force approach.

  • Technique systematically searches for a solution to problem among all available options by assuming that the solutions are represented by vectors () of values and by traversing through the domains of the vectors until the solutions is found.

  • For example: for 8 queens problems, queen Q1 attacks some positions, therefore queen Q2 has to comply with these constraints and be placed so that it is not directly attacked by Q1. Placing queen Q3 is harder, since we have to satisfy constraints of both Q1 and Q2.

  • Upon reaching a point, where the constraints make the placement of the next queen impossible, we relax the constraints and find new solution- this is done by going backwards and finding new admissible solution- by following simple rule: last placed, first displaced.

  • In other words if we place successfully queen on the ith column but cannot find solution for (i + 1) th queen, then going backwards we will try to find other admissible solution for the ith queen first. This process is called backtrack

  • Algorithm: -

  • Start with one queen at the first column first row

  • Continue with second queen from the second column first row

  • Go up until find a permissible situation

  • Continue with next queen

The backtracking algorithm

The Backtracking Algorithm

Given the image is define the backtracking algorithm