DS 1

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?

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?

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)   )

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
-> The point here is that you should have idea about these methods. If you are not master in these, It's fine, But you should know that there are some methods with these names.

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 chocolate 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