Data Structure FAQ

Data Structure FAQ © 4futureengineers.com

1. A useful tool for specifying the logical properties of a data type is a Ans: Abstract data type 2. Which one of the following is a LIFO list (i)stack (ii)queue (iii)linkadlist (iv)circular list Ans : (i)stack 3. Which one of the following is a fifo list (i)stack (ii)queue (iii)linked list (iv)Priority queue Ans : (ii)queue 4. For implementation of recursion tree we use Ans : stack 5. The primitive operation applied to the queue is/are Ans : insert & remove & empty 6. The items may be inserted at one end of queue is called Ans : front 7. In Queue the insert operation could be implemented by the statements as Ans : q.items[++q.rear] = x; 8. In the addition of Long Positive Integers Using Circular Lists we use the Ans : Circular List or Double Linked List 9. A finite set of elements that is either empty or is partitioned into three disjoined subsets is called Ans : binary tree 10. In binary tree the maximum level of any leaf in the tree is said to be ______ of the binary tree Ans : depth 11. We perform the folowing operation to traverse a nonempty binary tree in a order 1. Traverse the left subtree in that so called order 2. Visit the root. 3. Traverse the right subtree in that so called order Ans. inorder 12. If the records that it's sorting are in main memory then the sort is called as Ans : internal 13. Given two function f(n) & g(n),we say that f(n) is on the order of g(n) if there exist positive integers a & b such that f(n)<=ag(n) for all n=>b. is called f(n) Ans : O(g(n)) 14. The efficiency of the buble sort is Ans : O(log n) 15. An array of elements is sorted by choosing a pivot element & by partition.The sorting process is called Ans : Partition Exchange Sort or Quicksort 16. The efficiency of the quicksort is Ans : O(nlogn) 17. The efficiency of the Heapsort is Ans : O(nlogn) 18. It is possible to define an heap as an complete binary tree such that the content of each node is greater than or equal to the content of its father Ans : ascending heap or min heap 19. A binary tree in which the heigths of the two subtrees of every node never differ by more than 1 is called Ans : AVL tree 20. A balanced order-n multiway search tree in which each nonroot node contains at least (n-1)/2 keys is called a B-tree of order Ans : n 21. A function that transform a key into a table index is called Ans : hash function 22. In dealing with a hash clash,a technique is used that builds a linked list of all items whose keys hash to the same values is called Ans : chaining 23. The phenomenon, where 2 keys that hash into different values compete with each other in successive rehashes, is called Ans : primary clustering 24. Given a set of keys K={k1,k2,.....,kn}, a hash function h is such that h(ki)!=h(kj) for all distinct i and j called Ans : perfect hash function 25. The number of the arcs that have n as the head is called Ans : indegree of the node 26. The nodes of the graph are represented by a linked list of Ans : header node 27. The efficiency of Dijkstra's algorithm is Ans : O((e+n)logn) 28. In undirected graph in which every node is reachable from each other is termed as Ans : none of the above 29. A traversal method vists all the successors of a visited node before visited any successors of any of those successors is called Ans : breadth first search 30. An acyclic graph in which every node has one or no predecessors may be defined as Ans : forest 31. The space requirements for the quicksort depend on the Ans : no. of nested recursive calls & size of the stack 32. The efficiency of Straight Selection Sort is Ans : O(n2) 33. The average sorting time for binary tree sort is Ans : O(nlogn) 34. A matrix i.e, a two dimentional array which has many zeroes as its element is called Ans: sparse matrix 35. To denote the empty stack the top is set to Ans : -1 36. The expression AB/C-DE+AC- is called Ans : postfix 37. The expressino coef \| exp \|link can be represented as Ans : polynode 38. The computing time of the recursive merge sort is Ans : O(nlogn) 39. A,whiich is a finite sequence of n>0 or n=0 elements, a0,a1,a2,......a(n-1),is either a atom or list , is called Ans : generalized list 40. If A={a0,a1,a2,.....) is a generalized list ,then a0 is called Ans : head 41. Which of the following is a recursive list (i)D=(); (ii)A=(a,(b,c)); (iii)B=(A,A,()); (iv)C=(a,C); Ans : (iv)C=(a,C); 42. If T is a k-ary tree(i.e, a tree of degree k) with n nodes, each having a fixed size , then n(k-1)+1 of the nk child fields are Ans : 0 43. The maximum no. of nodes on level i of a binary tree is i=>1 Ans : (22.....to i-1) 44. The maximum number of nodes ina binary tree of depth k is k=>1 Ans : (222.....to k)-1 45. The height of a complete binary tree with n nodes is Ans : log(n+1) 46. If a complete binary tree with n nodes is represented sequentially, then for any nodes with index i,1<= i <=n,we have LeftChild(i) is at if it is < or = n Ans : 2i 47. A complete binary tree in which the key value in each node is no smaller than the key values in its children Ans : max heap 48. To represent a graph, we will write ,where V is the set of vertices,E is a set of edges Ans : G=(V,E) 49. The number of edges for which v is the head, is called ______ of the vertex v Ans : indegree 50. A two dimentional nxn array, say A, with the property that A[i][j] = 1 iff the edge (i,j) ( for a directed graph) is in E(G) Ans : adjacency matrix