QUESTION BANK 2016

SIDDHARTH GROUP OF INSTITUTIONS :: PUTTUR

Siddharth Nagar, Narayanavanam Road – 517583

QUESTION BANK (DESCRIPTIVE)

Subject with Code : DS (15A05201) Course & Branch: B.Tech - EEE

Year & Sem: II-B.Tech & I-Sem Regulation: R15

UNIT –I

ARRAYS AND LINKED LIST

1. Explain the following operations on arrays [5M+5M][L5]

A. Insertion B. merging
2. Narrate following operations on arrays [5M+5M][L6]
A. Searching B. Deletion
3. A. Why pointer arrays are efficient than arrays. Justify your answer by taking an example.
[5M][L4]
B. Explain about Multi-dimensional arrays [5M][L5]
4. Narrate following operations on single linked list [4M+3M+3M][L6]
A. Traversing
B. Insertion before head node
C. Insertion after tail node
5. Describe following operations on single linked list [3M+4M+3M][L1]
A. deleting head node
B. copying
C. deleting tail node
6. Explain following operations on single linked list with algorithm [5M+5M][L5]
A. Deleting a specified node B. Insertion after specified node
7. Write about the following operations on double linked list [4M+3M+3M][L6]
A. Deleting head node
B. Insertion after specified node
C. Insertion before head node
8. a) Define data structure? Name few data structures [2M][L1]
b) Define one-dimensional array and draw its memory representation [2M][L1]
c) What is indexing formula? [2M][L4]
d) Write steps to traverse an array. [2M][L6]
DATA STRUCTURES Page 1
 QUESTION BANK 2016

e) Define multi-dimensional array and draw it’s memory representation [2M][L1]

9. a) In how many ways we can arrange elements of a 2D array in memory [2M][L4]
b) What is pointer array? [2M][L4]
c) Draw the node structure of a double linked list [2M][L1]
d) Differentiate static data structure and dynamic data structure [2M][L1]
e) What are the applications of “linked lists”? [2M][L4]

UNIT 2

STACKS AND QUEUES

1. Write algorithm to perform STACK operation on a given set of numbers. [10M][L6]

2. Write algorithm to perform QUEUE operation on a given set of numbers. [10M][L6]
3. Explain enqueue() and dequeue() operations on circular queue. [10M][L5]
4. Narrate insertion and deletion operations on “priority Queue” using linked list. [10M][L6]
5. Explain different kinds of hash functions. [10M][L5]
6. Describe collision resolution techniques while using Hash tables. [10M][L1]
7. Write an algorithm to “convert infix expression to post fix expression” [10M][L6]
8. Write logic of push () and pop() operations on stack using linked list. [10M][L6]
9. Write logic of enqueue() and dequeue() operations on Queue using linked list. [10M][L6]
10. a) (A + B. / (C + D. – (D * E)”. Convert it into postfix expression. [2M][L3]
b) What is recursive function? [2M][L4]
c) Write algorithm to push an element into stack. [2M][L6]
d) Draw static and dynamic stacks representations. [2M][L1]
e) What are the applications of Queue? [2M][L4]
11. a) Define priority queue and Deque [2M][L1]
b) What is the drawback of linear Queue Data structure? [2M][L4]
c) What is hash table? [2M][L4]
d) Write down the types of hash functions. [2M][L6]
e) What are the collision resolution techniques? [2M][L6]

DATA STRUCTURES Page 2

 QUESTION BANK 2016

UNIT 3

TREES AND GRAPHS

1. Explain insertion and deletion of a new element in height balanced tree. [10M][L5]

2. Write Warshsall’s Algorithm for Shortest path problem and give an example [10M][L6]
3. Discuss the different Traversal Operations on a Binary Tree with Algorithms [10M][L4]
4. A. What are the advantages and disadvantages of sequential representation of a binary tree?
[10M][L4]
B. Write an algorithm to search an element in binary search tree? [10M][L6]
5. Construct AVL Tree using “8,9,10,2,1,5,6,4,7,11,12,3” elements inserting in sequence[10M][L3]
6. Illustrate heap sort technique using heap trees. [10M][L4]
7. A. In how many ways we can represent a graph? [5M][L4]
B. Explain about applications of graph [5M][L5]
8. Write BFS algorithm and illustrate it with an example. [10M][L6]
9. Write DFS algorithm and illustrate it with an example. [10M][L6]
10. Write an algorithm to insert elements into a binary search tree. [10M][L6]

11. a) What is inorder traversal of a tree? [2M][L4]

