# AMCAT Computer Science Questions with Answers – 5

### 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
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 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

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 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