Test: Array & Linked List


Test Description

20 Questions MCQ Test RRB JE for Computer Science Engineering | Test: Array & Linked List

Test: Array & Linked List for Computer Science Engineering (CSE) 2022 is part of RRB JE for Computer Science Engineering preparation. The Test: Array & Linked List questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Array & Linked List MCQs are made for Computer Science Engineering (CSE) 2022 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Array & Linked List below.
Solutions of Test: Array & Linked List questions in English are available as part of our RRB JE for Computer Science Engineering for Computer Science Engineering (CSE) & Test: Array & Linked List solutions in Hindi for RRB JE for Computer Science Engineering course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Array & Linked List | 20 questions in 60 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study RRB JE for Computer Science Engineering for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
1 Crore+ students have signed up on EduRev. Have you?
Test: Array & Linked List - Question 1

In a compact single dimensional array representation for lower triangular matrices (i.e all the elements above the diagonal are zero) of size n X n, non-zero elements, (i.e elements of lower triangle) of each row are stored one after another, starting from the first row, the index of the (i,j)th  element of the lower triangular matrix in this new representation is:

Detailed Solution for Test: Array & Linked List - Question 1

j+(sum of natural number till i-1) because if you form a lower triangular matrix it contains elements in rows 1,2,3,...
So C is the correct answer.
PS: Though not mentioned in question, from options it is clear that array index starts from 1 and not 0.

Test: Array & Linked List - Question 2

Let A be a two dimensional array declared as follows:

A: array [1 …. 10] [1 ….. 15] of integer;

Assuming that each integer takes one memory location, the array is stored in row-major order and the first element of the array is stored at location 100, what is the address of the element 

Detailed Solution for Test: Array & Linked List - Question 2

A [ LB1..............UB1,LB2.................UB2 ]

BA = Base address.

C = size of each element.

Row major order.

Loc(a[i][j]) = BA + [ (i-LB1) (UB2 - LB2 + 1) + (j - LB2) ] * C.

Column Major order

Loc(a[i][j]) = BA + [ (j-LB2) (UB1 - LB1 + 1) + (i - LB1) ] * C.

substituting the values. answer is A.

Test: Array & Linked List - Question 3

An n * n array ν is defined as follows : 

 

The sum of the elements of the array v is

Detailed Solution for Test: Array & Linked List - Question 3

The sum of the ith row and ith column is 0 as shown below. Since, the numbers of rows = no. of columns, the total sum will be 0.

Test: Array & Linked List - Question 4

A program P reads in 500 integers in the range [0, 100] representing the scores of 500 students. It then prints the frequency of each score above 50. What would be the best way for P to store the frequencies?

Detailed Solution for Test: Array & Linked List - Question 4

as we our area of interest is only the 50 numbers so take An array of 50 numbers where A[0] corresponds to 51...A[49]
corresponds to 100 then after reading an input just increment the counter in correct position as said above

Test: Array & Linked List - Question 5

The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each.
However, the procedure is flawed.

void find_and_replace (char *A, char *oldc, char *newc) {

for (int i=0; i<5; i++)

for (int j=0; j<3; j++)

if (A[i] == oldc[j])

 A[i] = newc[j];

}

The procedure is tested with the following four test cases.

(1) oldc = “abc”, newc = “dab”    

(2) oldc = “cde”, newc = “bcd”

(3) oldc = “bca”, newc = “cda”    

(4) oldc = “abc”, newc = “bac”

The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?

Detailed Solution for Test: Array & Linked List - Question 5

Here when the element of array A and oldc match , we replace that array element of A with array element of newc . For every element of A array update occurs maximum one time.

Similarly for (2) array element of A has updated with array element of newc less than or equal to one time,

Now, for (3) when i=0 , value of A match with oldc[2] i.e.'a' , and replace with newc[2] i.e. also 'a'. So, no changes
when i=1 value of array A[1]='b'
match with oldc[0]='b' and replace with newc[0]='c'.
Now, A[1]='c' which equal with next element of oldc[1]='c'.
So, replace again with newc[1]='d'.
Now, we can say here in array A[1] value replace with newc[0] value , and that newc[0] value replace with next newc[1]
value.

Similarly for (4) here 2 times replacement for A[0] with element newc[0] and newc[1]
Updating of newc value with another newc value is calling flaw here
So Ans B

 

Test: Array & Linked List - Question 6

The procedure given below is required to find and replace certain characters inside an input character string supplied in array A. The characters to be replaced are supplied in array oldc, while their respective replacement characters are supplied in array newc. Array A has a fixed length of five characters, while arrays oldc and newc contain three characters each.
However, the procedure is flawed.

void find_and_replace (char *A, char *oldc, char *newc) {    

for (int i=0; i<5; i++)        

for (int j=0; j<3; j++)            

if (A[i] == oldc[j])              

 A[i] = newc[j];

}

The procedure is tested with the following four test cases.

(1) oldc = “abc”, newc = “dab”    

(2) oldc = “cde”, newc = “bcd”

(3) oldc = “bca”, newc = “cda”    