b) Difference between complete binary tree and full binary tree? [2M][L1]
c) What is binary search tree? [2M][L4]
d) Give one example for DFS [2M][L1]
e) What is connected graph [2M][L4]
12. Write a procedure for topological sorting in a graph. [10M][L6]

UNIT – IV
SORTING
1. Explain in detail the following with an example
a) Straight Insertion sort [5M][L5]
B. List insertion sort [5M][L5]
2. Write and explain the algorithm for bubble sort with example. [10M][L6]
3. A. Give the classification of sorting methods. [5M][L6]
DATA STRUCTURES Page 3
 QUESTION BANK 2016

B. Sort 3,1,4,1,5,9,2,6 in decreasing order using heap sort. [5M][L3]

4. State and explain the algorithm to perform merge sort with example. [10M][L1&L5]
5. State and explain the algorithm to perform heap sort with example. [10M][L1&L5]
6. A. Give the classification of classic sorting techniques. [5M][L6]
B. Sort in ascending 34,2,56,7,12,4 using bubble sort. [5M][L3]
7. Write and explain the algorithm for quick sort with example. [10M][L6]
8. Give a procedure for heap sort and analyze its complexity. [10M][L6&L4]
9. Explain merge sorting with examples and analyze its complexity. [10M][L5&L4]
10. a) What is the difference between internal sorting and external sorting? [2M][L4]
b) What is Lexicographic order? [2M][L4]
c) Define stable sort. [2M][L1]
d) Define swap with example. [2M][L1]
e) Give the time complexity for quick sort. [2M][L6]

UNIT – V
SEARCHING
1. State and explain sequential sort algorithm with example problem. [10M][L1&L5]
2. State and explain binary sort algorithm with problem. [10M][L1&L5]
3. Define hashing and explain any four Hashing Methods with example. [10M][L1&L5]
4. A. What is hashed list search? [5M][L4]
B. Explain Linked list collision resolution method. [5M][L5]
5. A. Give the detail about bucket hashing. [5M][L6]
B. Write about the different folding methods. [5M][L6]
6. Explain the following. [3+3+4=10M][L5]
A. Key offset
B. Digit extraction method
C. Pseudorandom Collision Resolution
7. Perform Binary search method to find 22 from the following sorted array. [10M][L3]
4,7,8,10,14,21,22,36,62,77,81,91
8. Give the logics behind linear and binary search methods. [10M][L6]
9. Explain collision resolution. [10M][L5]
10. Explain Fibonacci search using an example. [10M][L5]
11. a) What are self-referential structures? [2M][L4]

DATA STRUCTURES Page 4

 QUESTION BANK 2016

b) What is meant by collision in hashing? [2M][L4]

c) Define sequential search. [2M][L1]
d) What is meant by probability search? [2M][L4]
e) Give the efficiency of sequential and binary sort. [2M][L6]

DATA STRUCTURES Page 5

 QUESTION BANK 2016

SIDDHARTH GROUP OF INSTITUTIONS :: PUTTUR

Siddharth Nagar, Narayanavanam Road – 517583

QUESTION BANK (OBJECTIVE)

Subject with Code : DS (15A05201) Course & Branch: B.Tech - EEE

Year & Sem: II-B.Tech & I-Sem Regulation: R15

UNIT 1

ARRAYS AND LINKED LIST

1. logical organization of data in computer memory is called [ ]

