# Basic CS-Data Structures [3i Infotech Placement]: Sample Questions 37 - 38 of 52

Glide to success with Doorsteptutor material for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

## Question 37

Data Structures
Edit

### Describe in Detail

Essay▾

Draw a binary tree for the expression:

A ⚹ B- (C + D) + (P/Q)

### Explanation

• The binary tree for arithmetic expression (Binary Expression Tree or BET) represents the expression in the infix notation.
• Two types of expressions that a binary expression tree represents are:
• Algebraic
• Boolean.
• Trees can represent both unary and binary operators.
• Example Arithmetic Expression:
• Tree for the above expression is drawn as:
• Leaves = operands (constants/variables)
• Non-leaf nodes = operators
• BET is used in most compilers
• No parenthesis is needed- tree structure conveys precedence.
• BET can be evaluated by using post order traversal.

## Question 38

Data Structures
Edit

### Describe in Detail

Essay▾

Classify the Hashing Functions based on the various methods by which the key value is found.

### Explanation

Direct method

• The key is the address without any algorithmic manipulation.
• Limited, but it can very powerful because there are no synonyms and therefore no collision.

Subtraction method:

• Key were sequential, but do not start from one- use subtraction method.

Example:

Keys from 1000 to 1100

Same problems & issues as the direct method.

Modulo-Division method

• Also known as division remainder method.
• Works with any list size, a list size of prime number produces fewer collisions that other list sizes.
• Formula to calculate address is
• Address = key MODULO listsize + 1
• Example:

Given data

Keys are: 137456 214562 140145

137456 % 19 + 1 = 11

214562 % 19 + 1 = 15

140145 % 19 + 1 = 2

Digit- Exchange method

• Selected digits are extracted from the key and used as the address.

Example:

• Six-digit employee number to hash with a three digit address (000 - 999) .
• Select the first, third and forth digits and use them as the address.
• The keys are:

379452 - 394

121267 - 112

378845 - 388

Mid-square method

• The key is squared and the address is selected from the middle of the square number.
• Limitation is the size of the key.

Example:

Folding method

• Two methods are used:
• Fold shift:
• The key value is divided into parts whose size matches the size of the required address.
• Then the left and right parts are shifted and added with the middle part.
• Fold boundary:
• The left and right numbers are folded on a fixed boundary between them.
• The two outside values are thus reversed.

Pseudo-random method.

• Key is used as the seed number generator and the resulting random number is scaled into the possible address range using modulo division
• A common random number generator is below:

y = ax + c

Example:

We use 15 and 7 for factors “a” and “c” , respectively

y = (ax + c) modulo list size

Modulo 307

, next addresses are 29,92 and so on.

Developed by: