Java Reference
In-Depth Information
5.
Write code to read a set of positive integers (terminated by 0) and create a heap in an array
H
with the
smallest
value at the top of the heap. as each integer is read, it is inserted among
the existing items such that the heap properties are maintained. at any time, if
n
numbers
have been read then
H[1..n]
must contain a heap. assume that
H
is large enough to hold all
the integers.
given the data:
51 26 32 45 38 89 29 58 34 23 0
show the contents of h after each number has been read and processed.
6.
a function is given an integer array
A
and two subscripts
m
and
n
. the function must
rearrange the elements
A[m]
to
A[n]
and return a subscript
d
such that all elements to
the left of
d
are less than or equal to
A[d]
and all elements to the right of
d
are greater
than
A[d]
.
7.
Write a function that, given an integer array
num
and an integer
n
, sorts the elements
num[1]
to
num[n]
using Shell sort. the function must return the number of key comparisons made in
performing the sort. You may use any reasonable method for determining increments.
8.
a single integer array
A[1..n]
contains the following:
A[1..k]
contains a min-heap and
A[k+1..n]
contains arbitrary values. Write efficient code to merge the two portions so that
A[1..n]
contains one min-heap. do
not
use any other array.
9.
an
integer
max-heap is stored in an array (
A
, say) such that the size of the heap (
n
, say) is
stored in
A[0]
and
A[1]
to
A[n]
contain the elements of the heap with the
largest
value
in
A[1]
.
(i) Write a function
deleteMax
which, given an array like
A
, deletes the largest element and
reorganizes the array so that it remains a heap.
(ii) given two arrays
A
and
B
containing heaps as described above, write programming
code to merge the elements of
A
and
B
into another array
C
such that
C
is in ascending
order. Your method must proceed by comparing an element of
A
with one in
B
. You may
assume that
deleteMax
is available.
10.
Write a recursive function for finding the k
th
smallest number in an array of
n
numbers,
without sorting the array.
11.
Write insertion sort using a binary search to determine the position in which
A[j]
will be
inserted among the sorted sublist
A[1..j-1]
.
12.
a sorting algorithm is said to be
stable
if equal keys retain their original relative order after
sorting. Which of the sorting methods discussed are stable?
13.
You are given a list of
n
numbers. Write efficient algorithms to find (i) the smallest (ii) the
largest (iii) the mean (iv) the median (the middle value) and (v) the mode (the value that
appears most often).
Write an efficient algorithm to find all five values.
14.
it is known that every number in a list of
n distinct
numbers is between 100 and 9999.
devise an efficient method for sorting the numbers.
Modify the method to sort the list if it may contain duplicate numbers.
Search WWH ::
Custom Search