Programming Question

Question 1 (25 pts):Suppose there are eight students with IDs 106500360, 120987540, 132490004, 134052199, 153450901,
175342111, 187800977, and 198966567. Suppose hash table, HT, is of the size 13, indexed 0,1,2, . . ., 12.
Show how these students’ IDs, in the order given, are inserted in HT using the hashing function h(k) =
k % 13, where k is a student ID.
IDs
106500360
120987540
132490004
134052199
153450901
175342111
187800977
198966567
HT index
Question 2 (25 pts):
Suppose there are eight students with IDs 106500361, 120987540, 132490004, 134052199,
153450900, 175342111, 187800977, and 198966574. Suppose hash table, HT, is of the size 19,
indexed 0, 1, 2, . . ., 18. Show how these students’ IDs, in the order given, are inserted in HT using
the hashing function h(k)= k % 19. Use linear probing to resolve collision.
IDs
106500361
120987540
132490004
134052199
153450900
175342111
187800977
198966574
HT index
Question 3 (25 pts):
Suppose there are eight students with IDs 103577331, 120987544, 139722100, 144885711,
153450906, 165342113, 177800977, and 198966574. Suppose hash table, HT, is of the size 19,
indexed 0, 1, 2, . . ., 18. Show how these students’ IDs, in the order given, are inserted in HT using
the hashing function h(k)= k % 19. Use quadratic probing to resolve collision.
IDs
103577331
120987544
139722100
144885711
153450906
165342113
177800977
198966574
HT index
Question 4:
By using the hashT class provided (hashT.h ), which uses quadratic probing to resolve collision, create a
hash table to keep track of student IDs and names.
Write a C++ code to;
(a) Ask the user to enter IDs and names of five students to be added to the hash table.
(b) Calculate the hash index from the student ID using the folding method.
(c) Add the information to the hash table.
(d) Ask the user to enter the student information to be deleted from the hash table.
(e) Remove the information from the hash table.
(f) Print the information.
Submit the cpp file, and copy and paste the screenshot of the output here.
Sample output:
Page
of 3
ZOOM
#ifndef HASH_T_H
#define HASH_T_H
//****************************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement a hash table as
// an ADT. It uses quadratic probing to resolve collisions.
//****************************************************************
#include
template
class hashT
{
public:
void insert(int hashIndex, const elemType& rec);
//Function to insert an item in the hash table. The first
//parameter specifies the initial hash index of the item to
//be inserted. The item to be inserted is specified by the
//parameter rec.
//Postcondition: If an empty position is found in the hash
// table, rec is inserted and the length is incremented by
// one; otherwise, an appropriate error message is
// displayed.
void search(int& hashIndex, const elemType& rec, bool& found)
const;
//Function to determine whether the item specified by the
//parameter rec is in the hash table. The parameter hashIndex
//specifies the initial hash index of rec.
//Postcondition: If rec is found, found is set to true and
// hashIndex specifies the position where rec is found;
// otherwise, found is set to false.
bool isItemAtEqual(int hashIndex, const elemType& rec) const;
//Function to determine whether the item specified by the
//parameter rec is the same as the item in the hash table
//at position hashIndex.
//Postcondition: Returns true if HTable[hashIndex] == rec;
// otherwise, returns false.
void retrieve(int hashIndex, elemType& rec) const;
//Function to retrieve the item at position hashIndex.
//Postcondition: If the table has an item at position
// hashIndex, it is copied into rec.
void remove(int hashIndex, const elemType& rec);
//Function to remove an item from the hash table.
//Postcondition: Given the initial hashIndex, if rec is found
// in the table it is removed; otherwise, an appropriate
// error message is displayed.
void print() const;
//Function to output the data.
hashT(int size = 101);
//constructor
//Postcondition: Create the arrays HTable and indexStatusList;
// initialize the array indexStatusList to 0; length = 0;
// HTSize = size; and the default array size is 101.
~hashT();
//destructor
//Postcondition: Array HTable and indexStatusList are deleted.
private:
elemType* HTable; //pointer to the hash table
int* indexStatusList; //pointer to the array indicating the
//status of a position in the hash table
int length; //number of items in the hash table
int HTSize; //maximum size of the hash table
};
template
void hashT::insert(int hashIndex, const elemType& rec)
{
int pCount;
int inc;
pCount = 0;
inc = 1;
while (indexStatusList[hashIndex] == 1
&& HTable[hashIndex] != rec && pCount < HTSize / 2) { pCount++; hashIndex = (hashIndex + inc) % HTSize; inc = inc + 2; } if (indexStatusList[hashIndex] != 1) { HTable[hashIndex] = rec; indexStatusList[hashIndex] = 1; length++; } else if (HTable[hashIndex] == rec) std::cerr