A.data style B.data manner C.data set D.all are wrong
2. 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
3. Address of the first element of an array is called [ ]
A. starting address B.base address C.both p &q are valid D.all are correct
4. Which of the following refers indexing formula [ ]
A. a[i]=M+(i-L)*w B.a[i]=M+(i+L)*w C.a[i]=M-(i+L)*w D.a[i]=M*(i-L)+w
5. Arrays are not static data structures [ ]
A. True B. false C. cann’t determine D. may be
6. A pointer array variable contains ------------as it’s elements [ ]
A. integer values B.addresses of memory locations
C.both p &q are valid D.none
7. What does link part of a tail node in a circular linked list hold? [ ]
A. address of head node B.address of header node
C.address of it’s previous node D.none
8.What is the value present in the address part of a header node in linked list [ ]
A. address of head node B.address of header node
C.address of tail node D.all are wrong
9. Tail node in circular linked list always points [ ]
A.header node B.head node C.NULL value D. it’s next node
address
10. How can we access the value present at nth- row ,pth- plane,mth- column of a multi-dimensional
array “x” [ ]
A.x[n][p][m] B.x[n][m][p] C.x[p][n][m] D.x[m][n][p]
11. memory for elements in an array is not allocated in contiguous locations(addresseD. [ ]
A.true B.false C. not possible D. cann’t predict
12. Each node in a linked list must contain at least ....fields [ ]
A.3 B.2 C.4 D.5
13. LLINK is the pointer pointing to the ... [ ]
A.successor node B.predecessor node C.head node D.last node
14. A linear list in which the pointer points only to the successive node is ...... [ ]
A.singly linked list B.double linked list C.circular linked list D. all are correct
15.If address part of the head node contains non null value,it means [ ]
A.list has exactly 1 node B.list has exactly 2 nodes
DATA STRUCTURES Page 6
 QUESTION BANK 2016

C.list has at least 2 nodes D.all are wrong

16.let us suppose,header node address is:100,head node address is:200 and a new node(address is 300)
is inserted after the header node.Then data part of the header node contains [ ]
A.100 B.200 C.300 D.NULL
17.Llink part of the header node in a circular double linked list contains [ ]
A.address of left most node B.A.address of right most node
C.address of head node D.both p&r
18.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
19.Memory for elements in linked list are allocated in non-contiguous locations [ ]
A. true B. false C. cann’t determine D. may be
20.Which of the following data structures are convenient to perform insertion and deletion operations
[ ]
A. arrays B. linked lists C. both A&B D.all are wrong
21. In liked representation of stack ....... holds the elements of the stack. [ ]

A. INFO fields B. TOP fields C. LINK fields D. NULL fields

22. What happens when you push a new node onto a stack? [ ]
A. The new node is placed at the front of the linked list
B. The new node is placed at the back of the linked list
C. The new node is placed at the middle of the linked list
D. No Changes happens
23. which of the following is disadvantage of arrays [ ]
A. static storage B. insertions require shifting of elements
C. deletions require shifting of elements D. all are correct
24. To traverse an array means [ ]
A. to process each element in an array B. to delete an element from an array
C. to insert an element into an array D. to combine two arrays into a single array
25. Finding the location of the element with a given value is: [ ]
A. Traversal B. Search C. Sort D. None of above
26.If the base address of a character array is 200 then what is the address of 3rd element in that array
[ ]
A.202 B.203 C.204 D. none
27. The memory address of first element in array is called? [ ]
A. base address B. first address C. stating address D. both a &c
28.the address of first node in a linked list is? [ ]
A. can’t say B.100 C. 0 D. none
29. A doubly linked list has .......... pointers with each node. [ ]
A. 0 B. 1 C. 2 D. 3
30. A doubly linked list is also called as.......... [ ]
A. linked list B. one way chain C. two way chain D. right link
31. In a linked list, insertion can be done as ......... [ ]
A. beginning B. end C. middle D. all of the above
32. To implement Sparse matrix dynamically, the following data structure is used [ ]
A. Trees B. Graphs C. Priority Queues D Linked List
33. Header of a linked list is a special node at the [ ]
A. end of the linked list B. at the middle of the linked list
C. beginning of the linked list D. none of these
34. Which of the following operations is performed more effi ciently by a doubly linked list than by

DATA STRUCTURES Page 7

 QUESTION BANK 2016

a linear linked list? [ ]

A. Deleting nodes whose location is given
B. Searching an unsorted list for a given item
C. Inserting a node after the node with a givenlocation
D. Traversing the list to process each node
35. Overflow condition in a linked list may occur when attempting to [ ]
A. create a node when free space pool is empty
B. traverse the nodes when free space pool isempty
C. create a node when linked list is empty
D. none of these
36. If an array is declared as arr[] = {1,3,5,7,9};then what is the value of sizeof(arr[3])? [ ]
A. 1 B. 2 C. 3 D. 8
37. If an array is declared as arr[] = {1,3,5,7,9};then what is the value of arr[3]? [ ]
A. 1 B. 7 C. 9 D. 5
38. If an array is declared as double arr[50]; how many bytes will be allocated to it? [ ]
A. 50 B. 100 C. 200 D. 400
39. If an array is declared as int arr[5][5], howmany elements can it store? [ ]
A. 5 B. 25 C.10 D. 0
40. The smallest element of an array’s index iscalled its [ ]
A. lower bound B. upper bound C. range D. extraction

UNIT 2

STACKS AND QUEUES

1. Stack is a [ ]
A. LIFO B. FIFO C. FILO D. LILO
2. Disks piled up one above the other represent a [ ]
A. Stack B. Queue C. Linked List D. Array
3. Reverse Polish notation is the other name of [ ]
A. Infix expression B. Prefix expression C. Postfix expression D. Algebraic expression
4. Using a recursive function takes more memory and time to execute. [ ]
A. true B. false C. can’t predict D. may be
5. The following sequence of operations is performed on a stack push(1), push(2), pop, push(1),
push(2), pop, pop, pop, push(2),pop. The sequence of the popped out values is [ ]
A. 2, 2, 1, 1, 2 B. 2, 2, 1, 2, 2 C. 2, 1, 2, 2, 1 D. 2, 1, 2, 2, 2
6. Infi nite recursion occurs when [ ]
A. a base case is omitted B. a base case is never reached
C. both A. and B. D. none of the above
7. The data structure used for recursion is [ ]
A. stack B. queue C. tree D. none of the above
8. A line in a grocery store represents a [ ]
A. Stack B. Queue C. Linked List D. Array
9. In a queue, insertion is done at [ ]
A. Rear B. Front C. Back D. Top
10. The function that deletes values from a queue is called [ ]
A. enqueue B. dequeue C. pop D. peek
11.The size of a linked queue cannot change during run time. [ ]
A. true B. false C. can’t predict D. may be
12. A queue is also called a [ ]
DATA STRUCTURES Page 8
 QUESTION BANK 2016

A. last in first out data structure B. first in last out data structure
C. first in first out data structure D. last in last out data structure
13. in a hash table, an element with key k is stored at index [ ]
A. k B. log k C. h(k) D. k2
14. In any hash function, M should be a [ ]
A. Prime number B. Composite number C. Even number D. Odd number
15. In which of the following hash functions, do consecutive keys map to consecutive hash values?
[ ]
A. Division method B. Multiplication method
C. Folding method D. Mid-square method
16. The process of examining memory locations in a hash table is called [ ]
A. Hashing B. Collision C. Probing D. Addressing
17. Which open addressing technique is free from clustering problems? [ ]
A. Linear probing B. Quadratic probing C. Double hashing D. Rehashing
18.A queue in which both insertions and deletions are possible at both ends is called [ ]
A.Dequeue B.Deq C.Deque D.Dique
19.A Queue in which elements are inserted and deleted based on it’s priority are called [ ]
A.Priority queue B.preference queue C.Deque D.circular queue
20.when do you say “a stack is full”? [ ]
A.top=size B.top==size C.top=size+1 D.none
21. Which data structures don’t obey FIFO strategy ? [ ]
A.array B.stack C.linked list D.none
22. Which of the following implementation of priority queue is efficient? [ ]
A.multi-queue B.circular queue C.single linked list D.double linked list
23. A queue in which elements are inserted and deleted based on priority is called [ ]
A.important queue B.circular queue C.priority queue D.none
24. Which of the following symbol is pushed onto the stack before converting a parenthesized
expression to postfix expression? [ ]
A.’{‘ B.’)’ C.’(‘ D.’}’
25.CPU uses which of the following data structures during execution of multiple programs at a time.
[ ]
A.stack B.queue C.tree D.array
26. When we consider starting index of queue is “ 0”.then which of the following conditions are used
to chech “queue full” condition? [ ]
A.rear=length B.rear==length C.rear==(length-1) D.none
27. How many minimum number of moves are needed to transfer 5 disks on a source tower to
destination tower? [ ]
A.8 B.30 C.32 D.31
28.In which of the following data structures insertion is not possible in the middle? [ ]
A.array B.linked list C.stack D.none
29.During recursive function calls computer utilizes? [ ]
A.queue B.array C.stack D.linked list
30.which of the following operations is not possible in input-restricted deque? [ ]
A.deletion at front B.insertion at front C.deletion at rear D.insertion at rear
31.which of the following operations is not possible in output-restricted deque? [ ]
A.deletion at front B.insertion at front C.deletion at rear D.insertion at rear
32.In multiple-queues with matrix representation of priority queue rows represent? [ ]
A.length of every queue B.priority
C.element count D.none
33.What is dynamic stack? [ ]

DATA STRUCTURES Page 9

 QUESTION BANK 2016

A. stack implementation with array B. A.stack implementation with linked list

C. A.stack implementation with circular queue D.none
34.In which of the following data structures key-value pairs exist? [ ]
A.hash table B.arrays C.stacks D.queues
35. Which open addressing technique is free from clustering problems? [ ]
A. Linear probing B. Quadratic probing C. Double hashing D. Rehashing
36. A hash function f defi ned as f(key) = key MOD7, with linear probing, is used to insert the keys
37, 38, 72, 48, 98, 11, 56 into a table indexed from 0 to 6. 11 will be stored in the location[ ]
A. 3 B. 4 C. 5 D. 6
37. The result of two keys hashing into the same bucket (index position D)? [ ]
A.collision B.clash C.error D.none
38. To store an item in a hash table, we use? [ ]
A.hash table B.hash function C.dictionary D.none
39. Escalator is a real time example for? [ ]
A.stack B.array C.circular queue D.none
40.Which data structure is used internally by printer while printing number of documents?[ ]
A.stack B.queue C.array D.none

UNIT 3

TREES AND GRAPHS

1. In Binary Search if the Search element is greater than the mid then the condition is [ ]
A. low = mid +1 B. high = mid-1 C. mid = (low+high)/2 D. None
2. The Binary Search Algorithms needs theelements to be in ________ Order [ ]
A. Ascending B. Random C. Both D. None
3. BFS makes use of __________ [ ]
A. Stack B. Queue C. List D. Heap
4. DFS makes use of __________ [ ]
A. Stack B. Queue C. List D. Heap
5. Topological Sorting is possible only with _____________ [ ]
A. DAGs B. Directed Graphs C. Cyclic Graphs D. All
6. A Graph where each vertex is connected to all other vertices is called____ [ ]
A. Completely Connected B. Directed Graphs C. Cyclic Graphs D. All
7. All Trees are ________ [ ]
A. Binary Trees B. Arrays C. Graphs D. Heaps.
8. In an M-ary Tree with M value as 2 is called as ______ Tree [ ]
A. Binary B. 3-ary Tree C. Skewed Tree D. Full Binary Tree
9. In _________ Binary tree all the leaf nodes will be all the same level [ ]
A. Complete B. Full C. Skewed D. All
10. __________ are height balanced trees. [ ]
A. AVL B. Red-Black C. Splay Trees D. B-Trees
11. 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
12. 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

DATA STRUCTURES Page 10

 QUESTION BANK 2016

13. 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
14. A binary tree is generated by inserting an inorder as 50, 15, 62, 5, 20, 58, 91, 3, 8, 37, 60, 24. 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)
15. A BST contains the values 1, 2, 3, 4, 5, 6, 7, 8. The tree is traversed in preorder and the values
are printed. The valid output is [ ]
A. 53124786 B. 53126487 C. 53241678 D. 53124768
16. In _________ traversal, the right subtree is processed last. [ ]
A. a preorder B. an inorder C. a postorder D. A. or B.
17. 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
18. 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
19.A list of integers is read one at a time, and a BST is constructed. Next, the tree is traversed and the
integers are printed. Which traversal would print the result in the original order of the input?
[ ]
A. Preorder B. Postorder C. Inorder D. None of the above
20.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
21. 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.
22. An edge that has identical end-points is called a [ ]
A. Multi-path B. Loop C. Cycle D. Multi-edge
23. The total number of edges containing the node u is called [ ]
A. In-degree B. Out-degree C. Degree D. None of these
24. 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
25. The number of edges that originate at u are called [ ]
A. In-degree B. Out-degree C. Degree D. source
26. The number of distinct simple graphs with upto 3 nodes is [ ]
A. 15 B. 10 C. 7 D. 9
27. 9. 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–1
28.elements arranged in hierarchical fachion is called [ ]
A.tree B.graph C.array D.linked list

DATA STRUCTURES Page 11

 QUESTION BANK 2016

29.a vertex with no edges incident on it is called [ ]

A.isolated vertex B.disjointed vertex C.special vertex D.none
30. A graph which doesn’t contain any self loops or parallel edges is called [ ]
A.simple graph B.plain graph C.acyclic graph D.none
31. If every vertex in a graph is connected with all other vertices then it is called [ ]
A.complete graph B.full graph C.connected graph D.simple graph
32.”map colouring” is an application of which of the following data structures [ ]
A.tree B.graph C.array D.linked list
33. Which of the following is associated with graph? [ ]
A.BFS B.DFS C.cycle D.all
34. Queue is used in which of the following graph traversal techniques [ ]
A.BFS B.DFS C.Inorder traversal D.post order traversal
35. Stack is used in which of the following graph traversal techniques [ ]
A.BFS B.DFS C.Inorder traversal D.post order traversal
36.”shortest path finding” is an application of ? [ ]
A.tree B.graph C.binary tree D.none
37. 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
38. Which way of tree representation is efficient? [ ]
A.array B.linked list C.circular queue D.stack
39. Two or more nodes with a same parent is called [ ]
A.siblings B.twins C.children D.both a&b
40. 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

UNIT 4

SORTING

1) The worst case occur in linear search algorithm when _____ [ ]

