2. DSA-PQ-Arrays - DSA QUESTION PAPER ATTACHED. PDF

Preview

Summary

DSA QUESTION PAPER ATTACHED....

Description

Practice Questions – Arrays Chapter Contents: Arrays, Two-Dimensional Array, Address Calculation, Dynamically Allocated Arrays, Abstract Data Types, Polynomials, Matrix Addition and Multiplications, Sparse Matrix. Question # 1

2 3 4 5

6 7 8

9

10

11

Question Design an algorithm that takes as input the size of the array and the base address and a particular index and prints the element at that index. Design an algorithm to sort elements by their frequency. Design an algorithm to add two polynomials of single variable. Design an algorithm to multiply two polynomials of two variables. A program P reads in 500 random integers in the range [0..100] presenting 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? Design an algorithm to delete all the vowels in a character array. Design an algorithm to print all the elements below the minor diagonal in a 2-D array. Design an algorithm to find a triplet that sum to a given value. For example, if the given array is {12, 3, 4, 1, 6, 9} and given sum is 24, then there is a triplet (12, 3 and 9) present in array whose sum is 24. Given an array, write an algorithm to find the maximum j – i such that arr[j] > arr[i]. Input: {34, 8, 10, 3, 2, 80, 30, 33, 1} Output: 6 (j = 7, i = 1) Input: {9, 2, 3, 4, 5, 6, 7, 8, 18, 0} Output: 8 ( j = 8, i = 0) Design an algorithm to replace every element in the array with the next greatest element present in the same array. For the input array [4, 5, 2, 25}, the next greater elements for each element are as follows. Element NGE 4 --> 5 5 --> 25 2 --> 25 25 --> -1 For the input array [13, 7, 6, 12}, the next greater elements for each element are as follows. Element NGE 13 --> -1 7 --> 12 6 --> 12 12 --> -1 Write an algorithm to find whether an array is subset of another array Data Structure and Algorithm (CS-2001) School of Computer Engineering

Complexity Level Simple

Simple Simple Moderate Moderate

Simple Simple Moderate

Moderate

High

Moderate

Examples: Input: arr1[] = {11, 1, 13, 21, 3, 7}, arr2[] = {11, 3, 7, 1} Output: arr2[] is a subset of arr1[]

12 13 14 15

Input: arr1[] = {10, 5, 2, 23, 19}, arr2[] = {19, 5, 3} Output: arr2[] is not a subset of arr1[] Write an algorithm to remove repeated elements in a given array. Write down the algorithm to find the k’th smallest and largest element in unsorted array Write an algorithm to find the number of occurrence of kth element in an integer array. Write an algorithm to replace every array element by multiplication of previous and next.

Moderate Moderate Simple Moderate

Input: arr[] = {2, 3, 4, 5, 6} Output: arr[] = {0, 8, 15, 24, 0}

16

17

18

19

20

21

// We get the above output using following // arr[] = {0*3, 2*4, 3*5, 4*6, 5*0} Consider the static array growing from both ends. Write the underflow and overflow condition for insertion and deletion from the perspective of both ends. Given an array of integers, and a number ‘sum’. Write an algorithm to find the number of pairs of integers in the array whose sum is equal to ‘sum’. Examples: Input : arr[] = {1, 5, 7, -1}, sum = 6 Output : 2 as Pairs with sum 6 are (1, 5) and (7, -1) Given an unsorted array, Write down the algorithm to find the minimum difference between any pair in given array. Input : {1, 5, 3, 19, 18, 25}; Output : 1 as Minimum difference is between 18 and 19 Given an array of integers, Write down the algorithm to count number of sub-arrays (of size more than one) that are strictly increasing. Input: arr[] = {1, 2, 3, 4} Output: 6 as there are 6 sub-arrays {1, 2}, {1, 2, 3}, {1, 2, 3, 4}, {2, 3}, {2, 3, 4} and {3, 4} Given an array of integers. All numbers occur twice except one number which occurs once. Write down the algorithm to find the number in O(n) time & constant extra space. Input: ar[] = {7, 3, 5, 4, 5, 3, 4}; Output: 7 Given a 2D array of size m X n, containing either 1 or 0. As we traverse through, where ever we encounter 0, we need to convert the whole corresponding row and column to 0, where the original value may or may not be 0. Devise an algorithm to solve the problem Data Structure and Algorithm (CS-2001) School of Computer Engineering

Simple

Moderate

Moderate

Moderate

High

High

22

23