(4) oldc = “abc”, newc = “bac”

If array A is made to hold the string “abcde”, which of the above four test cases will be successful in exposing the flaw in this procedure?

Detailed Solution for Test: Array & Linked List - Question 6

Here when the element of array A and oldc match , we replace that array element of A with array element of newc . For every element of A array update occurs maximum one time.

Similarly for (2) array element of A has updated with array element of newc less than or equal to one time,

Now, for (3) when i=0 , value of A match with oldc[2] i.e.'a' , and replace with newc[2] i.e. also 'a'. So, no changes

when i=1 value of array A[1]='b'

match with oldc[0]='b' and replace with newc[0]='c'.

Now, A[1]='c' which equal with next element of oldc[1]='c'.

So, replace again with newc[1]='d'.

Now, we can say here in array A[1] value replace with newc[0] value , and that newc[0] value replace with next newc[1] value.

Similarly for (4) here 2 times replacement for A[0] with element newc[0] and newc[1]

Updating of newc value with another newc value is calling flaw here

 

Test: Array & Linked List - Question 7

Consider the C function given below. Assume that the array list A contains n (> 0) elements, sorted in ascending order.

int ProcessArray(int *listA, int x, int n)

{
int i, j, k;

 i = 0;     j = n-1;

do {

 k = (i+j)/2;

if (x <= listA[k]) j = k-1;

if (listA[k] <= x) i = k+1;

}

while (i <= j);

if (listA[k] == x) return(k);

else return -1;

}

Which one of the following statements about the function Process Array is CORRECT?

Detailed Solution for Test: Array & Linked List - Question 7

By the logic of the algorithm it is clear that it is an attempted implementation of Binary Search. So option C is clearly eliminated. Let us now check for options A and D. A good way to do this is to create small dummy examples (arrays) and implement the algorithm as it is. One may make any array of choice. Running iterations of the algorithm would indicate that the loop exits when the x is not present. So option A is wrong. Also, when x is present, the correct index is indeed returned. D is also wrong. Correct answer is B. It is a correct implementation of Binary Search.

*Answer can only contain numeric values
Test: Array & Linked List - Question 8

A Young tableau is a 2D array of integers increasing from left to right and from top to bottom. Any unfilled entries are marked with ∞, and hence there cannot be any entry to the right of, or below a ∞. The following Young tableau consists of unique entries.

When an element is removed from a Young tableau, other elements should be moved into its place so that the resulting table is still a Young tableau (unfilled entries may be filled with a ∞). The minimum number of entries (other than 1) to be shifted, to remove 1 from the given Young tableau is _____.


Detailed Solution for Test: Array & Linked List - Question 8

1.We first need to shift 2 in place of 1 keeping 5 AND 14 intact as it isn't mentioned in the question that the entire row
elements move.
2. 4 is shifted up,next to 2(keeping 12 and infinity intact in column 2).
3. Now in second row 6 is shifted left.
4.18 shifts up to the second row
5. And finally 25 is shifted left to the third column.
So this takes 5 moves and still maintains the tableau property. Also infinity is placed to the right of 25 and below 23(unfilled entries to be filled with ∞). The final table would look as follows.

Test: Array & Linked List - Question 9

Consider an array A [1......n]. It consists of a permutation of numbers 1....n. Now compute another array B [1.....n] as follows: 

Detailed Solution for Test: Array & Linked List - Question 9

B is a permutation of array A

Infact, B gives the reverse index of all the elements of array A. Since the array A contains numbers [1..n] mapped to the locations [1...n] and A is a permutation of the numbers [1...n], the array B will also be a permutation of the numbers [1...n]. For example:

.

To see that option c is incorrect, let array C be the array attained from doing the same transformation twice, that is, 

We can see that C = A, which makes option c incorrect.

Test: Array & Linked List - Question 10

In a circular linked list oraganisation, insertion of a record involves modification of

Detailed Solution for Test: Array & Linked List - Question 10

suppose we have to insert node p after node q then
p->next=q->next
q->next=p
so two pointers
b)

Test: Array & Linked List - Question 11

Linked lists are not suitable data structures for which one of the following problems?

Detailed Solution for Test: Array & Linked List - Question 11

LInked list are suitable for
Insertion sort:->>No need to swap here just find appropriate place and join the link
Polynomial manipulation:->> Linked List is natural soln for polynomial manipulation .http://iiith.vlab.co.in/?
sub=21&brch=46&sim=490&cnt=697
Radix sort:->here we are putting digits according to same position(unit,tens) into buckets;
which can be effectively handle by linked list.
Not Suitable for
Binary search:-> Bcz finding mid element itself takes O(n) time.
So Option B is ans.

Test: Array & Linked List - Question 12

Which of the following statements is true?

I. As the number of entries in a hash table increases, the number of collisions increases.

II. Recursive programs are efficient

III. The worst case complexity for Quicksort is O (n2)

IV. Binary search using a linear linked list is efficient

Detailed Solution for Test: Array & Linked List - Question 12

