Quiz 1 M.Tech
The quiz contains 40 questions and time limit is 30 minutes. Each question carry 1 marks. No negative marking for wrong answer.
- 1.
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
- A.
X1, X2, X3, X4, X5, X6
- B.
X3, X4, X1, X5, X6, X2
- C.
X1, X3, X2, X4, X5, X6
- D.
None of the above.
Correct Answer
A. X1, X2, X3, X4, X5, X6 -
- 2.
The time factor when determining the efficiency of algorithm is measured by
- A.
Counting microseconds
- B.
Counting the number of key operations
- C.
Counting the number of statements
- D.
Counting the kilobytes of algorithm
Correct Answer
B. Counting the number of key operations -
- 3.
A queue has configuration a,b,c,d. To get configuration d,c,b,a. One needs a minimum of
- A.
2 deletion and 3 additions
- B.
3 deletions and 2 additions
- C.
3 deletions and 3 additions
- D.
3 deletions and 4 additions
Correct Answer
C. 3 deletions and 3 additions -
- 4.
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
- A.
Only 1
- B.
Only 2
- C.
Both 1 and 2
- D.
Both 2 and 3
Correct Answer
C. Both 1 and 2 - 5.
Given a binary search tree, which traversal type would print the values in the nodes in sorted order?
- A.
Preorder
- B.
Postorder
- C.
Inorder
- D.
None of the above
Correct Answer
C. Inorder -
- 6.
When inorder traversing a tree resulted E A C K F H D B G; the preorder traversal would return
- A.
FAEKCDBHG
- B.
FAEKCDHGB
- C.
EAFKHDCBG
- D.
FEAKDCHBG
Correct Answer
B. FAEKCDHGB -
- 7.
A machine took 200 sec to sort 200 names, using bubble sort. In 800 sec, it can approximately sort?
- A.
400 names
- B.
800 names
- C.
750 names
- D.
600 names
Correct Answer
A. 400 names -
- 8.
The average search time of hashing with linear probing will be less if the load factor?
- A.
Is far less than one
- B.
Equals one
- C.
Is far greater than one
- D.
None of the above
Correct Answer
A. Is far less than one -
- 9.
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
- A.
Theta(n)
- B.
Theta(logn)
- C.
Theta(1)
- D.
Theta(n^2)
Correct Answer
B. Theta(logn) -
- 10.
For snake game, we can use the following algorithms
- A.
BFS
- B.
DFS
- C.
MST
- D.
All of the above
Correct Answer
D. All of the above -
- 11.
Backtracking algorithms determine problem’s solutions by …........ searching the solution space for the given problem instance
- A.
Non-Systematically
- B.
Logically
- C.
Periodically
- D.
Systematically
Correct Answer
D. Systematically -
- 12.
To Delete an item from a Queue identify the correct set of statements
- A.
Q[REAR] = item; REAR ++;
- B.
Item = Q[REAR]; FRONT ++;
- C.
item = Q[FRONT]; FRONT++;
- D.
item = Q[FRONT]; REAR ++;
Correct Answer
C. item = Q[FRONT]; FRONT++; -
- 13.
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?
- A.
H1( day/month/year ) = day + month + year
- B.
H2( day/month/year ) = day + month*31 + year
- C.
h3( day/month/year ) = (day + month*31 + year*365) mod 4096
- D.
H4( day/month/year ) = (day + month*31 + year*365) mod 4093
Correct Answer
D. H4( day/month/year ) = (day + month*31 + year*365) mod 4093 -
- 14.
What is collision resolution with open addressing?
- A.
When collision happens, we create a new memory location outside of the existing table, and use a chain to link to the new memory location
- B.
When collision happens, we enlarge the hash table
- C.
When collision happens, we look for an unoccupied memory location in the existing table
- D.
We use an extra table to collect all collided data
Correct Answer
C. When collision happens, we look for an unoccupied memory location in the existing table -
- 15.
Which of the following has a desired key is searched, starting itself from hash address, sequentially in a table?
- A.
Quadratic probing
- B.
Linear probing
- C.
Chaining
- D.
Reverse probing
Correct Answer
B. Linear probing -
- 16.
With the “wrap around” implementation of a queue, which of the following code should be used to work out the next location of deletion?
- A.
front++
- B.
Front--
- C.
Front = (front % max_queue_size) + 1
- D.
Front = (front ++) % max_queue_size
Correct Answer
D. Front = (front ++) % max_queue_size -
- 17.
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.
- A.
Only 1
- B.
Only 2
- C.
Both 1 and 3
- D.
All of the above
Correct Answer
A. Only 1 - 18.
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?
- A.
Straight insertion sort
- B.
Binary insertion sort
- C.
Heap sort
- D.
Bubble Sort
Correct Answer
B. Binary insertion sort -
- 19.
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
- A.
Less than 1
- B.
Less than n
- C.
Less than m
- D.
Less than n/2
Correct Answer
A. Less than 1 -
- 20.
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.
A(n)=Omega W(n)
- B.
A(n)= Theta W(n)
- C.
A(n)= Big O W(n)
- D.
A(n)= Little O W(n)
Correct Answer
C. A(n)= Big O W(n) -
- 21.
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
- A.
F(n) x g(n)
- B.
Max(f(n),g(n))
- C.
Min(f(n),g(n))
- D.
F(n)+g(n)
Correct Answer
B. Max(f(n),g(n)) -
- 22.
The concept of order Big O is important because
- A.
It can be used to decide the best algorithm that solves a given problem
- B.
It determines the maximum size of a problem that can be solved in a given amount of time
- C.
It is the lower bound of growth rate of algorithm
- D.
Both 1 and 2
Correct Answer
B. It determines the maximum size of a problem that can be solved in a given amount of time -
- 23.
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).
- A.
For(i=N;i>=pos;i--) { a[i] = a[i+1]; }
- B.
For(i=pos;i
- C.
For(i=pos;i
- D.
For(i=pos-1;i
Correct Answer
B. For(i=pos;i -
- 24.
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?
- A.
Inorder Successor is always a leaf node
- B.
Inorder successor is always either a leaf node or a node with empty left child
- C.
Inorder successor may be an ancestor of the node.
- D.
Inorder successor is always either a leaf node or a node with empty right child
Correct Answer
C. Inorder successor may be an ancestor of the node. -
- 25.
Which of the following pairs of traversals is not sufficient to build a binary tree from the given traversals?
- A.
Preorder and Inorder
- B.
Inorder and Postorder
- C.
Preorder and Postorder
- D.
None of the above
Correct Answer
C. Preorder and Postorder -
- 26.
What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?
- A.
O(n) for all
- B.
O(Logn) for all
- C.
O(Logn) for search and insert, and O(n) for delete
- D.
O(Logn) for search, and O(n) for insert and delete
Correct Answer
A. O(n) for all -
- 27.
Which of the following algorithms can be used to most efficiently determine the presence of a cycle in a given graph ?
- A.
Breadth First Search
- B.
Prim’s Minimum Spanning Tree Algorithm
- C.
Kruskal’ Minimum Spanning Tree Algorithm
- D.
Depth First Search
Correct Answer
D. Depth First Search -
- 28.
Which of the following is true about linked list implementation of stack?
- A.
In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.
- B.
In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.
- C.
Both of the above
- D.
None of the above
Correct Answer
D. None of the above -
- 29.
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);
- A.
Rotates s left by k positions
- B.
Leaves s unchanged
- C.
Reverses all elements of s
- D.
None of the above
Correct Answer
A. Rotates s left by k positions -
- 30.
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
- A.
The list is empty or has exactly one element
- B.
The elements in the list are sorted in non-decreasing order of data value
- C.
The elements in the list are sorted in non-increasing order of data value
- D.
Not all elements in the list have the same data value
Correct Answer
B. The elements in the list are sorted in non-decreasing order of data value -
- 31.
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
- A.
A balanced binary search tree can be used but not a heap
- B.
A heap can be used but not a balanced binary search tree
- C.
Both balanced binary search tree and heap can be used
- D.
Neither balanced binary search tree nor heap can be used
Correct Answer
A. A balanced binary search tree can be used but not a heap - 32.
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?
- A.
Front node
- B.
Rear node
- C.
Not possible with a single pointer
- D.
Not possible with a single pointer
Correct Answer
B. Rear node -
- 33.
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?
- A.
LASTIN = LASTPOST
- B.
LASTIN = LASTPRE
- C.
LASTPRE = LASTPOST
- D.
None of the above
Correct Answer
D. None of the above -
- 34.
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.
- A.
O(LogLogn)
- B.
O(n)
- C.
O(Logn)
- D.
O(Logn * Logn)
Correct Answer
C. O(Logn) -
- 35.
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?
- A.
Heap Sort
- B.
Selection Sort
- C.
Insertion Sort
- D.
Merge Sort
Correct Answer
B. Selection Sort -
- 36.
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?
- A.
Descending priority queue
- B.
Ascending priority queue
- C.
FIFO queue
- D.
None of these
Correct Answer
B. Ascending priority queue -
- 37.
A________search begins the search with the element that is located in the middle of the array.
- A.
Serial
- B.
Random
- C.
Parallel
- D.
None of the above
Correct Answer
D. None of the above -
- 38.
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
- A.
Non-increasing order
- B.
Non-decreasing order
- C.
Strictly decreasing order
- D.
Strictly increasing order
Correct Answer
C. Strictly decreasing order -
- 39.
Queues serve major role in
- A.
Simulation of recursion
- B.
Simulation of arbitrary linked list
- C.
Simulation of limited resource allocation
- D.
All of the above
Correct Answer
C. Simulation of limited resource allocation -
- 40.
Which of the following data structure may give overflow error,even though the current number of element in it is less than its size?
- A.
Simple Queue
- B.
Circular Queue
- C.
Priority Queue
- D.
None of these
Correct Answer
A. Simple Queue -
Quiz Review Timeline +
Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.
-
Current Version
-
Jul 28, 2013Quiz Edited by
ProProfs Editorial Team -
Jul 28, 2013Quiz Created by
Refresher_Module
Back to top