Basic CS-Data Structures [TCS Placement]: Sample Questions 16 - 17 of 28

Get unlimited access to the best preparation resource for competitive exams : get questions, notes, tests, video lectures and more- for all subjects of your exam.

Question 16

Describe in Detail Essay▾

What is the data structures used to perform recursion?

Edit

Explanation

  • The data structure used for recursion is stack.
  • it՚s LOFO (Last in First Out) property that helps the stack “unfold” on return- This helps it know the data to be returned when function has to return.
  • System stack is used for storing the return addresses of the function calls.
  • Recursion makes use of system stack for storing the return addresses of the function calls.
  • Every recursive function has its equivalent iterative (non-recursive) function- such equivalent iterative procedures need to use explicit stack.
Given the Image is Define the Stack Data Structure

Question 17

Describe in Detail Essay▾

Classify the hashing functions based on the various methods by which the key value is found.

Edit

Explanation

There are 7 hashing functions based on how key value is found.

  • Direct Method
    • Key is the address without algorithmic manipulation
    • Data structure contains element for possible key
    • Example problems
      • To analyze total monthly sales by days of month
      • For each sale we need date and amount of sale
      • To calculate sales record for month, we need day of month as key for array and add sales amount to accumulator
      • Daily Sales [Sale Day] = Daily Sales [Sale Day] + Sale Amount
  • Subtraction Method
    • Direct and subtraction hash functions guarantee search effort without no collisions
    • In one to one hashing method only one key hashes to each address
    • Example
      • Company has 100 employees, employee number starts from 1001 to 1100
      • Hashing function subtracts 1000 from key to determine address
  • Modulo-Division Method
    • Divides the key by array size and use remainder for address
    • Algorithm works with any list size, but a prime number produces fewer collisions
    • Address = key MODULO list Size
  • Digit-Extraction Method
    • Digits are extracted from key and used as address
    • Example:
      • Six-digit employee number is used to hash three digit address (000 - 999)
      • For example, select first, third, and fourth digits as key
  • 379452 - 394
  • 121267 - 112
  • 378845 - 388
  • 160252 - 102
  • 045128 - 051
  • Mid-square Method
    • Key is squared and the address is selected from the middle of the squared number
    • Example
      • Given a key of 9452, midsquare address calculation is shown using four digit address (0000 - 9999)
      • 94522 = 89340304: address is 3403
    • Select first three digits and then use midsquare method
      • 379452: 3792 = 143641 - 364
      • 121267: 1212 = 014641 - 464
      • 378845: 3782 = 142884 - 288
      • 160252: 1602 = 025600 - 560
      • 045128: 0452 = 002025 - 202
  • Folding Method
    • Two folding methods
      • Fold shift
      • Fold boundary
    • Fold shift key value is divided into parts whose size matches size of required address
    • Left and right parts are shifted and added with middle part
    • In fold boundary, left and right numbers are folded on a fixed boundary between them and the center number
  • Pseudo-random Method
    • Key is used as seed in pseudorandom number generator and the random number is scaled into possible address range using modulo-division.
    • A common random number generator is y = ax + c
    • Example
      • Assume a = 17, c = 7, x = 121267, Prime number = 307
      • y = ( (17 ⚹ 121267) + 7) modulo 307
      • y = (2061539 + 7) modulo 307
      • y = 2061546 modulo 307
      • y = 41