A. Item is somewhere in the middle of the array
B. Item is not in the array at all
C. Item is the last element in the array
D. Item is the last element in the array or item is not there at all
2) If the number of records to be sorted is small, then ___ sorting can be efficient. [ ]
A. Merge B. Heap C. Selection D. Bubble
3) The complexity of sorting algorithm measures the ______ as a function of the number n of items to
be sorter. [ ]
A. average time B. running time
C. average-case complexity D. case-complexity
4) Which of the following is not a limitation of binary search algorithm? [ ]
A. must use a sorted array
B. requirement of sorted array is expensive when a lot of insertion and deletions are needed
C. there must be a mechanism to access middle element directly
D. binary search algorithm is not efficient when the data elements more than 1500.
DATA STRUCTURES Page 12
 QUESTION BANK 2016

5) The Average case occurs in linear search algorithm ______ [ ]

A. when item is somewhere in the middle of the array
B. when item is not the array at all
C. when item is the last element in the array
D. Item is the last element in the array or item is not there at all
6) Binary search algorithm cannot be applied to ______ [ ]
A. sorted linked list B. sorted binary trees
C. sorted linear array D. pointer array
7) Complexity of linear search algorithm is ________ [ ]
A. O(n) B. O(logn) C. O(n2) D. O(n logn)
8) Sorting algorithm can be characterized as ______ [ ]
A. Simple algorithm which require the order of n2 comparisons to sort n items.
B. Sophisticated algorithms that require the O(nlog2n) comparisons to sort items.
C. Both of the above
D. None of the above
9) The complexity of bubble sort algorithm is ______ [ ]
A. O(n) B. O(logn) C. O(n2) D. O(n logn)
10) State True or False for internal sorting algorithms. [ ]
i) Internal sorting are applied when the entire collection if data to be sorted is small enough that the
sorting can take place within main memory.
ii) The time required to read or write is considered to be significant in evaluating the performance of
internal sorting.
A. i-True, ii-True B. i-True, ii-False C. i-False, ii-True D. i-False, ii-False
11) The complexity of merge sort algorithm is ______ [ ]
A. O(n) B. O(logn) C. O(n2) D. O(n logn)
12) _______ is putting an element in the appropriate place in a sorted list yields a larger sorted order
list. [ ]
A. Insertion B. Extraction C. Selection D. Distribution
13) ______order is the best possible for array sorting algorithm which sorts n item. [ ]
A. O(n logn) B. O(n2) C. O(n+logn) D. O(logn)
14) ______ is rearranging pairs of elements which are out of order, until no such pairs remain.
[ ]
A. Insertion B. Exchange C. Selection D. Distribution
15) _______ is the method used by card sorter? [ ]
A. Radix sort B. Insertion C. Heap D. Quick
16) Which of the following sorting algorithm is of divide and conquer type? [ ]
A. Bubble sort B. Insertion sort C. Merge sort D. Selection sort
17) ______ sorting algorithm is frequently used when n is small where n is total number of elements.
[ ]
A. Heap B. Insertion C. Bubble D. Quick
18) Which of the following sorting algorithm is of priority queue sorting type? [ ]
A. Bubble sort B. Insertion sort C. Merge sort D. Selection sort
19) Which of the following is not the required condition for binary search algorithm?
[ ]
A. The list must be sorted
B. There should be the direct access to the middle element in any sub list
C. There must be mechanism to delete and/or insert elements in list.
D. Number values should only be present
20) Partition and exchange sort is ______ [ ]
A. quick sort B. tree sort C. heap sort D. bubble sort

