DSA MCQ Quistion Bank - Multiple Choice Questions for data structure and algorithm. PDF

Preview

Summary

Multiple Choice Questions for data structure and algorithm....

Description

D Y Patil College of Engineering, Akurdi-44 Department of Computer Engineering __________________________________________________________________________________ Question Bank for Online Examination Subject: Data Structures and Algorithms Compiled By: Rahul Y. Pawar

Which of the following data structures are indexed structures? A. linear arrays B. linked lists C. both of above D. none of above ANSWER: A 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 sublist C. There must be mechanism to delete and/or insert elements in list D. none of above ANSWER: C 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. housefull D. saturated ANSWER: B Which of the following is two way list? A. grounded header list B. circular header list C. linked list with header and trailer nodes D. none of above ANSWER: D A data structure where elements can be added or removed at either end but not in the middle A. Linked lists B. Stacks C. Queues D. Deque ANSWER: C

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 ANSWER: C The complexity of linear search algorithm is A. O(n) B. O(log n) C. O(n2) D. O(n log n) ANSWER: A Which of the following data structure is not linear data structure? A. Arrays B. Linked lists C. Both of above D. None of above ANSWER: D Each array declaration need not give, implicitly or explicitly, the information about A. the name of array B. the data type of array C. the first data from the set to be stored D. the index set of the array ANSWER: C To represent hierarchical relationship between elements, which data structure is suitable? A. Deque B. Priority C. Tree D. All of above ANSWER: C Identify the data structure which allows deletions at both ends of the list but insertion at only one enD. A. Input-restricted deque B. Output-restricted deque C. Priority queues D. None of above ANSWER: A Linked lists are best suited

A. for relatively permanent collections of data B. for the size of the structure and the data in the structure are constantly changing C. for both of above situation D. for none of above situation ANSWER: B Which of the following data structure is linear data structure? A. Trees B. Graphs C. Arrays D. None of above ANSWER: C Which of the following case does not exist in complexity theory A. Best case B. Worst case C. Average case D. Null case ANSWER: D An algorithm that calls itself directly or indirectly is known as A. Sub algorithm B. Recursion C. Polish notation D. Traversal algorithm ANSWER: B Finding the location of the element with a given value is: A. Traversal B. Search C. Sort D. None of above ANSWER: B Which 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 ANSWER: D What should be added in place of *ADD A STATEMENT HERE*, so that the function correctly reverses a linked list. A. *head_ref = prev;

B. *head_ref = current; C. *head_ref = next; D. *head_ref = NULL; ANSWER: A In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is A. log 2 n B. n/2 C. log 2 n – 1 D. n ANSWER: D Given pointer to a node X in a singly linked list. Only one pointer is given, pointer to head node is not given, can we delete the node X from given linked list? A. Possible if X is not last node B. Possible if size of linked list is even C. Possible if size of linked list is odd D. Possible if X is not first node ANSWER: A You are given pointers to first and last nodes of a singly linked list, which of the following operations are dependent on the length of the linked list? A. Delete the first element B. Insert a new element as a first element C. Delete the last element of the list D. Add a new element at the end of the list ANSWER: C In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is A. log2 n B. n/2 C. log2 n – 1 D. n ANSWER: D What is the time complexity to count the number of elements in the linked list? A. O(1) B. O(n) C. O(logn) D. O(n2) ANSWER: B

Which 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 ANSWER: D What is a memory efficient double linked list? A. Each node has only one pointer to traverse the list back and forth B. The list has breakpoints for faster traversal C. An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list D. A doubly linked list that uses bitwise AND operator for storing addresses ANSWER: A How do you calculate the pointer difference in a memory efficient double linked list? A. head xor tail B. pointer to previous node xor pointer to next node C. pointer to previous node – pointer to next node D. pointer to next node – pointer to previous node ANSWER: B What is the worst case time complexity of inserting a node in a doubly linked list? A. O(nlogn) B. O(logn) C. O(n) D. O(1) ANSWER: C What differentiates a circular linked list from a normal linked list? A. You cannot have the ‘next’ pointer point to null in a circular linked list B. It is faster to traverse the circular linked list C. You may or may not have the ‘next’ pointer point to null in a circular linked list D. Head node is known in circular linked list ANSWER: C Which of the following application makes use of a circular linked list? A. Undo operation in a text editor B. Recursive function calls C. Allocating CPU to resources D. Implement Hash Tables ANSWER: C Which of the following is false about a circular linked list? A. Every node has a successor

