Subject: Data Structures and Algorithms, C++ programming
please help with this take-home question. Need full marks please
double-check answers cannot take any chances NEED THE FULL ANSWER
AND CORRECT ANSWER, also within word limit with 10% lenience on the
word limit. will give an upvote if correct. Need
answer within 6 hours.
Subject Data Structures And Algorithms C Programming Please Help With This Take Home Question Need Full Marks Pleas 1 (95.98 KiB) Viewed 65 times
Question 19 (3 Marks) Suppose we wish to implement a set that can facilitate the fast lookup of ints. Suppose the number of ints to be stored is no more than n², and the ints do not equal each other. We have decided to use a two-dimensional array int A[n] [n] as the underlying data structure to store the ints. Our current mechanism is based on a simple division function h (k)=k%n and linear probing. Suppose we are to insert an int value (say x) to the set. We first calculate xon and then attempt to store x to the array cell A [x%n] [x%n]. If A[x\n] [x%n] is occupied, we check A[ (x%n+1) %n] [ (x%n+1) %n], A[ (x%n+2) %n] [ (x²n+2) %n], A[ (x%n+n-1) %n] [ (x%n+n-1) %n] one by one until an empty spot is found to store x or all those cells have been checked. Can you identify the problem with the above insertion approach for inserting ints to the set? Can you design an insertion mechanism that potentially allows for a faster looking up of ints from the two-dimensional array in practice? Please briefly describe your method in plain English, pseudo-code, or C++ code (word limit: 200).
Register for solutions, replies, and use board search function. Answer Happy Forum is an archive of questions covering all technical subjects across the Internet.