Placement Written test paper for MNC  Computer questions and answers Part – 5
Ques 121 : Choose the correct answer  
The time complexity of linear search algorithm over an array of n elements is  
Option 1 : O (log_{2} n)  Option 2 : O (n)  Option 3 : O (n log_{2} n )  Option 4 : O (n^{2})  


Ques 122 : Choose the correct answer 

Rajesh implements queue as a singlylinked linked list. The queue has n elements. The time complexity to ADD a new element to the queue:  
Option 1 : O (1)  Option 2 : O (log_{2} n)  Option 3 : O (n)  Option 4 : O (n log_{2} n )  


Ques 123 : Choose the correct answer 

The time required to insert an element in a stack with linked list implementation is  
Option 1 : O (1)  Option 2 : O (log_{2} n)  Option 3 : O (n)  Option 4 : O (n log_{2} n )  


Ques 124 : Choose the correct answer  
In the following sorting procedures, which one will be the slowest for any given array?  
Option 1 : Quick sort  Option 2 : Heap sort  Option 3 : Merge Sort  Option 4 : Bubble sort  


Ques 125 : Choose the correct answer  
Pankaj stores n data elements in a hash table. He is able to get the best efficiency achievable by a hash table. What is the time complexity of accessing any element from this hash table?  
Option 1 : O(1)  Option 2 : O(n^{2})  Option 3 : O(log n)  Option 4 : O(n)  


Ques 126 : Choose the correct answer  
Every element of a data structure has an address and a key associated with it. A search mechanism deals with two or more values assigned to the same address by using the key. What is this search mechanism?  
Option 1 : Linear Search  Option 2 : Binary search  Option 3 : Hash Coded Search  Option 4 : None of these  


Ques 127 : Choose the correct answer 

The order of magnitude of the worst case performance of a hash coded search (over N elements) is  
Option 1 : N  Option 2 : N log_{2} N  Option 3 : log_{2} N  Option 4 : not dependent upon N  


Ques 128 : Choose the correct answer  
A sorting algorithm traverses through a list, comparing adjacent elements and switching them under certain conditions. What is this sorting algorithm called?  
Option 1 : insertion sort  Option 2 : heap sort  Option 3 : quick sort  Option 4 : bubble sort  


Ques 129 : Choose the correct answer  
A sorting algorithm iteratively traverses through a list to exchange the first element with any element less than it. It then repeats with a new first element. What is this sorting algorithm called?  
Option 1 : insertion sort  Option 2 : selection sort  Option 3 : heap sort  Option 4 : quick sort  


Ques 130 : Choose the correct answer 

A sort which uses the binary tree concept such that any number in the tree is larger than all the numbers in the subtree below it is called  
Option 1 : selection sort  Option 2 : insertion sort  Option 3 : heap sort  Option 4 : quick sort  


Ques 131 : Choose the correct answer  
The average time required to perform a successful sequential search for an element in an array A(1 : n) is given by  
Option 1 : (n+1) / 2  Option 2 : log_{2}n  Option 3 : n(n+1) / 2  Option 4 : n^{2}  


Ques 132 : Choose the correct answer 

How many comparisons are needed to sort an array of length 5 if a straight selection sort is used and array is already in the opposite order?  
Option 1 : 1  Option 2 : 10  Option 3 : 50  Option 4 : 20  


Ques 133 : Choose the correct answer 

Queues serve a major role in  
Option 1 : simulation of recursion  Option 2 : simulation of arbitrary linked list  Option 3 : simulation of limited resource allocation  Option 4 : expression evaluation  


Ques 134 : Choose the correct answer 

The average search time of hashing with linear probing will be less if the load factor  
Option 1 : is far less than one  Option 2 : equals one  Option 3 : is far greater than one  Option 4 : none of these  


Ques 135 : Choose the correct answer 

Number of vertices of odd degree in a graph is  
Option 1 : is always even  Option 2 : always odd  Option 3 : either even or odd  Option 4 : always zero  


