Data Structure FAQ

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 
(iv)circular list

Ans : (i)stack 

3. Which one of the following is a fifo list 
(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)<=a*g(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
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 : (2*2* i-1) 

44. The maximum number of nodes ina binary tree of depth k is k=>1 
Ans : (2*2*2* 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