CS211 - Algorithms and Data Structures II

CS211 - Algorithms and Data Structures II

T Naughton, NUIM
Back to CS211 home

This lab exam is designed to test your basic C++ programming skills.

Problem 3A.1 A computer program is required that reads positive integers, one per line, from the keyboard into a list. The user indicates that they are finished by entering any negative integer (the negative integer itself is not stored). The computer program then checks if any of the numbers in the list is the square root of any other number in the list. The program terminates after finding the first such number. Write this program using fixed-size arrays, the new and delete commands, and a loop to copy the elements from one array to another.

Code to create an array of length len
int * templist; templist = new int[len];

Code to delete an array
delete [] templist;

Sample runs of the program:

If the list is (13, 3, 4, 9, 12) then the program should return
The number 9 has a square root of 3 in the list.

If the list is (13, 3, 4, 10, 12) then the program should return
No square roots found in the list.

Problem 3B.1 A computer program is required that reads single letters, one per line, from the keyboard into a list. The user indicates they are finished by entering a '%' character (the '%' itself is not stored). The computer program then checks if any of the letters, anywhere in the list, appear next to each other alphabetically. The program terminates after finding the first such pair of letters. Write this program using fixed-size arrays, the new and delete commands, and a loop to copy the elements from one array to another.

Code to create an array of length len
int * templist; templist = new int[len];

Code to delete an array
delete [] templist;

Sample runs of the program:

If the list is (z, d, f, c, r) then the program should return
Letters d and c appear next to each other alphabetically.

If the list is (z, d, f, b, r) then the program should return
No letters appear next to each other alphabetically.

Problem 3C.1 A computer program is required that reads positive integers, one per line, from the keyboard into a list. The user indicates they are finished by entering a negative integer (the negative integer itself is not stored). The computer program then checks if any of the numbers in the list is equal in value to the addition of any two neighbouring numbers in the list. The program terminates after finding the first such number. Write this program using fixed-size arrays, the new and delete commands, and a loop to copy the elements from one array to another.

Code to create an array of length len
int * templist; templist = new int[len];

Code to delete an array
delete [] templist;

Sample runs of the program:

If the list is (13, 19, 4, 9, 12) then the program should return
Element 0 is equal to the sum of neighbours 2 and 3.

If the list is (13, 4, 19, 9, 12) then the program should return
No neighbouring sums found in the list.

Lab Sheet 3

Take advantage of this time with demonstrators to:
1) Correct your mistakes (if any) from the previous class exam(s).
2) Finish problems 1.4 through 1.6 (if not yet finished).
3) Start problems 3.2 through 3.4 on this sheet.

Problem 3.2 Below is a diagram of a linked list stored in memory. What would happen to the data structure if code to 'Insert the string "Betty" after "Boo" in the list' is executed. Answer this question by drawing diagrams describing each step (yes, like a cartoon!) and clearly explain each step. (For example, the first step is to create a temporary pointer and make it point to the same thing as the head of the list. The second step is to compare what the temporary pointer is pointing to with the string "Boo". If they are the same do.... if not do....)

Problem 3.2

Figure for Problem 3.2

Problem 3.3 A computer program is required that reads positive integers, one per line, from the keyboard into a list. The user indicates that they are finished by entering any negative integer (the negative integer itself is not stored). The computer program then prints out the list of numbers, on a single line, separated with blank spaces. Write this program using a linked list.

Problem 3.4 Design a computer program to store your friends' telephone numbers. Use a linked list to store the name/number information. Although you are not required to write code, you must explain each of the data structures and functions in your program and show how they will work together. The final program must be capable of adding a friend's telephone number to the list, searching for a friend's number, and printing out the entire list to the screen.