Basic CSData 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
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.

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.
Question number: 2
» Basic CS » Data Structures
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 i^{th} column but cannot find solution for (i + 1) ^{th} queen, then going backwards we will try to find other admissible solution for the i^{th} 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