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 (n

^{2})
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(n

^{2}) 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: n

^{2}
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: 2

^{l-1}
Op 2: 3

^{l- 1}
Op 3: 2

^{l}Op 4: 2^{l}- 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