**Data Structures NPTEL Exam ****>>** Complete *Questions* and **Answers** of *Data Structure Course*

**>>**

*Questions*

**Answers**

*Data Structure Course*

- Term Data Structure refers to _________ and interrelationship between them.
- Data is nothing but ____________
- In what kind of storage we can easily insert,delete,concatenate and rearrange sub strings ?
- ADT is called as Abstract because
- If elements of the data structure forms a sequence of list then it is called as ____________
- The smallest element of an array’s index is called its
- In a circular linked list .
- A linear collection of data elements where the linear node is given by means of pointer is

called - A linear list in which the pointer points only to the successive node is ________
- Linked lists are best suited _______
- User push 1 element in the stack having already five elements and having stack size as 5 then stack becomes ___________.
- In the stack, If user try to remove element from the empty stack then it called as _______
- Process of removing element from the stack is called as _______.
- In the stack process of inserting an element in the stack is called as ___________.
- Stack in data structure is _________.
- Instack,Insertion and deletion can be done only at the_____ element
- What data structure is used to perform recursion?
- What is the type of the algorithm used in solving the 8 Queens problem?
- What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?
- Which of the following statement(s) about stack data structure is/are NOT correct?
- 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 ?
- The data structure required for Breadth First Search on a graph is?
- A queue is a ?
- In linked list implementation of a queue, where does a new element be inserted?
- A data structure in which elements can be inserted or deleted at/from both the ends but not in the middle is?
- In linked list implementation of a queue, front and rear pointers are tracked. Which of these pointers will change during an insertion into a NONEMPTY queue?
- A normal queue, if implemented using an array of size MAX_SIZE, gets full when
- A variant of the linked list in which none of the node contains NULL pointer is?
- In circular linked list, insertion of node requires modification of?
- In Binary trees nodes with no successor are called _________ .
- A connected graph T without any cycles is called a ……..
- Sequential representation of binary tree uses ……..
- A binary tree whose every node has either zero or two children is called …….
- Which indicates pre-order traversal?
- A BST is traversed in the following order recursively: Right, root, leftThe output sequence will be in
- In order to get the contents of a Binary search tree in ascending order, one has to traverse it in
- In order to get the information stored in a Binary Search Tree in the descending order, one should traverse it in which of the following order?
- What is the worst case time complexity for search, insert and delete operations in a general Binary Search Tree?
- Which of the following traversal outputs the data in sorted order in a BST?
- What is common in three different types of traversals (Inorder, Preorder and Postorder)?
- The inorder and preorder traversal of a binary tree are d b e a f c g and a b d e c f g, respectively. The postorder traversal of the binary tree is:
- Which of the following pairs of traversals is not sufficient to build a binary tree from the given traversals?
- Which traversal of tree resembles the breadth first search of the graph?
- Which of the following tree traversal uses a queue data structure?
- What is the expected time required to search for a value in a binary search tree containing n nodes? (You should make reasonable assumptions about the structure of the tree.)
- If node N is a terminal node in a binary tree then its ………
- In threaded binary tree ……… points to higher nodes in tree.
- In linked representation of Binary trees LEFT[k] contains the _____ of at the node N, where k is the location.
- The post order traversal of a binary tree is DEBFCA. Find out the pre order Traversal.
- The height of a BST is given as h. Consider the height of the tree as the no. of edges in the longest path from root to the leaf. The maximum no. of nodes possible in the tree is?
- Suppose we have numbers between 1 and 1000 in a binary search tree and want to search for the number 363. Which of the following sequence could not be the sequence of the node examined?
- Which type of traversal of binary search tree outputs the value in sorted order?
- A binary search tree is formed from the sequence 6, 9, 1, 2, 7, 14, 12, 3, 8, 18. The minimum number of nodes required to be added in to this tree to form an extended binary tree is?
- When a binary tree is converted in to an extended binary tree, all the nodes of a binary tree in the external node becomes
- The maximum number of elements in a heap of height h is
- In a full binary tree, every internal node has exactly two children. A full binary tree with 2n+1 nodes contains
- To represent hierarchical relationship between elements, Which data structure is suitable?
- In BST operations-______ must not leave ‘a gap’ in the tree.
- AVL trees have a faster _______________
- In ______________ tree, the heights of two child sub tree of any node differ by at most one
- Items 7,3,11,9 and 13 are inserted into an AVL tree. What happens when 12 is inserted?
- A binary search tree whose left sub tree and right sub tree differ in hight by at most 1 unit is called ……
- The balance factor for an AVL tree is either
- AVL trees have LL, LR, RR, RL rotations to balance the tree to maintain the balance factor (LR : Insert node in Right sub tree of Left sub tree of node A, etc). Among rotations the following are single and double rotations
- Which of the following is not possible as a balance factor of any node of an AVL tree?
- What data structure would you mostly likely see in a non recursive implementation of a recursive algorithm?
- An AVL delete is similar to a regular ______ tree delete.
- What maximum difference in heights between the leafs of a AVL tree is possible?
- In AVL tree delete ________ children is used to replace it with null.
- In AVL tree delete to delete will require you to go all the way back to the looking for imbalances.
- For each node X encountered, check if heights of left(x) and right(x) differ by atmost ____.
- Rotations in deletion have ______ cases for single rotations.
- Which of the following concepts make extensive use of arrays?
- In linked list each node contain minimum of two fields. One field is data field to store the data second field is?
- The concatenation of two list can performed in O(1) time. Which of the following variation of linked list can be used?
- The data structure required to check whether an expression contains balanced parenthesis is?
- The process of accessing data stored in a serial access memory is similar to manipulating data on a ________
- What does ‘stack underflow’ refer to?
- What is the time complexity of pop () operation when the stack is implemented using an array?
- If we have a tree of n nodes, how many edges will it have?
- Which of the following data structures can handle updates and queries in log(n) time on an array?
- Of the following data structures, which has a Last in First Out ordering? In other words, the one that came in last will be the first to be popped.
- What is the complexity of searching for a particular element in a Singly Linked List?
- Which of the following statements are correct with respect to Singly Linked List(SLL) and Doubly Linked List(DLL)?
- Minimum number of queues to implement stack is ___________
- What is the term for inserting into a full queue known as?
- What is the need for a circular queue?
- You are asked to perform a queue operation using a stack. Assume the size of the stack is some value ‘n’ and there are ‘m’ number of variables in this stack. The time complexity of performing dequeue operation is (Using only stack operations like push and pop)(Tightly bound)
- What is a dequeue?
- What is the time complexity of deleting from the rear end of the dequeue implemented with a singly linked list?
- What are the number of nodes of left and right subtree of the binary tree if the data is inserted in the following order: 45, 15, 8, 5 6, 5,65, 47, 12, 18, 10, 73, 50, 16, 61
- The worst case time complexity of AVL tree is better in comparison to binary search tree for
- A full binary tree with 2n+1 nodes contain
- If a node in a BST has two children, then its inorder predecessor has
- A full binary tree with n leaves contains
- One can convert a binary tree into its mirror image by traversing it in
- The number of leaf nodes in a complete binary tree of depth d is
- B Trees are generally
- What is the maximum possible number of nodes in a binary tree at level 6?
- Can a tree stored in an array using either one of inorder or post order or pre order traversals be again reformed?
- A full binary tree with 2n+1 nodes contain
- A binary tree whose every node has either zero or two children is called
- The degree of a vertices is the number of _______ to that vertex.
- A simple path is a path such that all vertices are _____.
- A ______ is a path that starts and ends at the same point.
- In undirected graph adjacency matrix is _______.
- A graph with numbers assigned to its edges is ______.
- Dynamic programming reduces ___________.
- Travelling salesman problem is an example of _________.
- A connected sub graph that connects all the vertices of the original connected graph is called _______.
- Prim’s algorithm follows a _______ approach to find a minimum spanning tree.
- ________ is defined as the shortest distance between source and destination.
- A complete binary tree can be stored as an array using _______ traversal.
- The accessing of location of elements in a heap is _______.
- Heap and ________ are considered to be synonyms of each other.
- Insertion into a heap can be done in ________ time.
- An empty heap is said to be in a state of ________.
- The heap is represented in the _______ data structure?
- The heap sort can be done in the order of ________ time?
- You reserve the heap property the ______ should always be less then the parent nodes?
- In heap we are removing the elements in the zero position and swapping it at the _____ position.
- The output that will be the maximum element and then you reheapify this between _______.
- ________ time to initialize hash table(b is the number of positions in hash table)
- ________ time to perform insert,remove and search.
- __________ is a method of collision resolution in hash tables.
- A _______ is an alternative method for representing a dictionary.
- ________ are the methods to deal with collision.
- Bubble sort, selection sort and insertion sort are all _______.
- The average time complexity of inserting sorting is ________
- Space complexity for bubble sort is ______.
- The worst time complexity for insertion sorting is _______.
- Which of the following is an external sorting?
- Based on which concept priority queue is done?
- Insert elements in a priority queue implemented with an unsorted sequence is done in ____.
- Insert elements in a priority queue implemented with sorted sequence is done in ____.
- Very slow way of sorting is ______.
- Which of the following sorting algorithm is of divide and conquer type?
- Brute force is a ______.
- In selection sort scan the array to find its ____ and swap it with the first element.
- _______ finds the minimum.
- Selection sort ______ smallest element with the value in the first position.
- The best, average and worst case time complexities of the selection sort.
- Bubble sort follows which method?
- Running time of bubble sort algorithm is _____.
- Bubble sort is also called as ________.
- Running time for both best case and worst case of bubble sort algorithm are _____.
- Worst case of bubble sort algorithm is nothing but _______.
- An adjacency matrix representation of a graph cannot contain information of :
- In Breadth First Search of Graph, which of the following data structure is used?
- For an undirected graph G with n vertices and e edges, the sum of the degrees of each vertex is
- What is the number of edges present in a complete graph having n vertices?
- A connected planar graph having 6 vertices, 7 edges contains _____________ regions.
- Which of the following properties does a simple graph not hold?
- What is the maximum number of edges in a bipartite graph having 10 vertices?
- In a max-heap, element with the greatest key is always in which node?
- Heap can be used as ________________
- Hash tree is generalization of ______
- Which of the following is a widely used form of the hash tree?
- Where is the hash tree used?
- Which of the following algorithmic paradigm is used in the merge sort?
- Hash tree is also known as _____
- What sorting algorithms have their best and worst case times equal?
- A technique for direct search is
- A sort which relatively passes through a list to exchange the first element with any element less than it and then repeats with a new first element is called
- The total number of companions required to merge 4 sorted files containing 15, 3, 9 and 8 records into a single sorted file is
- If several elements competing for the same bucket in the hash table,what is it called?
- The number of interchanges required to sort 5, 1, 6, 2 4 in ascending order using
- A characteristic of the data that binary search uses but the linear search ignores is the___________.
- In order to get the contents of a Binary search tree in ascending order, one has to traverse it in
- The worst-case time for binary search to find out a single item in an array is in _________________ ?
- The Worst case occur in linear search algorithm when
- All the above Which of the following is not the required condition for binary search algorithm
- The following sorting algorithm is of divide and conquer type
- The in-order traversal of tree will yield a sorted listing of elements of tree in ________________.
- The number of swappings needed to short the numbers 8, 22, 7, 9, 31, 19, 5, 13 in ascending order using bubble sort is
- Quick sort uses?
- Two main measures for the efficiency of an algorithm are _____.
- The complexity of bubble sort algorithm is ______.
- If we were sorting entries according to keys, then each bucket is a _______.
- Sorting algorithm can be characterized as ______.
- Radix and ______ do not work well when keys are very long.
- ______ works as long as the Bucket sort stages are stable sorts.
- Radix sort is ____ of bucket sort.
- Radix-sort perform the bucket sorts by ______.
- Radix and bucket sorts are ______.
- First implementation of merge sort was on the ENIAC in the year _______.
- _______ is a method of algorithm design.
- Merge sort has _______ running time
- _______ is a sorting algorithm based on the divide-and-conquer paradigm.
- The best case for the recursion are sub problems of size _____.
- What is the advantage of bubble sort over other sorting techniques?
- For merging two sorted lists of size m and n into sorted list of size m+n, we require comparisons of
- What is the best case complexity of QuickSort?
- The given array is arr = {2,3,4,1,6}. What are the pivots that are returned as a result of subsequent partitioning?
- In addition to the pancake sorting problem, there is the case of the burnt pancake problem in which we are dealing with pancakes (discs) that are burnt on one side only. In this case it is taken that the burnt side must always end up _______
- Which of the following is not a stable sorting algorithm?
- Which of the following is a stable sorting algorithm?
- Which of the following is not an in-place sorting algorithm?
- Running merge sort on an array of size n which is already sorted is
- 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?
- Which of the following is not a non-comparison sort?
- The time complexity of heap sort in worst case is
- If the given input array is sorted or nearly sorted, which of the following algorithm gives the best performance?
- Which of the following algorithm pays the least attention to the ordering of the elements in the input list?
- 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?
- Time complexity of bubble sort in best case is
- Given a number of elements in the range [0….n3]. Which of the following sorting algorithms can sort them in O(n) time?
- Which of the following algorithms has lowest worst case time complexity?
- Which of the following sorting algorithms is/are stable
- Counting sort performs …………. Numbers of comparisons between input elements.
- The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base 10 representation is
- The running time of radix sort on an array of n integers in the range [0……..n5 -1] when using base n representation is
- Which of the following sorting algorithm is in-place
- The radix sort does not work correctly if each individual digit is sorted using
- Which of the following sorting algorithm has the running time that is least dependant on the initial ordering of the input?
- Time complexity to sort elements of binary search tree is
- The lower bound on the number of comparisons performed by comparison-based sorting algorithm is
- Which of the following algorithm(s) can be used to sort n integers in range [1…..n3] in O(n) time?
- Which of the following algorithm design technique is used in the quick sort algorithm?
- Merge sort uses
- Disks are divided into logical units called _______.
- The extension of executable file types is _______.
- The extension of object file types is ________.
- What is Unicode?
- Which of the following device cannot be shared in network?
- All files involved in updating are sorted based on ________.
- In updating a sequential file New master file becomes __________.
- To make the updating process __________, all files are sorted on the same key.
- Disks can store ________ of characters.
- Secondary key fields should follow ______ fields in a record.
- External sorting algorithms makes _______ accesses to a storage device.
- Sorting is used to eliminate _________ in the collection of data
- The cost of accessing data is significantly ______ either bookkeeping or comparison costs.
- During 2nd pass of two-way merge sort in each pass the number of strings is reduced by ________ of the number.
- During 2nd pass of two-way merge sort in each pass the sizes of the strings are ______
- Cascade merge allow _______ way merge with only t tape units.
- _______ sort is the most efficient in terms of speed and utilisation of resources.
- Polyphase merge in each pass performs only ____ way merge.
- ________ merge sort minimizes disk I/O cost.
- Which of the following is an external sorting?
- A sequence set is a set of _____.
- A blocked file takes up ______ space than an unblocked file because of internal fragmentation.
- Sequential representation of binary tree uses _________
- A binary tree whose every node has either zero or two children is called ______
- The depth of complete binary tree is given by ______
- Number of records that can be stored in a B+ tree is __________.
- The maximum number of keys in a record is called the ______ of the B+ tree.
- The minimum number of keys per record is _____ of the maximum number of keys.
- Linked representation of binary tree needs _____ parallel arrays.
- In Binary trees nodes with no successor are called _______
- B+ tree contains __________
- Order is the _____ number of keys/pointers in a non-leaf node.
- ________ is the number pointers out of the node.
- B+ tree consist of a ______.
- A tree in which the value in every node is more than node-values in its left subtree and less than node-values in its right subtree.
- This Algorithm scans the lists by swapping the entries whenever pair of adjacent keys are out of desired order.
- The main characteristics of a good algorithm are ________
- Which of these is the time complexity involved in building a heap of n elements and cannot be expressed in lower order terms?
- For an algorithm the complexity of the average case is
- ________ sorting is much less efficient on large lists.
- ________ is a good choice for sorting lists of a few thousand items or less.
- The disadvantage of insertion sort is _________.
- The advantages of insertion sorting are ________.
- A tree is also known as _______ sort.
- An optimal quick sort is ________ ?
- If the input is random, then we can choose the key in position _______ as pivot.
- The main idea is to find the _____ position for the pivot element P.
- Best case is _____ same as merge sort.
- Worst case is ________.
- Quick sort is used to ______.
- First step in quick sort is _______.
- The _________ are stored in the original data array.
- Partitioning loops through, _______ elements below/above pivot.
- Partition splits array in two sub-arrays of size ______.
- Prims algorithm start at a source vertex and grow a ______.
- _______ finds a minimum cost spanning tree by selecting edges from the graph.
- In prims algorithm process is repeated until a ____ is formed.
- In _______ operations method incident edges is called once for each vertex.
- From the following choose the one which belongs to the algorithm paradigm other than to which others from the following belongs to.
- A “safe edge” is an edge of ____ which does not create a cycle.
- Kruskal’s algorithm also finds the minimum cost spanning tree of a _____ by adding edges.
- We need a data structure that maintains a _______.
- Is kruskal algorithm is whether than prim’s algorithm?
- What algorithmic technique does the kruskal algorithm follows?