info@tutorialdiary.com

# AMCAT Data Structure Questions Part 1 | AMCAT Questions | AMCAT Preparation

### 12:41 AM

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

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 1: O (log2 n)

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 4: Bubble 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

Op 5:

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

factor

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:

Correct Op : 2

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 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 1: stack

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 3: A [x+2x]

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

Op 5:

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

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

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

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

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:

Correct Op : 2

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"

}

}

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"

}

}

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

DELETE

DELETE

DELETE

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.

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 2: Stack

Op 3: Array

Op 4: Graph

Op 5:

Correct Op : 1