minimizing the time and space complexity. Given an unsorted array of numbers, write a function that returns true if array consists of consecutive numbers. Examples: a) If array is {5, 2, 3, 1, 4}, then the function should return true because the array has consecutive numbers from 1 to 5. b) If array is {83, 78, 80, 81, 79, 82}, then the function should return true because the array has consecutive numbers from 78 to 83. Given a n x n matrix. The problem is to find all the distinct elements common to all rows of the matrix. The elements can be printed in any order. Examples:

Moderate

High

Input : mat[][] = { {2, 1, 4, 3}, {1, 2, 3, 2}, {3, 6, 2, 3}, {5, 2, 5, 3} } Output : 2 3

24

Input : mat[][] = { {12, 1, 14, 3, 16}, {14, 2, 1, 3, 35}, {14, 1, 14, 3, 11}, {14, 25, 3, 2, 1}, {1, 18, 3, 21, 14} } Output : 1 3 14 Given a two dimensional array, Write a program to print lower triangular matrix and upper triangular matrix. Examples:

Simple

Input : matrix[3][3] = {1 2 3 456 7 8 9} Output : Lower : Upper : 100 123 450 056 789 009

25

Input : matrix[3][3] = {7 8 9 321 6 5 4} Output : Lower : Upper : 700 789 320 021 654 004 Given two matrices A and B. The task is to multiply matrix A and Data Structure and Algorithm (CS-2001) School of Computer Engineering

Moderate

26

matrix B recursively. If matrix A and matrix B are not multiplicative compatible, then generate output “Not Possible”. Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.

Moderate

Example Input matrix 0111 0011 1 1 1 1 // this row has maximum 1s 0000

27 28 29

30

31

32 33 34 35

36 37

Output: 2 Write a program to multiply two polynomials of two variables. Write down algorithm for sparse matrix multiplication using array Given the base address of an array B[1300. . . ..1900] as 1020 and size of each element is 2 bytes in the memory. Find the address of B[1700]. Consider the 30*5 matrix array MATRIX. Suppose Base (MATRIX)=100 and there are W=4 words per memory cell. Suppose the two dimensional array is stored using row-major order. Then what will be the address of MATRIX[10,2]. WAP to swap all the elements in the 1st column with all the corresponding elements in the last column, and 2nd column with the last but one column of a 2-D array. Write a program to reverse an array Find the elements those are occurring odd number of times in an array. Write a program to reverse an array LA1 is a linear array with N elements, LA2 is a liner array with M elements and LA3 is a liner array with M+N elements. Write the algorithm to sort LA1 & LA2 and merge LA1 & LA2 into LA3 & sort LA3 and print each element of LA3 Write down the code for allocating two dimensional array dynamically using double pointers Given an array of positive and negative numbers, arrange them such that all negative integers appear before all the positive integers in the array. The order of appearance should be maintained.

Moderate Simple Simple

Simple

Simple

Simple Simple Simple Simple

Simple Moderate

Examples:

38

Input: [12 11 -13 -5 6 -7 5 -3 -6] Output: [-13 -5 -7 -3 -6 12 11 6 5] Given n numbers (both +ve and -ve), arranged in a circle, find the maximum sum of consecutive number. Examples: Data Structure and Algorithm (CS-2001) School of Computer Engineering

High

Input: a[] = {8, -8, 9, -9, 10, -11, 12} Output: 22 (12 + 8 - 8 + 9 - 9 + 10) Input: a[] = {10, -3, -4, 7, 6, 5, -4, -1} Output: 23 (7 + 6 + 5 - 4 -1 + 10)

39

40

Input: a[] = {-1, 40, -14, 7, 6, 5, -4, -1} Output: 52 (7 + 6 + 5 - 4 - 1 - 1 + 40) Given an array of numbers, arrange them in a way that yields the largest value. For example, if the given numbers are {54, 546, 548, 60}, the arrangement 6054854654 gives the largest value. And if the given numbers are {1, 34, 3, 98, 9, 76, 45, 4}, then the arrangement 998764543431 gives the largest value. Given two integer arrays of same size, “arr[]” and “index[]”, reorder elements in “arr[]” according to given index array. It is not allowed to given array arr’s length. Example: Input: arr[] = [10, 11, 12]; index[] = [1, 0, 2]; Output: arr[] = [11, 10, 12] index[] = [0, 1, 2] Input: arr[] = [50, 40, 70, 60, 90] index[] = [3, 0, 4, 1, 2] Output: arr[] = [40, 60, 90, 50, 70] index[] = [0, 1, 2, 3, 4]

The End Data Structure and Algorithm (CS-2001) School of Computer Engineering

High

Simple...