B. Time complexity of inserting a new node at the head of the list is O(1) C. Time complexity for deleting the last node is O(n) D. We can traverse the whole circular linked list by starting from any point ANSWER: B Which of the following real world scenarios would you associate with a stack data structure? A. piling up of chairs one above the other B. people standing in a line to be serviced at a counter C. offer services based on the priority of the customer D. all of the mentioned ANSWER: A What does stack underflow refer to? A. accessing item from an undefined stack B. adding items to a full stack C. removing items from an empty stack D. index out of bounds exception ANSWER: C What is the time complexity of pop() operation when the stack is implemented using an array? A. O(1) B. O(n) C. O(logn) D. O(nlogn) ANSWER: A Array implementation of Stack is not dynamic, which of the following statements supports this argument? A. space allocation for array is fixed and cannot be changed during run-time B. user unable to give the input for stack operations C. a runtime exception halts execution D. all of the mentioned ANSWER: A Which of the following data structures can be used for parentheses matching? A. n-ary tree B. queue C. priority queue D. stack ANSWER: D When determining the efficiency of algorithm, the space factor is measured by A. Counting the maximum memory needed by the algorithm

B. Counting the minimum memory needed by the algorithm C. Counting the average memory needed by the algorithm D. Counting the maximum disk space needed by the algorithm The complexity of Bubble sort algorithm is A. O(n) B. O(log n) C. O(n2) D. O(n log n) Linked lists are best suited A. for relatively permanent collections of data B. for the size of the structure and the data in the structure are constantly changing C. for both of above situation D. for none of above situation If the values of a variable in one module is indirectly changed by another module, this situation is called A. internal change B. inter-module change C. side effect D. side-module update 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 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 The complexity of merge sort algorithm is A. O(n) B. O(log n) C. O(n2) D. O(n log n) The complexity of linear search algorithm is A. O(n) B. O(log n)

C. O(n2) D. O(n log n) 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 Which of the following data structure is linear data structure? A. Trees B. Graphs C. Arrays D. None of above 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 Which of the following data structure is not linear data structure? A. Arrays B. Linked lists C. Both of above D. None of above 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 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 Finding the location of the element with a given value is: A. Traversal B. Search

