Quiz 1 M.Tech

1. Which of the following has a desired key is searched, starting itself from hash address, sequentially in a table?

Quadratic probing

Linear probing

Chaining

Reverse probing

2. To Delete an item from a Queue identify the correct set of statements

Q[REAR] = item; REAR ++;

Item = Q[REAR]; FRONT ++;

Item = Q[FRONT]; FRONT++;

Item = Q[FRONT]; REAR ++;

3. An algorithm is made up of two independent time complexities f(n) and g(n). Then the complexities of the algorithm is in the order of

F(n) x g(n)

Max(f(n),g(n))

Min(f(n),g(n))

F(n)+g(n)

4. A queue has configuration a,b,c,d. To get configuration d,c,b,a. One needs a minimum of

2 deletion and 3 additions

3 deletions and 2 additions

3 deletions and 3 additions

3 deletions and 4 additions

5. Suppose you are given an array s[1...n] and a procedure reverse (s,i,j) which reverses the order of elements in a between positions i and j (both inclusive). What does the following sequence do, where 1 < k <= n: reverse (s, 1, k); reverse (s, k + 1, n); reverse (s, 1, n);

Rotates s left by k positions

Leaves s unchanged

Reverses all elements of s

None of the above

6. Given a binary search tree, which traversal type would print the values in the nodes in sorted order?

Preorder

Postorder

Inorder

None of the above

7. The time factor when determining the efficiency of algorithm is measured by

Counting microseconds

Counting the number of key operations

Counting the number of statements

Counting the kilobytes of algorithm

8. Which of the following is a collection of items into which items can be inserted arbitrarity and from which only the smallest item can be removed?

Descending priority queue

Ascending priority queue

FIFO queue

None of these

9. Which of the following pairs of traversals is not sufficient to build a binary tree from the given traversals?

Preorder and Inorder

Inorder and Postorder

Preorder and Postorder

None of the above

10. Given a sorted array of integers, what can be the minimum worst case time complexity to find ceiling of a number x in given array? Ceiling of an element x is the smallest element present in array which is greater than or equal to x. Ceiling is not present if x is greater than the maximum element present in array. For example, if the given array is {12, 67, 90, 100, 300, 399} and x = 95, then output should be 100.

O(LogLogn)

O(n)

O(Logn)

O(Logn * Logn)

11. Pick the correct statement(s) from the following set of statements.

In the Kruskal's algorithm, for the construction of minimal spanning tree for a graph, the selected edges always form a forest.
In Prim's algorithm, for the construction of minimal spanning tree for a graph, the selected edges always form an orchard.
DFS, BFS algorithms always make use of a queue, and stack respectively.

Only 1

Only 2

Both 1 and 3

All of the above

12. To delete an item from an array which loop is correct, where p is the position of deletion( assume array starts from 1 and N is the max no. of items in the array).

For(i=N;i>=pos;i--) { a[i] = a[i+1]; }

