# AMCAT Computer Science Questions with Answers - 6

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

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

Ques151. Which of the following is a bad implementation for a queue?
Op 1: Circular List
Op 4: Linear Static Array
Op 5:
Correct Op : 4

Ques152. Which of the following statements are true about a doubly-linked list?
Op 1: it may be either linear or circular
Op 2: it must contain a header node
Op 3: it will occupy same memory space as that of linear linked list, both having
same number of nodes
Op 4: None of these
Op 5:
Correct Op : 1

Ques153. Which of the following data structure may give overflow error, even though
the current number of element in it is less than its size ?
Op 1: Queue implemented in a linear array
Op 2: Queue implemented in a circularly connected array
Op 3: Stack implemented in a linear array
Op 4: none of these
Op 5:
Correct Op : 1

Ques154. Number of possible ordered trees with 3 nodes A, B, C is
Op 1: 16
Op 2: 12
Op 3: 13
Op 4: 14
Op 5:
Correct Op : 2

Ques155. The best sorting methods if number of swapping done is the only measure of
efficiency is
Op 1: Bubble sort
Op 2: Selection sort
Op 3: Insertion sort
Op 4: Quick sort
Op 5:
Correct Op : 3

Ques156. As part of the maintenance work, you are entrusted with the work of
rearranging the library books in a shelf in proper order, at the end of each day. The
ideal choice will be
Op 1: bubble sort
Op 2: insertion sort
Op 3: selection sort
Op 4: heap sort
Op 5:
Correct Op : 2

Ques157. A hash table can store a maximum of 10 records. Currently there are records
in locations 1, 3, 4, 7, 8, 9, 10. The probability of a new record going into location 2,
with a hash function resolving collisions by linear probing is
Op 1: 0.6
Op 2: 0.1
Op 3: 0.2
Op 4: 0.5
Op 5:
Correct Op : 1

Ques158. A full binary tree with n leaves contains
Op 1: 2n + 1 nodes
Op 2: log2 n nodes
Op 3: 2n - 1 nodes
Op 4: 2n nodes
Op 5:
Correct Op : 3

Ques159. An array contains the following elements in order: 7 6 12 30 18. Insertion sort
is used to sort the array in ascending order. How many times will an insertion be
Op 1: 2
Op 2: 3
Op 3: 4
Op 4: 5
Op 5:
Correct Op : 1

Ques160. An array of 5 numbers has the following entries in order: 7 4 5 10 8. Prashant
uses selection sort to sort this array in descending order. What will the array contain
after two iterations of selection sort?
Op 1: 10 8 7 5 4
Op 2: 10 8 5 7 4
Op 3: 8 10 5 7 4
Op 4: None of these
Op 5:
Correct Op : 2

Ques161. Srishti writes a program to find an element in the array A[5] with the following
elements in order: 8 30 40 45 70. She runs the program to find a number X. X is
found in the first iteration of binary search. What is the value of X?
Op 1: 40
Op 2: 8
Op 3: 70
Op 4: 30
Op 5:
Correct Op : 1

Ques162. The array A has n elements. We want to determine the position of X in the
array. We know that X is present in the array A and X can be present at any location
in the array with equal probability. How many comparisons will be required on
average to find the element X using linear search?
Op 1: n
Op 2: (n+1)/2
Op 3: 2*n
Op 4: n^2
Op 5:
Correct Op : 2

Ques163. A is an empty stack. The following operations are done on it.
PUSH(1)
PUSH(2)
POP
PUSH(5)
PUSH(6)
POP
What will the stack contain after these operations. (Top of the stack is underlined)
Op 1: 5 6
Op 2: 1 5
Op 3: 5 6
Op 4: 1 5
Op 5:
Correct Op : 2

Ques164. A stack is implemented as a linear array A[0…N-1]. Farhan writes the following
functions for pushing an element E in to the stack.
function PUSH( top, E, N )
{
if(X)
{
top= top+1
A[top] = E
}
else
{
print "Overflow"
}
}
Fill in the condition X
Op 1: top< N
Op 2: top <n-1
Op 3: top > 0
Op 4: top > 1
Op 5:
Correct Op : 2

Ques165. A stack is implemented as a linear array A[0…N-1]. Noor writes the following functions for popping
an element from the stack.
function POP( top, N )
{
if(X)
{
top = top - 1
}
else
{
print "Underflow"
}
}
Fill in the condition X
Op 1: top< N-1
Op 2: top<n
Op 3: top>1
Op 4: top >= 0
Op 5:
Correct Op : 4

Ques166. Q is an empty queue. The following operations are done on it:
DELETE
DELETE
DELETE
What will be the content of Q after these operations. Front is marked by (F) and Rear is marked by (R).
Op 1: 10(R) 13(F)
Op 2: 5(R) 10(F)
Op 3: 13(R) 10(F)
Op 4: 10(R) 5(F)
Op 5:
Correct Op : 1

Ques167. A queue is implemented as a (singly linked) linked-list for easy addition and deletion of elements.
Each node has an element and pointer to another node. Which node will point to empty/no location?
Op 1: Front
Op 2: Rear
Op 3: Both
Op 4: None of these
Op 5:
Correct Op : 2

Ques168. A stack is implemented as a (singly-linked) linked-list, where each node contains data and address of another node. The top node will contain the address of which node?
Op 1: No node. It will be empty
Op 2: The node containing the first element pushed into the stack.
Op 3: The node containing the element which was pushed just before the top element.
Op 4: None of these
Op 5:
Correct Op : 3

Ques169. A queue is implemented by a linear array of size 10 (and not as a circularly connected array). Front
and Rear are represented as an index in the array. To add an element, the rear index is incremented and
the element is added. To delete an element, the front index is incremented. The following operations
are done on an empty queue.
After this set of operations, what is the maximum capacity of the queue?
Op 1: 6
Op 2: 7
Op 3: 10
Op 4: None of these
Op 5:
Correct Op : 2

Ques170. A queue is implemented as a (singly linked) linked-list. Each node has an element and pointer to
another node. Rear and Front contain the addresses of the rear and front node respectively. If the
condition (rear isequal front) is true and neither is NULL, what do we infer about the linked list?
Op 1: It has no elements
Op 2: It has one element
Op 3: There is an error
Op 4: None of these
Op 5:
Correct Op : 2

Ques171. Jaswinder has a book of tickets and wants to store ticket numbers in a data structure. New tickets
are added to the end of the booklet. Ticket at the top of the stack is issued to the customer. Which data
structure should Jaswinder use to represent the ticket booklet?
Op 1: Queue
Op 2: Stack
Op 3: Array
Op 4: Graph
Op 5:
Correct Op : 1
</n
</n-1