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
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
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:

    : 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

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: