## Friday, 11 November 2016

### AMCAT Previous Years Questions on Data Structures : Arrays, Linked Lists, Trees, Graphs Stacks, Queues Hash Tables Heaps

 Topics Sub- Topics Expected Questions Basic Programming 10 - 12 Questions Data Structures 6 - 8 Questions OOPs 4 - 6 Questions Miscellaneous 4 - 5 Questions

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

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

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

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

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

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

Ques140. Stack is useful for implementing
Op 3: recursion
Op 4: none of these
Op 5:
Correct Op : 3

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

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

Ques143. Which of the following abstract data types can be used to represent a manyto-many
relation?
Op 1: Tree
Op 2: Stack
Op 3: Graph
Op 4: Queue
Op 5:
Correct Op : 3

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

Ques145. Which of the following sorting algorithms yield approximately the same worstcase
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

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

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

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

Ques149. 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 3: Address of last node
Op 4: Address of first node
Op 5:
Correct Op : 1

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

Ques151. Which of the following is a bad implementation for a queue?
Op 1: Circular List
Op 4: Linear Static Array
Op 5:
Correct Op : 4

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

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

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

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

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

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

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

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

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

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

Ques166. Q is an empty queue. The following operations are done on it:
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

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

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

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

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

Ques171. 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
</n
</n-1