Amcat programming questions or Amcat Computer programming questions are useful if you are attempting this module for Amcat Exam. This module consists of 25 questions and the time duration is 35 minutes.

Table of Contents

**Syllabus for Amcat programming Questions**

Topic | Subtopics |

Basic Programming | Data Types Iteration, Recursion, Decision Procedure, functions and scope |

Data Structures | Arrays, Linked Lists, Trees, Graphs Stacks, Queues Hash Tables Heaps Searching and Sorting |

OOPs | Polymorphism Abstraction Encapsulation Complexity Theory |

Miscellaneous | Searching and Sorting Complexity Theory |

**Amcat questions on Computer Programming**

Amcat sample questions on computer programming are given here with detailed solutions. Practicing these Amcat programming questions can help you answer atleast 70% of the questions asked in this module.

**Amcat Programming Questions – Set 1**

1) I have a problem to solve which takes as input a number n. The problem has a property that given the solution for (n-1), I can easily solve the problem for n. Which programming technique will I use to solve such a problem?

a) Iteration

b) Decision-making

c) Object Oriented Programming

d) Recursion

**Ans: d**

Recursion means calling again and again. Therefore problem n can be solved with the solution n-1, by repeatedly calling it.

2) The memory space needed by an algorithm has a fixed part independent of the problem instance solved and a variable part which changes according to the problem instance solved. In general, which of these two is of prime concern to an algorithm designer?

a) Fixed part

b) Variable Part

c) Product of fixed part and variable part

d) None of these

**Ans: b**

Variable part, since it changes according to the problem instance solved.

3) Pankaj and Mythili were both asked to write the code to evaluate the following expression:

a – b + c/(a-b) + (a-b)^2

Pankaj writes the following code statements (Code A):

print (a-b) + c/(a-b) + (a-b)*(a-b)

Mythili writes the following code statements (Code B):

d = (a-b)

print d + c/d + d*d

If the time taken to load a value in a variable, for addition, multiplication or division between two operands is same, which of the following is true?

a) Code A uses lesser memory and is slower than Code B

b) Code A uses lesser memory and is faster than Code B

c) Code A uses more memory and is faster than Code B

d) Code A uses more memory and is slower than Code B

**Ans: a**

Code A uses lesser memory and it is slower than code B. Since code B uses another variable d it needs to have more memory than code A. But code B will execute faster.

4) A queue is implemented as a singly-linked-list for easy addition and deletion of elements. Each node has an element and a pointer to another node. Which node will point to empty/no location?

a) Rear

b) Front

c) Both

d) None

**Ans: a**

The new node will always be added at the rear end, so the new/empty location will be pointed by Rear end.

5) 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).

a) 10(R) 13(F)

b) 5(R) 10(F)

c) 13(R) 10(F)

d) 10(R) 5(F)

**Ans: a**

Queue follows FIFO principle, so performing the FIFO operation the Front will be pointing to 13 and Rear will be pointing to 10.** **

6) 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?

a) 5 6

b) 1 6

c) 5 6

d) 1 5

**Ans: d**

To an Empty Stack A,

PUSH(1): 1

PUSH(2): 1 2

POP: 1

PUSH(5): 1 5

PUSH(6): 1 5 6

POP: 1 5

By the end of all the operation, the elements remaining are 1 5.

7) What is implied by the argument of a function?

a) The variables passed to it when it is called

b) The value it returns on execution

c) The execution code inside it

d) Its return type

**Ans: a**

The variables that are passed as inputs to a function in a function call are called arguments.** **

8) In a sequential programming language, code statements are executed in which order?

a) All are executed simultaneously

b) From top to bottom

c) From bottom to top

d) None of these

**Ans: b**

In a sequential programming language code statements are executed from top to bottom.

9) A pseudo-code is used. Assume that when two data-types are processed through an operator, the answer maintains the same data-type as the input data-types. Assume that all data-types have enough range to accommodate any number. If two different data-types are operated on, the result assumes the more expressive data-type.

What will be the output of the following pseudo-code statements?

Integer a = 456, b, c, d =10

b = a/d

c = a – b

print c

a) 410

b) 410.4

c) 411.4

d) 411

**Ans: d**

a/d = 456/10 = 45.6 =45 ( input data type and the output must be same) c = 456 – 45 = 411** **

10) Geeta takes as input 2 integer numbers, a and b, whose value can be between 0 and 31. She stores them as 5 bit numbers. She writes the following code to process these numbers to produce a third number c à c = 2*(a – b)

In how many minimum bits should Geeta store c?

a) 6 bits

b) 7 bits

c) 8 bits

d) 9 bits

**Ans: b**

c = 2*(a – b)

For lowest number, when a=0 and b=31 à c= 2*(0-31) = -62

For highest number, when a=31 and b=0 à c= 2*(31-0) = 62

