### AMCAT Computer Programming Previous Years Question answers with Solutions 5

Ques121. The time complexity of linear search algorithm over an array of n elements is

Ques121. The time complexity of linear search algorithm over an array of n elements is

Op 1: O (log2 n)

Op 2: O (n)

Op 3: O (n log2 n )

Op 4: O (n2

)

Op 5:

Correct Op : 2

**Ques122. Rajesh implements queue as a singly-linked linked list. The queue has n**

**elements. The time complexity to ADD a new element to the queue:**

Op 1: O (1)

Op 2: O (log2 n)

Op 3: O (n)

Op 4: O (n log2 n )

Op 5:

Correct Op : 1

**Ques123. The time required to insert an element in a stack with linked list**

**implementation is**

Op 1: O (1)

Op 2: O (log2 n)

Op 3: O (n)

Op 4: O (n log2 n )

Op 5:

Correct Op : 1

**Ques124. In the following sorting procedures, which one will be the slowest for any**

**given array?**

Op 1: Quick sort

Op 2: Heap sort

Op 3: Merge Sort

Op 4: Bubble sort

Op 5:

Correct Op : 4

**Ques125. 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?**

Op 1: O(1)

Op 2: O(n2

)

Op 3: O(log n)

Op 4: O(n)

Op 5:

Correct Op : 1

**Ques126. 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?**

Op 1: Linear Search

Op 2: Binary search

Op 3: Hash Coded Search

Op 4: None of these

Op 5:

Correct Op : 3

Ques127. The order of magnitude of the worst case performance of a hash coded search

(over N elements) is

Op 1: N

Op 2: N log2 N

Op 3: log2 N

Op 4: not dependent upon N

Op 5:

Correct Op : 1

**Ques128. A sorting algorithm traverses through a list, comparing adjacent elements and**

**switching them under certain conditions. What is this sorting algorithm called?**

Op 1: insertion sort

Op 2: heap sort

Op 3: quick sort

Op 4: bubble sort

Op 5:

Correct Op : 4

**Ques129. 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?**

Op 1: insertion sort

Op 2: selection sort

Op 3: heap sort

Op 4: quick sort

Op 5:

Correct Op : 2

**Ques130. 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**

Op 1: selection sort

Op 2: insertion sort

Op 3: heap sort

Op 4: quick sort

Op 5:

Correct Op : 3

**Ques131. The average time required to perform a successful sequential search for an**

**element in an array A(1 : n) is given by**

Op 1: (n+1) / 2

Op 2: log2n

Op 3: n(n+1) / 2

Op 4: n2

Op 5:

Correct Op : 1

**Ques132. 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?**

Op 1: 1

Op 2: 10

Op 3: 50

Op 4: 20

Op 5:

Correct Op : 2

**Ques133. Queues serve a major role in**

Op 1: simulation of recursion

Op 2: simulation of arbitrary linked list

Op 3: simulation of limited resource allocation

Op 4: expression evaluation

Op 5:

Correct Op : 3

**Ques134. The average search time of hashing with linear probing will be less if the load**

**factor**

Op 1: is far less than one

Op 2: equals one

Op 3: is far greater than one

Op 4: none of these

Op 5:

Correct Op : 1

**Ques135. Number of vertices of odd degree in a graph is**

Op 1: is always even

Op 2: always odd

Op 3: either even or odd

Op 4: always zero

Op 5:

Correct Op : 1

**Ques136. The algorithm design technique used in the quick sort algorithm is**

Op 1: Dynamic programming

Op 2: Back tracking

Op 3: Divide and conquer

Op 4: Greedy Search

Op 5:

Correct Op : 3

**Ques137. Linked lists are not suitable for**

Op 1: Insertion sort

Op 2: Binary search

Op 3: Queue implementation

Op 4: None of these

Op 5:

Correct Op : 2

**Ques138. A connected graph is the one which**

Op 1: Cannot be partitioned without removing an edge

Op 2: Can be partitioned without removing an edge

Op 3: does not contain a cycle

Op 4: Has even number of vertices

Op 5:

Correct Op : 1

**Ques140. Stack is useful for implementing**

Op 1: radix search

Op 2: breadth first search

Op 3: recursion

Op 4: none of these

Op 5:

Correct Op : 3

**Ques141. Which of the following is useful in traversing a given graph by breadth first**

**search?**

Op 1: stack

Op 2: set

Op 3: list

Op 4: queue

Op 5:

Correct Op : 4

**Ques142. Which of the following is useful in implementing quick sort?**

Op 1: stack

Op 2: set

Op 3: list

Op 4: queue

Op 5:

Correct Op : 1

**Ques143. Which of the following abstract data types can be used to represent a manyto-many**

**relation?**

Op 1: Tree

Op 2: Stack

Op 3: Graph

Op 4: Queue

Op 5:

Correct Op : 3

**Ques144. Two lists, A and B are implemented as singly linked link-lists. 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?**

Op 1: lastB -> next = firstA

Op 2: lastA = firstB

Op 3: lastA->next = firstB

Op 4: lastB = firstA

Op 5:

Correct Op : 3

**Ques145. Which of the following sorting algorithms yield approximately the same worstcase**

**and average-case running time behaviour in O (n log n)?**

Op 1: Bubble sort and Selection sort

Op 2: Heap sort and Merge sort

Op 3: Quick sort and Radix sort

Op 4: Tree sort and Median-of-3 Quick sort

Op 5:

Correct Op : 2

**Ques146. A complete binary tree with 5 levels has how many nodes? (Root is Level 1)**

Op 1: 15

Op 2: 25

Op 3: 63

Op 4: 31

Op 5:

Correct Op : 4

**Ques147. The maximum number of nodes on level I of a binary tree is which of the**

**following? (Root is Level 1)**

Op 1: 2l-1

Op 2: 3l-1

Op 3: 2l

Op 4: 2l – 1

Op 5:

Correct Op : 1

**Ques148. 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.**

Op 1: A [x+1]

Op 2: A [x+2]

Op 3: A [x+2x]

Op 4: All of these.

Op 5:

Correct Op : 1

**Ques149. In an implementation of a linked list, each node contains data and address.**

**Which of the following could the address field possibly contain?**

Op 1: Address of next node in sequence

Op 2: It’s own address

Op 3: Address of last node

Op 4: Address of first node

Op 5:

Correct Op : 1

**Ques150. 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?**

Op 1: a stack

Op 2: a queue

Op 3: Binary Tree

Op 4: None of these

Op 5:

Correct Op : 2