DATA STRUCTURES Page 13

 QUESTION BANK 2016

21) Finding the location of a given item in a collection of items is called ______ [ ]
A. Discovering B. Finding C. Searching D. Mining
22) Which of the following is an external sorting? [ ]
A. Insertion Sort B. Bubble Sort C. Merge Sort D. Tree Sort
23) Very slow way of sorting is _______ [ ]
A. Insertion sort B. Heap sort C. Bubble sort D. Quick sort
24) Which of the following is an internal sorting? [ ]
A. Tape Sort B. 2-way Merge Sort C. Merge Sort D. Tree Sort
25) Sorting a file F usually refers to sorting F with respect to a particular key called _____
[ ]
A. Basic key B. Primary key C. Starting key D. Index key
26) The time complexity of quick sort is ________ [ ]
A. O(n) B. O(logn) C. O(n2) D. O(n logn)
27) Selection sort first finds the .......... element in the list and put it in the first position.
[ ]
A. Middle element B. Largest element C. Last element D. Smallest element
28) Quick sort is also known as _________ [ ]
A. merge sort B. tree sort C. shell sort D. partition and exchange sort
29) The operation that combines the element is of A and B in a single sorted list C with n=r+s element
is called __________ [ ]
A. Inserting B. Mixing C. Merging D. Sharing
30) A tree sort is also known as _____ sort. [ ]
A. quick B. shell C. heap D. selection
31) _______ sorting is good to use when alphabetizing large list of names. [ ]
A. Merge B. Heap C. Radix D. Bubble
32) The easiest sorting is _______ [ ]
A. quick sort B. shell sort C. heap sort D. selection sort
33) Which of the following sorting algorithm is of divide and conquer type? [ ]
A. Bubble sort B. Insertion sort C. Quick sort D. Merge sort
34) Merging k sorted tables into a single sorted table is called ______ [ ]
A. k way merging B. k th merge C. k+1 merge D. k-1 merge
35) The function used to modify the way of sorting the keys of records is called [ ]
A. Indexing function B. Hash function
C. Addressing function D. All of the above
36) If the number of record to be sorted large and the key is short, then _____ sorting can be efficient.
[ ]
A. Merge B. Heap C. Radix D. Bubble
37) The total number of comparisons in a bubble sort is ______ [ ]
A. O(n logn) B. O(2n) C. O(n2) D. O(n)
38) If the number of record to be sorted large and the key is long, then _____ sorting can
be efficient. [ ]
A. Merge B. Heap C. Quick D. Bubble
39) The time complexity of heap sort is _______ [ ]
A. O(n) B. O(logn) C. O(n2) D. O(n logn)
40) The complexity of selection sort is _______ [ ]
A. O(n) B. O(n2) C. O(n logn) D. O(logn)