Ques 136 : Choose the correct answer 

The algorithm design technique used in the quick sort algorithm is  
Option 1 : Dynamic programming  Option 2 : Back tracking  Option 3 : Divide and conquer  Option 4 : Greedy Search  


Ques 137 : Choose the correct answer 

Linked lists are not suitable for  
Option 1 : Insertion sort  Option 2 : Binary search  Option 3 : Queue implementation  Option 4 : None of these  


Ques 138 : Choose the correct answer 

A connected graph is the one which  
Option 1 : Cannot be partitioned without removing an edge  Option 2 : Can be partitioned without removing an edge  Option 3 : does not contain a cycle  Option 4 : Has even number of vertices  


Ques 139 : Choose the correct answer 

Stack is useful for implementing  
Option 1 : radix search  Option 2 : breadth first search  Option 3 : recursion  Option 4 : none of these  


Ques 140 : Choose the correct answer 

Which of the following is useful in traversing a given graph by breadth first search?  
Option 1 : stack  Option 2 : set  Option 3 : list  Option 4 : queue  


Ques 141 : Choose the correct answer 

Which of the following is useful in implementing quick sort?  
Option 1 : stack  Option 2 : set  Option 3 : list  Option 4 : queue  


Ques 142 : Choose the correct answer 

Which of the following abstract data types can be used to represent a manytomany relation?  
Option 1 : Tree  Option 2 : Stack  Option 3 : Graph  Option 4 : Queue  


Ques 143 : Choose the correct answer 

Two lists, A and B are implemented as singly linked linklists. The address of the first and last node are stored in variables firstA and lastA for list A and firstB and lastB for list B. Given the address of a node is given in the variable node, the element stored in the node can be accessed by the statement node>data and the address to the next node can be accessed by node>next. Pankaj wants to append list B at end of list A. Which of the following statements should he use?  
Option 1 : lastB > next = firstA  Option 2 : lastA = firstB  Option 3 : lastA>next = firstB  Option 4 : lastB = firstA  


Ques 144 : Choose the correct answer 

Which of the following sorting algorithms yield approximately the same worstcase and averagecase running time behaviour in O (n log n)?  
Option 1 : Bubble sort and Selection sort  Option 2 : Heap sort and Merge sort  Option 3 : Quick sort and Radix sort  Option 4 : Tree sort and Medianof3 Quick sort  


Ques 145 : Choose the correct answer 

A complete binary tree with 5 levels has how many nodes? (Root is Level 1)  
Option 1 : 15  Option 2 : 25  Option 3 : 63  Option 4 : 31  


Ques 146 : Choose the correct answer 

The maximum number of nodes on level I of a binary tree is which of the following? (Root is Level 1)  
Option 1 : 2^{l1}  Option 2 : 3^{l1}  Option 3 : 2^{l}  Option 4 : 2^{l} – 1  


Ques 147 : Choose the correct answer 

Consider an array on which bubble sort is used. The bubble sort would compare the element A[x] to which of the following elements in a single iteration.  
Option 1 : A [x+1]  Option 2 : A [x+2]  Option 3 : A [x+2x]  Option 4 : All of these.  


Ques 148 : Choose the correct answer 

In an implementation of a linked list, each node contains data and address. Which of the following could the address field possibly contain?  
Option 1 : Address of next node in sequence  Option 2 : It’s own address  Option 3 : Address of last node  Option 4 : Address of first node  


Ques 149 : Choose the correct answer 

Surbhi wants to implement a particular data structure using a static array. She uses the concept of circular list to implement the data structure, because this allows her to efficiently use all fields of the array. Which data structure is Surbhi implementing?  
Option 1 : a stack  Option 2 : a queue  Option 3 : Binary Tree  Option 4 : None of these  


Ques 150 : Choose the correct answer 

Which of the following is a bad implementation for a queue?  
Option 1 : Circular List  Option 2 : Doubly linked list  Option 3 : Singly linked List  Option 4 : Linear Static Array 