Question

In: Computer Science

5. (20%) Suppose we have an array int a [8] = {1, 2, 3, 5, 6};...

5. (20%) Suppose we have an array int a [8] = {1, 2, 3, 5, 6}; and we also have a linked list L of 5 entries 1 -> 2 -> 3 -> 5 -> 6, where 1 is the first in the linked list L, followed by 2 etc. We want to put a new item 4 between 3 and 5 in the array a and in the linked list L

(a) Explain in plain English how you do that in the array a. You may have to shift items right (or left?) Do you use a loop like a for loop? You can write some C / C++ / C# / Java code etc. to convince me, but the code does not have to run.

(b) Explain in plain English how you do that in the linked list L. How do you change the link from 3 to 5 in the original list L? You can write some code or pseudo code to convince me.

Solutions

Expert Solution

(a) In order to insert the number 4 between 3 and 5 in the array, we have to first find the element after which we have to insert the element 4. In this case, the element we have to find is 3. So, we will need a for loop for searching for an element. Once the element is found, we will first increase the array size by 1, add the new element (here 4) and shift the rest of the elements to the right by one. Let us see the c++ for loop to achieve this.

Let n = number of elements = 5

f = is set to 0 if element we are looking for(3) is not found, othwerise false = 0

ins = initially set to the element to be inserted = 4

//start of code snippet

for(int i = 0; i < n; i++){

int temp;

if(a[i] == 3){

f = 1;

n++;

continue;

}

if(f==1){

temp = a[i];

a[i] = ins;

ins = temp;

}

}

(b) In order to insert a new element anywhere inside a linked list, all we need to do is forst find the node after which the new element is to be inserted, in this case, 3. Then we make a new node containing the element to be inserted(4) and change the link field of 3 to point to node 4, and the link field of node 4 to point to node 5. A snippet of c++ code to explain this:

node = abstract data type to store declare variables of node type. It has 2 fields, int data and node* next

head = pointer to the head of linked list

//start of snippet

node *ptr = new node;

ptr->data = 4;

ptr->next = NULL;

node *temp = head;

while(temp != NULL){

if(temp->data == 3){

ptr->next = temp->next;

temp->next = ptr;

}

}


Related Solutions

Suppose A is (10, 2, 5, 9, 1, 8, 2, 4). Consider the function: int BBOX(int...
Suppose A is (10, 2, 5, 9, 1, 8, 2, 4). Consider the function: int BBOX(int n, int k)             if (n <= 0) return 0;             else if (A[n] < k) return (1+ 2*BBOX(n-1,k+1));             else return BBOX(n-1,k-2);             Find BBOX(8, 5)
tens Units 1 5 2 3 4 8 5 2 5 6 9 6 1 3...
tens Units 1 5 2 3 4 8 5 2 5 6 9 6 1 3 5 4 7 9 7 0 0 4 5 6 9 9 8 1 3 5 6 8 9 9 0 1 2 3 5 9 The table represent a random sample of 31 test scores taken from a large lecture class. Find the following [round to 2 decimal points X. XX] a) [2 pts] Find the 5 number summary [L, Q1, Q2, Q3,...
Consider the following sorted int array: 1 3 4 5 7 9 10 12 If we...
Consider the following sorted int array: 1 3 4 5 7 9 10 12 If we search for the key value 10 in the array using the binary search algorithm, what is the sequence of indices that will be accessed in the array? (Hint: For a sublist between index values low and high, the middle index is calculated using: (low + high) / 2. So you need to show the sequence of indices of the middle index in each pass.)...
Solve the following Double Linked List sort: use int. array = {8, 3, 12, 9, 6,...
Solve the following Double Linked List sort: use int. array = {8, 3, 12, 9, 6, 2} and provide visualization development to the solution.
Assume we have two sequences of values S1 containing 1, 5, 3, 6, 7, 8 while...
Assume we have two sequences of values S1 containing 1, 5, 3, 6, 7, 8 while S2 containing 2, 5, 6, 9, 7. We store these two sequences as sets and perform a set intersection and set difference. Write C++ code to do that respectively.
x 2 8 5 9 4 3 9 6 7 8 y 3 6 5 7...
x 2 8 5 9 4 3 9 6 7 8 y 3 6 5 7 9 7 4 6 9 9 -5.48x + 0.17 5.48x + 0.17 -0.17x + 5.48 0.17x + 5.48
trace by using quicksort on the array : 4 6 5 3 2 7 1 using...
trace by using quicksort on the array : 4 6 5 3 2 7 1 using 7 as the pivot
QUESTION 5 What is printed? int[] aArray = {1, 2, 3, 4}; int[] bArray = {5,...
QUESTION 5 What is printed? int[] aArray = {1, 2, 3, 4}; int[] bArray = {5, 6, 7, 8}; bArray = aArray; System.out.print(bArray[2]); 1 points    QUESTION 6 What is printed? public static void main(String[] args) { int[] aArray = { 1, 2, 3, 4 }; System.out.print(aArray[2]); int i = aMeth(aArray); System.out.print(i + "" + aArray[2]); } public static int aMeth(int[] iArray) { for (int i = 0; i < iArray.length; i++) { iArray[i]++; } int[] bArray = { 5,...
Qno.1 Part(A). IN jAVA if 1.Int abc; 2. Int def = 8; 3. abc = def;...
Qno.1 Part(A). IN jAVA if 1.Int abc; 2. Int def = 8; 3. abc = def; ➢ Describe the procedure how much memory will be allocated when these three lines of codes will execute. ➢ Describe what will happened after execution of each of these line of code in term of memory allocation and data storage Qno.1 Part(B) A capacitor is constructed from two conductive metal plates 30cm x 50cm which are spaced 6mm apart from each other, and uses...
Consider a set A = { 1, 2, 3, 4, 5, 6, 8} Consider these relations,...
Consider a set A = { 1, 2, 3, 4, 5, 6, 8} Consider these relations, 1. R1 = { ( a, b) | a = 3b } Can you write down the pairs ? one such pair is ( 3, 1) 2. R2 = { (a, b) | 2a = b } Can you write down the pairs ? one such pair is (2, 4) 3. R3 = { ( a, b) | a >= 2b } Can you...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT