Data Structures & Algorithms

Exam 1

Sample 1, 75 Minutes

In the class ArrayLinearList a linear list is represented in a one-dimensional array element. The data member size is such that the list elements are in positions 0 through size-1 of the array. The member method rightShift shifts the elements of the linear list right by k positions and fills the empty positions at the left end with null. For example, if the list element[0:5] = [1, 2, 3, 4, 5, 6], whose size is 6, is shifted right by 3, the result is [0, 0, 0, 1, 2, 3, 4, 5, 6], whose size is 9.

(a)
[8] Write Java code for the rightShift member method.
(b) [2] What is the time complexity of your code as a function of the list size?
Consider the class Chain which has the data members firstNode and size. The data type of firstNode is ChainNode. Objects of type ChainNode have the data members element and next. Nodes on a chain are linked together using the field next.

The method isSorted, which is a member of Chain determines whether the chain elements are in ascending (more accurately nondecreasing) order of their element values. The method returns true if the chain is sorted and false if it is not.
(a)
[8] Write Java code for the isSorted member method. To compare two objects a and b you may do something like
```
if (((Comparable) a).compareTo(b) > 0)
{// come here only if a greater than b
}
```
(b) [2] What is the time complexity of your code as a function of the list length?
In an n x n N-matrix, all terms other than those in column 1, column n, and the main diagonal are zero. An N-matrix has at most 3n-2 nonzero terms. An N-matrix can be compactly stored in a one-dimensional array by first storing column 1, then column n, and then the remaining elements of the main diagonal.
```
                              x             x 
                              x x           x
                              x   x   zero  x
                              x     x       x
                              x       x     x
                              x  zero   x   x
                              x           x x
                              x             x


                         x denotes a possible nonzero
                         all other terms are zero
```
(a)
[2] Give a sample 4 x 4 N-matrix and its compact representation.
(b)
[8] Suppose that we are defining a class NMatrix that represents an n x n N-matrix in a one-dimensional array element as above. Besides element, the class has the data members n and zero (the zero element for the matrix). Write Java code for the member method set(i, j, newValue) which stores newValue as the (i,j) element of the N-matrix, 1 <= i <= n and 1 <= j <= n. The element is to be stored in the proper position of the one-dimensional array element.

Solutions