Range= -62 to 62, so It will fit on (-64 to 63) i.e., 2^7

Bits Required = 7

**Amcat Programming Question – Set 2**

11) Which of the following data structures may give overflow error, even though the current number of elements in it is less than its size?

a) Queue implemented in a linear array

b) Queue implemented in a circularly connected array

c) Stack implemented in a linear array

d) None of these

**Ans: a**

In a queue data structure implemented in a static linear array, for an enqueue operation the rear pointer is incremented. Similarly, for a dequeue operation the front pointer is incremented. When the front pointer is incremented, the memory space before front becomes useless. So even if the size is more the queue will end up showing an overflow error.** **

12) Number of possible ordered trees with 3 nodes A, B, C is

a) 16

b) 12

c) 13

d) 14

**Ans: b**** **

13) Farhan writes a code to find the factorial of an inputted number. His code gives correct answers for some inputs and incorrect answers for others. What kind of error does his program have?

a) Syntactical error

b) Run-time Error

c) Logical Error

d) None of these

**Ans: c**

Syntactical Error and Run-time error will not give any output. Logical error is a bug in a program that causes it to operate incorrectly, but not to terminate abnormally. A logic error produces unintended or undesired output, although it may not immediately be recognized as such. The problem to the given question can be Integer overflow. If int is 32 bits, then the largest value it can represent is 2147483647. But 13 factorial is 6227020800. If it is 64-bit integer type such a long long, this can give up to 20 factorial.

14) 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 Bubble Sort

a) Insertion Sort

b) Selection Sort

c) Heap Sort

d) None

**Ans: b**

Sorting of books in a library is an example of insertion sort. We pick a book and place it in its corresponding place as it is done in an insertion sort.** **

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

a) 0.6

b) 0.1

c) 0.2

d) 0.5

**Ans: a**

The probability is 6/10. Due to uniform distribution, the probability that the new record will be placed to any location X will be same for any X of (1,2,3,4,5,6,7,8,9,10) & will be equal to 1/10. Now if the hash function will try to place the new record in to any of the locations 1,7,8,9,10 the record will be redirected to location 2 due to collision resolution by linear probing. And if hash function will try to place the new record into 2, since location 2 is available, the record will go to location 2. So The probability of going new record into location 2, will be same as probability that the output of hash function is any one of (1,2,7,8,9,10) out of (1,2,3,4,5,6,7,8,9,10) where each location is equally likely. So the chances will be 6/10 i.e., 0.6** **

16) 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?

a) 2

b) 3

c) 4

d) 5

**Ans: a**

The insertion is made twice. First insertion is inserting 6 before 7. Second insertion is inserting 18 between 12 and 30.

17) Ragu writes a program to find an element in the array A[5] with the following elements in order: 18 32 44 46 57. 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?

a) 44

b) 18

c) 46

d) 32

**Ans: a**

The array has 18 32 44 46 57 Binary search is performed only on sorted arrays. In this search the middle element is identified and if the element to be searched is lesser than the middle element then all the elements to the right of the middle value are neglected and again the middle value is obtained for the remaining elements. If the element to be searched is greater than the middle element then all the elements to the left of the middle value are neglected and again the middle value is obtained for the remaining elements. If the value is obtained in the first iteration itself, then the value should be the middle element of the array. Here the middle element is 44.** **

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

a) top< N

b) top <N-1

c) top > 0

d) top > 1

**Ans: b**

The array is 0,1,2,……,N-1. The maximum size of the array is N-1. To perform a PUSH operation, the stack should have free space. This is checked using the top pointer. If the top pointer is less than N1(maximum size) then PUSH operation can be done. If not the condition is called Stack Overflow. Hence X should be top<N-1.** **

19) 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?

a) 6

b) 7

c) 10

d) None of these

**Ans: b**

The maximum size of the queue is 10. For every DELETE operation the front pointer is incremented and the space becomes useless. Here, there are three DELETE operations. So, the front pointer is incremented by three spaces and these three spaces become useless. Hence 10-3=7. Only 7 spaces are available which the maximum size of the array is.** **

20) Riyaz 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 Riyaz use to represent the ticket booklet?

a) Queue

b) Stack

c) Array

d) Graph

**Ans: a**

Tickets are added to the end and are removed from the top. This follows the logic of First In First Out. This logic can be represented using a queue data structure.

**Amcat Programming Questions – Set 3**

21) Pragya sells footballs. She has a large container to store footballs which is closed from below. Footballs are piled one on top of the other in the box. When new balls are supplied, Pragya puts the balls in the box from the top. When a customer buys a ball, she delivers the ball at the top of the pile to the customer. Each ball has a code. She wants to store the ball codes in a data structure to keep track of her inventory. What data-structure should she use?

a) Queue

b) Stack

c) Array

d) Graph

