4.1 When a data structure is linear there is an unique first, second, third .. last element. There is no such ordering when a data structure is nonlinear. A sequential list is linear and a tree is nonlinear.

4.3 Algorithm 2 is preferable. n log₂n is much less than either n2 or 2n as n becomes large.

4.6 O(1)

4.8

1. O(n)
2. O(n)
3. O(n²)
4. O(n³)

4.9

1. O(n)
2. O(log₂n) if the priority queue is implemented using a heap and O(n) if implemented using an array.
3. O(log₂n)
4. O(1)
5. O(1)

4.10 O(n)

4.12

1. 11 22 40 34
2. 11 16 34 22 40

4.13

1. //concatenate list L onto list K.
        void Concatenate(SeqList& K, SeqList& L)
   	{
   		//traverse list L, inserting each of its elements into list K.
   		//each element goes at the rear of K.
   		so list L is appended to K.
   		for(int i=0; i<L.ListSize();i++)
   			K.Insert(L.GetData(i));
   	}
   

2. //reverse list L
   void Reverse(SeqList& L)
   {
   	//use a temporary list tmp
   	SeqList tmp;
   
   	//traverse L in reverse inserting each element into list tmp.
   	//tmp is list L in reverse.
   	for(int i=L.ListSize()-1;i>=0;i--)
   		tmp.Insert(L.GetData(i));
   	//assign tmp to L
   	L=tmp;
   }
   

4.15 When a data value is deleted, its space becomes available. We make space available at the rear for subsequent insertions by moving each element in the tail of the list to the left one position.