CS201 Problem Set 2    Date: ______ Name: ________________

What is the logical order of  List 1: 21, 32, 66, 56_____________________________     
What is the logical order of List 2: 55, 60, 34, 78_____________________________    
What is the logical order of List 3: 90, 67, 77, 12_______________________________
What is the logical order of List 4: 22, 64, 94, 74, 16____________________________
What is the logical order of List 5: 60, 80, 40, 70, 30____________________________


Complete the following operations on these  linked lists

       List 1
List= 3  
Avail=   4  0

0 45   6
1  32  5
2  56  -1
3  21  1
4  78   30   0  2
 5  66  2  4
6  17  -1

 add 30 Prev =5

       List 2
List= 2   
Avail= 4  1

0 34 3
1 21 5
2 55 6
3 78 -1  4
4 31 10 1 1
5 45 -1
6 60 0

Add 10     Prev = 3

     List 3
List= 3    6
Avail= 6  0

0 55 4
1 67 5
2 12 -1
3 90 1
4 34 -1
5 77 2
6 20   95 0   3

Add 95     Prev=-1

     List 4
List= 3       
Avail= 6 5  

0 64 5  4
1 16 -1
2 48 -1
3 22 0
4 74 1
5 94  4   6
6 20 2

Delete 94

    List 5
List= 2  6
Avail=  4   2

0 70 5
1 50 -1
2 60 6   4
3 40 0
4 20 1
5 30 -1
6 80 3

Delete 60

 

 

List=2   Avail=-1 4

0 30 3
1 10 5
2 70 6
3 20 1
4 40 0 -1
5 50 -1
6 80  4 0

Delete 40

List= 1    Avail=5 0

0 94 3
1 51  4 5
2 25 6
3 68 -1
4 81 2
5 35 10 0 4
6 70 -1

Add 10    Prev= 1

List= 2   Avail=5 1

0 25 -1 5
1 37 3
2 44 6
3 50 -1
4 64 0
5 77 99 1 -1
6 80 4

Add 99    Prev=0

List=3 0     Avail=6

0 04 5
1 16 -1 3
2 28 -1
3 12 0 -1
4 54 1
5 64 4
6 70 2

Delete 12

List= 2       Avail=4

0 30 5
1 50 -1 3
2 80 6
3 90 0 -1
4 90 1
5 70 -1
6 30 3 0

Delete 90

 

 

 

 

 

 

 

 




Complete the following operations on the double linked list

  Avail=-1   4     Fl=2 Bl=5

0 50 3  4 6
1 70 5  3
2 20 6 -1
3 60 1 0
4 40 0 -1 6 -1
5  90 -1 1
6  30  4 0 2

Delete 40

 Avail=5 0  FL=1 5 BL=6

0 34 3  
1 21 4 -1
5
2 55 6  4
3 78 -1
4 31 2  1
5 45 10 0 1 -1
6 60 -1  2

Add 10

Avail=4 5   FL=2 BL=3  4

0 55 1
2
1 67 3 0
2 12 0
-1
3 90 -1 4  1
4 99
5 -1
3
5
6

6
-1

Add 99

Double Circular  
  Avail=5   FL= 3 0  BL=2

0 34 4
 3 2
1 66 2  4
2 78  3 0
 1
3 12 0 -1  2
4 54 1  0
5
6

6
-1 3

Delete 12

Double Cicurlar
   Avail=4  5
FL=2          BL=1

0 50 5  3
1 80  2
 0
2 20 6  1 4
3 40 0  2
4   10 5  2
 1
5
6
6
-1

Add 10

 

 

 

 

 

 

 

 

 




Complete the following operations on a stack. (Note: L.O. means give the logical order)

5  
4  99
3  21 34
2  10 70
1  85
0  55

top=-1 0 1 2 3 2 1 2 3 4

push 55
push 85
push 10
push 21
pop => __21____
pop => __10____
push 70
L.O. _70, 85, 55
push 34
push 99

L.O. _99, 34, 70, 85, 55

 

5  14
4  65
3  45 70
2  21
1  85
0  73

top= -1 0 1 2 3 2 3 4 5

push 73
push 85
push 21
push 45
pop => __45__
push 70
L.O. _70 21 85 73
push 65
push 14
L. O. _14, 65,70, 21,85,73

Work the following Queue Problems. (When working queue problems initialize Front to 0 and rear to -1)

0   Mike  Henry
1  Gary
2  John
3  Tom

Front=0 1 2 3
Rear= -1 0 1 2 3 0

Enqueue Mike
Enqueue Gary
Enqueue John
Dequeue=> __Mike_

Enqueue Tom
Dequeue=> _Gary_____
Dequeue=> _John_____
L.O. __Tom________
Enqueue Henry
L.O. __Tom, Henry______

0  Chuck David
1  Ed  Steve
2  Kevin  Tom
3  Larry

Front= 0 1 2 3
Rear= -1 0 1 2 3 0 1 2

Enqueue Chuck

Enqueue Ed
Dequeue => __Chuck__
Enqueue Kevin
Enqueue Larry
Enqueue David
Dequeue => ___Ed______
Dequeue => Kevin_____

Enqueue Steve
Enqueue Tom

L.O. _Larry, David, Steve, Tom_

Complete the following Hashing Problems using the following hash function:
loc = id % 10

               ID        Name         Link

0  20  John   -1 11 13 15
1      
2      
3  93  Steve  -1
4      
5  45  Mike  -1 10 12 14
6  36  Tom  -1
7      
8      
9      
10  75 Gary   -1
11  50  Dave   -1
12  15  Will  10
13  60  Pete   11
14  85  Lee  12
15  90 Kim   13

add 45 Mike
add 36 Tom
add 75 Gary
add 20 John
add 50 Dave
add 93 Steve
add 15 Will
add 60 Pete
add 85 Lee
add 90 Kim

 

 




 

        ID         Name      Link

0      
1      
2  32  Tom  -1 11 14
3  33   John  -1 12
4  44  Mike  -1 10 1315
5      
6      
7      
8      
9      
10  24  Ricky  -1
11  72  Gary  -1
12  23  Dave  -1
13  54   Steve  10
14  52   Will  11
15  64 Pete   13

 

add 44 Mike
add 32 Tom
add 24 Ricky
add 72 Gary
add 33 John
add 23 Dave
add 54 Steve
add 52 Will
add 64 Pete
add 01 Kim

Some Hashing questions
Given an ID of 3 digits and a hash function of loc = ID / 20, What would the primary hash area be?