Data Structures interview Questions

Data Structures

                                    HCL

1.What data structes you will use if you want to go to first record from

the last and vice versa?

ans.: doubly linked circular list

2.  given a height balanced tree. If we add one more node , how

    many nodes gets unbalanced ? Ans. 3

3. Given a arbitrary pointer  to an element in a singly linked list?

    what is the time complexity for its deletion . 

Ans. O(n)

4. S->S+S; s->s*s; s->a      how many parse trees possible : a+a*a+a   Ans. 5

5. order of  Hashing time

6) A choclate of size nXn is given and is to be made into pices of size 1x1. At a time both horizontal and a vertical cut is done. Find the order of complexity

a) 0(n2)

b) o(nlogn)

c) o(logn)

Ans : a

7) comparison between hashtable and binary tree

 

                        HUGHES

8) No. of nodes of degree 2 in a binary tree with n leaf nodes.

    Ans. n-1

9. To sorting array of 10 elements which sorting is best

a)slection

b)bubble

c)tree sort

d)....

ans:a

10  To saving space point of view which sort is best

a)selection

b)insertion

c)both a & b

d)...

11Which statement is wrong on heap

a)Any two childs should not same

b)..

c)..

d)...

ans:a

12) cyclometric complexity..

13) how many  null pointer are there in N number binary tree

ans:N+1

14) Two sorted list of size n what are the maximum comparison in merge

ANs:2n-1

15) two sorted lists of n elements will take at least

fine the order of complexity?

a. 2n

b. n/2

c. square(n)

16)if there are n nodes in a binary tree, how many null pointers are

there

ans:n+1;

17). if heap sort contains n elements, no of comparsions required are

a. log(n)

b. height of heap sort

c.

d.

18) which of the following is efficient in terms of space

a. insertion sort

b. quick sort

c. selection

d. both a and c

19) in sorted table contains elements , which of the searching is

false

a. hash table

b. binary searching

20) in associated memory for fast accessing

which one is used

a. single linked list

b. double  "

c. hash table

21) for hashing which is best on terms of buckets

a)100 b)50 c)21 d)32  ans 32

22) max and avg. height of sorted binary tree

a. logn n

b n logn

23) implementation of priority queue

  a. tree

   b linked list

    c doubly linked list

24) For a binary tree with n nodes, How many nodes are there which

  has got both a parent and a child?

25) Bubble sort : Given sequence of numbers what will be order of sequences

                 after two iterations.

                    Ans: very trivial, but you should know what bubble sort

                         does.

26)Bubble sort : how many swap operations has been done in the above

                 process?

27)What data structures you should use for dictionary searching and it

        should be capable of doing spell check also ?

                Ans: Hashing

28)Which is the best scheduling algo. (given five of them)

        Ans.:  Shortest Job First with Pre-emption

29) Bubble  sort is given ., No of times it executes

 ans .  n(n-1)/2

30) The appriximate ratio for no of internal nodes to total no

31) precedence order from high to low (  ( )  ++  /  )

32) preorder of  A*(B+C)/D-G  (*+ABC/-DG)

33) B-tree (failure nodes at same level)

 of nodes in k-ary tree of depth  n.

 ans. 1/k

34) merge sort  time complexity (  O(n log n)   )

35) while following sorting algorithem has average sorting behavior (heap

sort )

36)in binary search tree  which traversal is used for getting ascending

order values (inorder )

37) fun(n)

   {

    if(n<=2)

    return (1);

    else

     return ((fun(n-1)*fun(n-2));

     }

find the order of complexity of the programme.

possible answer ---- N(2^n)

38). average and worst time complexity in a sorted binary tree is

39) a tree is given and ask to find its meaning (parse-tree)

    (expression tree)

    ans. ((a+b)-(c*d))  ( not confirmed)

40) Compute the complexity of Binary search.

Ans : O(lg n) ( Answer in detail. This is not a multiple choice question.

          It carries more marks.)

41) A search procedure which assosiates an address with a key value and

   provides a mechanism for dealing with two or more values assigned to the

   same address to the same address is called.

   a) linear earch

   b) binary search

 *   c) hash coded search

  d) radix search

42)which data struture is needed to convert infix notations to postfix

notations?

a. linear list

b. queue

c. tree

d. stack            ans:d

43) recursive procedures are implemented by

a.queues

b.stacks

c.linked lists

d.strings

  

44) A linear list of elments in which deletion can be done from one end (front)and

insertion can take place only at the other end(rear)is known as

 *a) queues

  b)stacks

  c)trees

  d)deque

 

 45) A linear list in which elements can be added or removed at either

end but not in the middle is known as

 a)queue

 *b)deque

 c)stack

 d)tree

46)which of the following sorting procedure is slowest

  a)quick sort

  b)heap sort

  c)shell sort

  *d)bubble sort

47) The complexity of bublle sort is0(a),then kequals

        ans:2

48)  given a height balanced tree. If we add one more node , how

    many nodes gets unbalanced ? Ans. 3

49) Given a arbitrary pointer  to an element in a singly linked list?

    what is the time complexity for its deletion . Ans. O(n)

50) S->S+S; s->s*s; s->a

            how many parse trees possible : a+a*a+a   Ans. 5

51) order of  Hashing time

52) A choclate of size nXn is given and is to be made into pices of size 1x1. At a time both horizontal and a vertical cut is done. Find the order of complexity

a) 0(n2)

b) o(nlogn)

c) o(logn)

Ans : a

53) comparison between hashtable and binary tree