AMCAT DETAILS compiled questions on Data Structures and Algorithms. Hope this will be helpful for each and every AMCAT takers.
AMCAT Data Structure Questions Part 1 | AMCAT Questions for AMCAT Preparation
AMCAT Data Structure Questions Part 1 | AMCAT Questions for AMCAT Preparation
Ques. 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?
Op 1: Top-down Approach
Op 2: Bottom-Up
Approach Op 3: Procedural Programming Op 4: None of these
Op 5:
Correct Op :
1
Ques. The time complexity of linear
search algorithm over an array of n elements is
Op 2: O (n)
Op 3: O (n log2 n )
Op 4: O (n2)
Op 5:
Correct Op : 2
Ques. 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
Ques. 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
Ques. 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 5:
Correct Op : 4
Ques. 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
Ques. 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
Ques. 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
Correct Op : 1
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Ques. The average search time of hashing
with linear probing will be less if the load
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
Ques. 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
Ques. 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
Ques. 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:
Ques. 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
Ques. Stack is useful for implementing
Op 1: radix search
Op 2: breadth first search
Op 3: recursion
Op 4: none of these
Op 5:
Correct Op : 3
Ques. 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
Ques. Which of the following is useful in
implementing quick sort?
Op 2: set
Op 3: list
Op 4: queue
Op 5:
Correct Op : 1
Ques. Which
of the following abstract data types can be used to represent a many-to-many
relation?
Op 1: Tree
Op 2: Stack
Op 3: Graph
Op 4: Queue Op 5:
Correct Op : 3
Ques. 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?
Op 1: lastB ->
next = firstA Op 2: lastA = firstB
Op 3:
lastA->next = firstB Op 4: lastB = firstA
Op 5: Correct Op :
3
Ques. Which of the following sorting algorithms
yield approximately the same worst-case 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
Ques. 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
Ques. 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
Ques. 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 4: All of these.
Op 5:
Correct Op : 1
Ques. 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 2: It's own address
Op 3: Address of last node Op 4: Address of first node Op 5:
Correct Op : 1
Ques.
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
Ques. 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
Correct Op : 4
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Op 1: 2n + 1 nodes
Op 2: log2 n nodes
Op 3: 2n - 1 nodes
Op 4: 2n nodes
Op 5:
Correct Op : 3
Ques. 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
Ques. 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
Ques.
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
Op 2: 8
Op 3: 70
Op 4: 30 Op 5:
Correct Op : 1
Ques. 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
Ques. 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:
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Ques. 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
Ques. 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 3: Array
Op 4: Graph
Op 5:
Correct Op : 1
0 comments:
Post a Comment