DATA STRUCTURES Page 14

 QUESTION BANK 2016

UNIT 5

SEARCHING

1. In linear search algorithm the Worst case occurs when [ ]

A. The item is somewhere in the middle of the array
B. The item is not in the array at all
C. The item is the last element in the array
D. The item is the last element in the array or is not there at all
2. For an algorithm the complexity of the average case is [ ]
A. Much more complicated to analyze than that of worst case
B. Much more simpler to analyze than that of worst case
C. Sometimes more complicated and some other times simpler than that of worst case
D. None or above
3. The complexity of linear search algorithm is [ ]
A. O(n) B. O(log n) C. O(n2) D. O(n log n)
4. When determining the efficiency of algorithm the time factor is measured by [ ]
A. Counting microseconds
B. Counting the number of key operations
C. Counting the number of statements
D. Counting the kilobytes of algorithm
5. The elements of an array are stored successively in memory cells because [ ]
A. by this way computer can keep track only the address of the first element and the addresses
of other elements can be calculated
B. the architecture of computer memory does not allow arrays to store other than serially
C. both of above
D. none of above
6. Which of the following data structure is not linear data structure? [ ]
A. Arrays B. Linked lists C. Both of above D. None of above
7. The Average case occur in linear search algorithm [ ]
A. When Item is somewhere in the middle of the array
B. When Item is not in the array at all
C. When Item is the last element in the array
D. When Item is the last element in the array or is not there at all
8. Two main measures for the efficiency of an algorithm are [ ]
A. Processor and memory B. Complexity and capacity
C. Time and space D. Data and space
9. Finding the location of the element with a given value is: [ ]
A. Traversal B. Search C. Sort D. None of above
10. Which of the following case does not exist in complexity theory [ ]
A. Best case B. Worst case C. Average case D. Null case
11. The operation of processing each element in the list is known as [ ]
A. Sorting B. Merging C. Inserting D. Traversal
12. The complexity of Binary search algorithm is [ ]
A. O(n) B. O(log ) C. O(n2) D. O(n log n)
13. The Searching technique that takes o(1) time to find a data is [ ]
A.Linear Search B.Binary Search C.Hashing D.Tree Search
14. A technique for direct search is [ ]
A. Binary Search B.Linear Search C.Tree search D. Hashing

