CIS3355: Data Structures

The University of Texas at El Paso

Professor Kirs

Linked Lists: Sample Problems and Exercises

1.0010 List all the advantages and disadvantages of singly linked list. Of doubly linked lists?

1.0050 I have five books which I have listed in a spreadsheet as follows:

Title	Author	Year Written	Value
Anna Karenina	Tolstoy	1876	125
Great Gadsby, The	Fitzgerald, F.S.	1932	50
Guliver’s Travels	Swift	1726	250
Rhetoric	Aristotle	329 BC	1500
Vanity Fair	Thackeray	1847	750

a. Set up the needed structure template (call it struct booktemplate) to link the list alphabetically by author (make up string lengths as you see fit).

SEE SOLUTION

b. Assign the variable book to the structure template. Show the declarations necessary.

SEE SOLUTION

c. Assume that the base address of the variable book is 9000. Set up a table which would show all of the linkages.

SEE SOLUTION

d. Now link the list by year written and value (maintaining the linkages established above). Show the modified struct booktemplate. Assuming that the base address of books remains 9000, show (in tabular form) how the linkages would appear.

SEE SOLUTION

1.0100 Given the following structured object and declarations:

struct studentinfo { char ssn[11], name[28], address[30];

int age, IQ;

float gpa, balance;

struct studentinfo *next, *previous; };

void main()

