UNIT-I

1. A Singly linked list has .......... pointers with each node. [ ]

A. 0 B. 1 C. 2 D. 3
2. The memory address of the first element of an array is called [ ]
A. floor address B. foundation address C. first address D. base address
3. Two dimensional arrays are also called [ ]
A. Tables arrays B. matrix arrays C. both of above D. none of above
4. A doubly linked list is also called as _________ [ ]
A. linked list B. one way chain C. two way chain. D. right link
5. A data structure in which elements can be inserted or deleted at/from both the ends but not in the
middle is? [ ]
A. Queue B. Circular queue C. Double ended queue D. Priority queue
6.Which of the following is not a type of Dequeue? [ ]
A. Input Restricted Queue B. Output Restricted Queue C. both a & b D. None
7. Which of the following data structure can't store the non-homogeneous data elements?
A. Arrays B. Records C. Pointers D. Stacks [ ]
8. Which of the following data structure is non linear type? [ ]
A. Strings B. Lists C. Stacks D. Graph
9. A block of memory can be requested at run time using____________ [ ]
A. malloc B. calloc C. both A&B D. None
10. In a linked list, insertion can be done as ......... [ ]
A. beginning B. end C. middle D. all of the above
11. RLINK is the pointer pointing to the ... [ ]
A. successor node B. predecessor node C. head node D. last node
12. A linear list in which each node has point to the predecessor and successors nodes is called
[ ]
A. singly linked list B. circular linked list C. doubly linked list D. linear linked list
13.A variable P is called pointer if_____________________ [ ]
A. P contains the address of an element in DATA.
B. P points to the address of first element in DATA
C. P can store only memory addresses
D. P contain the DATA and the address of DATA
14. ________ is collection of same type elements. [ ]
A. Array B. Structure C. Both D. None
15. The logical or mathematical model of particular organization of data is called….. [ ]
A. Data Structure B. Data Arrangement C. Data formation D. Data Configuration
16.If the Linked List is Empty, then the value of the head node is [ ]
A. -1 B. NULL C. 1 D. None of Above
17. Traversing means_________ [ ]
A. Visiting all the nodes of the list B. shifting all the nodes forward
C. Randomly accessing the elements D. None
18.Each node in a linked list has two pairs of ____ and ____ [ ]
A. Link field and Information field B. Link field and avail field
C. Avail field and Information field D. Address field and link field
19.The value of the first index in linked-list is ____________ [ ]
A. –1 B. 0 C. 1 D. None
20. Which of the following is disadvantage in using “linked lists”? [ ]
A. requires more memory B. dynamic data structure
C. elements are deleted and inserted easily D. None
21. In C, if you pass an array as an argument to a function, what actually gets passed? [ ]
A. Value of elements in array B. First element of the array
 C. Base address of the array D. Address of the last element of array
22. A pointer array variable contains ------------as it’s elements [ ]
A. integer values B. addresses of memory locations C. both A&B D. None
23. A linked list where the last node points the header node is called______ [ ]

A. Linked List B. Double Linked List C. Circular Linked List D. All

