Data structure Quick reference - 7

32. What is binary search?
In computer science, binary search, also known as half-interval search, logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array. Binary search compares the target value to the middle element of the array.

33. What is a Memory pool?
Memory pools, also called fixed-size blocks allocation, is the use of pools for memory management that allows dynamic memory allocation comparable to malloc or C++'s operator new. As those implementations suffer from fragmentation because of variable block sizes, it is not recommendable to use them in a real time system due to performance. A more efficient solution is preallocating a number of memory blocks with the same size called the memory pool. The application can allocate, access, and free blocks represented by handles at run time.

34. What are the drawback of sequential access?
The biggest drawback of sequential access is that it's very slow. You will see sequential access mostly in backup tapes, or the big, clunky magnetic tapes that are used to backup large amounts of data. For this purpose, the method is acceptable because the speed of access isn't important.Fixed amount of storage remains allocated to the data structure even if it contains less data.

35. What is a Circular linked list?
Circular linked list is a sequence of elements in which every element has link to its next element in the sequence and the last element has a link to the first element in the sequence. That means circular linked list is similar to the single linked list except that the last node points to the first node in the list.

36. What is Tree traversal algorithm ?
Tree traversal is the process of visiting each node in a tree, such as a binary tree or binary search tree, exactly once. There are several effective traversal algorithms which we will cover below.

37. What are the tasks performed during preorder traversal ?
A pre-order traversal on a tree performs the following steps starting from the root:

  • Return the root node value. 
  • Traverse the left subtree by recursively calling the pre-order function. 
  • Traverse the right subtree by recursively calling the pre-order function.

38. What are the different binary tree traversal techniques ?
Preorder traversal
Inorder traversal
Postorder traversal
1 2 3 4 5 6 7 8 9 10