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

Describe in Detail


Draw a binary tree for the expression:

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


  • 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
Arithmetic Expression
  • BET is used in most compilers
  • No parenthesis is needed- tree structure conveys precedence.
  • BET can be evaluated by using post order traversal.
Binary Expression Tree

Question 38

Data Structures

Describe in Detail


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


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.


    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.


    • 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.


    : address is 3403

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


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: