AMCAT Placement Paper - 1

1.Which data structure is needed to convert infix notations to postfix notations
linear list
tree
stack
queue
Ans-> stack

2.    Which sorting method is slowest
Quick sort
Heap sort
Shell sort
Bubble sort
Ans-> Bubble sort

3. O log(n) can be conneted with
Selection sort
Insertion sort
Binary sort
Merge sort
Ans-> Binary sort

4. The memory address of the first element of an array is called
floor address
first address
foundation address
base address
Ans-> Binary address

5. Which of the following name does not relate to stacks

FIFO lists
LIFO list
Piles
Push-down lists
Ans-> FIFO lists
6. Which of the following data structure is linear data structure

Trees
Graphs
Array
None of above
Ans-> Array
7. The complexity of linear search algorithm is

O(n)
O(log n)
O(n2)
O(n log n)
Ans-> O(n)
8.  The complexity of Binary search algorithm is

O(n)
O(log n)
O(n2)
O(n log n)
Ans-> O(log n)
9.  Information about an array used in a program will be stored in

symbol table
activation record
dope vector
system table
Ans-> dope vector
10. Deletion from one end and insertion from other end is

stack
branch
tree
queue
Ans-> queue
11. minimum number of stacks of size n required to implement a queue of size n

One
Two
Three
Four
Ans-> Two
In the following sorting procedures, which one will be the slowest for any given array?
Option 1 : Quick sort
Option 2 : Heap sort
Option 3 : Merge Sort
Option 4 : Bubble sort
Ans-4
Que: Choose the correct answer
The time required to insert an element in a stack with linked list implementation is
Option 1 : O (1)
Option 2 : O (log2 n)
Option 3 : O (n)
Option 4 : O (n log2 n )
Ans-1
Que: Choose the correct answer
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:
Option 1 : O (1)
Option 2 : O (log2 n)
Option 3 : O (n)
Option 4 : O (n log2 n )
Ans-B
Que: Choose the correct answer
The time complexity of linear search algorithm over an array of n elements is
Option 1 : O (log2 n)
Option 2 : O (n)
Option 3 : O (n log2 n )
Option 4 : O (n2)
Ans-2
Que: Choose the correct answer
To solve a problem, it is broken in to a sequence of smaller sub-problems, till a stage that the sub-problem can be easily
solved. What is this design approach called?
Option 1 : Top-down Approach
Option 2 : Bottom-Up Approach
Option 3 : Procedural Programming
Option 4 : None of these
Ans-4
Que: Choose the correct answer
Tarun wants to write a code to divide two numbers. He wants to warn the user and terminate the program if he or she
enters 0 as the divisor. Which programming construct can he use to do this?
Option 1 : Iteration
Option 2 : Decision-making
Option 3 : Recursion
Option 4 : None of these
Ans-2
Que: Choose the correct answer
A robust program has which one of the following features?
Option 1 : It runs correctly on some inputs
Option 2 : It is robust to hardware damage
Option 3 : It can handle incorrect input data or data types.
Option 4 : None of these
Ans-3

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?
Option 1 : 1
Option 2 : 10
Option 3 : 50
Option 4 : 20
Ans-10
Que: Choose the correct answer
The average time required to perform a successful sequential search for an element in an array A(1 : n) is given by
Option 1 : (n+1) / 2
Option 2 : log2n
Option 3 : n(n+1) / 2
Option 4 : n2
Ans-option A
Que: Choose the correct answer
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
Option 1 : selection sort
Option 2 : insertion sort
Option 3 : heap sort
Option 4 : quick sort
Ans-heap sort
Que: Choose the correct answer
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?
Option 1 : insertion sort
Option 2 : selection sort
Option 3 : heap sort
Option 4 : quick sort
Ans-option 1
Que: Choose the correct answer
A sorting algorithm traverses through a list, comparing adjacent elements and switching them under certain conditions.
What is this sorting algorithm called?
Option 1 : insertion sort
Option 2 : heap sort
Option 3 : quick sort
Option 4 : bubble sort
Ans-Bubble sort

Que: Choose the correct answer
The order of magnitude of the worst case performance of a hash coded search (over N elements) is
Option 1 : N
Option 2 : N log2 N
Option 3 : log2 N
Option 4 : not dependent upon N
Ans-N
Que: Choose the correct answer
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?
Option 1 : O(1)
Option 2 : O(n2)
Option 3 : O(log n)
Option 4 : O(n)
Ans-1
Que: Choose the correct answer
Which of the following abstract data types can be used to represent a many-to-many relation?
Option 1 : Tree
Option 2 : Stack
Option 3 : Graph
Option 4 : Queue
Que: Choose the correct answer
A connected graph is the one which
Option 1 : Cannot be partitioned without removing an edge
Option 2 : Can be partitioned without removing an edge
Option 3 : does not contain a cycle
Option 4 : Has even number of vertices
Que: Choose the correct answer
Linked lists are not suitable for
Option 1 : Insertion sort
Option 2 : Binary search
Option 3 : Queue implementation
Option 4 : None of these
Que: Choose the correct answer
Number of vertices of odd degree in a graph is
Option 1 : is always even
Option 2 : always odd
Option 3 : either even or odd
Option 4 : always zero
Que: Choose the correct answer
The average search time of hashing with linear probing will be less if the load factor
Option 1 : is far less than one
Option 2 : equals one
Option 3 : is far greater than one
Option 4 : none of these
Que: Choose the correct answer
Queues serve a major role in
Option 1 : simulation of recursion
Option 2 : simulation of arbitrary linked list
Option 3 : simulation of limited resource allocation
Option 4 : expression evaluation
Which of the following data structure may give overflow error, even though the current number of element in it is less
than its size ?
Option 1 : Queue implemented in a linear array
Option 2 : Queue implemented in a circularly connected array
Option 3 : Stack implemented in a linear array
Option 4 : none of these
Que: Choose the correct answer
Number of possible ordered trees with 3 nodes A, B, C is
Option 1 : 16
Option 2 : 12
Option 3 : 13
Option 4 : 14
Que: Choose the correct answer
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
Option 1 : 0.6
Option 2 : 0.1
Option 3 : 0.2
Option 4 : 0.5
Que: Choose the correct answer
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?
Option 1 : 10 8 7 5 4
Option 2 : 10 8 5 7 4
Option 3 : 8 10 5 7 4
Option 4 : None of these
Que: Choose the correct answer
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?
Option 1 : 2
Option 2 : 3
Option 3 : 4
Option 4 : 5
Que: Choose the correct answer
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?
Option 1 : a stack
Option 2 : a queue
Option 3 : Binary Tree
Option 4 : None of these
Que: Choose the correct answer
In an implementation of a linked list, each node contains data and address. Which of the following could the address
field possibly contain?
Option 1 : Address of next node in sequence
Option 2 : It’s own address
Option 3 : Address of last node
Option 4 : Address of first node
Que: Choose the correct answer
The maximum number of nodes on level I of a binary tree is which of the following? (Root is Level 1)
Option 1 : 2l-1
Option 2 : 3l-1
Option 3 : 2l
Option 4 : 2l – 1
Que: Choose the correct answer
A complete binary tree with 5 levels has how many nodes? (Root is Level 1)
Option 1 : 15
Option 2 : 25
Option 3 : 63
Option 4 : 31
Que: Choose the correct answer
Which of the following sorting algorithms yield approximately the same worst-case and average-case running time
behaviour in O (n log n)?
Option 1 : Bubble sort and Selection sort
Option 2 : Heap sort and Merge sort
Option 3 : Quick sort and Radix sort
Option 4 : Tree sort and Median-of-3 Quick sort
Que: Choose the correct answer
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?
Option 1 : lastB -> next = firstA
Option 2 : lastA = firstB
Option 3 : lastA->next = firstB
Option 4 : lastB = firstA
Now we know the importance of data structures in AMCAT exams, you may want to refer the syllabus  of data structures here
You have to sort a list L consisting of a sorted list followed by a few “random” elements.
Which of the following sorting methods would be especially suitable for such a task?
(A) Bubble sort (B) Selection sort
(C) Quick sort (D) Insertion sort
Ans-D
B Trees are generally
(A) very deep and narrow (B) very wide and shallow
(C) very deep and very wide (D) cannot say
Ans-D
A technique for direct search is
(A) Binary Search (B) Linear Search
(C) Tree Search (D) Hashing
And-D
If a node having two children is deleted from a binary tree, it is replaced by its
(A) Inorder predecessor (B) Inorder successor
(C) Preorder predecessor (D) None of the above
Ans-B
The searching technique that takes O (1) time to find a data is
(A) Linear Search (B) Binary Search
(C) Hashing (D) Tree Search
Ans-C
A mathematical-model with a collection of operations defined on that model is called
(A) Data Structure (B) Abstract Data Type
(C) Primitive Data Type (D) Algorithm
Ans-B
The number of interchanges required to sort 5, 1, 6, 2 4 in ascending order using Bubble Sort
is
(A) 6 (B) 5
(C) 7 (D) 8
Ans-B
The postfix form of the expression (A+ B)*(C*D− E)*F / G is
(A) AB+ CD*E − FG /** (B) AB + CD* E − F **G /
(C) AB + CD* E − *F *G / (D) AB + CDE * − * F *G /
Ans-A
In worst case Quick Sort has order
(A) O (n log n) (B) O (n2/2)
(C) O (log n) (D) O (n2/4)
Ans-B
A full binary tree with 2n+1 nodes contain
(A) n leaf nodes (B) n non-leaf nodes
(C) n-1 leaf nodes (D) n-1 non-leaf nodes
Ans-B
If a node in a BST has two children, then its inorder predecessor has
(A) no left child (B) no right child
(C) two children (D) no child
Ans-B
A sort which relatively passes through a list to exchange the first element with any element
less than it and then repeats with a new first element is called
(A) insertion sort. (B) selection sort.
(C) heap sort. (D) quick sort.
Ans-D
Which of the following sorting algorithms does not have a worst case running time of O(n^2) ?
(A) Insertion sort (B) Merge sort
(C) Quick sort (D) Bubble sort
Ans-B
The smallest element of an array’s index is called its
(A) lower bound. (B) upper bound.
(C) range. (D) extraction.
Ans-A
The data structure required for Breadth First Traversal on a graph is
(A) queue (B) stack
(C) array (D) tree
Ans-A
The quick sort algorithm exploit _________ design technique
(A) Greedy (B) Dynamic programming
(C) Divide and Conquer (D) Backtracking
Ans-C
The data structure required to check whether an expression contains balanced parenthesis is
(A) Stack (B) Queue
(C) Tree (D) Array
Ans-
The data structure required to evaluate a postfix expression is
(A) queue (B) stack
(C) array (D) linked-list
Ans-B
Which of the following sorting methods would be most suitable for sorting a list which is
almost sorted
(A) Bubble Sort (B) Insertion Sort
(C) Selection Sort (D) Quick Sort
Ans-A
O(N) (linear time) is better than O(1) constant time.
(A) True (B) False
Ans-B
The best average behaviour is shown by
(A) Quick Sort (B) Merge Sort
(C) Insertion Sort (D) Heap Sort
Ans-A

No comments:

Post a Comment