Binary search using linked list is not efficient as it will not give O(logn), because we will not be able to find the mid in constant time. Finding mid in linked list takes O(n) time.

Recursive programs are not efficient because they take a lot of space, Recursive methods will often throw
Stack Overflow  Exception while processing big sets. moreover it has its own advantages too.

Test: Array & Linked List - Question 13

The concatenation of two lists is to be performed on O (1) time. Which of the following implementations of a list should be used?

Detailed Solution for Test: Array & Linked List - Question 13

A) & B) Here it is not possble to do it in O(1) , unless we have pointer to end of one list. As we have not given that pointer, A & B are not option.
D) It is not possible to do here in O(1), because we will need to allocate memory for bigger array to hold both list & Copy it.
C) It is possible in O(1) as we can break list at any location & connect it anywhere. We don't need to traverse to end of anything here !

Test: Array & Linked List - Question 14

In the worst case, the number of comparisons needed to search a single linked list of length n for a given element is

Detailed Solution for Test: Array & Linked List - Question 14

A & C is not correct as we can not do binary search in Linked list.
B seems like average case, be we are asked for worst case.
Worst case is we do not find the element in list. We might end up searching entire list & comparing with each element. So
answer -> D. n

Test: Array & Linked List - Question 15

Consider the function f defined below.

 struct item {

int data;

struct item * next;

};

int f(struct item *p) {

 return ((p == NULL) || (p->next == NULL)|| 

((p->data <= p ->next -> data) &&

f(p->next)));

}

For a given linked list p, the function  f returns 1 if and only if

Detailed Solution for Test: Array & Linked List - Question 15

It returns 1 if and only if the linked list is sorted in non-decreasing order- B option.
It returns 1 if the list is empty or has just 1 element also, but if and only if makes A option false.

Test: Array & Linked List - Question 16

A circularly linked list is used to represent a Queue. A single variable p is used to access the Queue. To which node should point such that both the operations enqueue and dequeue can be performed in constant time?

Detailed Solution for Test: Array & Linked List - Question 16

The pointer points to the Rear node.

EnQueue: Insert newNode after Rear, and make Rear point to the newly inserted node:

//struct node *newNode;
newNode->next = rear->next;
rear->next = newNode;
rear=newNode;

DeQueue: Delete the Front node, and make the second node the front node.

//rear->next points to the front node.
//front->next points to the second node.
struct node* front;
front = rear->next;
rear->next = front->next;
free(front);

Test: Array & Linked List - Question 17

Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among  Union, intersection,membership,cardinality will be the slowest?

Detailed Solution for Test: Array & Linked List - Question 17

membership is linear search 

cardinality is linear - 

for union we need to ensure no duplicate elements should be present    for each element we need to check if
that element exists in other set for intersection also for every element in set1 we need to scan set2 

Test: Array & Linked List - Question 18

Let P be a singly linked list. Let Q be the pointer to an intermediate node x in the list. What is the worst-case time complexity of the best-known algorithm to delete the node x from the list ?

Detailed Solution for Test: Array & Linked List - Question 18

simple solution is to traverse the linked list until you find the node you want to delete. But this solution requires pointer to the head node which contradicts the problem statement.

Time complexity of this approach is O(1)

Test: Array & Linked List - Question 19

The following C function takes a singly-linked list of integers as a parameter and rearranges the elements of the list. The list is represented as pointer to a structure. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after the function completes execution?

struct node {int value; struct node *next;);

void rearrange (struct node *list) {

struct node *p, *q;

int temp;

if (!list || !list -> next) return;

 p = list; q = list -> next;

while (q) {

temp = p -> value;

p -> value = q -> value;

q -> value = temp;

p = q -> next;

q = p ? p -> next : 0;

}

}

 

 

Detailed Solution for Test: Array & Linked List - Question 19

i think it's B) 2 1 4 3 6 5 7:
as,
p and q are swapping each other.where q is p->next all the time.

Test: Array & Linked List - Question 20

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after function completes execution?

struct node {    

int value;

struct node *next;

};

void rearrange(struct node *list) {

struct node *p, *q;

 int temp;

 if (!list || !list -> next) return;

 p = list; q = list -> next;

 while(q) {

temp = p -> value; p->value =  q -> value;

q->value = temp; p = q ->next;

 q = p? p ->next : 0;

 }   
}

Detailed Solution for Test: Array & Linked List - Question 20

The loop is interchanging the adjacent elements of the list. But after each interchange, next interchange starts from the
unchanged elements only (due to p = q -> next;).
1st iteration 1 2 3 4 5 6 7
=> 2 1 3 4 5 6 7
2nd iteration 2 1 4 3 5 6 7
3rd iteration 2 1 4 3 6 5 7
p pointing to null q pointing to 7, as p is false hence q=p? p->next:0; will return q=0 ending the loop
answer = option B

Use Code STAYHOME200 and get INR 200 additional OFF
Use Coupon Code
Information about Test: Array & Linked List Page
In this test you can find the Exam questions for Test: Array & Linked List solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Array & Linked List, EduRev gives you an ample number of Online tests for practice