CS201 Problem Set 2    Date: ______ Name: ________________

What is the logical order of  List 1:_____________________________
What is the logical order of List 2: ______________________________
What is the logical order of List 3: _______________________________
What is the logical order of List 4: _______________________________
What is the logical order of List 5: ________________________________

Complete the following operations on these  linked list

       List 1
List=3      Avail=4

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

 add 30 Prev =5

       List 2
List=2    Avail=4

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

Add 10     Prev = 3

     List 3
List=3   Avail=6

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

Add 95     Prev=-1

     List 4
List=3       Avail=6

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

Delete 94

    List 5
List=2  Avail=4

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

Delete 6

 

List=2       Avail=-1

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

Delete 40

List=   1    Avail=5

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

Add 10    Prev= 1

List=    2   Avail=5

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

Add 99    Prev=0

List=3       Avail=6

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

Delete 12

List= 2       Avail=4

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

Delete 90


Complete the following operations on the double linked list

  Avail=-1     Fl=2 Bl=5

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

Delete 40

 Avail=5  FL=1 BL=6

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

Add 10

Avail=4   FL=2 BL=3

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

5
6

6
-1

Add 99

Double Circular  
  Avail=5   FL= 3  BL=2

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

6
-1

Delete 12

Double Cicurlar
   Avail=4  FL=2 BL=1

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

5
6
6
-1

Add 10

 

 

 

 

 

 

 

 

 


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

5  
4  
3  
2  
1  
0  

top=

push 55
push 85
push 10
push 21
pop => ______
pop => ______
push 70
L.O. _______________
push 34
push 99

L.O. _______________

 

5  
4  
3  
2  
1  
0  

top=

push 73
push 85
push 21
push 45
pop => ______
push 70
L.O. _______________
push 65
push 14
L. O. _______________

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

0  
1  
2  
3  

Front=
Rear=

Enqueue Mike
Enqueue Gary
Enqueue John
Dequeue=> ______

Enqueue Tom
Dequeue=> ______
Dequeue=> ________
L.O. _______________
Enqueue Henry
L.O. ________________

0  
1  
2  
3  

Front=
Rear=

Enqueue Chuck

Enqueue Ed
Dequeue => ________
Enqueue Kevin
Enqueue Larry
Enqueue David
Dequeue => _________

Dequeue => _________
Enqueue Steve
Enqueue Tom

L.O. __________________

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

          ID        Name         Link

0      
1      
2      
3      
4      
5      
6      
7      
8      
9      
10      
11      
12      
13      
14      
15      

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      
3      
4      
5      
6      
7      
8      
9      
10      
11      
12      
13      
14      
15      

 

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?