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