1answer.
Ask question
Login Signup
Ask question
All categories
  • English
  • Mathematics
  • Social Studies
  • Business
  • History
  • Health
  • Geography
  • Biology
  • Physics
  • Chemistry
  • Computers and Technology
  • Arts
  • World Languages
  • Spanish
  • French
  • German
  • Advanced Placement (AP)
  • SAT
  • Medicine
  • Law
  • Engineering
baherus [9]
3 years ago
12

Show the array that results from the following sequence of key insertions using a hashing system under the given conditions: 5,

205, 406, 5205, 8205, 307 (you can simply list the non-null array slots and their contents)
a. array size is 100, linear probing used.
b. array size is 100, quadratic probing used.
Computers and Technology
1 answer:
sergejj [24]3 years ago
3 0

Answer:

a) Linear probing is one of the hashing technique in which we insert values into the hash table indexes based on hash value.

Hash value of key can be calculated as :

H(key) = key % size ;

Here H(key) is the index where the value of key is stored in hash table.

----------

Given,

Keys to be inserted are : 5 , 205, 406,5205, 8205 ,307

and size of the array : 100.

First key to be inserted is : 5

So, H(5) = 5%100 = 5,

So, key 5 is inserted at 5th index of hash table.

-----

Next key to inserted is : 205

So, H(205) = 205%100 = 5 (here collision happens)

Recompute hash value as follows:

H(key) =(key+i) % size here i= 1,2,3...

So, H(205) =( 205+1)%100 = 206%100 = 6

So, key 205 is inserted in the 6th index of the hash table.

----------

Next Key to be inserted : 406

H(406) = 406%100 = 6(collision occurs)

H(406) =(406+1) %100 = 407%100 = 7

So, the value 406 is inserted in 7the index of the hash table.

-----------------

Next key : 5205

H(5205) = 5205%100 = 5(collision)

So, H(5205) = (5205+1)%100 = 6( again collision)

So, H(5205) = 5205+2)%100 = 7(again collision)

So, H(5205) = (5205+3)%100 = 8 ( no collision)

So, value 5205 is inserted at 8th index of the hash table.

-------------

Similarly 8205 is inserted at 9th index of the hash table because , we have collisions from 5th to 8th indexes.

-------------

Next key value is : 307

H(307) = 307%100 = 7(collision)

So, (307+3)%100 = 310%100 = 10(no collision)  

So, 307 is inserted at 10th index of the hash table.

So, hash table will look like this:

Key       index

5         5

205         6

406         7

5205 8

8205 9

307         10

b) Quadratic probing:

Quadratic probing is also similar to linear probing but the difference is in collision resolution. In linear probing in case of collision we use : H(key) = (key+i)%size but here we use H(key) =( key+i^2)%size.

Applying Quadratic probing on above keys:.

First key to be inserted : 5.

5 will go to index 5 of the hash table.

-------

Next key = 205 .

H(205) = 205%100 = 5(collision)

So. H(key)= (205+1^2)%100 = 6(no collision)

So, 205 is inserted into 6th index of the hash table.

--------

Next key to be inserted 406:

So, 406 %100 = 6 (collision)

(406+1^2)%100 = 7(no collision)

So, 406 is moved to 7th index of the hash table.

----------

Next key is : 5205

So, 5205%100 = 5 (collision)

So, (5205+1^2)%100 = 6 ( again collision)

So, (5205+2^2)%100 = 9 ( no collision)

So, 5205 inserted into 9th index of hash table.

-----------

Next key is 8205:

Here collision happens at 5the , 6the , 9th indexes,

So H(8205) = (8205+4^2)%100 = 8221%100 = 21

So, value 8205 is inserted in 21st index of hash table.

--------

Next value is 307.

Here there is collision at 7the index.

So, H(307) = (307+1^2)%100 = 308%100= 8.

So, 307 is inserted at 8the index of the hash table.

Key           Index

5                  5

205                  6

406                  7

5205                9

8205               21

307                   8

You might be interested in
Light travels at 3 × 108 meters per second. A light-year is the distance a light beam travels in one year.Write a PYTHON program
Volgvan

Answer: This is a python code

def lightyear():

   rate=3*100000000   //speed of light

   seconds=365*24*60*60   //number of seconds in 1 year

   return str((rate*seconds)/1000)+" km"    //distance=speed x time

print(lightyear()) //will print value of light hear in kilometers

OUTPUT :

9460800000000.0 km

