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 ++