DATA STRUCTURES Page 15

 QUESTION BANK 2016

15.The Complexity of searching an element form a set n elements using Binary Search algorithm is
[ ]
A.O(n2) B.O(log n) C.O(n2) D.O(n log n)
16.The worst case occur in linear search algorithm when [ ]
A. Item is somewhere in the middle of the array
B. Item is not in the array at all
C. Item is the last element in the array
D. Item is the last element in the array or item is not there at all
17. The Average case occurs in linear search algorithm [ ]
A. when item is somewhere in the middle of the array
B.when item is not the array at all
C. when item is the last element in the array
D. Item is the last element in the array or item is not there at all
18. In_____,Search start at the beginning of the list and check every element in the list
[ ]
A. Linear search B. Binary search C. Hash Search D. Binary Tree search
19. If h is any hashing function and is used to hash n keys in to a table of size m,
where n<=m, the expected number of collisions involving a particular key x is [ ]
A. less than 1 B. less than n C. less than m D. less than n/2
20. 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
21. A technique for direct search is [ ]
A. Binary Search B. Linear Search C. Tree Search D. Hashing
22. The searching technique that takes O (1) time to find a data is [ ]
A. Linear Search B. Binary Search C. Hashing D. Tree Search
23.The complexity of searching an element from a set of n elements using Binary search
algorithm is [ ]
A. O(n) B. O(log n) C. O(n2) D. O(n log n)
24.The goal of hashing is to produce a search that takes [ ]
A. O(1)time B. O(n2)time C. O(log n )time D. O(n log n )time
25. 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 of these
26. Which of the following case does not exist in complexity theory? [ ]
A. Best case B. Worst case C. Average case D. Null case
27. The worst case occur in linear search algorithm when [ ]
A. Item is somewhere in the middle of the array
B. Item is not in the array at all
C. Item is the last element in the array
D. Item is the last element in the array or is not there at all
28. The average case occur in linear search algorithm when [ ]
A. Item is somewhere in the middle of the array
B. Item is not in the array at all
C. Item is the last element in the array
D. Item is the last element in the array or is not there at all
29. The complexity of linear search algorithm is [ ]
A. O(n) B. O(log n) C. O(n2) D. O(n log n)
30. The complexity of binary search algorithm is [ ]

DATA STRUCTURES Page 16

 QUESTION BANK 2016

A. O(n) B. O(log n) C. O(n2) D. O(n log n)

31. Binary search algorithm cannot be applied [ ]
A. sorted linked list B. sorted binary trees C. sorted linear array D. pointer array
32. Which of the following is not the required condition for the binary search algorithm?
[ ]
A. The list must be sorted
B. there should be the direct access to the middle element in any sublist
C. there must be mechanism to delete and / or insert elements in list
D. none of above
33. ____ is the common programming technique used for hashing in all hashing functions.
[ ]
A. Cloning B. Bit Shifting C. Hash mapping D. Listing
34. The hash String() member function is called by other member functions of the Hash table class
whenever a function needs to convert a ________________ . [ ]
A. a hash number key to a key B. key to a hash number key
C. a key to an Index D. None of these

35. An algorithm that calls itself directly or indirectly is known as [ ]

A. Sub algorithm B. Recursion
C. Polish notation D. Traversal algorithm
36. When new data are to be inserted into a data structure, but there is no available space; this situation
is usually called [ ]
A. underflow B. overflow C. houseful D. saturated
37. An application iterates the hashtable by calling the ______ and ______ member functions.
[ ]
A. hasNext() and hasDelete() B. hasNext() and getNextKey()
C. Both A and B D. None of these
38. The time factor when determining the efficiency of algorithm is measured by [ ]
A. Counting microseconds
B. Counting the number of key operations
C. Counting the number of statements
D. Counting the kilobytes of algorithm
39. A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear
probing. After inserting 6 values into an empty hash table, the table is as shown below.

Which one of the following choices gives a possible order in which the key values could have been
inserted in the table? [ ]
A. 46, 42, 34, 52, 23, 33
B. 34, 42, 23, 52, 33, 46

DATA STRUCTURES Page 17

 QUESTION BANK 2016

C. 46, 34, 42, 23, 52, 33

D. 42, 46, 33, 23, 34, 52
40. How many different insertion sequences of the key values using the same hash function and
linear probing will result in the hash table shown above? [ ]
A. 10 B. 20 C. 30 D. 40

Prepared by: Ms. Priyadarshini R, Mr Sainath N

DATA STRUCTURES Page 18