Explanation:

In the above code, there is a variable rate, which stores the speed of light, i.e. distance traveled by light in 1 second which is in meters. Another variable is seconds, which store the number of seconds in 1 year, which is no of days in 1 year multiplied by the number of hours in a day multiplied by the number of minutes in an hour multiplied by the number of seconds in a minute. Finally, distance is speed multiplied by time, so distance is printed in kilometers and to convert distance in kilometers it is divided by 1000.

4 0
3 years ago
Consider a hypothetical microprocessor generating 16-bit addresses with 16-bit data accesses (i.e. each access retrieves 16 bits
Vlad [161]
A. number of addresses is 65536
b. memory capacity is 128 kbytes or 131072 bytes
c. The last memory address is FFFF which is 65535

8 0
3 years ago
In this scenario, two friends are eating dinner at a restaurant. The bill comes in the amount of 47.28 dollars. The friends deci
pickupchik [31]

Answer:

The java program for the given scenario is as follows.

import java.util.*;

import java.lang.*;

public class Main

{

   //variables for bill and tip declared and initialized

   static double bill=47.28, tip=0.15;

   //variables for total bill and share declared

   static double total, share1;

public static void main(String[] args) {

    double total_tip= (bill*tip);

    //total bill computed

    total = bill + total_tip;

    //share of each friend computed

    share1 = total/2;

    System.out.printf("Each person needs to pay: $%.2f", share1);  

}

}

Explanation:

1. The variables to hold the bill and tip percent are declared as double and initialized with the given values.

static double bill=47.28, tip=0.15;

2. The variables to hold the values of total bill amount and total tip are declared as double.

3. All the variables are declared outside main() and at class level, hence declared as static.

4. Inside main(), the values of total tip, total bill and share of each person are computed as shown.

double total_tip= (bill*tip);

total = bill + total_tip;

share1 = total/2;

5. The share of each person is displayed to the user. The value is displayed with only two decimal places which is assured by %.2f format modifier. The number of decimal places required can be changed by changing the number, i.e. 2. This format is used with printf() and not with println() method.

System.out.printf("Each person needs to pay: $%.2f", share1);  

6. The program is not designed to take any user input.

7. The program can be tested for any value of bill and tip percent.

8. The whole code is put inside a class since java is a purely object-oriented language.

9. Only variables can be declared outside method, the logic is put inside a method in a purely object-oriented language.

10. As shown, the logic is put inside the main() method and only variables are declared outside the method.

11. Due to simplicity, the program consists of only one class.

12. The output is attached.

5 0
3 years ago
Read 2 more answers
The _____ is an information and communication-based electronic exchange environment mostly occupied by sophisticated computer an
Airida [17]

Answer:

The correct answer to the following question will be "Marketspace".

Explanation:

  • A relatively new marketing term which seems to be a simulated market place. It's an area for the electronic exchange of ideas and information in which external boundary restrictions are removed, termed as Marketspace.
  • The electronic trading world focused on connectivity often filled by advanced computer and telecommunications technology and digitized deals.

Therefore, Marketspace is the right answer.

5 0
3 years ago
A sample member of the list data is a1 = ['male', True] where the second item is True if the person is on the phone.
Ira Lisetskai [31]
Answer:

0

Explanation:
In the lists, indexation starts from 0, because of that in if statement we compare item[0] which is 'male' and 'male', and then males is itterated within for loop.
8 0
3 years ago
Read 2 more answers
Other questions:
  • When did Kodak introduce film photography to the commercial market?
    10·2 answers
  • If you were given a 3D microscope to use for photography, which object(s) would you most want to photograph?
    10·2 answers
  • When should an individual consider entering parenthood?
    5·1 answer
  • When the increment or decrement operator is placed before the operand (or to the operand's left), the operator is being used in
    6·1 answer
  • i got a set of headphones and when i plug them into my speakers the right side only works how do i fix the left side of them
    12·1 answer
  • Using a personal computer to produce high quality printed documents.
    10·1 answer
  • Enter the answer.
    11·2 answers
  • If you want to present slides to fellow students your coworkers which productivity software should you use to create them
    15·2 answers
  • Rolulzoss<br>A. State three positive uses of computers in the government sector​
    10·1 answer
  • which scheduling algorithm allocate the CPU firt to the process that request the CPU first, (a) first come first serve,(b) short
    9·1 answer
Add answer
Login
Not registered? Fast signup
Signup
Login Signup
Ask question!