DS interview ques

1) Define data structure in terms of relation?
A : The possible ways in which the data items or atoms are logically related define different data structures.

2) How do you define a vector for a data structure?
The simplest data structure that makes use of computed address to locate its elements in the one – dimensional array and is called as a vector.

3) Define stack
An important sub class of lists permits the insertion or deletion of an element to occur only at one end. A linear list belonging to this sub class is called a stack.

4)State the theorem which is used to determine whether a given expression is valid or not.
A polish suffix formula is well formed if and only if the rank of the formula is “one” and the rank of any proper head of a polish formula is greater than or equal to “one”.

What is a priority queue?
Waiting queue may not operate on a strictly first in first out basis, but on some complex priority scheme based on such factors as what compiler is being used, the execution time required, number of print lines, etc. The resulting queue is called a priority queue.

11) What is linear hashing?
In linear hashing, the table is gradually expanded by splitting the buckets in order until the table has doubled its size.

12) What is splitting?
Splitting refers to the rehashing of a bucket b and its overflow in order to distribute the keys in them among b and one other primary location.

13) What is a one way chain or singly linked linear list?
A list has been defined to consist of an ordered set of elements which may vary in number. A simple way to represent a linear list is to expand each node to contain a link or pointer to the next time.

14) Name two desirable properties of hashing functions.
Some of the desirable properties of a hashing function are speed and the generation of addresses uniformly.

15) What is the distant relationship between a list structure and a digraph?
In particular, a list is a directed graph with one source node corresponding to the entire list and with every node immediately connected to the source code.

16) Define Simulation?
Simulation is the process of forming an abstract model from a real situation in order to understand the impact of modifications and the effect of introducing various strategies on the situation.

17) Define Index area and its subdivisions?
Index area is created automatically by the data-management routines in the operating systems. A number of index levels may be involved in an indexed sequential file. The lowest of index is the track index, which is always written on the first track of the cylinders for the indexed sequential file. The track index contains two entries for each prime track of the cylinder a normal entry and an overflow entry.

18) Given N discs of decreasing size stacked on one needle and two empty needles, it is required to stack all the discs onto a second needle in decreasing order of size. The third needle may be used as temporary storage.
The movement of the discs is restricted by the following rules
(1) A disc may be moved from any needle to any other
(2) Only one disc may be moved at a time
(3) At no time may a larger disc rest upon smaller disc explain the solution?
Ans) The solution to this problem is most clearly seen with the aid of induction, to move one disc, merely move it from needle A to needle C. To move two discs, move the first disc to needle B, move the second from needle A to needle C, then move the disc from needle B to needle C.

19) Define addressing and linear addressing functions?
There are many data structures which can be represented so as to permit the referencing of any element by knowing its position in the structure. The selection operation associated with such a structure is said to possess an addressing function. An addressing function for a data structure consisting of n elements is a function which maps the ith element of the data structure onto an integer between one and n. In the case of a vector, the addressing function f maps the ith element onto the integer I, which is a linear addressing function.

20) What exactly does this procedure BUBBLE_SORT (K, N) does?
Given a vector K of N elements, this procedure sorts the elements into ascending order using the method just described. The variables PASS and LAST denote the pass counter and position of the last unsorted elements respectively. The variable I is used to index the vector elements. The variable EXCHS is used to count the number of exchanges made on any pass. All variables are integer.

http://www.coders2020.com/interview/data_structures_interview_questions