TCS Papers: Sample Questions 491 - 492 of 502

Examrace Placement Series prepares you for the toughest placement exams to top companies.

Question number: 491

» Basic CS » Data Structures

Essay Question▾

Describe in Detail

In RDBMS, what is the efficient data structure used in the internal storage representation?


B + tree.

  • In B + tree, all the data is stored only in leaf nodes, making searching easier.

  • The B + Tree is called a balanced tree because every path from the root node to a leaf node is the same length, thus requiring the same number of nodes to be read from the disc.

  • The B + Tree consists of two types of nodes

    • Internal nodes: Internal nodes point to other nodes in the tree

    • Leaf nodes: Point to data in the database using data pointers. Leaf nodes also contain an additional pointer, called the sibling pointer, which is used to improve the efficiency of certain types of search.

  • All the nodes in a B + Tree must be at least half full except the root node which may contain a minimum of two entries.

  • Algorithms inserting and deleting data from a B + Tree guarantee each node will be at least half full.

  • Searching for a value in the B + Tree starts from root and moves downwards until it reaches a leaf node.

  • Both internal and leaf nodes contain key values that are used to guide the search for entries in the index. This is shown in the diagram

Image of the B+ tree

Image of the B + Tree

Given the image is define the B + tree structure

Question number: 492

» Basic CS » Data Structures

Essay Question▾

Describe in Detail

If you are using C language to implement the heterogeneous linked list, what pointer type will you use?


  • A linked list is known as heterogeneous when nodes of linked list can contain different type of information.

  • A void pointer can point to any type of data either in-built data type or user defined structure.

  • We can do this by creating an array or linked list of elements that encode both the data and the type of data.

  • We could use a struct that includes a type indicator and a union of the various types that we want to handle, and the create an array or linked list of that struct:

typedef struct {int type_indi; union {float f; int i; double d; void * p; char c; } } item;

item array [10];

  • For a linked list instead of an array, we would also need to add a item * next pointer.