C. Sort D. None of above Which of the following case does not exist in complexity theory A. Best case B. Worst case C. Average case D. Null case The operation of processing each element in the list is known as A. Sorting B. Merging C. Inserting D. Traversal Arrays are best data structures A. for relatively permanent collections of data B. for the size of the structure and the data in the structure are constantly changing C. for both of above situation D. for none of above situation Each array declaration need not give, implicitly or explicitly, the information about A. the name of array B. the data type of array C. the first data from the set to be stored D. the index set of the array The complexity of Binary search algorithm is A. O(n) B. O(log ) C. O(n2) D. O(n log n What is the worst case time complexity of linear search algorithm? A - Ο(1) B - Ο(n) C - Ο(log n) D - Ο(n2) Stack is used for A - CPU Resource Allocation B - Breadth First Traversal C - Recursion D - None of the above

Which of the following asymptotic notation is the worst among all? A - Ο(n+9378) B - Ο(n3) C - nΟ(1) D - 2Ο(n) Which of the following searching techniques do not require the data to be in sorted form A - Binary Search B - Interpolation Search C - Linear Search D - All of the above Which of the following is example of in-place algorithm? A - Bubble Sort B - Merge Sort C - Insertion Sort D - All of the above Which of the below given sorting techniques has highest best-case runtime complexity − A - quick sort B - selection sort C - insertion sort D - bubble sort Which of the following uses memoization? A - Greedy approach B - Divide and conquer approach C - Dynamic programming approach D - None of the above! Recursion uses more memory space than iteration because A - it uses stack instead of queue. B - every recursive call has to be storeD. C - both A & B are true. D - None of the above are true. The following sorting algorithms maintain two sub-lists, one sorted and one to be sorted − A - Selection Sort B - Insertion Sort C - Merge Sort D - both A &am; B Interpolation search is an improved variant of binary search. It is necessary for this search algorithm to work that −

A - data collection should be in sorted form and equally distributeD. B - data collection should be in sorted form and but not equally distributeD. C - data collection should be equally distributed but not sorteD. D - None of the above. Which data structure allows deleting data elements from front and inserting at rear? A. Stacks B. Queues C. Deques D. Binary search tree Identify the data structure which allows deletions at both ends of the list but insertion at only one enD. A. Input-restricted deque B. Output-restricted deque C. Priority queues D. None of above Which of the following data structure is non-linear type? A. Strings B. Lists C. Stacks D. None of above Which of the following data structure is linear type? A. Strings B. Lists C. Queues D. All of above To represent hierarchical relationship between elements, which data structure is suitable? A. Deque B. Priority C. Tree D. All of above A binary tree whose every node has either zero or two children is called A. Complete binary tree B. Binary search tree C. Extended binary tree D. None of above The depth of a complete binary tree is given by A. Dn = n log2n

B. Dn = n log2n+1 C. Dn = log2n D. Dn = log2n+1 When representing any algebraic expression E which uses only binary operations in a 2-tree, A. the variable in E will appear as external nodes and operations in internal nodes B. the operations in E will appear as external nodes and variables in internal nodes C. the variables and operations in E will appear only in internal nodes D. the variables and operations in E will appear only in external nodes A binary tree can easily be converted into q 2-tree A. by replacing each empty sub tree by a new internal node B. by inserting an internal nodes for non-empty node C. by inserting an external nodes for non-empty node D. by replacing each empty sub tree by a new external node When converting binary tree into extended binary tree, all the original nodes in binary tree are A. internal nodes on extended tree B. external nodes on extended tree C. vanished on extended tree D. None of above The post order traversal of a binary tree is DEBFCA. Find out the pre order traversal A. ABFCDE B. ADBFEC C. ABDECF D. ABDCEF Which of the following sorting algorithm is of divide-and-conquer type? A. Bubble sort B. Insertion sort C. Quick sort D. All of above An algorithm that calls itself directly or indirectly is known as A. Sub algorithm B. Recursion C. Polish notation D. Traversal algorithm In a binary tree, certain null entries are replaced by special pointers which point to nodes higher in the tree for efficiency. These special pointers are called A. Leaf

B. branch C. path D. thread The in order traversal of tree will yield a sorted listing of elements of tree in A. Binary trees B. Binary search trees C. Heaps D. None of above In a Heap tree A. Values in a node is greater than every value in left sub tree and smaller than right sub tree B. Values in a node is greater than every value in children of it C. Both of above conditions applies D. None of above conditions applies In a graph if e=[u, v], Then u and v are called A. endpoints of e B. adjacent nodes C. neighbors D. all of above A connected graph T without any cycles is called A. a tree graph B. free tree C. a tree D. All of above In a graph if e=(u, v) means A. u is adjacent to v but v is not adjacent to u B. e begins at u and ends at v C. u is processor and v is successor D. both b and c If every node u in G is adjacent to every other node v in G, A graph is said to be A. isolated B. complete C. finite D. strongly connected Match the following. A. Completeness i) How long does it take to find a solution B. Time Complexity ii) How much memory need to perform the search. C. Space Complexity iii) Is the strategy guaranteed to find the solution when there in one.

A. a-iii, b-ii, c-i B. a-i, b-ii, c-iii C. a-iii, b-i, c-ii D. a-i, b-iii, c-ii The number of comparisons done by sequential search is ……………… A. (N/2)+1 B. (N+1)/2 C. (N-1)/2 D. (N+2)/2 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 State True or False. i) Binary search is used for searching in a sorted array. ii) The time complexity of binary search is O(logn). A. True, False B. False, True C. False, False D. True, True Which of the following is not the internal sort? A. Insertion Sort B. Bubble Sort C. Merge Sort D. Heap Sort State True or False. i) An undirected graph which contains no cycles is called forest. ii) A graph is said to be complete if there is an edge between every pair of vertices. A. True, True B. False, True C. False, False D. True, False In a queue, the initial values of front pointer f rare pointer r should be …….. and ……….. respectively. A. 0 and 1 B. 0 and -1

C. -1 and 0 D. 1 and 0 In a circular queue the value of r will be .. A. r=r+1 B. r=(r+1)% [QUEUE_SIZE – 1] C. r=(r+1)% QUEUE_SIZE D. r=(r-1)% QUEUE_SIZE Which of the following statement is true? i) Using singly linked lists and circular list, it is not possible to traverse the list backwards. ii) To find the predecessor, it is required to traverse the list from the first node in case of singly linked list. A. i-only B. ii-only C. Both i and ii D. None of both The advantage of …………….. is that they solve the problem if sequential storage representation. But disadvantage in that is they are sequential lists. A. Lists B. Linked Lists C. Trees D. Queues What will be the value of top, if there is a size of stack STACK_SIZE is 5 A. 5 B. 6 C. 4 D. None ………… is not the operation that can be performed on queue. A. Insertion B. Deletion C. Retrieval D. Traversal There is an extra element at the head of the list called a ………. A. Antinel B. Sentinel C. List header D. List head

In general, the binary search method needs no more than ……………. comparisons. A. [log2n]-1 B. [logn]+1 C. [log2n] D. [log2n]+1...