{ struct studentinfo student[5] = {{“123457689”, “Gates, W.”,”99 Microsoft

Ln”,38,108,3.87,4500,NULL,NULL},{“234567890”, “Ford, H.”,“17 Michigan

Ave”, 125,115,3.10,250.00,,}, {“345678901”,“Trump, D.”,”1 Trump

Towers”,55,110,1.86,500,,},{ “456789012”, “Astor, J.J.”, ”20 Wall Street”,76,

100,2.76, 1000,,},{ “567890123”,“Carnegie, A.”,”100 Steel St”, 81, 79, 2.25,0,,};

struct studentinfo * first, * last;

Using a linked list, I have ordered the names alphabetically (in ascending order). Field next will hold the address of the next person (alphabetically) on the list. Field previous will hold the address of the previous person (alphabetically) on the list. Variable first will point to the first person (alphabetically) on the list, and variable last will point to the last person (alphabetically) on the list.

When I entered the command: printf (“%lu\n”, &student[2]);

I received the output: 7828

For each of the following printf statements, show the output which would be obtained:

a. printf(“%lu\n”,first);

a. printf(“%lu\n”,last);

a. printf(“%s\n”, first->address);

a. printf(“%lu\n”,&student[1].balance);

a. printf(“%f5.2\n”,student[3].next->balance);

a. printf(“%lu\n”, ++first);

a. printf(“%d\n”,last->previous->age);

SEE SOLUTIONS FOR ALL PARTS

1.0110 Given the following section of code:

struct studinfo { char studentname[25];

int age, credithours;

float gpa;

struct studinfo *next, *previous; };

/* next points to the next record in the linked list; previous points to the previous record in the linked list */

struct studinfo *head, *present, student[5] = {{“Shakespeare, Bill”,256,12,3.56,NULL,NULL},

{“Albee, Edward”,76,120,2.78,NULL,NULL},{“Voltaire”,56,82,3.75,NULL,NULL},

{“Chaucer, Geoffry”,420,91,3.25,NULL,NULL}, {“Grisham, John”,46,24,1.57,NULL,NULL}} ;

// head will point to the first record in the list after it is linked by studentname in ascending order

For the following questions, assume that I have developed a list which is linked (the code necessary is NOT shown), in ascending order, on student[].studentname. Assume that the base address (in RAM) for the database (for student; NOT the linked list) is 4000.

a. What is the value of head (after the links are complete)?

b. What is the value of &student[3]?

c. What the value of student[0].next?

d. What is the value of student[2].previous -> gpa?

e. What is the value of student[4].next -> studentname?

f. What is the value of student[3].previous -> previous?

g. given present = student[0].next; what is the value of --present?

h. What would be the value of student[2].next AFTER the command

student[2].next = (struct studinfo *) malloc(sizeof(struct studinfo));?

i. Explain your answer to the above question

j, Explain how I would remove Albee, Edward from the LINKED list

SEE SOLUTIONS FOR ALL PARTS

1.0120 Given the following section of code:

struct studinfo { char studentname[30];

struct studinfo *nextgpa;

short age, credithours;

long weightindrams;

float gpa; };

// nextage points to the next record in the linked list in terms of age

struct studinfo *head, *present, student[6] = {{“Christie, Agatha”,, 96, 82, 37324, 3.05},

{“Shakespeare, Bill”,, 256,12, 52253, 3.56}, {“Albee, Edward”,, 76, 120, 72689, 2.78},

{“Voltaire”,, 56, 82, 64766, 3.75,}, {“Chaucer, Geoffry”,, 420, 91, 41566, 3.25},

{“Grisham, John”,, 46, 24, 66456, 1.57}} ;

// head will point to the first record in the list after it is linked by gpa in ascending (lowest to

// highest) order and present will be used to point to a record.

For the following questions, assume that I have developed a list which is linked (the code necessary is NOT shown), in ascending (lowest to highest) order, on student[].gpa.

The command: printf(“%lu\n”,&student[3].weightindrams); yields the output: 7686

1. What is the value of head (after the links are complete)? ___________________

2. What is the value of &head (after the links are complete)? __________________

3. What is the value of &student[4]? _____________________________________

4. What the value of student[0].nextgpa? _________________________________

5. What is the value of student[2].nextgpa-> weightindrams? ________________

6 What is the value of student[4].nextgpa -> studentname? _________________

7. If present = student[3].nextgpa;

what is the value of ++present ??? _____________________________________

8. If present = student[0].nextgpa;

what is the value of present -> nextgpa ->nextgpa ->credithours ? __________

9. What the value of &student[85].age ? _____________________________

SEE SOLUTIONS FOR ALL PARTS

1.0130 Given the following structured object and declarations:

struct studentinfo { struct studentinfo *previousgpa;

char ssn[11], name[28], address[30];

short age, IQ;

float gpa, balance;

struct studentinfo *nextbalance; };

void main()

{ struct studentinfo student[5] = {{,“123457689”, “Gates, W.”,”99 Microsoft

Ln”,47,108,3.87,4500, },{,“234567890”, “Ford, H.”,“17 Michigan

Ave”, 125,115,3.10,250.00,}, {,“345678901”,“Trump, D.”,”1 Trump

Towers”,65,86,1.86,1500,},{ ,“456789012”, “Astor, J.J.”, ”20 Wall Street”,116,

100,2.76, 800,},{ ,“567890123”,“Carnegie, A.”,”100 Steel St”, 81, 79, 2.25,0,};

struct studentinfo * highgpa, * lowbalance, *arecord;

I am going to use this information to create a linked list which will be linked on two fields:

1. The list will be linked on gpa in descending order (i.e., I will store the address of the person with the highest gpa in location highgpa. The person who has the highest gpa will point to the person with the next highest gpa, and so on until we get to the person with the lowest gpa).

2. The list will also be linked by balance. Location lowbalance will hold the address of the person with the lowest balance. That person will point to the person with next lowest balance, and so forth.

When I entered the command: printf (“%lu\n”, &student[2].name);

I received the output: 8625

For each of the following printf statements, show the output which would be obtained:

A. printf(“%lu\n”,highgpa); ___________________

B. printf(“%lu\n”,&highgpa); ___________________

C. printf(“%lu\n”,lowbalance); ___________________

D. printf(“%s\n”, student[4].previousgpa->previousgpa); ___________________

E. printf(“%lu\n”,&student[2].IQ); ___________________

F. printf(“%s\n”,student[3].nextbalance->nextbalance->name); ___________________

G. printf(“%lu\n”, ++lowbalance) ___________________

H. if I first enter the command: arecord = record[4].nextbalance; what will be printed out by the command:

printf(“%d\n\n”, ++arecord->age); ___________________

I. printf(“%lu\n”,&student[10].address); ___________________

SEE SOLUTIONS FOR ALL PARTS