1. Trace the code and give the output in #1 to #5

   #include<iostream.h>
   
   typedef int DataType;
   #include "aseqlist.h"
   
   void PrintList const SeqList &L)
   {
   	for(int i=0; i< L.ListSize();i++)
   		cout << L.GetData(i) << " " ;
   	cout << endl;
   }
   
   void main(void)
   {
   	SeqList.L;
   
   	L.Insert(5);	
   	L.Insert(10);
   	L.Insert(1);
   	L.Insert(15);
   	PrintList(L);		//#1 _______
   
   	if (L.GetData(1)==10)
   		L.DeleteFront();
   	PrintList(L);			//#2 _______
   
   	L.Insert(25);
   	L.Delete(1);
   	cout << L.ListSize() << endl;	// #3 ______
   
   	PrintList(L);		//#4 ________
   	while(!L.ListEmpty())
   	{
   		cout << L.GetData(0) << endl;	//#5 _______
   		L.DeleteFront();
   	}
   }
   

2. In the program what would the output at #5 be for the loop

   while(!L.ListEmpty())
   {
   	cout << L.GetData(L.ListSize()-1) << endl;	//#5
   	L.DeleteFront();
   }
   

3. Trace the program and give the output, assuming that PrintList prints the items in the list

   #include<iostream.h>
   
   typedef int DataType;
   #include "aseqlist.h"
   
   void F(SeqList& L)
   {
   	int itemval = L.GetData(0);
   	
   	while (L.Find(itemval))
   		L.Delete(itemval);
   }
   
   void main(void)
   {
   	int i, item;
   	SeqList L;
   
   	for(i=0; i<5; i++)
   	{
   		cin >> item;	//input an item
   		L.Insert(item);
   	}
   	F(L);		//Call the function
   	PrintList(L);	//Print the list
   }
   

   • What is output for input 1 2 3 4 5 <output> _____
   • What is output for input 7 2 4 7 3 <output> _____
4. Revise the code from part C to have a new function F and a modified main program.

   SeqList F(SeqList& L)
   {
   	int itemval, i;
   	SeqList K;
   
   	while(!L.ListEmpty())
   	{
   		itemval=L.GetData(0);
   		K.Insert(itemval);
   		while(L.Find(itemval))
   			L.Delete(itemval);
   	}
   	return K;
   }
   
   void main(void)
   {
   	int i item;
   	SeqList L, K;
   
   	for(i=0;i<5;i++)
   	{
   		cin >> item;	//input an item
   		L.Insert(item);
   	}
   	K=F(L);		//Call the Function
   	PrintList(K);
   }
   

   • What is output for input 1 2 1 3 2 <output>_________
   • What is output for input 8 8 8 1 8 <output>_________

void RSE(SeqList L)
{
	int item;
	while(L.ListSize()>0)
	{
		item=L.GetData(L.ListSize()-1);
		L.delete(item);
		cout << item << " ";
	}
	cout << endl;
}

1. Assume SeqList has values 1 5 2 9 6. The output from RSE is
   1. 1 5 2 9 6
   2. 1 2 5 6 9
   3. 6 9 2 5 1
   4. 6 1 5 9 2
2. Assume SeqList has values 1 2 3 2 1. The output from RSE is
   1. 1 2 3 2 1
   2. 1 1 2 2 3
   3. 1 3 1 2 2
   4. 3 2 2 1 1

1. O(n)
2. O(n²)
3. O(log₂n)
4. O(n ³)
5. O(2ⁿ)
6. O(1)

1. f(n) = 2n-3 _____
2. f(n)= (n ³+3n+7)/(n-2) _____
3. f(n)=(2n²-3)/(n²+1) _____
4. The complexity of determining the length of a C++ string that contains n characters. _____
5. To sort a collection of n items first scan the list, remove the largest item and place it in the first position. Then scan the list of remaining elements, remove its largest element, and put it in the second position. Repeat the process of scanning the sublist, selecting the largest element and placing it in the next position in the ordered list.

   What is the complexity of this sort process? _____

6. The complexity of determining the length of a byte-count (Pascal) string that contains n characters is _____
7. One-inch square stickers are used to cover the surface of a cubic box that has volume n-cubic inches. What is the complexity of covering the outer surface of the box? ______

1. Pop an element from a stack _________
2. Sort an array of n integers ________
3. Print a linked list with n items ________

1. Binary search of an n element list
   1. O(n)
   2. O(log₂n)
   3. O(n log₂n)
   4. O(n ³)
2. Exchange sort
   1. O(n²)
   2. O(n)
   3. O(n log₂n)
   4. O(n ³)
3. Finding the minimum of an n element list.
   1. O(n²)
   2. O(n)
   3. O(n log₂n)
   4. O(n ³)
4. Inserting into a SeqList object.
   1. O(n²)
   2. O(n)
   3. O(n log₂n)
   4. O(n ³)
5. Deleting an element from a SeqList object.
   1. O(n²)
   2. O(n)
   3. O(n log₂n)
   4. O(n ³)

1. True
2. False

1. True
2. False

1. Read the value in the middle of the list and then move left or right, depending on the value.
   1. stack
   2. queue
   3. tree
   4. array
2. Data consists of name, social security number and pay rate
   1. sequential list
   2. paragraph
   3. record
   4. set
3. Find the definition of man using the syntax D["man"]
   1. stack
   2. queue
   3. dictionary
   4. priority queue
4. The most important print job is run first.
   1. queue
   2. priority queue
   3. stack
   4. tree
5. If the data is less than the current one, descend left; otherwise descend right.
   1. graph
   2. stack
   3. sequential list
   4. tree
6. Retrieve the last two data values that were input.
   1. queue
   2. stack
   3. sequential list
   4. hash table
7. Simulate the checkout line in the grocery store
   1. queue
   2. stack
   3. graph
   4. tree.

#include "aseqlist.h"

DataType F(SeqList& L)
{
	DataType x =L.GetDat(0);
	
	for(int i=1; i< L.ListSize();i++)
		if(L.GetData()<x)
		x=L.GetData();
	L.Delete(x);
	return x;
}

1. Find and return the maximum value in list
2. Find and delete the maximum value in list
3. Find and return the minimum value in list
4. Find and delete the maximum value in list