Basic CS [3i Infotech Placement]: Sample Questions 167 - 168 of 243

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

Question 167

Edit

Describe in Detail

Essay▾

What is object file? How can you access object file?

Explanation

Understanding of Object File
  • Object file is binary representation of source file.
  • Object and executable files have ELF format.
  • It is a collection of various sections segregating type of data in:
    • Text section
    • Data section
    • Stack
    • Heap.
  • These file are produced as the output of the compiler.
  • They consist of function definitions in binary executable by themselves.
  • Object files end in “. o” by convention, although on some operating systems, they often end in “. obj” .

Question 168

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: