WorksheetsData Structure Quiz 1
Total questions: 9
Worksheet time: 5mins
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?
An array of 50 numbers
An array of 100 numbers
An array of 500 numbers
A dynamically allocated array of 550 numbers
Consider an array consisting of –ve and +ve numbers. What would be the worst case time complexity of an algorithm to segregate the numbers having same sign altogether i.e all +ve on one side and then all -ve on the other?
O(N)
O(N Log N)
O(N * N)
O(N Log Log N)
A three dimensional array in ‘C’ is declared as int A[x][y][z]. Consider that array elements are stored in row major order and indexing begins from 0. Here, the address of an item at the location A[p][q][r] can be computed as follows (where w is the word length of an integer):
&A[0][0][0] + w(y * z * q + z * p + r)
&A[0][0][0] + w(y * z * p + z*q + r)
&A[0][0][0] + w(x * y * p + z * q+ r)
&A[0][0][0] + w(x * y * q + z * p + r)
Consider a two dimensional array A[20][10]. Assume 4 words per memory cell, the base address of array A is 100, elements are stored in row-major order and first element is A[0][0]. What is the address of A[11][5] ?
575
460
570
560
Which of the following points is/are true about Linked List data structure when it is compared with array
Arrays have better cache locality that can make them better in terms of performance.
It is easy to insert and delete elements in Linked List
Random access is not allowed in a typical implementation of Linked Lists
All of the above
Which of the following sorting algorithms can be used to sort a random linked list with minimum time complexity?
Insertion Sort
Quick Sort
Heap Sort
Merge Sort
In the worst case, the number of comparisons needed to search a singly linked list of length n for a given element is
log 2 n
n/2
n
log 2 n – 1
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?
union only
union, intersection
membership, cardinality
intersection, membership
What are the time complexities of finding 8th element from beginning and 8th element from end in a singly linked list? Let n be the number of nodes in linked list, you may assume that n > 8.
O(1) and O(n)
O(1) and O(1)
O(n) and O(1)
O(n) and O(n)
