Data Structures Posted on January 25, 2019February 2, 2019 by aerovijay A data structure is a Specific way to store and organize data in a computer's memory so that these data can be used efficiently later. Data may be arranged in many different ways such as the logical or mathematical model for a particular organization of data is termed as a data structure. The variety of a specific data model depends on the two factors - Firstly, it must be loaded enough in structure to reflect the actual relationships of the data with the real world object. Secondly, the formation should be simple enough so that anyone can efficiently process the data each time it is necessary. Which of these best describes an array? A data structure that shows a hierarchical behavior Container of objects of similar types Container of objects of mixed types All of the mentioned How do you initialize an array in C? int arr[3] = (1,2,3); int arr(3) = {1,2,3}; int arr[3] = {1,2,3}; int arr(3) = (1,2,3); How do you instantiate an array in Java? int arr[] = new int(3); int arr[]; int arr[] = new int[3]; int arr() = new int(3); When does the ArrayIndexOutOfBoundsException occur? Compile-time Run-time Not an error None of the mentioned Which of the following concepts make extensive use of arrays? Binary trees Scheduling of processes Caching Spatial locality What are the advantages of arrays? Easier to store elements of same data type Used to implement other data structures like stack and queue Convenient way to represent matrices as a 2D array All of the mentioned Process of inserting an element in stack is called ____________ Create Push Evaluation Pop Consider the usual algorithm for determining whether a sequence of parentheses is balanced.The maximum number of parentheses that appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(())) are: 1 2 3 4 or more Here is an infix expression: 4 + 3*(6*3-12). Suppose that we are using the usual stack algorithm to convert the expression from infix to postfix notation.The maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression? 1 2 3 4 Which of the following applications may use a stack? A parentheses balancing program Tracking of local variables at run time Compiler Syntax Analyzer All of the mentioned 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 ? Queue Stack Tree Linked list The data structure required for Breadth First Traversal on a graph is? Stack Array Queue Tree A queue is a ? FIFO (First In First Out) list LIFO (Last In First Out) list Ordered array Linear tree 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? ABCD DCBA DCAB ABDC A data structure in which elements can be inserted or deleted at/from both the ends but not in the middle is? Queue Circular queue Dequeue Priority queue What kind of linked list is best to answer question like “What is the item at position n?” Singly linked list Doubly linked list Circular linked list Array implementation of linked list Linked list is considered as an example of ___________ type of memory allocation. Dynamic Static Compile time None of the mentioned In Linked List implementation, a node carries information regarding Data Link Data and Link None of the mentioned Which of the following points is/are true about Linked List data structure when it is compared with array Arrays have better cache locality that can make them better in terms of performance It is easy to insert and delete elements in Linked List Random access is not allowed in a typical implementation of Linked Lists All of the mentioned Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity? Insertion Sort Quick Sort Heap Sort Merge Sort What are splay trees? self adjusting binary search trees self adjusting binary trees a tree with strings a tree with probability distributions Which of the following is false about a doubly linked list? We can navigate in both the directions It requires more space than a singly linked list The insertion and deletion of a node take a bit longer None of the mentioned What is a memory efficient double linked list? Each node has only one pointer to traverse the list back and forth The list has breakpoints for faster traversal An auxiliary singly linked list acts as a helper list to traverse through the doubly linked list None of the mentioned How do you calculate the pointer difference in a memory efficient double linked list? head xor tail pointer to previous node xor pointer to next node pointer to previous node – pointer to next node pointer to next node – pointer to previous node What is the time complexity of inserting a node in a doubly linked list? O(nlogn) O(logn) O(n) O(1) What differentiates a circular linked list from a normal linked list? You cannot have the ‘next’ pointer point to null in a circular linked list It is faster to traverse the circular linked list You may or may not have the ‘next’ pointer point to null in a circular linked list All of the mentioned Which of the following application makes use of a circular linked list? Undo operation in a text editor Recursive function calls Allocating CPU to resources All of the mentioned Consider a small circular linked list. How to detect the presence of cycles in this list effectively? Keep one node as head and traverse another temp node till the end to check if its ‘next points to head Have fast and slow pointers with the fast pointer advancing two nodes at a time and slow pointer advancing by one node at a time Cannot determine, you have to pre-define if the list contains cycles None of the mentioned What is the time complexity for converting decimal to binary numbers? O(1) O(n) O(logn) O(nlogn) Which data structure can be used suitably to solve the Tower of Hanoi problem? Tree Heap Priority queue Stack Which among the following is not a palindrome? Madam Dad Malayalam Maadam Which data structure can be used to test a palindrome? Tree Heap Stack Priority queue What is the number of moves required in the Tower of Hanoi problem for k disks? 2k – 1 2k + 1 2k + 1 2k – 1 Which of the following real world scenarios would you associate with a stack data structure? piling up of chairs one above the other people standing in a line to be serviced at a counter offer services based on the priority of the customer all of the mentioned What does ‘stack underflow’ refer to? accessing item from an undefined stack adding items to a full stack removing items from an empty stack index out of bounds exception What is the time complexity of pop() operation when the stack is implemented using an array? O(1) O(n) O(logn) O(nlogn) Which of the following statements are correct with respect to Singly Linked List(SLL) and Doubly Linked List(DLL)? Complexity of Insertion and Deletion at known position is O(n) in SLL and O(1) in DLL SLL uses lesser memory per node than DLL DLL has more searching power than SLL All of the mentioned What is an AVL tree? a tree which is balanced and is a height balanced tree a tree which is unbalanced and is a height balanced tree a tree with three children a tree with atmost 3 children Minimum number of queues to implement stack is ___________ 3 4 1 2 What is a bit array? Data structure for representing arrays of records Data structure that compactly stores bits An array in which most of the elements have the same value None of the mentioned Which of the following is an advantage of bit array? Exploit bit level parallelism Maximal use of data cache Can be stored and manipulated in the register set for long periods of time All of the mentioned Which class in Java can be used to represent bit array? BitSet BitVector BitArray BitStream What is a dynamic array? A variable size data structure An array which is created at runtime The memory to the array is allocated at runtime An array which is reallocated everytime whenever new elements have to be added How will you implement dynamic arrays in Java? Set Map HashMap List What are parallel arrays? Arrays of the same size Arrays allocated one after the other Arrays of the same number of elements Arrays allocated dynamically What are the advantages of parallel arrays over the traditional arrays? When a language does not support records, parallel arrays can be used Increased locality of reference Ideal cache behavior All of the mentioned What is a sparse array? Data structure for representing arrays of records Data structure that compactly stores bits An array in which most of the elements have the same value None of the mentioned What are the advantages of sparse matrices over normal matrices? Size Speed Easily compressible All of the mentioned Which of the following property does not hold for matrix multiplication? Associative Distributive Commutative None of the mentioned Which of the following are the uses of matrices? In solving linear equations Image processing Graph theory All of the mentioned What is a skip list? a linkedlist with size value in nodes a linkedlist that allows faster search within an ordered sequence a linkedlist that allows slower search within an ordered sequence a tree which is in the form of linked list Skip lists are similar to which of the following datastructure? stack heap binary search tree balanced binary search tree What is xor linked list ? uses of bitwise XOR operation to decrease storage requirements for doubly linked lists uses of bitwise XOR operation to decrease storage requirements for linked lists uses of bitwise operations to decrease storage requirements for doubly linked lists just another form of linked list Free lists are used in static memory allocation dynamic memory allocation contagious allocations are used for speeding up linked list operations What are implicit and explicit implementations of freelists? garbage collection and new or malloc operators respectively new or malloc and garbage collection respectively implicit implementation is not favored explicit implementation is not favored What are the important properties of xor lists X⊕X = 0 X⊕0 = X (X⊕Y)⊕Z = X⊕(Y⊕Z) All of the mentioned Binary trees can have how many children? 2 any number of children 0 or 1 or 2 0 or 1 If the tree is not a complete binary tree then what changes can be made for easy access of children of a node in the array ? every node stores data saying which of its children exist in the array no need of any changes continue with 2w and 2w+1, if node is at i keep a seperate table telling children of a node use another array parallel to the array with tree For the tree below, write the pre-order traversal. 2, 7, 2, 6, 5, 11, 5, 9, 4 2, 7, 5, 2, 6, 9, 5, 11, 4 2, 5, 11, 6, 7, 4, 9, 5, 2 2, 7, 5, 6, 11, 2, 5, 4, 9 For the tree below, write the in-order traversal. 2, 7, 2, 6, 5, 11, 5, 9, 4 2, 7, 5, 2, 6, 9, 5, 11, 4 2, 5, 11, 6, 7, 4, 9, 5, 2 2, 7, 5, 6, 11, 2, 5, 4, 9 For the tree below, write the level-order traversal. 2, 7, 2, 6, 5, 11, 5, 9, 4 2, 7, 5, 2, 6, 9, 5, 11, 4 2, 5, 11, 6, 7, 4, 9, 5, 2 2, 7, 5, 6, 11, 2, 5, 4, 9 What is a complete binary tree? Each node has exactly zero or two children A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from right to left A binary tree, which is completely filled, with the possible exception of the bottom level, which is filled from left to right None of the mentioned The number of edges from the root to the node is called __________ of the tree. Height Depth Length None of the mentioned Which of the following is false about a binary search tree? The left child is always lesser than its parent The right child is always greater than its parent The left and right sub-trees should also be binary search trees None of the mentioned What are the conditions for an optimal binary search tree and what is its advantage? The tree should not be modified and you should know how often the keys are accessed, it improves the lookup cost You should know the frequency of access of the keys, improves the lookup time The tree can be modified and you should know the number of elements in the tree before hand, it improves the deletion time None of the mentioned Is it true that splay trees have O(logn) amortized complexity ? true false What is a Cartesian tree? a skip list in the form of tree a tree which obeys cartesian product a tree which obeys heap property and whose inorder traversal yields the given sequence a tree which obeys heap property only After applying the below operations on a input sequence, what happens?i. construct a cartesian tree for input sequenceii. put the root element of above tree in a priority queueiii. if( priority queue is not empty) then.search and delete minimum value in priority queue.add that to output.add cartesian tree children of above node to priority queue constructs a cartesian tree sorts the input sequence does nothing produces some random output When it would be optimal to prefer Red-black trees over AVL trees? when there are more insertions or deletions when more search is needed when tree must be balanced when log(nodes) time complexity is needed What is a weight balanced tree? A binary tree that stores the sizes of subtrees in nodes A binary tree with an additional attribute of weight A height balanced binary tree A normal binary tree What are the operations that can be performed on weight balanced tree? all basic operations and set intersection, set union and subset test all basic operations set intersection, set union and subset test only insertion and deletion What is the special property of red-black trees and what root should always be? a color which is either red or black and root should always be black color only height of the tree pointer to next node a color which is either green or black The null left pointer pointing to predecessor and null right pointer pointing to successor. how many types of threaded tree are possible with this convention? inorder, postorder, preorder traversals inorder postorder preorder What is a threaded binary tree traversal? a binary tree traversal using stacks a binary tree traversal using queues a binary tree traversal using stacks and queues a binary tree traversal without using stacks and queues Heap exhibits the property of a binary tree? True False What is the space complexity of searching in a heap? O(logn) O(n) O(1) O(nlogn) Heap can be used as ________________ Priority queue Stack A decreasing order array None of the mentioned What is the other name of weak heap? Min-heap Max-heap Relaxed -heap Leonardo heap Choose the correct properties of weak-heap. Every node has value greater than the value of child node Every right child of node has greater value than parent node Every left child of node has greater value than parent node None of the mentioned What is a hash table? A structure that maps values to keys A structure that maps keys to values A structure used for storage A structure used to implement stack and queue The main distinguishable characterstic of a binomial heap from a binary heap is that it allows union operations very efficiently it does not allow union operations that could easily be implemented in binary heap the heap structure is not similar to complete binary tree the location of child node is not fixed i.e child nodes could be at level (h-2) or (h-3), where h is height of heap and h>4 What is direct addressing? Distinct array position for every possible key Fewer array positions than keys Fewer keys than array positions None of the mentioned Which of the following is true? A graph may contain no edges and many vertices A graph may contain many edges and no vertices A graph may contain no edges and no vertices None of the mentioned What would be the number of zeros in the adjacency matrix of the given graph? 10 6 16 0 Adjacency matrix of all graphs are symmetric. False True If there are more than 1 topological sorting of a DAG is possible, which of the following is true. Many Hamiltonian paths are possible No Hamiltonian path is possible Exactly 1 Hamiltonian path is possible Given information is insufficient to comment anything Which of the following statement is true. There exists a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9 There exists a MultiGraph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9 There exists a MultiGraph as well as a Simple Graph having 10 vertices such that minimum degree of the graph is 0 and maximum degree is 9 None of the mentioned Which of the following logical operation can be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams? Conjunction Disjunction Negation All of the mentioned In which of the following case does a Propositional Directed Acyclic Graph is used for? Representation of Boolean Functions String Matching Searching Sorting of number What is a randomized QuickSort? The leftmost element is chosen as the pivot The rightmost element is chosen as the pivot Any element in the array is chosen as the pivot A random number is generated which is used as the pivot Where is linear searching used? When the list has only a few elements When performing a single search in an unordered list Used all the time When the list has only a few elements and When performing a single search in an unordered list What is the advantage of bubble sort over other sorting techniques? It is faster Consumes less memory Detects whether the input is already sorted All of the mentioned What is the advantage of recursive approach than an iterative approach? Consumes less memory Less code and easy to implement Consumes more memory All of the mentioned When the topological sort of a graph is unique? When there exists a hamiltonian path in the graph In the presence of multiple nodes with indegree 0 In the presence of single node with indegree 0 None of the mentioned When is the uniform binary search an optimization over the usual binary search? A table lookup is generally faster than an addition and a shift Many searches will be performed on the same array Many searches will be performed on several arrays of the same length All of the mentioned Which algorithmic technique does Fibonacci search use? Brute force Divide and Conquer Greedy Technique Backtracking What is the advantage of selection sort over other sorting techniques? It requires no additional storage space It is scalable It works best for inputs which are already sorted It is faster than any other sorting technique In recursion, the condition for which the function will stop calling itself is ____________ Best case Worst case Base case There is no such condition Recursion is a method in which the solution of a problem depends on ____________ Larger instances of different problems Larger instances of the same problem Smaller instances of the same problem Smaller instances of different problems Which of the following statements is true? Recursion is always better than iteration Recursion uses more memory compared to iteration Recursion uses less memory compared to iteration Iteration is always better and simpler than recursion Which of the following problems can be solved using recursion? Factorial of a number Nth fibonacci number Length of a string All of the mentioned