1- We are performing the following operations on the ADTs below. Show the value
ID: 673080 • Letter: 1
Question
1- We are performing the following operations on the ADTs below. Show the value returned by the peek and remove operations. Add 20, 7, 5, 8. Remove (a). Add 10, 14. Peek (a). Add 9. Remove (b). Add 3, 11. Peek (b). a) FIFO Queue Remove (a)= ________ Peek (a) = _________ Remove (b) = ________ Peek (b) = _________ b) Stack Remove (a)= ________ Peek (a) = _________ Remove (b) = ________ Peek (b) = _________ 2- We are performing the following operations on a Deque implemented using an array. The initial capacity of the array is 5 and the array doubles whenever the deque reaches its capacity. Please show the physical state (draw the array cells) of the array after each of the operations. For the array elements with “junk” values, leave any existing value in the array but cross it out. Show next to the array the values of the lo and hi indices. a) pushFront C lo= hi= b) pushFront A c) pushBack Z d) popFront e) pushBack U f) pushFront K g) popBack h) pushBack J i) pushFront H j) pushBack P k) popFront 3 - Write a recursive function called printNums that takes as a parameter an int n and prints all the numbers from 0 to n. Run your code to ensure it does what you intended to do. e.g.: printNums(5) should print 0 1 2 3 4 5. – Point out the base case and the recursive step. – How many stack frames deep is this for a given number n? 4 - Write a recursive function called linearSearch that takes as a parameter an array of ints, array size and the value to look for and returns the index of that value in the array if the value is present, or -1 if not found. Run your code to ensure it does what you intended to do. e.g.: linearSearch([2, 9, 6, 4, 7], 5, 4) should return 3 linearSearch([2, 9, 6, 4, 7], 5, 2) should return 0 linearSearch([2, 9, 6, 4, 7], 5, 3) should return -1 – Point out the base case and the recursive step. – How many stack frames deep is this for a given number n? 5- We are using the binary search algorithm to look for a value in the array below. For each step of the algorithm write the value that is looked at and the values in the array that are left in consideration for the next step (cross out what is “thrown away”). No code to write. 3 4 8 11 17 21 25 30 33 39 a - Look for the value 25. How many steps does it take until we find it? b – Look for the value 5. How many steps does it take to find out that 5 is not present?
Explanation / Answer
1. a. FIFO Queue:
Add 20, 7, 5, 8.
Remove (a) = 20.
Add 10, 14.
Peek (a) = 7.
Add 9.
Remove (a) = 7.
Add 3, 11.
Peek (a) = 5.
b. Stack:
Add 20, 7, 5, 8.
Remove (b) = 8.
Add 10, 14.
Peek (b) = 14.
Add 9.
Remove (b) = 9.
Add 3, 11.
Peek (b) = 11.
3. printNums(n):
int printNums(int n)
{
if(n == -1)
return 0;
printNums(n-1);
printf("%i ",n);
return 0;
}
The base case is: if(n == -1), this ensures the loop will go deep till 0 from n, to print all those numbers.
This is an n+1 stack frames deep.
4. linearSearch() recursive program:
int lsearch(int array[],int n,int key)
{
int i;
if(n==0)
return -1;
else if(array[n-1]==key)
return n-1;
else
return lsearch(array,n-1,key);
}
The base case is: if(n == 0), which means if there are no elements in the list to search for.
The depth of the stack frames, depends on the values you are searching for, and the values that are in the array.
In the worst case, it will proceed for n frames deep.
5. Binary Search:
Given list:
In binary search, everytime the mid value is calculated, given the low and high values of the indices of the array.
binsearch(array,low,high,key)
a. (i) binsearch(array,0,9,25). mid = 4. array[mid] = 17.
As the search key(25) is greater than, array[mid] value (17) move the low to mid+1.
(ii) binsearch(array,5,9,25). mid = 7. array[mid] = 30.
As the search key(25) is less than, array[mid] value (30) move the high to mid-1.
(iii) binsearch(array,5,6,25). mid = 5. array[mid] = 21.
As the search key(25) is greater than, array[mid] value (21) move the low to mid+1.
(iv) binsearch(array,6,6,25). mid = 6. array[mid] = 25.
Element is found so return the mid value: 6.
The recursive steps required to identify the element 25 is 4.
b. (i) binsearch(array,0,9,5). mid = 4. array[mid] = 17.
As the search key(5) is less than, array[mid] value (17) move the high to mid-1.
(ii) binsearch(array,0,3,5). mid = 1. array[mid] = 4.
As the search key(5) is greater than, array[mid] value (4) move the low to mid+1.
(iii) binsearch(array,2,3,5). mid = 2. array[mid] = 8.
As the search key(5) is less than, array[mid] value (8) move the high to mid-1.
(iv) binsearch(array,2,1,5). As the low and high crossovers, the elements in the list are exhausted and the search key is not found in the list. Therefore, we can conclude that the element is not found in the list.
0 1 2 3 4 5 6 7 8 9 3 4 8 11 17 21 25 30 33 39Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.