INTERVIEW QUS ON DATASTR
INTERVIEW QUS ON DATASTR
MOST IMPORTANT QUESTIONS ON DATA STRUCTURE
1. Define O & Ɵ notation. 2. Explain ‘Stack data structure’ with example. (all operations of stack with ex) 3. Explain ‘Queue data structure’ with example. 4. Explain heap sort with example. 5. Write the applications of Array and difference between array and linked list. 6. What are the working principle of Circular queue, circular linked list and double linked list? 7. Write the algorithm for insertion at begin, at between, at end for single linked list. 8. Define Binary search tree and strictly binary tree with example. 9. Write the algorithms of Insertion, bubble, heap, quick, radix, selection sort 10. Write the procedure of Infix to prefix conversion with example. 11. What is the Linear search technique? 12. Explain AVL tree with creating example. 13. Write the algorithm to evaluate postfix expression. 14. Explain different hash functions. 15. Define algorithm and flowchart.
Multiple-choice Question & Answers in Data Structure and Python
Which of the following is not a property of an algorithm? | |
| a)Input | b)Output |
| c)Definiteness | d)Timeliness |
| Explanation:What is the time complexity of inserting at the end in dynamic arrays? | |
| a)O(1) | b) O(n) |
| c)O(logn) | d) Either O(1) or O(n) |
| Explanation: Depending on whether the array is full or not, the complexity in dynamic array varies. If you try to insert into an array that is not full, then the element is simply stored at the end, this takes O(1) time. If you try to insert into an array which is full, first you will have to allocate an array with double the size of the current array and then copy all the elements into it and finally insert the new element, this takes O(n) time. 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) |
| Explanation: pop() accesses only one end of the structure, and hence constant time. To find a data of an array will take | |
| a)O(1) | b)O(n) |
| c)Cannot determine | d)depend upon the type of array |
| Explanation: finding a data of an array is done by checking all possiblity, hence O(n). In the best 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)n | d)1 |
| Explanation: The best case is searching element is found at the beginning, hence O(n). What is the time complexity to count the number of elements in the doubly linked list? | |
| a)O(1) | b)O(n) |
| c)O(logn) | d)O(n2) |
| Explanation: To count the number of elements, you have to traverse through the entire list, hence complexity is O(n). Which is not the valid index of an array arr? | |
| a)arr[0] | b)arr[n] |
| c)arr[-1] | d)[10]-arr |
| Explanation: List cannot be subtracted from array. To insert a data in stack which operation is used? | |
| a)Front | b)Push |
| c)Pop | d)Rear |
| Explanation: In data structure, Push operation is used to insert elements into a stack. To remove a data in stack which operation is used? | |
| a)Front | b)Push |
| c)Pop | d)Rear |
| Explanation: In data structure, Pop operation is used to remove top element from a stack. Array contain the data in | |
| a)Various type | b)Homogeneous type |
| c)Distinct type | d)Heterogeneous type |
| Explanation: Arrays can hold only homogeneous data types elements. To find an element of an array will take | |
| a)O(1) | b)O(n) |
| c)Cannot determine | d)depend upon the type of array |
| Explanation: Finding a data of an array is done by checking all possiblity, hence O(n) From where does the insertion and deletion of elements get accomplished in Queues? | |
| a)Front & Rear ends respectively | b)Rear & Front ends respectively |
| c)Only Front ends | d)Only Rear ends |
| Explanation: In Queue data structure, Elements are inserted from the rear and deletion take place from the front ends respectively. What should be the value of rear (end) if the queue is full (elements are completely occupied )? | |
| a)1 | b)-1 |
| c)MAX + 1 | d)MAX - 1 |
| Explantion: Considering, Max is the upper range of the queue then rear take place from 0 to MAX-1 for insertion. Thus, rear == MAX-1 is the condition when queue is full. Where the elements are stored in accordance to the representation of Queue by a Linked Structure? | |
| a)mesh | b)node |
| c)mesh and node | d)none of these |
| Explanation: Node stores elements in accordance to representation of Queue - Data Structure. Process of removing an element from stack is called __________ | |
| a)Create | b)Push |
| c)Evaluation | d)Pop |
| Explanation: In data structure, Pop operation is used to remove top element from a stack. Pushing an element into stack already having five elements and stack size of 5, then stack becomes | |
| a)Overflow | b)Crash |
| c)Underflow | d)User flow |
| Explanation: Overflow is a state where no more insertion can take place. What is the result of the following operation? Top (Push (S, X)) | |
| a)X | b)X+S |
| c)S | d)XS |
| Explanation: Pushing an element is stored into topmost position into a stack. Hence, X is the topmost element stored in the stack. Which data structure is used for implementing recursion? | |
| a)Queue | b)Stack |
| c)Array | d)List |
| Explanation: Recursion makes use of system stack for storing the return addresses of the function calls. Every recursive function has its equivalent iterative (non-recursive) function. Even when such equivalent iterative procedures are written, explicit stack is to be used. Convert the following infix expressions into its equivalent postfix expressions (A B ⋀D)/(E – F) G. | |
| a)(A B D ⋀ +E F – / G+ ) | b)(A B D +⋀ E F – / G ) |
| c)(A B D ⋀+ E F/- G+ ) | d)(A B D E F+ ⋀ / – G+ ) |
| Explanation: Try it as yourself. Which of the following statement(s) about stack data structure is/are NOT correct? | |
| a)Linked List are used for implementing Stacks | b)Top of the Stack always contain the new node |
| c)Stack is the FIFO data structure | d)Null link is present in the last node at the bottom of the stack |
| Explanation: Stack follows LIFO data structure. Option a, b, and d are correct. What is the value of the postfix expression 6 3 2 4 + – *: | |
| a)1 | b)40 |
| c)74 | d)-18 |
| Explanation: Try it as yourself. 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 / |
| Explanation: Try it as yourself. The process of accessing data stored in a serial access memory is similar to manipulating data on a ________ | |
| a)Heap | b)Binary Tree |
| c)Array | d)Stack |
| Explanation: In serial access memory data records are stored one after the other in which they are created and are accessed sequentially. In stack data structure, elements are accessed sequentially. Stack data structure resembles the serial access memory. Which data structure is needed to convert infix notation to postfix notation? | |
| a)Branch | b)Tree |
| c)Queue | d)Stack |
| Explanation: The Stack data structure is used to convert infix expression to postfix expression. The purpose of stack is to reverse the order of the operators in the expression. Using what formula can a parent node be located in an array? | |
| a)(i+1)/2 | b)(i-1)/2 |
| c)i/2 | d)2i/2 |
| Explanation: If a binary tree is represented in an array, parent nodes are found at indices (i-1)/2. If the elements “A”, “B”, “C” and “D” are placed in a stack and are deleted one at a time, what is the order of removal? | |
| a)ABCD | b)DCBA |
| c)DCAB | d)ABDC |
| Explanation: Stack follows LIFO approach. i.e. Last in First Out Approach. So, the order of removal elements are DCBA. A queue follows __________ | |
| a)FIFO (First In First Out) principle | b)LIFO (Last In First Out) principle |
| c)Ordered array | d)Linear tree |
| Explanation: In Queue data structure, Elements are inserted from the rear and deletion take place from the front ends respectively. This approach is called FIFO approach. If the elements “A”, “B”, “C” and “D” are placed in a queue and are deleted one at a time, in what order will they be removed? | |
| a)ABCD | b)DCBA |
| c)DCAB | d)ABDC |
| Explanation: Queue follows FIFO approach. i.e. First in First Out Approach. So, the order of removal elements are ABCD. Queues serve major role in ______________ | |
| a)Simulation of recursion | b)Simulation of arbitrary linked list |
| c)Simulation of limited resource allocation | d)Simulation of heap sort |
| Explanation: Simulation of limited resource allocation is the major role of QUEUE. In the linked list, each node contain a minimum of two fields. One field is the data field to store the data the second field is? | |
| a)Pointer to character | b)Pointer to integer |
| c)Pointer to node | d)Node |
| Explanation: Each node in a linked list contains data and a pointer (reference) to the next node. Second field contains pointer to node. Identify the reason which doesn’t play a key role to use threaded binary trees? | |
| a)The storage required by stack and queue is more | b)The pointers in most of the nodes of a binary tree are NULL |
| c)It is difficult to find a successor node | d)They occupy less size |
| Explanation: Threaded binary trees are introduced to make the Inorder traversal faster without using any stack or recursion. Stack and Queue require more space and pointers in the majority of binary trees are null and difficulties are raised while finding successor nodes. Size constraints are not taken on threaded binary trees, but they occupy less space than a stack/queue. How many common operations are performed in a binary tree? | |
| a)1 | b)2 |
| c)3 | d)4 |
| Explanation: Three common operations are performed in a binary tree- they are insertion, deletion and traversal. How many types of insertion are performed in a binary tree? | |
| a)1 | b)2 |
| c)3 | d)4 |
| Explanation: Two kinds of insertion operation is performed in a binary tree- inserting a leaf node and inserting an internal node. In a binary search tree, which of the following traversals would print the numbers in the ascending order? | |
| a)Level-order traversal | b)Pre-order traversal |
| c)Post-order traversal | d)In-order traversal |
| Explanation: Inorder traversal of BST prints it in ascending order. The only trick is to modify recursion termination condition in standard Inorder Tree Traversal. In a full binary tree if a number of internal nodes is I, then the number of leaves L are? | |
| a)L = 2*I | b)L = I + 1 |
| c)L = I – 1 | d)L = 2*I – 1 |
| Explanation: Theorem: Let T be a nonempty, full binary tree Then: (a) If T has I internal nodes, the number of leaves is L = I + 1. (b) If T has I internal nodes, the total number of nodes is N = 2I + 1. The number of edges from the root to the node is called __________ of the tree. | |
| a)Height | b)Depth |
| c)Length | d)Width |
| Explanation: The number of edges from the root to the node is called depth of the tree. Which of the following tree data structures is not a balanced binary tree? | |
| a)AVL tree | b)Red-black tree |
| c)Splay tree | d)B-tree |
| Explanation: All the tree data structures given in options are balanced, but B-tree can have more than two children. What is the worst case complexity of bubble sort? | |
| a)O(nlogn) | b)O(logn) |
| c)O(n) | d)O(n2) |
| Explanation: Bubble sort has a worst-case and average complexity of О(n2), where n is the number of items being sorted. Merge sort uses which of the following technique to implement sorting? | |
| a)backtracking | b)greedy algorithm |
| c)divide and conquer | d)dynamic programming |
| Explanation: Merge sort uses the technique of divide and conquer in order to sort a given array. It divides the array into two halves and apply merge sort algorithm to each half individually after which the sorted versions of these halves are merged together. What is the worst-case time complexity of merge sort? | |
| a)O(n log n) | b)O(n2) |
| c)O(n2 log n) | d)O(n log n2) |
| Explanation: In the worst case, merge sort does about 39% fewer comparisons than quicksort does in the average case. In terms of moves, merge sort's worst case complexity is O(n log n). Which of the following is not in place sorting algorithm? | |
| a)quick sort | b)merge sort |
| c)heap sort | d)insertion sort |
| Explanation: Bubble sort is an example of in-place sorting. However, in some sorting algorithms, the program requires space which is more than or equal to the elements being sorted. Sorting which uses equal or more space is called not-in-place sorting. Merge-sort is an example of not-in-place sorting. Which of the following stable sorting algorithm takes the least time when applied to an almost sorted array? | |
| a)Quick sort | b)Insertion sort |
| c)Selection sort | d)Merge sort |
| Explanation: Insertion sort takes linear time to sort a partially sorted array. Though merge and quick sort takes O(n*logn) complexity to sort, merge sort is stable. What is the worst-case time complexity of a quick sort algorithm? | |
| a)O(N) | b)O(N log N) |
| c)O(N2) | d)O(log N) |
| Explanation: Like Merge Sort, QuickSort is a Divide and Conquer algorithm. Although the worst case time complexity of QuickSort is O(n2). What is the average running time of a quick sort algorithm? | |
| a)O(N) | b)O(N log N) |
| c)O(N2) | d)O(log N) |
| Explanation: QuickSort is a Divide and Conquer algorithm. This, the average running time of a quick sort algorithm is O(n log n). Which one of the following sorting algorithm is best suited to sort an array of 1 million elements? | |
| a)Quick sort | b)Insertion sort |
| c)Selection sort | d)Merge sort |
| Explanation: The Quick sort is best suited to sort the array of 1 million elements. The practical implementations of Quick sort use randomised version. In practice randomised Quick sort algorithms rarely shows worst case behaviour and is almost always O(nlogn). On which algorithm is heap sort based on? | |
| a)Fibonacci heap | b)Binary tree |
| c)Priority queue | d)FIFO |
| Explanation: Heap sort is based on the algorithm of priority queue and it gives the best sorting time. The worst-case occur in linear search algorithm when | |
| a)Item is somewhere in the array | b)Item is not |
| c)item is the first element in the array | d)item is the last element in the array or not there at all |
| Explanation: In linear search all items must be consider in wost case. What is the worst-case complexity of binary search using recursion? | |
| a)O(nlogn) | b)O(logn) |
| c)O(n) | d)O(n2) |
| Explantion: For a binary search, the worst-case is when the target item is not in the search list. or, when the target is found in the middle of the search list. Post-order traversal followed… | |
| a)Root-Left-Right | b)Left-Root-Right |
| c)Left-Right-Root | d)Right-Left-Root |
| Explanation: The tree traversal is a form of graph traversal and refers to the process of visiting each node in a tree data structure, exactly once. In post order traversal, root is consider at the end. Key-value pairs are usually seen ina) Hash tablesb)Heaps c)Both Hash tables and Heapsd)Skip list Explanation: Hash table or hash map is a data structure used to store key-value pairs. It is a collection of items stored to make it easy to find them later. |
Comments
Post a Comment
Please do not enter any spam link in the comment box.