24. . In a circular linked list [ ]
A. Components are all linked together in some sequential manner.
B. There is no beginning and no end.
C. Components are arranged hierarchically.
D. Forward and backward traversal within the list is permitted.
25. Which of the following data structures are convenient to perform insertion and deletion
operations [ ]
A. arrays B. linked lists C. both A&B D. None
26. A 2D array which contains majority of elements as null or zero [ ]
A. sparce matrix B. sparse matrix C. null matrix D. All are correct
27. Memory for elements in an array is allocated in --------------------------- [ ]
A)contiguous locations(addresses) B)random locations(addresses) C)can’t predict
D)all are wrong options
28. The smallest element of an array’s index iscalled its [ ]
A)lower bound B) upper bound C) range D) boundary
29. A doubly linked list has .......... pointers with each node. [ ]
A) 0 B) 1 C) 2 D) 3
30. To implement Sparse matrix dynamically, the following data structure is used [ ]
A) Trees B) Graphs C) Priority Queues D) Linked List
31. Linked lists are not suitable to for the implementation of? [ ]
a) Insertion sort b) Radix sort c) Polynomial manipulation d) Binary search
32. Linked list is considered as an example of ___________ type of memory allocation. [ ]
a) Dynamic b) Static c) Compile time d) Heap
33Which of these is not an application of linked list? [ ]
a) To implement file systems b) For separate chaining in hash-tables
c) To implement non-binary trees d) Random Access of elements
34. A linear collection of data elements where the linear node is given by means of
pointer is called? [ ]
a) Linked list b) Node list c) Primitive list d) None
35. Consider an implementation of unsorted singly linked list. Suppose it has its
representation with a head and tail pointer. Given the representation, which of [ ]
the following operation can be implemented in O(1) time?
i) Insertion at the front of the linked list
ii) Insertion at the end of the linked list
iii) Deletion of the front node of the linked list
iv) Deletion of the last node of the linked list
a) I and II
b) I and III
c) I,II and III
d) I,II and IV
36. In linked list each node contain minimum of two fields. One field is data field to [ ]
store the data second field is?
a) Pointer to character
b) Pointer to integer
c) Pointer to node
d) Node
37. The concatenation of two list can performed in O(1) time. Which of the following variation of linked list can
be used?
a) Singly linked list
b) Doubly linked list
c) Circular doubly linked list
d) Array implementation of list
38.Consider the following definition in c programming language
struct node
{
int data;
struct node * next;
}
typedef struct node NODE;
NODE *ptr;
Which of the following c code is used to create new node?
a) ptr=(NODE*)malloc(sizeof(NODE));
b) ptr=(NODE*)malloc(NODE);
c) ptr=(NODE*)malloc(sizeof(NODE*));
d) ptr=(NODE)malloc(sizeof(NODE));
39.In doubly linked lists, traversal can be performed?
a) Only in forward direction
b) Only in reverse direction
c) In both directions
d) None
40.A variant of the linked list in which none of the node contains NULL pointer is?
a) Singly linked list
b) Doubly linked list
c) Circular linked list
d) None
 UNIT-II

1. The term "push" and "pop" is related to the [ ]