For(i=pos;i

For(i=pos-1;i

13. A________search begins the search with the element that is located in the middle of the array.

Serial

Random

Parallel

None of the above

14. Which of the following is true about linked list implementation of stack?

Both of the above

None of the above

15. Which of the following data structure may give overflow error,even though the current number of element in it is less than its size?

Simple Queue

Circular Queue

Priority Queue

None of these

16. When inorder traversing a tree resulted E A C K F H D B G; the preorder traversal would return

FAEKCDBHG

FAEKCDHGB

EAFKHDCBG

FEAKDCHBG

17. Queues serve major role in

Simulation of recursion

Simulation of arbitrary linked list

Simulation of limited resource allocation

All of the above

18. Backtracking algorithms determine problem's solutions by …........ searching the solution space for the given problem instance

Non-Systematically

Logically

Periodically

Systematically

19. Let W(n) and A(n) denote respectively, worst and average case running time of an algorithm executed on an input of size n. Which of the following is always true?

A(n)=Omega W(n)

A(n)= Theta W(n)

A(n)= Big O W(n)

A(n)= Little O W(n)

20. The average search time of hashing with linear probing will be less if the load factor?

Is far less than one

Equals one

Is far greater than one

None of the above

21. Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph ?

Breadth First Search

Prim’s Minimum Spanning Tree Algorithm

Kruskal’ Minimum Spanning Tree Algorithm

Depth First Search

22. Consider the function f defined below. struct item { int data; struct item * next; }; int f(struct item *p) { return ( (p == NULL) || (p->next == NULL) || (( P->data <= p->next->data) && f(p->next)) ); } For a given linked list p, the function f returns 1 if and only if

The list is empty or has exactly one element

The elements in the list are sorted in non-decreasing order of data value

The elements in the list are sorted in non-increasing order of data value

Not all elements in the list have the same data value

23. The minimum number of comparisons required to determine if an integer appears more than n/2 times in a sorted array of n integers is

Theta(n)

Theta(logn)

Theta(1)

Theta(n^2)

24. What is collision resolution with open addressing?

When collision happens, we enlarge the hash table

When collision happens, we look for an unoccupied memory location in the existing table

We use an extra table to collect all collided data

25. Consider a situation where swap operation is very costly. Which of the following sorting algorithms should be preferred so that the number of swap operations are minimized in general?

Heap Sort

Selection Sort

Insertion Sort

Merge Sort

26. A priority queue is used to implement a stack S that stores characters PUSH(C)is implemented as INSERT(Q,C,K)where K is an appropriate integer key chosen by the implementation.POP is implemented as DELETEMIN(Q).For a sequence of operations,the key chosen are in

Non-increasing order

Non-decreasing order

Strictly decreasing order

Strictly increasing order

27. In which of the following sorting algorithm, number of comparison needed is the minimum if items are initially in reverse order and is maximum if items are in order?

Straight insertion sort

Binary insertion sort

Heap sort

Bubble Sort

28. What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?

O(n) for all

O(Logn) for all

O(Logn) for search and insert, and O(n) for delete

O(Logn) for search, and O(n) for insert and delete

29. A machine took 200 sec to sort 200 names, using bubble sort. In 800 sec, it can approximately sort?

400 names

800 names

750 names

600 names

30. With the "wrap around" implementation of a queue, which of the following code should be used to work out the next location of deletion?

Front++

Front--

Front = (front % max_queue_size) + 1

Front = (front ++) % max_queue_size

31. A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should p point such that both the operations enQueue and deQueue can be performed in constant time?

Front node

Rear node

Not possible with a single pointer

32. If the out degree of every node is exactly equal to M or 0 and the num ber of nodes at level K is Mk-1 [consider root at level 1], then tree is called as

Full m-ary tree
Complete m-ary tree
Positional m-ary tree

Only 1

Only 2

Both 1 and 2

Both 2 and 3

33. A data structure is required for storing a set of integers such that each of the following operations can be done in (log n) time, where n is the number of elements in the set.

Delection of the smallest element
Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?

A balanced binary search tree can be used but not a heap

A heap can be used but not a balanced binary search tree

Both balanced binary search tree and heap can be used

Neither balanced binary search tree nor heap can be used

34. For snake game, we can use the following algorithms

BFS

DFS

MST

All of the above

35. The concept of order Big O is important because

It can be used to decide the best algorithm that solves a given problem

It determines the maximum size of a problem that can be solved in a given amount of time

It is the lower bound of growth rate of algorithm

Both 1 and 2

36. Suppose that we have a data file containing records of famous people, and we need to build a hash table to find a record from the person's birthday. The size of the hash table is 4096. The following are hash functions which convert a birthday to an integer. Which of the following function is the best?

H1( day/month/year ) = day + month + year

H2( day/month/year ) = day + month*31 + year

H3( day/month/year ) = (day + month*31 + year*365) mod 4096

H4( day/month/year ) = (day + month*31 + year*365) mod 4093

37. If h is any hashing function and is used to hash n keys into a table of size m, where n<=m, the expected number of collisions involving a particular key x is

Less than 1

Less than n

Less than m

Less than n/2

38. Let LASTPOST, LASTIN and LASTPRE denote the last vertex visited in a postorder, inorder and preorder traversal. Respectively, of a complete binary tree. Which of the following is always true?

LASTIN = LASTPOST

LASTIN = LASTPRE

LASTPRE = LASTPOST

None of the above

39. In delete operation of BST, we need inorder successor (or predecessor) of a node when the node to be deleted has both left and right child as non-empty. Which of the following is true about inorder successor needed in delete operation?

Inorder Successor is always a leaf node

Inorder successor is always either a leaf node or a node with empty left child

Inorder successor may be an ancestor of the node.

Inorder successor is always either a leaf node or a node with empty right child

40. 6 files X1, X2, X3, X4, X5, X6 have 150, 250, 55, 85, 125, 175 number of records respectively. The order of storage ot optimize access time is

X1, X2, X3, X4, X5, X6

X3, X4, X1, X5, X6, X2

X1, X3, X2, X4, X5, X6

None of the above.