Quiz 1 M.Tech

40 Questions | Attempts: 107
Share
SettingsSettings
Please wait...
  • 1/40 Questions

    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
Please wait...
Quiz 1 M.Tech - Quiz
About This Quiz

The quiz contains 40 questions and time limit is 30 minutes. Each question carry 1 marks. No negative marking for wrong answer.

Quiz Preview

  • 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 ++;

    Correct Answer
    A. item = Q[FRONT]; FRONT++;
  • 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)

    Correct Answer
    A. Max(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

    Correct Answer
    A. 3 deletions and 3 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

    Correct Answer
    A. Rotates s left by k positions
  • 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

    Correct Answer
    A. Inorder
  • 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

    Correct Answer
    A. Counting the number of key operations
  • 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

    Correct Answer
    A. Ascending priority queue
  • 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

    Correct Answer
    A. Preorder and Postorder
  • 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)

    Correct Answer
    A. O(Logn)
  • 11. 

    Pick the correct statement(s) from the following set of statements.
    1. In the Kruskal’s algorithm, for the construction of minimal spanning tree for a graph, the selected edges always form a forest.
    2. In Prim’s algorithm, for the construction of minimal spanning tree for a graph, the selected edges always form an orchard.
    3. DFS, BFS algorithms always make use of a queue, and stack respectively.

    • Only 1

    • Only 2

    • Both 1 and 3

    • All of the above

    Correct Answer
    A. Only 1
  • 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;i

    • For(i=pos-1;i

    Correct Answer
    A. For(i=pos;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

    Correct Answer
    A. None of the above
  • 14. 

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

    • In push operation, if new nodes are inserted at the beginning of linked list, then in pop operation, nodes must be removed from end.

    • In push operation, if new nodes are inserted at the end, then in pop operation, nodes must be removed from the beginning.

    • Both of the above

    • None of the above

    Correct Answer
    A. 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

    Correct Answer
    A. Simple Queue
  • 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

    Correct Answer
    A. FAEKCDHGB
  • 17. 

    Queues serve major role in

    • Simulation of recursion

    • Simulation of arbitrary linked list

    • Simulation of limited resource allocation

    • All of the above

    Correct Answer
    A. Simulation of limited resource allocation
  • 18. 

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

    • Non-Systematically

    • Logically

    • Periodically

    • Systematically

    Correct Answer
    A. 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)

    Correct Answer
    A. A(n)= Big 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

    Correct Answer
    A. Is far less than one
  • 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

    Correct Answer
    A. 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

    Correct Answer
    A. The elements in the list are sorted in non-decreasing order of 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)

    Correct Answer
    A. Theta(logn)
  • 24. 

    What is collision resolution with open addressing?

    • 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

    • 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

    Correct Answer
    A. When collision happens, we look for an unoccupied memory location in the existing table
  • 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

    Correct Answer
    A. Selection 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

    Correct Answer
    A. Strictly decreasing 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

    Correct Answer
    A. Binary insertion 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

    Correct Answer
    A. O(n) for all
  • 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

    Correct Answer
    A. 400 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

    Correct Answer
    A. 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

    • Not possible with a single pointer

    Correct Answer
    A. Rear node
  • 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
    1. Full m-ary tree
    2. Complete m-ary tree
    3. Positional m-ary tree
     

    • Only 1

    • Only 2

    • Both 1 and 2

    • Both 2 and 3

    Correct Answer
    A. Both 1 and 2
  • 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

    Correct Answer
    A. A balanced binary search tree can be used but not a heap
  • 34. 

    For snake game, we can use the following algorithms

    • BFS

    • DFS

    • MST

    • All of the above

    Correct Answer
    A. 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

    Correct Answer
    A. It determines the maximum size of a problem that can be solved in a given amount of time
  • 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

    Correct Answer
    A. 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

    Correct Answer
    A. Less than 1
  • 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

    Correct Answer
    A. 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

    Correct Answer
    A. Inorder successor may be an ancestor of the node.
  • 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.

    Correct Answer
    A. X1, X2, X3, X4, X5, X6

Quiz Review Timeline (Updated): Jul 28, 2013 +

Our quizzes are rigorously reviewed, monitored and continuously updated by our expert board to maintain accuracy, relevance, and timeliness.

  • Current Version
  • Jul 28, 2013
    Quiz Edited by
    ProProfs Editorial Team
  • Jul 28, 2013
    Quiz Created by
    Refresher_Module
Back to Top Back to top
Advertisement