### 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 2: Doubly linked list

Op 3: Singly linked 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**

**made?**

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

**}**

**return top**

**}**

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

**}**

**return top**

**}**

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

**ADD 5**

**ADD 7**

**ADD 46**

**DELETE**

**ADD 13**

**DELETE**

**DELETE**

**ADD 10**

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

**ADD 1; DELETE; ADD 2; ADD 3; ADD 4; DELETE, DELETE**

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

## No comments:

## Post a Comment