**Ans: b**

The foot balls are put in the box from the top and are removed from the top. This follows the logic Last In First Out. This logic can be represented using a stack data structure.

22) A[0…19] is an array of maximum size 20. The number of elements it contains is stored in the variable, numberElements. Currently it contains 11 elements. Swati wants to insert an element val after the mth element in the array. She writes the following code for it:

for X

A[n+1] = A[n]

end

A[m] = val

Fill in X.

a) n = (m+1) to (numberElements-1) increment 1

b) n = m to numberElements increment 1

c) n = m to (numberElements-1) increment 1

d) n = (m+1) to (numberElements) increment 1

**Ans: c**

The elements will have to be moved from right to left. The condition would be moving the elements from the m^{th} position till the last position. The last position can be identified by numberElements-1(since array index starts from 0,1,2,3,…). Number of elements is 11. So the elements will be stored from 0 to 10. The starting value will be from the m^{th} position. So from m^{th} position till the last position we will have to increment 1 to create free space. So, n= m to (numberElements-1) increment 1.

23) To fully specify a singly linked linked-list, which of the following options is necessarily required?

a) Address of first element

b) Address of last element

c) Address of first and last element

d) All the above are insufficient

**Ans: a**

To fully specify a linked list, we need HEAD pointer. The HEAD pointer holds the address of the first element. Hence address of the first element is required.

24) A list is implemented as a singly linked link-list. The address of the first and last node are stored in variables first and last. 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. Yusuf writes the code to delete the first element from the linked-list. He writes the following function, where first and last are passed by reference.

function deleteElement(first, last)

{

if (first isequal null)

{ print “List empty” }

else

{

first = first->next

}

}

In which of the following scenarios will the code not work properly?

a) When the list has no elements

b) When the list has a single element

c) When the list has two elements

d) It will work well in all possible cases.

**Ans: d**

When the list has no elements the program will successfully return “List empty”. When list has a single element, the node->next value will be NULL. When executing the ‘first=first->next’ statement the first pointer will take NULL value which will successfully eliminate the first node from the list. When list has two elements then the program will move the first pointer to the next node which will successfully eliminate the first node from the list.

25) Which of these is untrue about a binary search tree?

a) Each node has two children

b) A node may have no children

c) A node may have one child

d) Every node except the root has a parent

**Ans: a**

Each node may have two children. But it is not a compulsion that each node should have two children. A node in a binary search tree may have no child or a single child or at most two children.

26) For a binary search tree, which traversal will result in a sorted list?

a) Preorder

b) Inorder

c) Postorder

d) None of these

**Ans: b**

In a binary search tree all the elements less than the root node are towards the left subtree and all the elements greater than the root node are towards the right subtree. The left most node of a tree will have the minimum value and the right most node of the tree will have the maximum value. To sort the elements in ascending order, the traversal must be: left sub tree, root, right sub tree. This is done by in order traversal.

27) Fiza have a binary search tree and want to derive a list sorted in descending order from it. For each node, what traversal ordering will Fiza use?

a) left sub-tree, root, right sub-tree

b) root, left sub-tree, right sub-tree

c) right sub-tree, root, left sub-tree

d) root, right sub-tree, left-subtree

**Ans: c**

In a binsary search tree all the elements less than the root node are towards the left subtree and all the elements greater than the root node are towards the right subtree. The left most node of a tree will have the minimum value and the right most node of the tree will have the maximum value. To sort the elements in descending order, the traversal must be: right subtree, root, left subtree.

28) For a binary tree with n nodes, what is the time complexity to search an element in it?

a) O(log n)

b) O(n)

c) O(n^{2})

d) None of these

**Ans: a**

29) To search an element in a binary tree, all the nodes need not be visited. Therefore, it is not O(n). The number of possibilities reduces by half for every iteration. Hence the time complexity is O(log n).

We have a list of elements and we want to sort them using insertion sort. Which data structure among the following should we use to store the elements to give low time-complexity of sorting on average?

(Assume all access times as would be in a real-world scenario)

a) Array

b) Linked List

c) Stack

d) Hash Table

**Ans: b**

Stack and hash table cannot be used for sorting since the order of the elements in them cannot be modified. Array will not be efficient as inserting an element in the middle will have to move all the elements. Linked list data structure would be efficient for sorting as inserting an element in the middle will require only change in pointers and no movement of data.

30) Rashmi works on a computer where the time of comparing two numbers is very high and this time dominates the execution time. She implements a few different sorting algorithms. One algorithm out of these always took the same amount of execution time irrespective of the input array. Which sorting algorithm was this?

a) Quicksort

b) Bubble sort

c) Insertion Sort

d) None of these

**Ans: b**

Bubble sort makes the maximum number of comparisons.

Once you have completed practicing Amcat programming questions, then you can check out Amcat Automata Questions.