A. array B. lists C. Stacks D. all of above
2. The data structure required to check whether an expression contains balanced parenthesis is?
A. Stack B. Queue C. Array D. Tree [ ]
3.The postfix form of A*B+C/D is? [ ]
A. *AB/CD+ B. AB*CD/+ C. A*BC+/D D. ABCD+/*
4. Which data structure is needed to convert infix notation to postfix notation? [ ]
A. Branch B. Tree C. Queue D. Stack
5. Which of the following statement(s) about stack data structure is/are NOT correct? [ ]
A. Stack data structure can be implemented using linked list
B. New node can only be added at the top of the stack
C. Stack is the FIFO data structure
D. The last node at the bottom of the stack has a NULL link
6. Consider the linked list implementation of a stack. Which of the following node is considered as Top
of the stack? [ ]
A. First node B. Last node C. Any node D. Middle node
7. A queue is a data structure in which insertions and deletions are made respectively at:___
A. rear and front B. front and front C. front and rear D. rear and rear [ ]
8. The prefix form of A-B/ (C * D ⋀ E) is? [ ]
A. -/*⋀ACBDE B. -ABCD*⋀DE C. -A/B*C⋀DE D. -A/BC*⋀DE
9. A stack is a data structure in which all insertions and deletions of entries are made at
A. One end B. In the middle C. Both the ends D. At any position [ ]
10. Quick Sort also called [ ]
A. Exchange-Partition sort B. Linear sort C. Divide sort D.None
11. New nodes are added to the ____________ of the queue. [ ]
A. front B. back C. middle D. None
12. Stacks are dynamically represented using _______ [ ]
A.Pointers B. Structures C. Linked lists D. None
13. When stack is said to be empty? [ ]
A. TOP==N B. TOP==0 C. FRONT==0 D. FRONT=REAR=0
14. The insertion and deletion are done at _______ of the stack [ ]
A. FRONT B. REAR C. TOP D. None
15.The PUSH operation is used to _____ [ ]
A. Insert an element B. Remove an element C. Move an element D. None
 16. A stack holds elements equal to its capacity and if PUSH is performed then such a situation is called
[ ]
A. Stack overflow B. Stack underflow C. Illegal operation D. None
17. The data structure used in railway reservation is [ ]
A.Stacks B. Queues C. Priority queues D. Binary tree
18. If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time,
in what order they will be removed? [ ]
A. ABCD B. ABDC C. DCAB D. DCBA
19. A linear list of elements in which deletion can be done from one end (front) and insertion can take
place only at the other end (rear) is known as a ? [ ]
A. Queue B. Stack C. Tree D. Linked list
20. Stack is a _______ data structure. [ ]
A. FIFO B. LIFO C. both a and b D. FOLI
21. The pointer TOP increases when an ________ [ ]
A. Element is inserted B. Element is deleted C. Element is displayed D. None
22. What is the postfix form of the following prefix *+ab–cd [ ]
A. ab+cd–* B. abc+*– C. ab+*cd– D. b+*cd–
23. Which of the following is not an inherent application of stack? [ ]
A. Reversing a string B. Evaluation of postfix expression
C. Implementation of recursion D. Job scheduling
24. The prefix notation is also called as_____ notation [ ]
A. Polish B. Reverse polish C. Infix D. Postfix
25. The Towers of Hanoi is an application of ______ [ ]
A. Stack B. Queue C. Linked list D. Dequeue
26. . In evaluation of postfix expression the data structure used is [ ]
A. Queues B. Stacks C. Arrays D. Binary tree
27. 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 /
28. The postfix form of A*B+C/D is? [ ]
A. *AB/CD+ B. AB*CD/+ C. A*BC+/D D. ABCD+/*
29. In Towers of Hanoi problem the possible number of moves are [ ]
A. 2n-1 B. 2n-1 C. 3n-1 D. All
30. A circular queue is implemented using an array of size 10. The array index starts with 0, front
is 6, and rear is 9. The insertion of next element takes place at the array index. [ ]
A. 0 B. 7 C. 9 D. 10
31. Stack data structure works based on ________ principle. [ ]
A. FIFO B. LIFO C. FILO
 32. The prefix notation is also called as_____ notation [ ]
A. Polish B. Reverse polish C. Infix D. Postfix
33. 18.In a priority queue, insertion and deletion takesplace at ……………… [ ]
 A) front, rear end B) only at rear end C)only at front d)At any position
34. Which of the following is useful in the implementation of quick sort ? [ ]
A)Set B)Queue C)Stack D)List
35. Well formed parenthesis can be checked using following data structure ? [ ]
A)Stack B)List C)Queue D)Hash Map
36. Post fix form of -(A + B) * C [ ]
A) ABC * + B)ABC + * C)AB + C * D)AB * C +
37. Expression in which Operator is written after Operand is called as ________. [ ]
A) Postfix Expression B)Prefix Expression C)Infix Expression d)none
38. Data Structure required to evaluate infix to postfix is __________. [ ]
A)Heap B)Stack C)Pointer D)Queue
39. What would be the Prefix notation for the given equation? [ ]
A+B*C^D
a) +A*B^CD b) +A^B*CD c) *A+B^CD d) ^A*B+CD
40.Out of the following operators (^, *, +, &, $), the one having highest priority is [ ]
_________
a) + b) $ c) ^ d) &
 UNIT-III
1.All Trees are ________ [ ]
A)Binary Trees B)Arrays C)Graphs D)Heaps.
2. In which of the following trees all leaf nodes must be at same level? [ ]
A)Complete B)Full C)Skewed D)All
3. In a Complete Binary Tree if a Node is at index I then its root is at _______ [ ]
A)i/2 B) 2I C) 2I+1 D) 2I+2
4. In a Complete Binary Tree if a Node is at index I then its left child is at ___ [ ]
A)i/2 B)2I C)2I+1 D)2I+2
5. A Binary search tree is constructed using 1, 2, 3, 4, 5, 6, 7, 8.then
what is the result of preorder traversal? [ ]
A)53124786 B)53126487 C)12345678 D)none
6. In which of the following collision resolution techniques,an index in
a hash table can accommodate more than one key? [ ]
A)chaining B)bucket hashing C)both a&b D)none
7. Which of the following must be complete binary tree? [ ]
A)red-black tree B)AVL tree C)heap tree D)B-Tree
8. In a Complete Binary Tree if a Node is at index I then its right child is at ___ [ ]
A)i/2 B)2I C)2I+1 D)2I+2
9. A binary tree is generated by inserting 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24 in order.
The number of nodes in the left and right subtree, respectively is given by [ ]
A)(4, 7) B)(7, 4) C)(8, 3) D)(3, 8)

10. In which of the following traversals root node is visited first? [ ]

A)a preorder B)an inorder C)a postorder D)A or B
11. Which of the following traversal techniques lists the nodes of a BST in
ascending order? [ ]
A)Postorder B)Inorder C) Preorder D) All of a, b, c
12. A binary tree has a height of 5. What is the minimum number of nodes it can have? [ ]
A)31 B)15 C)5 D)1
13. A list of integers is read one at a time, and a BST is constructe Next, the tree is traversed and
the integers are printe Which traversal would print the result in the original
order of the input? [ ]
A)Preorder B) Postorder C) Inorder D)None of the above
14. A binary tree T h as n leaf nodes. The number of nodes of degree 2 in T is [ ]
A)log2 n B) n – 1 C)n D) 2n
15. A binary tree where every non-leaf node has non-empty left and right subtrees is called
a strictly binary tree. Such a tree wi th 10 leaves [ ]
A)cannot have more than 19 nodes. B)has exactly 19 nodes.
C)has exactly 17 nodes. D)cannot have more than 17 nodes.
16. An edge that has identical end-points is called a [ ]
A)Multi-path B) Loop C) Cycle D) Multi-edge
17. The number of different binary trees possible with "6" nodes is [ ]
A)5 B)9 C)6 D)10
18. Which way of tree representation is efficient? [ ]
A)array B)linked list C)circular queue D)stack
19. Two or more nodes with a same parent is called [ ]
A)siblings B)twins C)children D)both a&b
20. A tree in which no node can have more than two children is called [ ]
A)binary tree B)skewed tree C)binary search tree D)All
21. The total number of edges containing the node u is called [ ]
A)In-degree B) Out-degree C)Degree D)None of these
22. elements arranged in hierarchical fachion is called [ ]
A)tree B)graph C)array D)linked list
23. Stack is used in which of the following graph traversal techniques [ ]
A)BFS B)DFS C)Inorder traversal D)post order traversal
24. The number of different binary trees possible with "3" nodes is [ ]
A)5 B)9 C)6 D)10
25. A binary tree T has n leaf nodes. The number of nodes of degree 2 in T is [ ]
A)n-1 B)n C)n-2
26. What is common in three different types of traversals (Inorder, Preorder and Postorder)?[ ]
A Root is visited before right subtree B)Left subtree is always visited before right subtree
C Root is visited after left subtree D)All of the above
27. Which traversal of tree resembles the breadth first search of the graph? [ ]
A)Preorder B)Inorder C)Postorder D)Level order
28. Which of the following tree traversal uses a queue data structure?
(A) Preorder (B) Inorder (C) Postorder (D) Level order
29. For the tree below, write the pre-order traversal. [ ]

a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9
30.  For the tree below, write the post-order traversal. [ ]

a) 2, 7, 2, 6, 5, 11, 5, 9, 4
b) 2, 7, 5, 2, 6, 9, 5, 11, 4
c) 2, 5, 11, 6, 7, 4, 9, 5, 2
d) 2, 7, 5, 6, 11, 2, 5, 4, 9
31. To obtain a prefix expression, which of the tree traversals is used? [ ]
a) Level-order traversal b) Pre-order traversal c) Post-order traversal d) In-order traversal
32. What is an AVL tree? [ ]
a) a tree which is balanced and is a height balanced tree
b) a tree which is unbalanced and is a height balanced tree
c) a tree with three children
d) a tree with atmost 3 children
33. Why we need to a binary tree which is height balanced? [ ]
a) to avoid formation of skew trees
b) to save memory
c) to attain faster memory access
d) to simplify storing
34. What is the maximum height of an AVL tree with p nodes? [ ]
a) p b) log(p) c) log(p)/2 d) p⁄2
35. What is the special property of red-black trees and what root should always be? [ ]
a) a color which is either red or black and root should always be black color only
b) height of the tree
c) pointer to next node
d) a color which is either green or black

36. Which of the following is an application of Red-black trees and why? [ ]

a) used to store strings efficiently
b) used to store integers efficiently
c) can be used in process schedulers, maps, sets
d) for efficient sorting

37. When to choose Red-Black tree, AVL tree and B-trees? [ ]

a) many inserts, many searches and when managing more items respectively
b) many searches, when managing more items respectively and many inserts respectively
c) sorting, sorting and retrieval respectively
d) retrieval, sorting and retrieval respectively

38. While inserting into ………………………….., insertions are done at a leaf and will replace an external node with an
internal node with two external children. [ ]
A) red-black tree B) AVL tree C) binary search tree D) binary heap tree
39. The order with which the nodes are inserted affects the running time of the ……………………. search algorithm.
A) AVL Tree B) Red-Black Tree C) Binary Search Tree D) Binary Heap Tree
40The order with which the nodes are inserted affects the running time of the ……………………. search algorithm.
A) AVL Tree [ ]
B) Red-Black Tree
C) Binary Search Tree
D) Binary Heap Tree
 UNIT-IV
1.A Graph where each vertex is connected to all other vertices is called___ [ ]
A)Completely Connected B)Directed Graphs C)Cyclic Graphs D)All
2. which of the following implementation of hash table is collision free? [ ]
A)array B)linked list(chaining) C)both a&b D)none
3.secondary clustering doesn’t occur in following type of closed hashing technique? [ ]
A)Quadratic probing B)linear probing C)random probing D)both a &b
4. In which of the following,Hash table is an array of pointers
(i.e collection of memory addresses) [ ]
A)open hashing B)closed hashing C)chaining D)both a&c
5. In which of the following hash table implementations,elements(keys)
are organized as linked lists? [ ]
A)open addressing B)chaining C)closed hashing D) both a&c
6. Let us suppose ,hash table of size(n)=6.If collision occurred at index “4” then
if we use linear probing then sequence of probed indices Would be? [ ]
A)5-0-1-2-3 B)1-2-3-4-5 C)4-5-0-1-2 D)none
7. consider key=122466,hash table size(n)=100 &hash table index starts from “0”.
Identify the location of above key using “pure folding “ hashing method [ ]
A)102 B)10 C)2 D)none
8. consider key=122466,hash table size(n)=100 &hash table index starts from “0”.
Identify the location of above key using “digit analysis “ hashing method
(consider numbers at even positions from left to right) [ ]
A)246 B)642 C)266 D)none
9.Arrangement of given data in dictionary order is called [ ]
A)ascending B)descending C)lexicographic D)none
10. Hash table is a kind of ? [ ]
A)Array B)Linked list C)table D)set
11.Which of the following is associated with graph? [ ]
A)BFS B)DFS C)cycle D)all
12.shortest path finding” is an application of ? [ ]
A)tree B)graph C)binary tree D)none
13. If there is a path between any two vertices in a graph then it is called [ ]
A)simple graph B)connected graph C)complete graph D)path graph
14. A graph in which there exists a path between any two of its nodes is called [ ]
A)Complete graph B)Connected graph C) Digraph D) In-directed graph
15. Which is the most appropriate matching for the following pairs? [ ]
X: depth-first search 1: heap
Y: breadth-first search 2: queue
Z: sorting 3: stack
A)X–1, Y–2, Z–3 B)X–3, Y–1, Z–2
C)X–3, Y–2, Z–1 D)X–2, Y–3, Z–
16. Which of the following is associated with graph? [ ]
A)BFS B)DFS C)cycle D)all
17. In which of the following collision resolution techniques,an index in a hash table can
accommodate more than one key? [ ]
A)chaining B)closed hashing C)both a&b D)none
18. In which of the following hash table implementations,elements(keys)
are organized as linked lists? [ ]
A)open addressing B)chaining C)closed hashing D) both a&
19. Insert keys “2,6,10,3,40,11,46,49” into a hash table of size(n)=7 using chaining
collision resolution technique then What will be the previous element of “11”? [ ]
A)46 B)49 C)40 D)none
20. In which of the following collision resolution techniques,an index in
a hash table can accommodate more than one key? [ ]
A)chaining B)bucket hashing C)both a&b D)none
21. In Binary Search if the Search element is greater than the mid then the condition is [ ]
A)left= mid +1 B)right= mid-1 C)mid = (left+right)/2 D)None
22. The Binary Search Algorithms needs theelements to be in ________ Order [ ]
A)Ascending B)Random C)Both D)None
23. Which of the following searching is faster than others? [ ]
A)linear B)binary C)hashed search D)sentinel
24. Which of the following searching requires less time [ ]
A)sequential B)linear C)binary D)sentinel
25. The process of identifying or finding index(location of a key(element) in a given set
of numbers is called [ ]
A)searching B)finding C)identifying D)none
26. This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Graph”.
26. Which of the following statements for a simple graph is correct? [ ]
a) Every path is a trail
b) Every trail is a path
c) Every trail is a path as well as every path is a trail
d) Path and trail have no relation
27. What is the number of edges present in a complete graph having n vertices? [ ]
a) (n*(n+1))/2
b) (n*(n-1))/2
c) n
d) Information given is insufficient

28. In a simple graph, the number of edges is equal to twice the sum of the degrees of the vertices[ ].
a) True
b) False

29. A connected planar graph having 6 vertices, 7 edges contains _____________ regions. [ ]
a) 15
b) 3
c) 1
d) 11

30. Which of the following properties does a simple graph not hold? [ ]
a) Must be connected
b) Must be unweighted
c) Must have no loops or multiple edges
d) Must have no multiple edges

31. What is the maximum number of edges in a bipartite graph having 10 vertices? [ ]
a) 24
b) 21
c) 25
d) 16

32. Which of the following is true? [ ]

a) A graph may contain no edges and many vertices
b) A graph may contain many edges and no vertices
c) A graph may contain no edges and no vertices
d) A graph may contain no vertices and many edges

33. For a given graph G having v vertices and e edges which is connected and has no cycles, which of the
following statements is true? [ ]
a) v=e
b) v = e+1
c) v + 1 = e
d) v = e-1

34. A graph with all vertices having equal degree is known as a __________ [ ]
a) Multi Graph
b) Regular Graph
c) Simple Graph
d) Complete Graph

35. Which of the following ways can be used to represent a graph? [ ]

a) Adjacency List and Adjacency Matrix
b) Incidence Matrix
c) Adjacency List, Adjacency Matrix as well as Incidence Matrix
d) No way to represent

36. Dijkstra’s Algorithm will work for both negative and positive weights? [ ]
a) True
b) False

37. A graph having an edge from each vertex to every other vertex is called a ___________ [ ]
a) Tightly Connected
b) Strongly Connected
c) Weakly Connected
d) Loosely Connected

38. What would be the DFS traversal of the given Graph? [ ]

a) ABCED
b) AEDCB
c) EDCBA
d) ADECB

39. What is the maximum number of edges present in a simple directed graph with 7 vertices if there exists no
cycles in the graph? [ ]
a) 21
b) 7
c) 6
d) 49
40. All Graphs have unique representation on paper. [ ]
a) True
b) False
 UNIT-V
1. Which of the following is not a stable sorting algorithm? [ ]
a) Insertion sort b) Selection sort c) Bubble sort d) Merge sort
2. Which of the following is a stable sorting algorithm? [ ]
a) Merge sort b) Typical in-place quick sort c) Heap sort d) Selection sort
3. Which of the following is not an in-place sorting algorithm [ ]
a) Selection sort b) Heap sort c) Quick sort d) Merge sort
4. Running merge sort on an array of size n which is already sorted is [ ]
a) O(n)b) O(nlogn) c) O(n2) d) None
5. The time complexity of a quick sort algorithm which makes use of median, found by an O(n)
algorithm, as pivot element is [ ]
a) O(n2) b) O(nlogn) c) O(nloglogn)d) O(n)
6. Which of the following is not a noncomparison sort? [ ]
a) Counting sort b) Bucket sort c) Radix sort d) Shell sort
7. The time complexity of heap sort in worst case is [ ]
a) O(logn) b) O(n)c) O(nlogn) d) O(n2)
8. If the given input array is sorted or nearly sorted, which of the following algorithm gives the best
performance? [ ]
a) Insertion sort b) Selection sort c) Quick sort d) Merge sort
9. Which of the following algorithm pays the least attention to the ordering of the elements in the input
list? [ ]
a) Insertion sort b) Selection sort c) Quick sort d) None
10. Consider the situation in which assignment operation is very costly. Which of the following sorting
algorithm should be performed so that the number of assignment operations is minimized in general
a) Insertion sort b) Selection sort c) Heap sort d) None [ ]
11. Time complexity of bubble sort in best case is [ ]
a) θ (n) b) θ (nlogn) c) θ (n2) d) θ (n(logn) 2)
12. Given a number of elements in the range [0….n3]. which of the following sorting algorithms can sort
them in O(n) time? [ ]
a) Counting sort b) Bucket sort c) Radix sort d) Quick sort
13. Which of the following algorithms has lowest worst case time complexity? [ ]
a) Insertion sort b) Selection sort c) Quick sort d) Heap sort
14. Which of the following sorting algorithms is/are stable [ ]
a) Counting sort b) Bucket sort c) Radix sort d) All of the above
15. Counting sort performs …………. Numbers of comparisons between input elements. [ ]
a) 0 b) n c) nlogn d) n2
16. The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base
10 representation is [ ]
a) θ (n) b) θ (nlogn) c) θ (n2) d) none
17. The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base n
representation is [ ]
a) θ (n) b) θ (nlogn) c) θ (n2) d) None
18. Which of the following sorting algorithm is in-place [ ]
a) Counting sort b) Radix sort c) Bucket sort d) None
19. The radix sort does not work correctly if each individual digit is sorted using [ ]
a) Insertion sort b) Counting sort c) Selection sort d) Bubble sort
20. Which of the following sorting algorithm has the running time that is least dependant on the initial
ordering of the input? [ ]
a) Insertion sort b) Quick sort c) Merge sort d) Selection sort
21. Time complexity to sort elements of binary search tree is [ ]
a) O(n) b) O(nlogn) c) O(n2) d) O(n2logn)
22. The lower bound on the number of comparisons performed by comparison-based sorting algorithm is
a) Ω (1) b) Ω (n) c) Ω (nlogn) d) Ω (n2) [ ]
23. Which of the following algorithm(s) can be used to sort n integers in range [1…..n3] in O(n) time?
a) Heap sort b) Quick sort c) Merge sort d) Radix sort [ ]
24. Which of the following algorithm design technique is used in the quick sort algorithm?[ ]
a) Dynamic programming b) Backtracking c) Divide-and-conquer d) Greedy method
25. Merge sort uses [ ]
a) Divide-and-conquer b) Backtracking c) Heuristic approach d) Greedy
approach
26. For merging two sorted lists of size m and n into sorted list of size m+n, we require comparisons of
a) O(m) b) O(n) c) O(m+n) d) O(logm + logn) [ ]
27. A sorting technique is called stable if it [ ]
a) Takes O(nlogn) times
b) Maintains the relative order of occurrence of non-distinct elements
c) Uses divide-and-conquer paradigm
d) Takes O(n) space
28. In a heap with n elements with the smallest element at the root, the seventh smallest element can be
found in time [ ]
a) θ (nlogn) b) θ (n) c) θ (logn) d) θ (1)
29. What would be the worst case time complexity of the insertion sort algorithm, if the inputs are
restricted to permutation of 1…..n with at most n inversion? [ ]
a) θ (n2) b) θ (nlogn) c) θ (n1.5) d) θ (n)
30. In a binary max heap containing n numbers, the smallest element can be found in time[ ]
a) θ (n) b) θ (logn) c) θ (loglogn) d) θ (1)
31.In which sorting, consecutive adjacent pairs of elements in the array are compared with each other?
[ ]
A) Bubble sort B) Selection sort C) Merge sort D) Radix sort
32. Which of the following sorting methods will be the best if the number
of swappings done is theonly measure of efficiency? [ ]
A) Bubble sort B) Selection sort C) Insertion sort D) Quick sort
33. In ordered search elements are arranged in [ ]
A)random B)descending C)ascending D)none
34. What is the worst case complexity of bubble sort? [ ]
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

35. What is the average case complexity of bubble sort? [ ]

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

36. Which of the following is not an advantage of optimised bubble sort over other sorting techniques in case
of sorted elements? [ ]
a) It is faster
b) Consumes less memory
c) Detects whether the input is already sorted
d) Consumes less time

37. What is the best case efficiency of bubble sort in the improvised version? [ ]
a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)

38. What is the worst case complexity of selection sort? [ ]

a) O(nlogn)
b) O(logn)
c) O(n)
d) O(n2)
39. What is the advantage of selection sort over other sorting techniques? [ ]
a) It requires no additional storage space
b) It is scalable
c) It works best for inputs which are already sorted
d) It is faster than any other sorting technique
40. What is the disadvantage of selection sort? [ ]
a) It requires auxiliary memory
b) It is not scalable
c) It can be used for small keys
d) It takes linear time to sort the elements