# OS Data Structures Interview Preparation Guide

OS Data Structures frequently Asked Questions by expert members with experience in OS Data Structures. These interview questions and answers on OS Data Structures will help you strengthen your technical skills, prepare for the interviews and quickly revise the concepts. So get preparation for the OS Data Structures job interview

## 14 OS Data Structures Questions and Answers:

### 1 :: What are input function and output function in c language?

printf,scanf,getch,getchar,getche,kbhit etc

### 2 :: Tell me applications of linked lists and mostly used linked list?

Used mainly to represent elements in a dynamic environment where it is added on an ad-hoc basis.

Especially in the cases where the total number of elements in the list cannot be pre-decided, linked lists are used. This does not lead to space insufficiency or space wastage as in case of arrays.

For eg. The no. of terms in a order-n polynomial varies greatly, using an array to store the co-efficients is an inefficient methods. If the array size is declared 100, a quadratic equation will use just 3 index and the rest 99 will be wasted. While for a sine or cosine series (from x to infinity) an overflow error might occur..!

Especially in the cases where the total number of elements in the list cannot be pre-decided, linked lists are used. This does not lead to space insufficiency or space wastage as in case of arrays.

For eg. The no. of terms in a order-n polynomial varies greatly, using an array to store the co-efficients is an inefficient methods. If the array size is declared 100, a quadratic equation will use just 3 index and the rest 99 will be wasted. While for a sine or cosine series (from x to infinity) an overflow error might occur..!

### 3 :: Explain simple algorithm for bubble sort?

void bubble(int x[],int n)

{

int hold,j,pass;

int switched=true;

for(pass=0;pass<n-1&&switched=true;pass++){

switched=false;

for(j=0;j<n-pass-1;j++)

if(x[j]>x[j+1]){

switched=true;

hold=x[j];

x[j]=x[j+1];

x[j+1]=hold;

}

}

}

{

int hold,j,pass;

int switched=true;

for(pass=0;pass<n-1&&switched=true;pass++){

switched=false;

for(j=0;j<n-pass-1;j++)

if(x[j]>x[j+1]){

switched=true;

hold=x[j];

x[j]=x[j+1];

x[j+1]=hold;

}

}

}

### 4 :: Explain applications of stacks and their uses?

Keeping track of nested invocation calls in a procedural

programming language, such as C/C++.

Each function call results in a new entry being placed into

the program run-time stack. This new

entry contains memory space for local variables (which can

grow dynamically) and for a return

pointer to the instruction in the function that invoked the

current function (caller/callee). As

functions terminate, their stack entry is "popped out," with

the return values written to the proper

location in the caller.

Since nested procedural/ function invocation levels are

entered and exited in LIFO order, a stack

is the most appropriate data structure to handle this

functionality.

Evaluating arithmetic expressions.

Stacks can be used to parse arithmetic expressions and

evaluate them efficiently, as we shall

see as part of this assignment.

To eliminate the need for direct implementation of recursion.

As recursive function calls require a lot of overhead, it is

often the case that recursive algorithms

are "unrolled" into non-recursive ones. Since recursive

calls are entered/exited in LIFO order the

use of stacks to mimic recursion is a natural choice.

programming language, such as C/C++.

Each function call results in a new entry being placed into

the program run-time stack. This new

entry contains memory space for local variables (which can

grow dynamically) and for a return

pointer to the instruction in the function that invoked the

current function (caller/callee). As

functions terminate, their stack entry is "popped out," with

the return values written to the proper

location in the caller.

Since nested procedural/ function invocation levels are

entered and exited in LIFO order, a stack

is the most appropriate data structure to handle this

functionality.

Evaluating arithmetic expressions.

Stacks can be used to parse arithmetic expressions and

evaluate them efficiently, as we shall

see as part of this assignment.

To eliminate the need for direct implementation of recursion.

As recursive function calls require a lot of overhead, it is

often the case that recursive algorithms

are "unrolled" into non-recursive ones. Since recursive

calls are entered/exited in LIFO order the

use of stacks to mimic recursion is a natural choice.

### 5 :: Tell me why do tree always takes o(log n) time?

Tree always takes o(log n) time because tree has height is

(log n).

(log n).

### 6 :: Do you know how to find the number of possible tree in the given tree?

number of possible tree = (2 power n) - n.

for example:

A tree contain three node.

so n=3.

possible tree = 8 - 3 = 5.

for example:

A tree contain three node.

so n=3.

possible tree = 8 - 3 = 5.

### 7 :: Tell me how to search an element in sorted linked list with time complexity is O(log n)?

we can use the binary search algorithm for this problem because this searching algorithm has O(log n) performance in both worse and average case.

### 8 :: What is the different between B-tree and B+ tree?

It's all about branching factor. Because of the way B+-Trees store records (called "satellite information") at the leaf level of the tree, they maximize the branching factor of the internal nodes. High branching factor allows for a tree of lower height. Lower tree height allows for less disk I/O. Less disk I/O theoretically means better performance

In a B- tree you can store both keys and data in the internal/leaf nodes. But in a B+ tree you have to store the data in the leaf nodes only.

A B+ - Tree is in the form of a balanced tree in which every path from the root of the tree to a leaf of the tree is the same length.

Each nonleaf node in the tree has between [n/2] and n children, where n is fixed.

B+ - Trees are good for searches, but cause some overhead issues in wasted space.

In a B- tree you can store both keys and data in the internal/leaf nodes. But in a B+ tree you have to store the data in the leaf nodes only.

A B+ - Tree is in the form of a balanced tree in which every path from the root of the tree to a leaf of the tree is the same length.

Each nonleaf node in the tree has between [n/2] and n children, where n is fixed.

B+ - Trees are good for searches, but cause some overhead issues in wasted space.

### 9 :: What is R-B tree?

A red black tree is a binary tree where

1. every node has color.

2. root node is always black

3. the child of a black node is either black or red

4. both the child nodes of every red node must be black

5. all the leaves must be black

1. every node has color.

2. root node is always black

3. the child of a black node is either black or red

4. both the child nodes of every red node must be black

5. all the leaves must be black

### 10 :: Why enum can not be used directly with printf function?

enum is not an basic data type like int,float and all it is

a user defined data type, and printf function works only

with basic data type, we 've overload printf function to

make it work for user defined data types :)

a user defined data type, and printf function works only

with basic data type, we 've overload printf function to

make it work for user defined data types :)