Given a linked list of integers sorted in the ascending order, and a pointer to a single node containing an integer, insert the node in the linked list so that it remains sorted.
Question 2:
Given two null terminated linked lists, combine their nodes
so that the nodes of the new list alternate between those of
the two original nodes: <first node of first list, first
node of second list, second node of first list, second node
of second list, ... >.
Note: Do not allocate any new nodes.
Question 3:
A stirling number of the first kind is defined as follows:
o s(0,0) = 1
o s(n,0) = 0, for all n > 0
o s(n+1,k) = s(n,k-1) – n * s(n, k), for all n ?0 and
k>0
Write a recursive routine to calculate stirling numbers of the
first kind.
Question 4:
Given an array of size N, with its items in no particular order,
and a number k with 0 ? k ? N, find the smallest item that is
larger than or equal to at least k items, O( N) time. You may
rearrange the items of the array if you wish.
Hint: Consider how you can use the partition subroutine
Question 5:
A deque is a data structure consisting of a list of items,
on which the following operations are possible:
· push(x): Insert x on the front end of the deque.
· pop( ): Remove the front item from the deque and return
it.
· inject(x): Insert x on the rear end of the deque.
· eject( ): Remove the rear item from the deque and return
it.
Describe routines to support the deque that take constant number of steps for each operation. You may use array-based or pointer-based implementation.
Question 6:
For each of the following program fragments, give an analysis
of the running time. You may use summations to evaluate the
running times of nested loops.
(a) sum = 0
for i = 1 to n
for j = 1 to i * i
for k = 1 to j
sum ++
(b) sum = 0
for i = 1 to n
for j = 1 to i * i
if j mod i == 0
for k = 1 to j
sum ++